Collision detection for rotated rectangles.

Games
#1

I’m working on a game and… let me preface this with “I am NOT using physics. I do not intend to use physics!”.
So I have a screen object that rotates (via an enterFrame handler). It is a long thin graphic and it’s trimmed to minimize transparent pixels.

I’m using this to detect my collisions (stolen from the forums)

local function hasCollided(obj1, obj2)  
 if obj1 == nil then  
 return false  
 end  
 if obj2 == nil then  
 return false  
 end  
 local left = obj1.contentBounds.xMin \<= obj2.contentBounds.xMin and obj1.contentBounds.xMax \>= obj2.contentBounds.xMin  
 local right = obj1.contentBounds.xMin \>= obj2.contentBounds.xMin and obj1.contentBounds.xMin \<= obj2.contentBounds.xMax  
 local up = obj1.contentBounds.yMin \<= obj2.contentBounds.yMin and obj1.contentBounds.yMax \>= obj2.contentBounds.yMin  
 local down = obj1.contentBounds.yMin \>= obj2.contentBounds.yMin and obj1.contentBounds.yMin \<= obj2.contentBounds.yMax  
 return (left or right) and (up or down)  
end

So if the object is on it’s 0, 80, 180 or 270 degree angles, this works perfectly. But if the object is rotated to another angle like say 45, the boundingBox creates a huge area of collision that isn’t part of the graphic:

+------+  
|\\ |  
| \\ |  
| \\ |  
| \\ |  
| \\|  
+------+

So I need to be able to call a function that will check the physical bounds not the ones based on extending the box.

I so would love a doesPolygonIntersectPolygon() API call.

Any thoughts?

(and please don’t respond with “use physics!”)

Rob
[import]uid: 19626 topic_id: 21240 reply_id: 321240[/import]

#2

Have you tried to determine if the point of collision is in the polygonal space as of the rotated rectangle?
[import]uid: 3826 topic_id: 21240 reply_id: 84158[/import]

#3

plz go with physics :smiley:

here’s the example of how to achieve that using physics :smiley:

[lua]local rect = display.newRect(0,0,100,100)
local rect1 = display.newRect(110,0,100,100)
rect:setReferencePoint(display.TopLeftReferencePoint)
rect1:setReferencePoint(display.TopLeftReferencePoint)

function chkInterSect(rect1, rect2)

if math.abs(rect1.rotation) < 1 and math.abs(rect2.rotation) < 1 then
return not ((rect1.x > rect2.x + rect2.width) or (rect2.x > rect1.x + rect1.width) or (rect1.y > rect2.y + rect2.height) or (rect2.y > rect1.y + rect1.height))
end

local function chkForRotated(rect1, rect2)

local x1 = rect2.x-rect1.x
local y1 = rect2.y-rect1.y

local x2 = x1*math.cos(math.rad(rect1.rotation)) + y1*math.sin(math.rad(rect1.rotation))
local y2 = y1*math.cos(math.rad(rect1.rotation)) - x1*math.sin(math.rad(rect1.rotation))

local angle1 = math.cos(math.rad(rect2.rotation - rect1.rotation))
local angle2 = math.sin(math.rad(rect2.rotation - rect1.rotation))
local arr1 = { rect2.width*angle1, -rect2.height*angle2, rect2.width*angle1 - rect2.height*angle2}
local arr2 = { rect2.width*angle2, rect2.height*angle1, rect2.width*angle2 + rect2.height*angle1}

local minX = 0
local maxX = 0
local minY = 0
local maxY = 0
for i=1,3 do
if minX > arr1[i] then
minX = arr1[i]
end
if maxX < arr1[i] then
maxX = arr1[i]
end
if minY > arr2[i] then
minY = arr2[i]
end
if maxY < arr2[i] then
maxY = arr2[i]
end
end

return x2 + maxX < 0 or x2 + minX > rect1.width or y2 + maxY < 0 or y2 + minY > rect1.height
end

return not (chkForRotated(rect1,rect2) or chkForRotated(rect2,rect1))
end

local function callMe()
if chkInterSect(rect,rect1) then
rect:setFillColor(255,0,0)
rect1:setFillColor(255,0,0)
else
rect:setFillColor(255)
rect1:setFillColor(255)
end
end
Runtime:addEventListener(“enterFrame”,callMe)

local function moveandRotateMe(e)
if e.phase == “began” then
display.getCurrentStage():setFocus(e.target)
elseif e.phase == “moved” then
e.target.x = e.x
e.target.y = e.y
elseif e.phase == “ended” then
e.target.rotation = e.target.rotation + 10
display.getCurrentStage():setFocus(nil)
end
end
rect:addEventListener(“touch”,moveandRotateMe)
rect1:addEventListener(“touch”,moveandRotateMe)[/lua]

plz note it will work only with TopLeftReferencePoint point for other reference point you have to change code accordingly
:slight_smile: [import]uid: 12482 topic_id: 21240 reply_id: 84166[/import]

#4

hey rob
google separating axis theorem for lua
[import]uid: 7911 topic_id: 21240 reply_id: 84203[/import]

#5

I was looking at the polygon methods last night. Even found a pretty simple javascript example that worked on concave polygons too.

I was thinking last night that it’s easy enough to check the polygon, but the harder thing will be rotating the polygon for my spinning things.

Thanks! I appreciate it.
[import]uid: 19626 topic_id: 21240 reply_id: 84213[/import]

#6

hi rob have you tried above example that can work for rectangle without physics :frowning: [import]uid: 12482 topic_id: 21240 reply_id: 84344[/import]

#7

I built a test app using your code and it seems to work really well, but I’m center reference point and when I try to adjust for that, so far it has been a big fail.

I thought I had it (the initial collisions looked good) but once I moved/rotated the 2nd block the collisions were very off. I’m continuing to research.

SAT will work for a couple of my objects (triangles) but I have two concave objects I have to figure out how to handle (will probably do multiple rectangles but I have to figure out how I’m going to record the polygon points in my existing data structure.

This leaves me my rotating and rotated items which your code would work well on once I figure out my reference point problems. It’s almost like “Top Left” changes as the object rotates if that makes any sense.
[import]uid: 19626 topic_id: 21240 reply_id: 84435[/import]

#8

as ur object rotates corona treats it still as an axis aligned object so the size of the bounding box changes [import]uid: 7911 topic_id: 21240 reply_id: 84443[/import]

#9

SAT will work, so for my objects that are rotated, but not continuously rotating, I will be able to work out the points of the polygon for them. I’m left with my rotating objects whose points change as they rotate. I just have to work out the calculations on them I guess. Which I think @hgvyas123’s method above is doing.
[import]uid: 19626 topic_id: 21240 reply_id: 84444[/import]

#10

can’t you change reference point at the start of my function and at the return set it again to center because topLeftReferencePoint is necessary to avoid some calculation of finding all points

also i was under the impression that you need it for rectangles only is this for the any number of points? or just for triangle and rectangle?
[import]uid: 12482 topic_id: 21240 reply_id: 84585[/import]

#11

Most of my objects are rectangles and most of the time tihey are axis aligned so bounding box is great
But like most platformers I have up and down ramps ( my triangles).

I have some long thin blocks that can form walls, floors and ramps in one graphic rather than blocks and wedges. These rectangles can be rotated to form a ramp.

Then I have a long thin graphic. That rotates like a paddle wheel. Then my last problem is a U shape and I need the middle to be open. Concave shapes break SAT so I have to make it into 3 rectangles

I tried just changing the ref points and it didn’t work for some reason [import]uid: 19626 topic_id: 21240 reply_id: 84589[/import]

#12

try this,

[lua]local rect = display.newRect(0,0,100,100)
local rect1 = display.newRect(110,0,100,100)

function chkInterSect(rect1, rect2)
rect1:setReferencePoint(display.TopLeftReferencePoint)
rect2:setReferencePoint(display.TopLeftReferencePoint)
if math.abs(rect1.rotation) < 1 and math.abs(rect2.rotation) < 1 then
rect1:setReferencePoint(display.CenterReferencePoint)
rect2:setReferencePoint(display.CenterReferencePoint)
return not ((rect1.x > rect2.x + rect2.width) or (rect2.x > rect1.x + rect1.width) or (rect1.y > rect2.y + rect2.height) or (rect2.y > rect1.y + rect1.height))
end

local function chkForRotated(rect1, rect2)
rect1:setReferencePoint(display.TopLeftReferencePoint)
rect2:setReferencePoint(display.TopLeftReferencePoint)
local x1 = rect2.x-rect1.x
local y1 = rect2.y-rect1.y

local x2 = x1*math.cos(math.rad(rect1.rotation)) + y1*math.sin(math.rad(rect1.rotation))
local y2 = y1*math.cos(math.rad(rect1.rotation)) - x1*math.sin(math.rad(rect1.rotation))

local angle1 = math.cos(math.rad(rect2.rotation - rect1.rotation))
local angle2 = math.sin(math.rad(rect2.rotation - rect1.rotation))
local arr1 = { rect2.width*angle1, -rect2.height*angle2, rect2.width*angle1 - rect2.height*angle2}
local arr2 = { rect2.width*angle2, rect2.height*angle1, rect2.width*angle2 + rect2.height*angle1}

local minX = 0
local maxX = 0
local minY = 0
local maxY = 0
for i=1,3 do
if minX > arr1[i] then
minX = arr1[i]
end
if maxX < arr1[i] then
maxX = arr1[i]
end
if minY > arr2[i] then
minY = arr2[i]
end
if maxY < arr2[i] then
maxY = arr2[i]
end
end

return x2 + maxX < 0 or x2 + minX > rect1.width or y2 + maxY < 0 or y2 + minY > rect1.height
end
rect1:setReferencePoint(display.CenterReferencePoint)
rect2:setReferencePoint(display.CenterReferencePoint)
return not (chkForRotated(rect1,rect2) or chkForRotated(rect2,rect1))
end

local function callMe()
if chkInterSect(rect,rect1) then
rect:setFillColor(255,0,0)
rect1:setFillColor(255,0,0)
else
rect:setFillColor(255)
rect1:setFillColor(255)
end
end
Runtime:addEventListener(“enterFrame”,callMe)

local function moveandRotateMe(e)
if e.phase == “began” then
display.getCurrentStage():setFocus(e.target)
elseif e.phase == “moved” then
e.target.x = e.x
e.target.y = e.y
elseif e.phase == “ended” then
e.target.rotation = e.target.rotation + 10
display.getCurrentStage():setFocus(nil)
end
end
rect:addEventListener(“touch”,moveandRotateMe)
rect1:addEventListener(“touch”,moveandRotateMe)[/lua] [import]uid: 12482 topic_id: 21240 reply_id: 84591[/import]

#13

for the triangle may be this post will help

http://developer.anscamobile.com/forum/2011/11/15/need-help-move-object-limited-area-triangle

:slight_smile: [import]uid: 12482 topic_id: 21240 reply_id: 84592[/import]

#14

The squares in this example are still rotating around a corner reference point, which I don’t understand given that it’s set to center reference point.

[import]uid: 19626 topic_id: 21240 reply_id: 84674[/import]

#15

ohh yes may be because the continuous checking the func and changing reference point ?

[import]uid: 12482 topic_id: 21240 reply_id: 84866[/import]