Graphics enhanced version of this site

BD-Tree: Output-Sensitive Collision Detection for Reduced Deformable Models
D. James and D. Pai
ACM Transactions on Graphics (SIGGRAPH 2004), Vol. 23, No. 3, August, 2004.

Jump to: Download | Abstract | Notes | Text Reference | BibTeX Reference

Adobe portable document format (pdf) [4951 KB]

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

We introduce the Bounded Deformation Tree, or BD-Tree, 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 arbitary displacement fields, and are used in a variety of applications of interactive computer graphics. The BD-Tree is a bounding sphere hierarchy for output-sensitive 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 reduced deformation coordinates. We show that the BD-Tree is also extremely simple to implement, and performs well in practice for a variety of real-time and complex off-line deformable simulation examples.

Note: AVI Video available at: http://graphics.cs.cmu.edu/projects/bdtree/JamesPai_BDTree04_divx_high.avi

D. James and D. Pai, "BD-Tree: Output-Sensitive Collision Detection for Reduced Deformable Models," ACM Transactions on Graphics (SIGGRAPH 2004), Vol. 23, No. 3, August, 2004.

@article{James_2004_5209,
   author = "Doug James and Dinesh Pai",
   title = "BD-Tree: Output-Sensitive Collision Detection for Reduced Deformable Models",
   journal = "ACM Transactions on Graphics (SIGGRAPH 2004)",
   month = "August",
   year = "2004",
   volume = "23",
   number = "3",
   note = "AVI Video available at: http://graphics.cs.cmu.edu/projects/bdtree/JamesPai_BDTree04_divx_high.avi"
}