Archived

This topic is now archived and is closed to further replies.

leiavoia

Faster 2D Polygon-Polygon Collision?

Recommended Posts

leiavoia    960
For a 2D game using irregular polygons as collision areas (just a closed list of vertices), is there a fast way to check for true intersections? I''m not interested in the cheap way (throw a sphere around them), i want an exact calculation. After searching, the only solution i can come up with is to check every line segment of poly A against every segment of poly B. Is there a faster way than this? Also, this method is flawed as it will not check for such a collision where there are no segment overlaps (not that i''d expect that to be a big problem):
+-----+
|     |
| +-+ |
| | | |
| +-+ |
|     |
+-----+ 

Share this post


Link to post
Share on other sites
Ademan555    361
I dont believe theres a faster way, however, i am very interested in algorythms that allow you to test moving segments against other moving segments, or moving spheres, (of course tahts not jsut 1 algo) anyways, i kinda thoughti had it figured out, but then i realized, that segments can do a hell of a lot more than just translate, tehy can rotate too! now im compltely at a loss... anyone got any ideas?

-Dan

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
To solve the problem of a polygon being completely contained in another polygon, you can check one point from each polygon to see if it is completely contained in the other polygon.

To speed up collision checks, you can use a space partitioning scheme (like a quadtree of some sort) to avoid having to test polygons that can''t possibly be overlapping. For the polygon-polygon test itself, you can try to create a bounding hierarchy for each polygon, and test the hierarchies against each other, descending down to the individual line segments. Depending on the complexity and shape of the polygons, this could be faster or slower.

Share this post


Link to post
Share on other sites
leiavoia    960
I''m doing my game is opengl so pixel-collisions are out (besides being expensive). Less important items i''m just going to wrap in a sphere or bounding box, but the important ones (like the player ;-) i want to wrap with a "custom" polygon (think "scissor cut-out"). But then the only decent way i can think of to check if i''ve hit something is to check all my segments against the other geometry''s segments. I only plan to do this for a few certain objects, so i guess it''s not a really big deal.

Share this post


Link to post
Share on other sites
romer    323
Check out this article. They talk about using polygonal armatures, which is basically a set of vertices that describe a polygon bounding volume. To test for a collision between two armatures, you test the line segments of the two armatures against each other and see if they intersect. The article has a formula for you to use and discusses some simple optimizations. Of course, there's a lot more which you can add to help speed up the calculations is a world of multiple objects (such as using quadtrees, checking for a separating axis between two objects, etc.), but I think this is more or less what you're looking for.

To make sure that an object that ends up completely inside another object between two frames registers as a collision, I think you can do some form of an interval test, but I'm not well versed in collision detection, so I'm not 100% certain.

[edited by - MRom on May 26, 2004 3:02:43 AM]

Share this post


Link to post
Share on other sites
oliii    2196
the separation axis algorithm, once again... you''ll need to split the polygon in convex polygons, or just triangles. And can be extended to test with velocities as well.

the axis for the separation tests are the vector perpendicular to the edges of the polygon.

Share this post


Link to post
Share on other sites