Non-physical collision method using bounds for rotating object doesn't work?

I recently noticed that the collision listener is not working properly for rotating obstacles.

The code the I am using is this from the tutorial in corona on non-physical collision. It’s simple to understand and works well.

But when there is a rectangle object with rotation applied to it, the collision isn’t accurate. I guess this is because of the usual behavior of content bounds.

\_M.hasCollidedRect = function( obj1, obj2) if ( obj1 == nil ) the 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

Can anyone please point me to any other method to detect non-physical collision on rotating objects. I don’t want to add physics just for the sake of two or three rotating obstacles.

Yeah, that code assumes that the objects are rectangular and haven’t rotated. This isn’t really unusual behaviour, it’s just that the function is only usable under one very specific scenario.

I created a function for this very thing some time ago. My approach was to create a vertices matrix for every rectangle (or polygon). Then, whenever I rotated the rect, I adjusted the vertices matrix based on the rect’s rotation by using rotation matrix. I then used the updated vertices matrix to output the rect’s minX, maxX, minY and maxY values. These min and max values were used in a function to compare if the player and the rect’s regions are overlapping. If they were, then I would compare each of the player’s sides against the rect’s sides and see if any of them intersect.

This method works with rects, as well as all sorts of polygons. Others may have different approaches to this issue.

Hi.

If you’re going down this road, I can’t recommend enough learning about projection. Get it down cold!  :slight_smile:

(Similarly, the dot product.)

That would let you do something akin to what XeduR mentions. Choose one of your two rectangles. We want to pretend this one is lined up with the x- and y-axes. Find two of its corners next to each other. I believe you could do, say, rect:localToContent(rect.width / 2, rect.height / 2), until you’re more comfortable about the math.

This is where projection comes in. First off, find the four corners of the other rectangle, following the same approach as before.

Now, we want to set up triangles like what you see in the projection link. We already have our segment from the first rectangle, which will be the bottom side. The long, diagonal side will go from one point on the segment (either one, just stick with it, and also use this decision to orient the segment) to one of the corners in the second rectangle.

We do this for all corners and find their projections. The scalar projection is our “component” along the segment, basically our “x” in “first rectangle space”. Now, in 2D it happens that rotating a direction (x, y) by 90 degrees is as simple as (-y, x). We can find our “y” component (in particular, with the correct sign) as the scalar projection of our rejection from the previous step with this rotated direction.

At this point we have our second rectangle in the “first rectangle space”. Because it’s probably rotated, you can’t do the easier checks from before, although of course you can see if all points are left / right / above / below.

What you can do, especially if you only care about overlap (i.e. ignoring one rectangle inside the other without touching), is to just check

all pairs of sides. I have some code handy for that, for two segments AB and CD :

local M = {} local function Lerp (x, y, vx, vy, s) return x + s \* vx, y + s \* vy end function M.Intersect (ax, ay, bx, by, cx, cy, dx, dy) local vx, vy, wx, wy = bx - ax, by - ay, dx - cx, dy - cy local vpx, vpy, wpx, wpy = -vy, vx, -wy, wx local pqx, pqy, vpw = cx - ax, cy - ay, vpx \* wx + vpy \* wy -- Common case. if 1 + vpw^2 ~= 1 then local s, t = -(wpx \* pqx + wpy \* pqy) / vpw, -(vpx \* pqx + vpy \* pqy) / vpw if s \>= 0 and s \<= 1 and t \>= 0 and t \<= 1 then return Lerp(ax, ay, vx, vy, s) -- Segments are parallel or degenerate. else -- MUCH longer, but if you run into this you can basically do the -- stuff from the tutorial end return false end return M

I can elaborate if necessary.

A physics engine, including Box2D if I’m not mistaken, will use something like the separating axis theorem, which also builds on top of projection.

David Eberly also has (C++) code for this at his Geometric Tools site. Relevant to what I said above would be the aligned / oriented box cases.

(A few years ago I was trying to write up a little geometry tutorial and then got carried away; it’s a hopeless mess at the moment, but I have delusions of giving it more love again. The “vector basics” and “vector intersections” pages in particular develop some of what I wrote above, but are among the pages most of in need of polish.)

as per StarCrunch,… between localToContent() and contentToLocal(), you can put rect2’s coordinates into rect1’s frame, then it’s just axis-aligned tests as before (which is a special-cased version of separating axis theorem, requiring only 4 simple inequality tests)

Looks like I’m gonna be spending the whole day(probably more) on learning this. I will look into separating  axis theorem as well as the special-cased version of axis theorem as davebollinger suggested. Thanks starCrunch for sharing the code, without which it would have been hard for me to understand.

try this (below), it’s perhaps the “conceptually simplest” way to do it with what Corona gives you.  (tho maybe not the “mathematically simplest” behind-the-scenes)  StarCrunch’s post is worth re-reading if you need docs for it (as i’m too lazy to redo it, and he already describes the projection of B on to A bit)  it’s not a “hard” problem, but gets asked a lot, maybe this’ll put it to bed.

--- pass me two rotated rects and i'll return boolean true/false if they overlap local function overlaps(a,b) -- b's local coordinates converted to content coordinates local bhw, bhh = b.width/2, b.height/2 local bcx1, bcy1 = b:localToContent(-bhw, -bhh) local bcx2, bcy2 = b:localToContent( bhw, -bhh) local bcx3, bcy3 = b:localToContent( bhw, bhh) local bcx4, bcy4 = b:localToContent(-bhw, bhh) -- b's content coordinates converted to a's local coordinates local blx1, bly1 = a:contentToLocal(bcx1, bcy1) local blx2, bly2 = a:contentToLocal(bcx2, bcy2) local blx3, bly3 = a:contentToLocal(bcx3, bcy3) local blx4, bly4 = a:contentToLocal(bcx4, bcy4) -- get the bounding box (of b in a's frame) local bminx = math.min(blx1, blx2, blx3, blx4) local bmaxx = math.max(blx1, blx2, blx3, blx4) local bminy = math.min(bly1, bly2, bly3, bly4) local bmaxy = math.max(bly1, bly2, bly3, bly4) -- is there a separating axis? local ahw, ahh = a.width/2, a.height/2 if (bminx \> ahw) then return false end if (bmaxx \< -ahw) then return false end if (bminy \> ahh) then return false end if (bmaxy \< -ahh) then return false end -- no: return true -- note: it would be "better" to inline the math.min/max's -- (so that early exit might eliminate some calls) -- but left separate for clarity end -------- -- DEMO: -------- local CCX, CCY = display.contentCenterX, display.contentCenterY local aRect = display.newRect(CCX-50, CCY, 200, 50) local bRect = display.newRect(CCX+50, CCY, 80, 100) Runtime:addEventListener("enterFrame", function(e) aRect.rotation = aRect.rotation + 1.234 bRect.rotation = bRect.rotation - 2.345 local hit = overlaps(aRect, bRect) aRect:setFillColor(hit and 1 or 0, hit and 0 or 1, 0) bRect:setFillColor(hit and 1 or 0, hit and 0 or 1, 0) end)

Wow, I learn a lot from you davebollinger. You should probably start a blog on best Practices in corona. You also give an insight on what works and what doesn’t. I admire your coding style. Thanks for the solution Sir.

Yeah, that code assumes that the objects are rectangular and haven’t rotated. This isn’t really unusual behaviour, it’s just that the function is only usable under one very specific scenario.

I created a function for this very thing some time ago. My approach was to create a vertices matrix for every rectangle (or polygon). Then, whenever I rotated the rect, I adjusted the vertices matrix based on the rect’s rotation by using rotation matrix. I then used the updated vertices matrix to output the rect’s minX, maxX, minY and maxY values. These min and max values were used in a function to compare if the player and the rect’s regions are overlapping. If they were, then I would compare each of the player’s sides against the rect’s sides and see if any of them intersect.

This method works with rects, as well as all sorts of polygons. Others may have different approaches to this issue.

Hi.

If you’re going down this road, I can’t recommend enough learning about projection. Get it down cold!  :slight_smile:

(Similarly, the dot product.)

That would let you do something akin to what XeduR mentions. Choose one of your two rectangles. We want to pretend this one is lined up with the x- and y-axes. Find two of its corners next to each other. I believe you could do, say, rect:localToContent(rect.width / 2, rect.height / 2), until you’re more comfortable about the math.

This is where projection comes in. First off, find the four corners of the other rectangle, following the same approach as before.

Now, we want to set up triangles like what you see in the projection link. We already have our segment from the first rectangle, which will be the bottom side. The long, diagonal side will go from one point on the segment (either one, just stick with it, and also use this decision to orient the segment) to one of the corners in the second rectangle.

We do this for all corners and find their projections. The scalar projection is our “component” along the segment, basically our “x” in “first rectangle space”. Now, in 2D it happens that rotating a direction (x, y) by 90 degrees is as simple as (-y, x). We can find our “y” component (in particular, with the correct sign) as the scalar projection of our rejection from the previous step with this rotated direction.

At this point we have our second rectangle in the “first rectangle space”. Because it’s probably rotated, you can’t do the easier checks from before, although of course you can see if all points are left / right / above / below.

What you can do, especially if you only care about overlap (i.e. ignoring one rectangle inside the other without touching), is to just check

all pairs of sides. I have some code handy for that, for two segments AB and CD :

local M = {} local function Lerp (x, y, vx, vy, s) return x + s \* vx, y + s \* vy end function M.Intersect (ax, ay, bx, by, cx, cy, dx, dy) local vx, vy, wx, wy = bx - ax, by - ay, dx - cx, dy - cy local vpx, vpy, wpx, wpy = -vy, vx, -wy, wx local pqx, pqy, vpw = cx - ax, cy - ay, vpx \* wx + vpy \* wy -- Common case. if 1 + vpw^2 ~= 1 then local s, t = -(wpx \* pqx + wpy \* pqy) / vpw, -(vpx \* pqx + vpy \* pqy) / vpw if s \>= 0 and s \<= 1 and t \>= 0 and t \<= 1 then return Lerp(ax, ay, vx, vy, s) -- Segments are parallel or degenerate. else -- MUCH longer, but if you run into this you can basically do the -- stuff from the tutorial end return false end return M

I can elaborate if necessary.

A physics engine, including Box2D if I’m not mistaken, will use something like the separating axis theorem, which also builds on top of projection.

David Eberly also has (C++) code for this at his Geometric Tools site. Relevant to what I said above would be the aligned / oriented box cases.

(A few years ago I was trying to write up a little geometry tutorial and then got carried away; it’s a hopeless mess at the moment, but I have delusions of giving it more love again. The “vector basics” and “vector intersections” pages in particular develop some of what I wrote above, but are among the pages most of in need of polish.)

as per StarCrunch,… between localToContent() and contentToLocal(), you can put rect2’s coordinates into rect1’s frame, then it’s just axis-aligned tests as before (which is a special-cased version of separating axis theorem, requiring only 4 simple inequality tests)

Looks like I’m gonna be spending the whole day(probably more) on learning this. I will look into separating  axis theorem as well as the special-cased version of axis theorem as davebollinger suggested. Thanks starCrunch for sharing the code, without which it would have been hard for me to understand.

try this (below), it’s perhaps the “conceptually simplest” way to do it with what Corona gives you.  (tho maybe not the “mathematically simplest” behind-the-scenes)  StarCrunch’s post is worth re-reading if you need docs for it (as i’m too lazy to redo it, and he already describes the projection of B on to A bit)  it’s not a “hard” problem, but gets asked a lot, maybe this’ll put it to bed.

--- pass me two rotated rects and i'll return boolean true/false if they overlap local function overlaps(a,b) -- b's local coordinates converted to content coordinates local bhw, bhh = b.width/2, b.height/2 local bcx1, bcy1 = b:localToContent(-bhw, -bhh) local bcx2, bcy2 = b:localToContent( bhw, -bhh) local bcx3, bcy3 = b:localToContent( bhw, bhh) local bcx4, bcy4 = b:localToContent(-bhw, bhh) -- b's content coordinates converted to a's local coordinates local blx1, bly1 = a:contentToLocal(bcx1, bcy1) local blx2, bly2 = a:contentToLocal(bcx2, bcy2) local blx3, bly3 = a:contentToLocal(bcx3, bcy3) local blx4, bly4 = a:contentToLocal(bcx4, bcy4) -- get the bounding box (of b in a's frame) local bminx = math.min(blx1, blx2, blx3, blx4) local bmaxx = math.max(blx1, blx2, blx3, blx4) local bminy = math.min(bly1, bly2, bly3, bly4) local bmaxy = math.max(bly1, bly2, bly3, bly4) -- is there a separating axis? local ahw, ahh = a.width/2, a.height/2 if (bminx \> ahw) then return false end if (bmaxx \< -ahw) then return false end if (bminy \> ahh) then return false end if (bmaxy \< -ahh) then return false end -- no: return true -- note: it would be "better" to inline the math.min/max's -- (so that early exit might eliminate some calls) -- but left separate for clarity end -------- -- DEMO: -------- local CCX, CCY = display.contentCenterX, display.contentCenterY local aRect = display.newRect(CCX-50, CCY, 200, 50) local bRect = display.newRect(CCX+50, CCY, 80, 100) Runtime:addEventListener("enterFrame", function(e) aRect.rotation = aRect.rotation + 1.234 bRect.rotation = bRect.rotation - 2.345 local hit = overlaps(aRect, bRect) aRect:setFillColor(hit and 1 or 0, hit and 0 or 1, 0) bRect:setFillColor(hit and 1 or 0, hit and 0 or 1, 0) end)

Wow, I learn a lot from you davebollinger. You should probably start a blog on best Practices in corona. You also give an insight on what works and what doesn’t. I admire your coding style. Thanks for the solution Sir.