Broadphase

From Physics Simulation Wiki

Jump to: navigation, search

Contents

Broadphase

This is a rough description but should be enough for those unfamiliar with broadphase who are trying to understand Bullet's API.

The broadphase algorithm usually uses the bounding boxes of objects in the world to quickly compute a conservative approximate list of colliding pairs. The list will include every pair of objects that are colliding, but it may also include pairs of objects whose bounding boxes intersect but are still not close enough to collide. Later stages will calculate exact collisions, and thus these extra pairs will be eliminated, but those algorithms are much slower so we don't want to run them on every pair of rigid bodies in the world.

Algorithms Supported By Bullet

There are various kinds of broadphase algorithms that improve upon the naive O(n^2) algorithm that just returns the complete list of pairs. These optimised broadphases sometimes introduce even more non-colliding pairs but this is offset by their generally improved execution time. They have different performance characteristics and none outperform the others in all situations.

Dynamic AABB Tree

This is implemented by the btDbvtBroadphase in Bullet.

As the name suggests, this is a dynamic AABB tree. One useful feature of this broadphase is that the structure adapts dynamically to the dimensions of the world and its contents. It is very well optimized and a very good general purpose broadphase. It handles dynamic worlds where many objects are in motion, and object addition and removal is faster than SAP.


Sweep and Prune (SAP)

In Bullet, this is the AxisSweep range of classes. This is also a good general purpose broadphase, with a limitation that it requires a fixed world size, known in advance. This broadphase has the best performance for typical dynamics worlds, where most objects have little or no motion. Both btAxisSweep3 and bt32AxisSweep3 quantize the begin and end points for each axis as integers instead of floating point numbers, to improve performance.

The following link is a general introduction to broadphase and also a description of the Sweep and Prune algorithm (although it calls it "Sort and Sweep"):

http://www.ziggyware.com/readarticle.php?article_id=128

Also, take a look at the wikipedia page:

http://en.wikipedia.org/wiki/Sweep_and_prune


CD TestFramework Broadphase Benchmark

Pierre Terdiman created a framework to test various collision detection algorithms. We made a version that compares several broadphases. You can see the results in the CDTestFramework.

Other Tips For Increasing Broadphase Speed

If you have a large amount of static trimesh collision shapes, batch them together using a single btBvhTriangleShape. This will only have one entry in the broadphase.

If you use collision masks to disable collisions, instead of a near callback, you can filter out unwanted pairs earlier in the pipeline and improve performance. See Collision Things

Personal tools