Phases of Collision Detection

Member
Posts: 260
Joined: 2005.05
Post: #1

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?
Moderator
Posts: 869
Joined: 2003.01
Post: #2
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.
Sage
Posts: 1,487
Joined: 2002.09
Post: #3
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=safa...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.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Member
Posts: 260
Joined: 2005.05
Post: #4
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.)
Member
Posts: 260
Joined: 2005.05
Post: #5
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.
Sage
Posts: 1,487
Joined: 2002.09
Post: #6
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.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.