Fast collision detection for deformable models using representative-triangles

ABSTRACT

We present a new approach to accelerate collision detection for deformable models. Our formulation applies to all triangulated models and significantly reduces the number of elementary tests between features of the mesh, i.e., vertices, edges and faces. We introduce the notion of Representative-Triangles, standard geometric triangles augmented with mesh feature information and use this representation to achieve better collision query performance. The resulting approach can be combined with bounding volume hierarchies and works well for both inter-object and self-collision detection. We demonstrate the benefit of Representative-Triangles on continuous collision detection for cloth simulation and N-body collision scenarios. We observe up to a one-order of magnitude reduction in feature-pair tests and up to a 5X improvement in query time.

REFERENCES

• 1: 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]
• 2: Ehmann, S., and Lin, M. C. 2001. Accurate and fast proximity queries between polyhedra using convex surface decomposition. Computer Graphics Forum (Proc. of Eurographics'2001) 20, 3, 500--510.
• 3: Christer Ericson, Real-Time Collision Detection (The Morgan Kaufmann Series in Interactive 3-D Technology) (The Morgan Kaufmann Series in Interactive 3D Technology), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004
• 4: 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]
• 5: Naga K. Govindaraju , David Knott , Nitin Jain , Ilknur Kabul , Rasmus Tamstorf , Russell Gayle , Ming C. Lin , Dinesh Manocha, Interactive collision detection between deformable models using chromatic decomposition, ACM SIGGRAPH 2005 Papers, July 31-August 04, 2005, Los Angeles, California
• 6: Hubbard, P. M. 1993. Interactive collision detection. In Proceedings of IEEE Symposium on Research Frontiers in Virtual Reality.
• 7: Hutter, M., and Fuhrmann, A. 2007. Optimized continuous collision detection for deformable triangle meshes. In Proc. WSCG '07, 25--32.
• 8: James T. Klosowski , Martin Held , Joseph S. B. Mitchell , Henry Sowizral , Karel Zikan, Efficient Collision Detection Using Bounding Volume Hierarchies of k-DOPs, IEEE Transactions on Visualization and Computer Graphics, v.4 n.1, p.21-36, January 1998 [doi>10.1109/2945.675649 ]
• 9: Larsson, T., and Akenine-Möller, T. 2006. A dynamic bounding volume hierarchy for generalized collision detection. Computers and Graphics 30, 3, 451--460.
• 10: Lin, M., and Canny, J. F. 1991. Efficient algorithms for incremental distance computation. In IEEE Conference on Robotics and Automation, 1008--1014.
• 11: Lin, M., and Manocha, D. 2003. Collision and Proximity Queries. In Handbook of Discrete and Computational Geometry: Collision detection
• 12: Brian Mirtich, V-Clip: fast and robust polyhedral collision detection, ACM Transactions on Graphics (TOG), v.17 n.3, p.177-208, July 1998 [doi>10.1145/285857.285860]
• 13: Tomas Möller, A fast triangle-triangle intersection test, Journal of Graphics Tools, v.2 n.2, p.25-30, 1997
• 14: Otaduy, M., Chassot, O., Steinemann, D., and Gross, M. 2007. Balanced hierarchies for collision detection between fracturing objects. In IEEE Virtual Reality.
• 15: Provot, X. 1997. Collision and self-collision handling in cloth model dedicated to design garment. Graphics Interface, 177--189.
• 16: Sanna, A., and Milani, M. 2004. CDFast: an algorithm combining different bounding volume strategies for real time collision detection. SCI Proceedings 2, 144--149.
• 17: Avneesh Sud , Naga Govindaraju , Russell Gayle , Ilknur Kabul , Dinesh Manocha, Fast proximity computation among deformable models using discrete Voronoi diagrams, ACM SIGGRAPH 2006 Papers, July 30-August 03, 2006, Boston, Massachusetts
• 18: Tang, M., Yoon, S., Curtis, S., and Manocha, D. 2007. Interactive continuous collision detection between deformable models using connectivity-based culling. UNC Chapel Hill, Technical Report.
• 19: Teschner, M., Kimmerle, S., Heidelberger, B., Zachmann, G., Raghupathi, L., Fuhrmann, A., Cani, M.-P., Faure, F., Magnenat-Thalmann, N., Strasser, W., and Volino, P. 2005. Collision detection for deformable objects. Computer Graphics Forum 19, 1, 61--81.
• 20: Oren Tropp , Ayellet Tal , Ilan Shimshoni, A fast triangle to triangle intersection test for collision detection: Research Articles, Computer Animation and Virtual Worlds, v.17 n.5, p.527-535, December 2006 [doi>10.1002/cav.v17:5]
• 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: Wingo Sai-Keung Wong , George Baciu, A randomized marking scheme for continuous collision detection in simulation of deformable surfaces, Proceedings of the 2006 ACM international conference on Virtual reality continuum and its applications, June 14-April 17, 2006, Hong Kong, China [doi>10.1145/1128923.1128954]
• 23: Wingo Sai-Keung Wong , George Baciu, Dynamic Interaction between Deformable Surfaces and Nonsmooth Objects, IEEE Transactions on Visualization and Computer Graphics, v.11 n.3, p.329-340, May 2005 [doi>10.1109/TVCG.2005.44]
• 24: Yoon, S., Curtis, S., and Manocha, D. 2007. Ray tracing dynamic scenes using selective restructuring. Proc. of Eurographics Symposium on Rendering.
• 25: Gabriel Zachmann , Rene Weller, Kinetic bounding volume hierarchies for deformable objects, Proceedings of the 2006 ACM international conference on Virtual reality continuum and its applications, June 14-April 17, 2006, Hong Kong, China [doi>10.1145/1128923.1128955]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.6 Methodology and Techniques
          Subjects: Graphics data structures and data types

Keywords:
bounding-volume hierarhcy, collision detection, continuous collision detection, deformable collisions, self-collision