Broad Phase Components
The broad phase collision detection components are executed in a collision pipeline.
In SOFA, collision detection usually involves complex meshes (e.g. a set of triangles). For an accurate collision response, the collision detection detects which pairs of collision elements are in intersection.
The naive approach would be to test every pair of collision elements. The number of tests depends on the number of objects, and the number of collision elements in each object. For performances reasons, this approach is never selected because of its quadratic complexity.
Instead, the collision detection will be divided in two parts:
- The broad phase collision detection
- The narrow phase collision detection
The Broad Phase
In SOFA, the role of the broad phase is usually to prune a maximum number of pairs of collision models which are not in intersection. Considering collision models (usually there are more than one collision model per object), there are between (no self collision) and (if all collision models can self collide) pairs of collision models.
The output of the broad phase is a collection of pairs of collision models which are potentially in intersection. At this stage, it is not known if those pairs are actually in intersection or not. It is not known which collision elements (i.e. point/line/triangle) are in intersection with which collision elements. The list of pairs is provided as an input to the narrow phase collision detection.
Before starting the broad phase, all collision models in the scene must be listed. This is done in the function
void PipelineImpl::computeCollisionDetection() with:
std::vector<CollisionModel*> collisionModels; root->getTreeObjects<CollisionModel> (&collisionModels);
Then, the broad phase collision detection is executed in 3 functions:
void BroadPhaseDetection::addCollisionModels(const sofa::helper::vector<core::CollisionModel *>& v)
addCollisionModels is called on the list of all collision models in the scene. Internally, this function is just a loop calling the following function:
void BroadPhaseDetection::addCollisionModel(core::CollisionModel *cm)
The implementation of these 3 functions (
endBroadPhase) defines the behavior of the broad phase. It is where the algorithm is implemented. To implement a new broad phase algorithm, a developer will probably derive a class from
BroadPhaseDetection and override the 3 mentioned functions.
After the execution of the broad phase, the list of potential colliding pairs is stored in
sofa::helper::vector< CollisionModelPair > BroadPhaseDetection::cmPairs;
Finally, the collision pipeline provides this list to a narrow phase collision detection.
Examples of Components
The following components are all broad phase collision detections, and can be placed in a simulation scene:
- ParallelBruteForceBroadPhase (plugin MultiThreading)
- THMPGSpatialHashing (plugin THMPGSpatialHashing)
- BulletCollisionDetection (plugin BulletCollisionDetection)
Read more on SOFA API documentation
Last modified: 6 June 2023