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