Broad Phase Collision Detection

[bronxbomber92]

Hello,

I'm considering different methods for doing broad phase collision detection. At the moment, the approach proposed in "Optimized Spatial Hashing for Collision Detection of Deformable Objects" seems to be the most appealing. This is what's used in the Chipmunk engine. Other possibilities are some type of BVH (which I haven't done much research on).

I'd like to be able to support AABB, OBB, Bounding Sphere, and Capsules at collider types when doing narrow phase, and I'm not sure how well the Spatial hashing collision detection method would work. The paper states:

The proposed algorithm detects, whether a vertex
penetrates a tetrahedron, but it does not detect,
whether an edge intersects with a tetrahedron.

I'm not sure if they're referring to the broad phase or barrow phase.

So, my questions are;
What do most people use (what's the most common?) method for broad phase collision?
Does the spatial hashing method deal with broad phase and narrow phase, or one or the other? Has anyone used this method before (in 3D)?
Are there any papers out there the cover some other methods for broad phase collision (for example, BVH)?

Thanks!

[Erwin Coumans]

What do most people use (what's the most common?) method for broad phase collision?
Does the spatial hashing method deal with broad phase and narrow phase, or one or the other? Has anyone used this method before (in 3D)?
Are there any papers out there the cover some other methods for broad phase collision (for example, BVH)?
Thanks!

Many people in the professional game industry (including physics middleware companies) use the Sweep and Prune broadphase (SAP).

You can find a practical discussion by Pierre Terdiman in his recent Sweep and Prune posting. Bullet physics library has an optimized and robust implementation of the 3-axis SAP broadphase in btAxisSweep3 and bt32BitAxisSweep3

Hope this helps,
Erwin

[bronxbomber92]

Thank, this helps very much! I will give this a read.

I've done a little more research, and I've found a paper on the method I-Collide uses, a paper on SWIFT's method, Erleben's paper on BVH "An Introduction to Approximatting heterogeneous Bounding Volume Hierarchies", and the papers of Stephane Redon on CCD.

I will read most of the papers, and see which seems best for my situation. I'm excited!

[bronxbomber92]

After reading the SAP document, I've got a rather trivial question. Would storing the AABB boxes in a STL vector be appropriate? Is there any pitfalls I should look out for if I were to use a STL vector?

Edit - Nevermind