BD-tree: output-sensitive collision detection for reduced deformable models

ABSTRACT

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 arbitrary 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 of 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.

REFERENCES

• 1: ALEXA, M., AND MÜLLER, W. 2000. Representing Animations by Principal Components. Computer Graphics Forum 19, 3 (Aug.), 411--418.
• 2: Gareth Bradshaw , Carol O'Sullivan, Adaptive medial-axis approximation for sphere-tree construction, ACM Transactions on Graphics (TOG), v.23 n.1, p.1-26, January 2004 [doi>10.1145/966131.966132]
• 3: Robert Bridson , Ronald Fedkiw , John Anderson, Robust treatment of collisions, contact and friction for cloth animation, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 4: BROWN, J., SORKIN, S., BRUYNS, C., LATOMBE, J., MONTGOMERY, K., AND STEPHANIDES, M. 2001. Real-Time Simulation of Deformable Objects: Tools and Application. In Proceedings of Computer Animation 2001.
• 5: Gilles Debunne , Mathieu Desbrun , Marie-Paule Cani , Alan H. Barr, Dynamic real-time deformations using space & time adaptive sampling, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.31-36, August 2001 [doi>10.1145/383259.383262]
• 6: DINGLIANA, J., AND O'SULLIVAN, C. 2000. Graceful Degradation of Collision Handling in Physically Based Animation. Computer Graphics Forum 19, 3 (Aug.), 239--248.
• 7: Petros Faloutsos , Michiel van de Panne , Demetri Terzopoulos, Dynamic Free-Form Deformations for Animation Synthesis, IEEE Transactions on Visualization and Computer Graphics, v.3 n.3, p.201-214, July 1997 [doi>10.1109/2945.620488]
• 8: GANOVELLI, F., DINGLIANA, J., AND O'SULLIVAN, C. 2000. BucketTree: Improving collision detection between deformable objects. In Spring Conference in Computer Graphics (SCCG2000), 156--163.
• 9: S. Gottschalk , M. C. Lin , D. Manocha, OBBTree: a hierarchical structure for rapid interference detection, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.171-180, August 1996 [doi>10.1145/237170.237244]
• 10: Leonidas Guibas , An Nguyen , Daniel Russel , Li Zhang, Collision detection for deforming necklaces, Proceedings of the eighteenth annual symposium on Computational geometry, p.33-42, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513405]
• 11: Philip M. Hubbard, Collision Detection for Interactive Graphics Applications, IEEE Transactions on Visualization and Computer Graphics, v.1 n.3, p.218-230, September 1995 [doi>10.1109/2945.466717]
• 12: Doug L. James , Dinesh K. Pai, ArtDefo: accurate real time deformable objects, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.65-72, July 1999 [doi>10.1145/311535.311542]
• 13: Doug L. James , Dinesh K. Pai, DyRT: dynamic response textures for real time deformation simulation with graphics hardware, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 14: JIMENEZ, P., THOMAS, F., AND TORRAS, C. 2001. 3D Collision Detection: A Survey. Computers and Graphics 25, 2 (Apr.), 269--285.
• 15: LARSSON, T., AND AKENINE-MÖLLER, T. 2001. Collision Detection for Continuously Deforming Bodies. In Eurographics 2001, A. Chalmers and T.-M. Rhyne, Eds., Eurographics, 325--333.
• 16: LARSSON, T., AND AKENINE-MÖLLER, T. 2003. Efficient collision detection for models deformed by morphing. The Visual Computer 19, 2, 164--174.
• 17: J. P. Lewis , Matt Cordner , Nickson Fong, Pose space deformation: a unified approach to shape interpolation and skeleton-driven deformation, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.165-172, July 2000 [doi>10.1145/344779.344862]
• 18: LIN, M. C., AND GOTTSCHALK, S. 1998. Collision detection between geometric models: A survey. In Proc. of IMA Conference on Mathematics of Surfaces, 37--56.
• 19: MANOCHA, D., LIN, M. C., DOGGETT, M., GREENE, N., HOFF, K., KILGARD, M., AND KRISHNAN, S. 2002. Interactive Geometric Computations Using Graphics Hardware. In SIGGRAPH 2002 Course Notes, ACM SIGGRAPH.
• 20: QUINLAN, S. 1994. Efficient Distance Computation between Non-Convex Objects. In IEEE Intern. Conf. on Robotics and Automation, IEEE, 3324--3329.
• 21: Gino van den Bergen, Efficient collision detection of complex deformable models using AABB trees, Journal of Graphics Tools, v.2 n.4, p.1-13, April 1997
• 22: Joe Warren , Joseph D. Warren , Henrik Weimer, Subdivision Methods for Geometric Design: A Constructive Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 23: WELZL, E. 1991. Smallest enclosing disks (balls and ellipsoids). In New Results and New Trends in Comp. Sci., H. Maurer, Ed., vol. 555 of Lecture Notes Comp. Sci. Springer-Verlag, 359--370.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

Keywords:
collision, deformable, output-sensitive, sphere trees