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):

+-----+
|     |
| +-+ |
| | | |
| +-+ |
|     |
+-----+ 

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.

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.

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]