Jump to content

[TOPIC: topicViewTemplate]
[GLOBAL: userSmallPhoto]
Photo

Non-physical collision method using bounds for rotating object doesn't work?
Started by Quitalizner Dec 20 2018 06:11 AM

6 replies to this topic
non-physical collision contentbounds rotating rectangles

Best Answer StarCrunch , 20 December 2018 - 01:04 PM

Hi.

 

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

 

(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.)

[TOPIC CONTROLS]
[/TOPIC CONTROLS]
[modOptionsDropdown]
[/modOptionsDropdown]
[reputationFilter]
[TOPIC: post.html]
#1

Quitalizner

[GLOBAL: userInfoPane.html]
Quitalizner
  • Enthusiast

  • 38 posts
  • Corona SDK

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.



[TOPIC: post.html]
#2

XeduR @Spyric

[GLOBAL: userInfoPane.html]
XeduR @Spyric
  • Contributor

  • 582 posts
  • Corona SDK

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.



[TOPIC: post.html]
#3

StarCrunch

[GLOBAL: userInfoPane.html]
StarCrunch
  • Contributor

  • 787 posts
  • Corona SDK

  Best Answer

Hi.

 

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

 

(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.)


  • Quitalizner likes this

[TOPIC: post.html]
#4

davebollinger

[GLOBAL: userInfoPane.html]
davebollinger
  • Corona Geek

  • 1,304 posts
  • Enterprise

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)



[TOPIC: post.html]
#5

Quitalizner

[GLOBAL: userInfoPane.html]
Quitalizner
  • Enthusiast

  • 38 posts
  • Corona SDK

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.



[TOPIC: post.html]
#6

davebollinger

[GLOBAL: userInfoPane.html]
davebollinger
  • Corona Geek

  • 1,304 posts
  • Enterprise

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)



[TOPIC: post.html]
#7

Quitalizner

[GLOBAL: userInfoPane.html]
Quitalizner
  • Enthusiast

  • 38 posts
  • Corona SDK

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.




[topic_controls]
[/topic_controls]

Also tagged with one or more of these keywords: non-physical collision, contentbounds, rotating rectangles