Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » Collision with rotated rectangles.

This thread is locked; no one can reply to it. rss feed Print
Collision with rotated rectangles.
Chris Katko
Member #1,881
January 2002
avatar

Is there an easy way to do collision detection with two rotated rectangles?

I keep finding articles on "bounding box around a rotated rectangle" and that's not what I want. I don't want a gigantic box around a rectangle when it's rotated by 45-degree. I just want to check whether two rotated rectangles are colliding.

Think GTA 1 with cars rotating around.

{"name":"latest","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/5\/e\/5efbcada3e8e2467d5d7a2920075bf7a.png","w":800,"h":600,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/5\/e\/5efbcada3e8e2467d5d7a2920075bf7a"}latest

-----sig:
“Programs should be written for people to read, and only incidentally for machines to execute.” - Structure and Interpretation of Computer Programs
"Political Correctness is fascism disguised as manners" --George Carlin

anto80
Member #3,230
February 2003
avatar

In this case I'm using 2 inner rectangles.
One of them with larger width, and the other with larger height. These 2 stay inside the original rotated rectangle.
Thats not a very accurate solution but it's fast.

Another slower way would be to calculate distances between the 2 center points, with sqrt. And compare it to rectangle size.
More accurate but not the top of the accuracy either.

___________
Currently working on his action/puzzle game CIPHER PUSHER : Blocks/Vortexes/Seafood! Facebook - Twitter - webpage

Rodolfo Lam
Member #16,045
August 2015

You could use instead circles for collision detection. You would test if the radius of each circle intercept. The borders of the rectangles will not trigger collisions, but its also fast

l j
Member #10,584
January 2009
avatar

http://www.metanetsoftware.com/technique/tutorialA.html

Everything you need and more as far as I can tell.
Well at least the basic math you need, all examples include AABBs but the technique works for non aligned boxes as well.

Johan Halmén
Member #1,550
September 2001

Is one point inside a triangle?
Shouldn't be hard to find out.
Are any of three points inside of a triangle?
Three times more work, but equally easy.
Are two triangles colliding?
Doubles the work of previous step, but equally easy.

So how would I do the first step?
Find center point of one triangle, it is always inside the triangle.
Take one vertex of the other triangle. Check if it's on same side of one side as the center point. Repeat for all three sides.

{"name":"610354","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/6\/a\/6ae24f7adc12dc271a859cee221e0546.png","w":800,"h":1109,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/6\/a\/6ae24f7adc12dc271a859cee221e0546"}610354
P is the middle point that you know is inside the triangle. X is a vertex of another triangle. Form the vectors AB, AX and AP. Check the cross products ABxAX and ABxAP. If the results are vectors pointing in the same directions, X and P are on the same side of the line AB[1]. Of course, X could still be outside the triangle, far to the left. But just repeat with the two other sides of the triangle.

References

  1. If the resulting vectors point in opposite directions, X and P are on opposite sides of AB. Since your triangle and P and X are all in one plane, everything is just in an xy world and the vectors only have i and j components. But you need the z dimension and its k vector component for the cross product. And the sign of this k component tells you if your resulting vectors point in the same direction. Same sign => X and P are on same side of AB. Not same sign => X and P are on opposite sides of AB.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Years of thorough research have revealed that the red "x" that closes a window, really isn't red, but white on red background.

Years of thorough research have revealed that what people find beautiful about the Mandelbrot set is not the set itself, but all the rest.

Polybios
Member #12,293
October 2010

Don't know whether this would work, but I'd start with checking on which side of the edges of rectangle R the 4 vertices of rectangle S are (i.e. "inside / outside" side).
One check for vertex V against edge CD (of rectangle ABCD) would be:
Take the "normal" of an edge which is another edge in the rectangle case: (A-C) pointing "inside". Check the sign of the dot product of (A-C) dot (V-C). If it's positive, V lies on the "inside" side of CD. I don't know if you could infer collision status from the 16 results. You can safely stop if all 4 vertices are on the "outside" side of one edge, though. And you can stop as soon as you have found a vertex that is on the inside side of all edges.
So this would require about 32 vector subtractions and 16 dot products.
Edit: Actually, it might well be that you need to check with the rectangles reversed, too. So it would take 32 dot products in the worst case. But you could probably exclude some of the cases. Oh well. I'd just follow the link Aaron provided.

Johan Halmén
Member #1,550
September 2001

So why did I think triangles, when the OP was about rectangles? :P

<edit />

You can't just check if one vertex is inside the other rectangle. All vertices can be outside and still the rectangles collide. Just put them across each other. How about checking two line segments AB and CD and check where the lines cross. Be it point P. Is P inside the line segment AB? Is it inside CD? If both are true, there's a collision. You have to check 4 sides against 4 sides. Checking 2 sides, you find the crossing point. Then you check the point against both sides. Well, that would be at least 32 calculations of some kind.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Years of thorough research have revealed that the red "x" that closes a window, really isn't red, but white on red background.

Years of thorough research have revealed that what people find beautiful about the Mandelbrot set is not the set itself, but all the rest.

Chris Katko
Member #1,881
January 2002
avatar

Perhaps this is more complex than necessary, but last night I was thinking (which I think others have suggested):

- Convert all points to axis-aligned with rectangle A
- For the four points in rectangle B, check if any are inside rectangle A.

All vertices can be outside and still the rectangles collide.

How? Unless we're talking about very large/small rectangles--one rectangle completely inside the other?

My knowledge of geometry, linear algebra, and trig is very stale (years!) and I never learned as much as I wish I would have. So I've seen some articles but I think I need to be "walked through" solutions a little more than usual on this topic.

-----sig:
“Programs should be written for people to read, and only incidentally for machines to execute.” - Structure and Interpretation of Computer Programs
"Political Correctness is fascism disguised as manners" --George Carlin

jmasterx
Member #11,410
October 2009

I attempted this a few years ago on android https://github.com/jmasterx/BloodshedAndMayhem

I used OrientedBoundingBox collision detection. You might find something useful in it.

https://github.com/jmasterx/BloodshedAndMayhem/blob/master/src/com/jkgames/gta/OBB2D.java

I first check if the bounding boxes intersect, if they do, and the angles are not 0, do the expensive SAT test.

http://gamedevelopment.tutsplus.com/tutorials/collision-detection-using-the-separating-axis-theorem--gamedev-169

Polybios
Member #12,293
October 2010

How? Unless we're talking about very large/small rectangles--one rectangle completely inside the other?

Think of a cross...

You can't just check if one vertex is inside the other rectangle.

My approach would have been to calculate 16 bits indicating whether the four points of R are on the "inside" or "outside" side of the edges of S and then deal with the 65536 cases. ::) Which, by the way, wouldn't be enough. You would have gotten the "cross" case right, though, I think. :P

"Projecting" / the SAT test is the way to go, I guess. It's more or less a similar, but more elegant approach that reduces complexity: For every edge involved, take its normal as projection axis and project all the vertices onto it. Take the min/max of both rectangle's vertices projections and check for overlap. If there's one axis where the projections don't overlap, there's no collision. So with 2 rectangles, there's 4 different normals and 8 vertices to project for each, which leads to 32 calculations in the worst case.

Chris Katko
Member #1,881
January 2002
avatar

Polybios said:

Think of a cross...

That's interesting. I wonder how "effective" I could be by merely adding a fifth point in the center, or even a "rectangle" but with points at half-widths along each line.

8 or 9 points, and smaller "vehicles" won't need those extra points.

I wonder how effective, and fast it would be compared to other algorithms. Game mechanics-wise, I'm pretty sure it would be fine.

-----sig:
“Programs should be written for people to read, and only incidentally for machines to execute.” - Structure and Interpretation of Computer Programs
"Political Correctness is fascism disguised as manners" --George Carlin

Mark Oates
Member #1,146
March 2001
avatar

SAT is the right way to do this. I like jmasterx's idea of using a bigger bbox first before going in for the SAT.

Go to: