[JP04]
Cornell University Program of Computer Graphics 

Bdtree: outputsensitive collision detection for reduced deformable models.Doug L. James and Dinesh K. Pai.ACM Trans. Graph., 23(3):393398, 2004. We introduce the Bounded Deformation Tree, or BDTree, which can perform collision detection with reduced deformable models at costs comparable to collision detection with rigid objects. Reduced deformable models represent complex deformations as linear superpositions of arbitrary displacement fields, and are used in a variety of applications of interactive computer graphics. The BDTree is a bounding sphere hierarchy for outputsensitive collision detection with such models. Its bounding spheres can be updated after deformation in any order, and at a cost independent of the geometric complexity of the model; in fact the cost can be as low as one multiplication and addition per tested sphere, and at most linear in the number of reduced deformation coordinates. We show that the BDTree is also extremely simple to implement, and performs well in practice for a variety of realtime and complex offline deformable simulation examples.
The accompanying video is available as a AVI file JP04.avi This paper is available as a PDF file JP04.pdf (4.7M).
 
