iDevGames Forums
Phases of Collision Detection - Printable Version

+- iDevGames Forums (http://www.idevgames.com/forums)
+-- Forum: Development Zone (/forum-3.html)
+--- Forum: Game Programming Fundamentals (/forum-7.html)
+--- Thread: Phases of Collision Detection (/thread-838.html)



Phases of Collision Detection - Ingemar - Aug 19, 2009 05:38 AM

Continuing the tangent from this thread: http://www.idevgames.com/forum/showthread.php?t=17950

Skorche Wrote:Collision detection is normally broken down into several phases:
Broad Phase: Finding out which objects to collide against other objects. The simplest method is to check collisions with every object against every other object. This is very fast when you have small groups of objects that you want to collide against each other (< 10 we'll say), but extremely slow when you have a lot of objects (< 1000). The reason is that for 10 objects you would need 45 mid-phase checks and for 1000 you would need 499500. It doesn't scale to large numbers very well, and when you have a lot of objects you'll spend more time doing mid-phase checks than anything else. To speed up the broad phase, you'll need to use a smarter algorithm such as sort and sweep, spatial hashing, quadtrees, or some other spatial index that only tries combinations of objects that are likely to be colliding.

Mid Phase: This is where you normally do a simple collision check such as a bounding box or bounding sphere check because they would be faster than your narrow phase. Most spatial index structures are going to return some false positives, and it's best to catch them early instead of calling the more expensive narrow phase collision routines.

Narrow Phase: The narrow phase is the most specific and most expensive collision detection check such as a polygon to polygon check or a pixel to pixel check. A lot of games do just fine with bounding spheres or bounding boxes and don't need a more specific narrow phase check.
Your breakdown is correct, but I'd like to discuss the naming of each phase. In Watt's book, he uses the term "broad phase" for the simplified bounding shapes, which means that the global organization needs another name. Möller doesn't use these names at all (maybe to avoid confusion). Do you have some other reference for the naming?


Phases of Collision Detection - DoG - Aug 19, 2009 07:21 AM

Broad phase does generally reference the space partitioning. Maybe "space partitioning", "bounding volume collisions" and "exact collisions" work, though the last two would be what I call the narrow phase (there is no mid phase Smile ), as doing the exact intersection test is typically done rightaway if a bounding volume collision is detected, instead of first doing bounds checks on all objects before doing the exact collisions.


Phases of Collision Detection - Skorche - Aug 19, 2009 07:50 AM

I've seen the "mid phase" term used a few times, though I don't really book mark things so I can't give references that I didn't just make up the term.

There are other people using the term, though Google puts a post written by me very high in the search results. Rasp http://www.google.com/search?client=safari&rls=en-us&q=mid-phase+collision&ie=UTF-8&oe=UTF-8 Not very convincing to my case. Heh.

I've heard it stated that way because many spatial indexes or bounding hierarchies don't actually store the bounding boxes and can't perform this check before identifying it as a potential collision pair. My spatial hash does not because it assumes that the objects are moving and only retrieves the bounding box with a callback when rehashing. Spatial hashing is also a very cheap broad phase algorithm in many ways, but can also return a significant fraction of false positives requiring an early short circuit if you are using something moderately expensive such as SAT for colliding objects.

If the broad-phase algorithm already does something that compares bounding volumes, I guess I would consider the mid phase as part of the broad phase then. Though doing a simple bounding volume test is almost always recommended over a precise primitive test. Bounding spheres and boxes are generally so much cheaper, that it's worth making the extra comparisons if it avoids calling the main body of the precise test even a fraction of the time.


Phases of Collision Detection - Ingemar - Aug 19, 2009 02:05 PM

I don't mind broad-mid-narrow, there are three phases all right, but I need some better references to consider that the proper terms (whatever that means). I have used prof. Watt's naming and I don't know any other publications that uses the other naming. I can check a few other books though. I would expect Christer Ericsson to use the "right" terms so I'll have a look in his book tomorrow. (It is bed-time now.)


Phases of Collision Detection - Ingemar - Aug 22, 2009 12:08 AM

I checked out my books. Watt includes the space partitioning phase in "broad phase", while Ericsson calls everything except the space partitioning phase "narrow".

I like the three-phase view better, but it gets tricky to know what to call it when the literature disagrees like this.


Phases of Collision Detection - Skorche - Aug 24, 2009 06:11 AM

I dunno, I just always thought of it as the following:
Broad phase: Use a smart algorithm to cull out most of the non-colliding pairs.
Mid phase: Use a yes/no quick test, bounding spheres or AABBs to clean up the false positives pairs that the broad-phase sent.
Narrow phase: Specific collision tests with all of the goodies. Contact points, normals, penetration depth, all the good stuff.