Code for Rotated Rectangle Collision Detection

Games
#1

Hi,

I’m a newbie to Corona, but I am a Mathematics student so know my way around the geometry in collision detection (or at least I like to think I do). I am making a game and it needs to detect collisions between rotated rectangles, after looking on the internet I found a lot of people have the same problem. The separating axis theorem is often suggested as advice, but I imagine its complexity puts people off.

So here is my code for the collision detection: 

local function isCollision( x10, y10, height1, width1, radrot1, x20, y20, height2, width2, radrot2 ) --x10, y10 is centre point of rect1. x20, y20 is centre point of rect2 --height1, width1 are half heights/widths of rect1, radrot is rotation of rect in radians local radius1 = math.sqrt( height1\*height1 + width1\*width1 ) local radius2 = math.sqrt( height2\*height2 + width2\*width2 ) local angle1 = math.asin( height1 / radius1 ) local angle2 = math.asin( height2 / radius2 ) local x1 = {}; local y1 = {} local x2 = {}; local y2 = {} x1[1] = x10 + radius1 \* math.cos(radrot1 - angle1); y1[1] = y10 + radius1 \* math.sin(radrot1 - angle1) x1[2] = x10 + radius1 \* math.cos(radrot1 + angle1); y1[2] = y10 + radius1 \* math.sin(radrot1 + angle1) x1[3] = x10 + radius1 \* math.cos(radrot1 + math.pi - angle1); y1[3] = y10 + radius1 \* math.sin(radrot1 + math.pi - angle1) x1[4] = x10 + radius1 \* math.cos(radrot1 + math.pi + angle1); y1[4] = y10 + radius1 \* math.sin(radrot1 + math.pi + angle1) x2[1] = x20 + radius2 \* math.cos(radrot2 - angle2); y2[1] = y20 + radius2 \* math.sin(radrot2 - angle2) x2[2] = x20 + radius2 \* math.cos(radrot2 + angle2); y2[2] = y20 + radius2 \* math.sin(radrot2 + angle2) x2[3] = x20 + radius2 \* math.cos(radrot2 + math.pi - angle2); y2[3] = y20 + radius2 \* math.sin(radrot2 + math.pi - angle2) x2[4] = x20 + radius2 \* math.cos(radrot2 + math.pi + angle2); y2[4] = y20 + radius2 \* math.sin(radrot2 + math.pi + angle2) local axisx = {}; local axisy = {} axisx[1] = x1[1] - x1[2]; axisy[1] = y1[1] - y1[2] axisx[2] = x1[3] - x1[2]; axisy[2] = y1[3] - y1[2] axisx[3] = x2[1] - x2[2]; axisy[3] = y2[1] - y2[2] axisx[4] = x2[3] - x2[2]; axisy[4] = y2[3] - y2[2] for k = 1,4 do local proj = x1[1] \* axisx[k] + y1[1] \* axisy[k] local minProj1 = proj local maxProj1 = proj for i = 2,4 do proj = x1[i] \* axisx[k] + y1[i] \* axisy[k] if proj \< minProj1 then minProj1 = proj elseif proj \> maxProj1 then maxProj1 = proj end end proj = x2[1] \* axisx[k] + y2[1] \* axisy[k] local minProj2 = proj local maxProj2 = proj for j = 2,4 do proj = x2[j] \* axisx[k] + y2[j] \* axisy[k] if proj \< minProj2 then minProj2 = proj elseif proj \> maxProj2 then maxProj2 = proj end end if maxProj2 \< minProj1 or maxProj1 \< minProj2 then return false end end return true end

If anyone wants to use this or give any suggestions then feel free. Main ideas used can be found here 

Andy

#2

Corona SDK uses Box2D physics engine, so there is no need to write own routines like this  :slight_smile:

#3

Hogwash - not everybody wants to use physics in their game, or have that overhead when it’s not needed. Traditional collision-detection routines are equally as important as physics-based implementations.

Thanks to the OP, always great to see people contributing to the community and particularly thinking outside of the box rather then just relying on the API’s that Corona provides.

#4

there is a reason. if your app doesn’t use physics and you don’t want the extra over head of physics. and if your objects are in a diff. moving group
now with that said physics is the easiest way
without physics the easiest way would be to use circle collision detection although would be as accurate

#5

not be as accurate

#6

Corona SDK uses Box2D physics engine, so there is no need to write own routines like this  :slight_smile:

#7

Hogwash - not everybody wants to use physics in their game, or have that overhead when it’s not needed. Traditional collision-detection routines are equally as important as physics-based implementations.

Thanks to the OP, always great to see people contributing to the community and particularly thinking outside of the box rather then just relying on the API’s that Corona provides.

#8

there is a reason. if your app doesn’t use physics and you don’t want the extra over head of physics. and if your objects are in a diff. moving group
now with that said physics is the easiest way
without physics the easiest way would be to use circle collision detection although would be as accurate

#9

not be as accurate

#10

Andy, I tried your code and while it works for horizontal collision, it doesn’t seem to work vertically. That is, I’m trying to keep two rectangles touching. When I drag on left/right, the test works. When I drag one up/down, the test doesn’t work.

Here’s the code I’m using (yours).

local function isCollision( x10, y10, height1, width1, radrot1, x20, y20, height2, width2, radrot2 ) --x10, y10 is centre point of rect1. x20, y20 is centre point of rect2 --height1, width1 are half heights/widths of rect1, radrot is rotation of rect in radians local radius1 = math.sqrt( height1\*height1 + width1\*width1 ) local radius2 = math.sqrt( height2\*height2 + width2\*width2 ) local angle1 = math.asin( height1 / radius1 ) local angle2 = math.asin( height2 / radius2 ) local x1 = {}; local y1 = {} local x2 = {}; local y2 = {} x1[1] = x10 + radius1 \* math.cos(radrot1 - angle1); y1[1] = y10 + radius1 \* math.sin(radrot1 - angle1) x1[2] = x10 + radius1 \* math.cos(radrot1 + angle1); y1[2] = y10 + radius1 \* math.sin(radrot1 + angle1) x1[3] = x10 + radius1 \* math.cos(radrot1 + math.pi - angle1); y1[3] = y10 + radius1 \* math.sin(radrot1 + math.pi - angle1) x1[4] = x10 + radius1 \* math.cos(radrot1 + math.pi + angle1); y1[4] = y10 + radius1 \* math.sin(radrot1 + math.pi + angle1) x2[1] = x20 + radius2 \* math.cos(radrot2 - angle2); y2[1] = y20 + radius2 \* math.sin(radrot2 - angle2) x2[2] = x20 + radius2 \* math.cos(radrot2 + angle2); y2[2] = y20 + radius2 \* math.sin(radrot2 + angle2) x2[3] = x20 + radius2 \* math.cos(radrot2 + math.pi - angle2); y2[3] = y20 + radius2 \* math.sin(radrot2 + math.pi - angle2) x2[4] = x20 + radius2 \* math.cos(radrot2 + math.pi + angle2); y2[4] = y20 + radius2 \* math.sin(radrot2 + math.pi + angle2) local axisx = {}; local axisy = {} axisx[1] = x1[1] - x1[2]; axisy[1] = y1[1] - y1[2] axisx[2] = x1[3] - x1[2]; axisy[2] = y1[3] - y1[2] axisx[3] = x2[1] - x2[2]; axisy[3] = y2[1] - y2[2] axisx[4] = x2[3] - x2[2]; axisy[4] = y2[3] - y2[2] for k = 1,4 do local proj = x1[1] \* axisx[k] + y1[1] \* axisy[k] local minProj1 = proj local maxProj1 = proj for i = 2,4 do proj = x1[i] \* axisx[k] + y1[i] \* axisy[k] if proj \< minProj1 then minProj1 = proj elseif proj \> maxProj1 then maxProj1 = proj end end proj = x2[1] \* axisx[k] + y2[1] \* axisy[k] local minProj2 = proj local maxProj2 = proj for j = 2,4 do proj = x2[j] \* axisx[k] + y2[j] \* axisy[k] if proj \< minProj2 then minProj2 = proj elseif proj \> maxProj2 then maxProj2 = proj end end if maxProj2 \< minProj1 or maxProj1 \< minProj2 then print ("NO COLLISION") return false end end return true end
#11

want my two cents?  first, yes, there are plenty of cases where box2d is overkill, where DIY approaches are completely valid, so i’ll applaud your effort and for sharing your solution.

however… just glancing over the code (i haven’t run it), i think you’ve may have inadvertently made the topic more complex than it was to begin with, by taking a trig instead of vector approach – all of that trig vanishes with a proper dot product and project method.  fwiw

(unfortunately, i’m not aware of vector class implementation accepted/adopted as de facto by the “corona community”, so those who need one tend to roll their own, all incompatible of course :frowning: )

#12

Indeed, dot-products would be better…so the Internet says…but I haven’t done this kind of math for 30 years. So, I’m still kinda stuck. There are plenty of places to read about this stuff, but getting it right is non-trivial, it turns out. Any help appreciated.

#13

not necessarily “better”, just perhaps more concise/clear.

besides, the dot products are already in there, question is:  do you see them?  it’s just a “structural” thing

i’m walking a tightrope here, as it wasn’t my intent to criticize, but if simplification were the goal…

  do you know which parts are the vertex transformation, and which parts the SAT?

  so you’d know how to split those out if one shape were static and could cache many values?

  on which line is the edge normal calculated?  what is x2[2]?

  why radius/asin if already given rotation in radians, why not just general 2d rotation formula?

  do you see it’s been specifically optimized for rectangles with two sets of parallel axes?

  would you know what to do to extend it for use on triangles, other general convex n-gons?

  would you know how to extend if you need penetration distance?

that’s where i was coming from with “seem less complex, or not?”

#14

Hmm. I did begin to parse it all out, but my goal was to simply find (for free!) a working function, rather than figure one out. My use is quite simple, and this function does more than I need. However, it exists…which is more useful than other recipes I’ve found.

I have discovered that a big problem is that Corona reports contentHeight of a rotated object as it’s rotated height, using contentBounds. So, I have been passing the wrong values to the function! I’m working on that now.

The joke is, I’m no longer convinced I need it all — I’m trying to keep a shape on-screen while using pinch/zoom/rotate/move, and it seems that a proper rotate with two fingers cannot move anything off screen!

#15

It’s been a long time since I made this code and I can’t quite remember exactly what it all means now.

However, I’m sure I used all the trig functions as the most efficient way to produce the answers. The dot product procedure had it’s own calculations which might have involved using sin and cos, whereas the method above uses only sin or cos in each operation (I don’t know how correct this is)
 

I did test it quite extensively in my game though and I never ran into any problems. If you still require it, I can dig the old code out and see if I ever updated it from what I posted here

Andy

 

 

#16

Andy, thank you. I’ve discovered that the params I was sending were clearly wrong, e.g. height/width. For a rotated rectangle.contentHeight, Corona returns the height as measured from the lowest vertex to the highest, i.e. from the bounding box. Oops. to know the real height/width, I’ll have to find those w/o rotation!

Update: I can confirm, by capturing the contentHeight/width BEFORE rotation, I can now pass the correct value to the function, and it DOES detect collision!

I just found a collision library, so maybe that will solve everything: http://vrld.github.com/HardonCollider

#17

Here is my modified function (plus demo code) which detects collision between rotated rectangles.

local g = display.newGroup() local c1,c2 --x10, y10 is centre point of rect1. x20, y20 is centre point of rect2 --height1, width1 are half heights/widths of rect1, radrot is rotation of rect in radians local function isCollision( obj, obj2 ) local cos = math.cos local sin = math.sin local asin = math.asin local sqrt = math.sqrt local rad = math.rad local pi = math.pi local x10 = obj.x local y10 = obj.y local r = obj.rotation obj.rotation = 0 local height1 = obj.\_height/2 local width1 = obj.\_width/2 obj.rotation = r local radrot1 = rad(obj.rotation) local x20 = obj2.x local y20 = obj2.y r = obj2.rotation obj2.rotation = 0 local height2 = obj2.\_height/2 local width2 = obj2.\_width/2 obj2.rotation = r local radrot2 = rad(obj2.rotation) local radius1 = sqrt( height1\*height1 + width1\*width1 ) local radius2 = sqrt( height2\*height2 + width2\*width2 ) local radius1 = sqrt( height1\*height1 + width1\*width1 ) local radius2 = sqrt( height2\*height2 + width2\*width2 ) local angle1 = asin( height1 / radius1 ) local angle2 = asin( height2 / radius2 ) local x1 = {}; local y1 = {} local x2 = {}; local y2 = {} x1[1] = x10 + radius1 \* cos(radrot1 - angle1); y1[1] = y10 + radius1 \* sin(radrot1 - angle1) x1[2] = x10 + radius1 \* cos(radrot1 + angle1); y1[2] = y10 + radius1 \* sin(radrot1 + angle1) x1[3] = x10 + radius1 \* cos(radrot1 + pi - angle1); y1[3] = y10 + radius1 \* sin(radrot1 + pi - angle1) x1[4] = x10 + radius1 \* cos(radrot1 + pi + angle1); y1[4] = y10 + radius1 \* sin(radrot1 + pi + angle1) x2[1] = x20 + radius2 \* cos(radrot2 - angle2); y2[1] = y20 + radius2 \* sin(radrot2 - angle2) x2[2] = x20 + radius2 \* cos(radrot2 + angle2); y2[2] = y20 + radius2 \* sin(radrot2 + angle2) x2[3] = x20 + radius2 \* cos(radrot2 + pi - angle2); y2[3] = y20 + radius2 \* sin(radrot2 + pi - angle2) x2[4] = x20 + radius2 \* cos(radrot2 + pi + angle2); y2[4] = y20 + radius2 \* sin(radrot2 + pi + angle2) local axisx = {}; local axisy = {} axisx[1] = x1[1] - x1[2]; axisy[1] = y1[1] - y1[2] axisx[2] = x1[3] - x1[2]; axisy[2] = y1[3] - y1[2] axisx[3] = x2[1] - x2[2]; axisy[3] = y2[1] - y2[2] axisx[4] = x2[3] - x2[2]; axisy[4] = y2[3] - y2[2] for k = 1,4 do local proj = x1[1] \* axisx[k] + y1[1] \* axisy[k] local minProj1 = proj local maxProj1 = proj for i = 2,4 do proj = x1[i] \* axisx[k] + y1[i] \* axisy[k] if proj \< minProj1 then minProj1 = proj elseif proj \> maxProj1 then maxProj1 = proj end end proj = x2[1] \* axisx[k] + y2[1] \* axisy[k] local minProj2 = proj local maxProj2 = proj for j = 2,4 do proj = x2[j] \* axisx[k] + y2[j] \* axisy[k] if proj \< minProj2 then minProj2 = proj elseif proj \> maxProj2 then maxProj2 = proj end end if maxProj2 \< minProj1 or maxProj1 \< minProj2 then return false end end return true end local b = display.newRect(0,0, 500,300) b.x = 500 b.y = 300 b.\_height = b.contentHeight b.\_width = b.contentWidth b.rotation = 0 b:setFillColor(.5, .5, 1, .5) local shape1 = display.newRect(0,0, 200,100) shape1.x = 0 shape1.y = 0 shape1.\_height = shape1.contentHeight shape1.\_width = shape1.contentWidth shape1.rotation = 20 b:setFillColor(1, .5, .5, .5) print( "contentHeight: ".. shape1.contentHeight ) function shapeMove( event ) local phase = event.phase if phase == "began" then display.getCurrentStage():setFocus( self, event.id ) shape1.isFocus = true elseif shape1.isFocus then if phase == "moved" then -- Move the shape shape1.x = event.x shape1.y = event.y if ( isCollision(shape1, b) ) then print ("Collision") shape1:setFillColor(250,0,0) else shape1:setFillColor(250,250,250,100) end elseif phase == "ended" then display.getCurrentStage():setFocus( self, nil ) shape1.isFocus = false end end end Runtime:addEventListener( "touch", shapeMove )
#18

Awesome, glad to see you got it working :slight_smile:

#19

Andy, I tried your code and while it works for horizontal collision, it doesn’t seem to work vertically. That is, I’m trying to keep two rectangles touching. When I drag on left/right, the test works. When I drag one up/down, the test doesn’t work.

Here’s the code I’m using (yours).

local function isCollision( x10, y10, height1, width1, radrot1, x20, y20, height2, width2, radrot2 ) --x10, y10 is centre point of rect1. x20, y20 is centre point of rect2 --height1, width1 are half heights/widths of rect1, radrot is rotation of rect in radians local radius1 = math.sqrt( height1\*height1 + width1\*width1 ) local radius2 = math.sqrt( height2\*height2 + width2\*width2 ) local angle1 = math.asin( height1 / radius1 ) local angle2 = math.asin( height2 / radius2 ) local x1 = {}; local y1 = {} local x2 = {}; local y2 = {} x1[1] = x10 + radius1 \* math.cos(radrot1 - angle1); y1[1] = y10 + radius1 \* math.sin(radrot1 - angle1) x1[2] = x10 + radius1 \* math.cos(radrot1 + angle1); y1[2] = y10 + radius1 \* math.sin(radrot1 + angle1) x1[3] = x10 + radius1 \* math.cos(radrot1 + math.pi - angle1); y1[3] = y10 + radius1 \* math.sin(radrot1 + math.pi - angle1) x1[4] = x10 + radius1 \* math.cos(radrot1 + math.pi + angle1); y1[4] = y10 + radius1 \* math.sin(radrot1 + math.pi + angle1) x2[1] = x20 + radius2 \* math.cos(radrot2 - angle2); y2[1] = y20 + radius2 \* math.sin(radrot2 - angle2) x2[2] = x20 + radius2 \* math.cos(radrot2 + angle2); y2[2] = y20 + radius2 \* math.sin(radrot2 + angle2) x2[3] = x20 + radius2 \* math.cos(radrot2 + math.pi - angle2); y2[3] = y20 + radius2 \* math.sin(radrot2 + math.pi - angle2) x2[4] = x20 + radius2 \* math.cos(radrot2 + math.pi + angle2); y2[4] = y20 + radius2 \* math.sin(radrot2 + math.pi + angle2) local axisx = {}; local axisy = {} axisx[1] = x1[1] - x1[2]; axisy[1] = y1[1] - y1[2] axisx[2] = x1[3] - x1[2]; axisy[2] = y1[3] - y1[2] axisx[3] = x2[1] - x2[2]; axisy[3] = y2[1] - y2[2] axisx[4] = x2[3] - x2[2]; axisy[4] = y2[3] - y2[2] for k = 1,4 do local proj = x1[1] \* axisx[k] + y1[1] \* axisy[k] local minProj1 = proj local maxProj1 = proj for i = 2,4 do proj = x1[i] \* axisx[k] + y1[i] \* axisy[k] if proj \< minProj1 then minProj1 = proj elseif proj \> maxProj1 then maxProj1 = proj end end proj = x2[1] \* axisx[k] + y2[1] \* axisy[k] local minProj2 = proj local maxProj2 = proj for j = 2,4 do proj = x2[j] \* axisx[k] + y2[j] \* axisy[k] if proj \< minProj2 then minProj2 = proj elseif proj \> maxProj2 then maxProj2 = proj end end if maxProj2 \< minProj1 or maxProj1 \< minProj2 then print ("NO COLLISION") return false end end return true end
#20

want my two cents?  first, yes, there are plenty of cases where box2d is overkill, where DIY approaches are completely valid, so i’ll applaud your effort and for sharing your solution.

however… just glancing over the code (i haven’t run it), i think you’ve may have inadvertently made the topic more complex than it was to begin with, by taking a trig instead of vector approach – all of that trig vanishes with a proper dot product and project method.  fwiw

(unfortunately, i’m not aware of vector class implementation accepted/adopted as de facto by the “corona community”, so those who need one tend to roll their own, all incompatible of course :frowning: )