|
Collision with rotated rectangles. |
Chris Katko
Member #1,881
January 2002
|
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"} -----sig: |
anto80
Member #3,230
February 2003
|
In this case I'm using 2 inner rectangles. Another slower way would be to calculate distances between the 2 center points, with sqrt. And compare it to rectangle size. ___________ |
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
|
http://www.metanetsoftware.com/technique/tutorialA.html Everything you need and more as far as I can tell.
|
Johan Halmén
Member #1,550
September 2001
|
Is one point inside a triangle? So how would I do the first step? {"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"} References
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 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). |
Johan Halmén
Member #1,550
September 2001
|
So why did I think triangles, when the OP was about rectangles? <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 what people find beautiful about the Mandelbrot set is not the set itself, but all the rest. |
Chris Katko
Member #1,881
January 2002
|
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 Johan Halmén said: 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: |
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. Agui GUI API -> https://github.com/jmasterx/Agui |
Polybios
Member #12,293
October 2010
|
Chris Katko said: How? Unless we're talking about very large/small rectangles--one rectangle completely inside the other? Think of a cross... Johan Halmén said: 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. "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
|
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: |
Mark Oates
Member #1,146
March 2001
|
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. -- |
|