Soft Body Dynamics - Collision Detection For Deformable Objects

Collision Detection For Deformable Objects

Realistic interaction of simulated soft objects with their environment may be important for obtaining visually realistic results. Cloth self-intersection is important in some applications for acceptably realistic simulated garments. This is challenging to achieve at interactive frame rates, particularly in the case of detecting and resolving self collisions and mutual collisions between two or more deformable objects.

Collision detection may be discrete/a posteriori (meaning objects are advanced in time through a pre-determined interval, and then any penetrations detected and resolved), or continuous/a priori (objects are advanced only until a collision occurs, and the collision is handled before proceeding). The former is easier to implement and faster, but leads to failure to detect collisions (or detection of spurious collisions) if objects move fast enough. Real-time systems generally have to use discrete collision detection, with other ad hoc ways to avoid failing to detect collisions.

Detection of collisions between cloth and environmental objects with a well defined "inside" is straightforward since the system can detect unambiguously whether the cloth mesh vertices and faces are intersecting the body and resolve them accordingly. If a well defined "inside" does not exist (e.g. in the case of collision with a mesh which does not form a closed boundary), an "inside" may be constructed via extrusion. Mutual- or self-collisions of soft bodies defined by tetrahedra is straightforward, since it reduces to detection of collisions between solid tetrahedra.

However, detection of collisions between two polygonal cloths (or collision of a cloth with itself) via discrete collision detection is much more difficult, since there is no unambiguous way to locally detect after a timestep whether a cloth node which has penetrated is on the "wrong" side or not. Solutions involve either using the history of the cloth motion to determine if an intersection event has occurred, or doing a global analysis of the cloth state to detect and resolve self-intersections. Pixar has presented a method which uses a global topological analysis of mesh intersections in configuration space to detect and resolve self-interpenetration of cloth. Currently, this is generally too computationally expensive for real-time cloth systems.

To do collision detection efficiently, primitives which are certainly not colliding must be identified as soon as possible and discarded from consideration to avoid wasting time. To do this, some form of spatial subdivision scheme is essential, to avoid a brute force test of primitive collisions. Approaches used include:

• Bounding volume hierarchies (AABB trees, OBB trees, sphere trees)
• Grids, either uniform (using hashing for memory efficiency) or hierarchical (e.g. Octree, kd-tree)
• Coherence-exploiting schemes, such as sweep and prune with insertion sort, or tree-tree collisions with front tracking.
• Hybrid methods involving a combination of various of these schemes, e.g. a coarse AABB tree plus sweep-and-prune with coherence between colliding leaves.