University logo GIVE logo

Self collision detection for deformable models

Work done by Peter Bozarov as a Master's degree project.

One special aspect of deformable models, is that they can collide with themselves. To handle these collisions, it is required to detect these collisions first. Speaking in more detail, it is required that all parts of the surface that mutually collide are detected.

This process can be sped up with a bounding volume hierarchy, but this still has quadratic worst-case complexity. In practice, it is quite slow. One optimization is to eliminate flat parts of the bounding volume tree, since a flat part of a surface can never self-collide. (this was proposed by Magenat-Thalmann and Volino).

This scheme was implemented, and it was found that introducing the flatness test eliminated a substantial amount of primitive/primitive tests. Unfortunately, to make the test fully correct, the contour of the region under consideration should also be checked for self-intersections. This contour test is expensive both at runtime, and during the construction of the hierarchy. Moreover it is only needed in the vicinity of cuts. The recommendation therefore is to skip the contour tests, and not apply the flatness criterion near cuts.

The scheme was also adapted for cutting: when removing and inserting triangles on the surface, the bounding volume tree has to be rebuilt. This was shown to have acceptable time complexity.

GIVE > Virtual Environments > Virtual Surgery > Self collisions.