Interactive continuous collision detection between deformable models using connectivity-based culling

ABSTRACT

We present an interactive algorithm for continuous collision detection between deformable models. We introduce two techniques to improve the culling efficiency and reduce the number of potentially colliding triangle candidate pairs. First, we present a novel formulation for continuous normal cones and use these normal cones to efficiently cull large regions of the mesh from self-collision tests. Second, we exploit the mesh connectivity and introduce the concept of "orphan sets" to eliminate almost all redundant elementary tests between adjacent triangles. In particular, we can reduce the number of elementary tests by many orders of magnitude. These culling techniques have been combined with bounding volume hierarchies and can result in one order of magnitude performance improvement as compared to prior algorithms for deformable models. We highlight the performance of our algorithm on several benchmarks, including cloth simulations, N-body simulations and breaking objects.

REFERENCES

• 1: L.-E. Andersson , N. F. Stewart , M. Zidani, Conditions for use of a non-selfintersection conjecture, Computer Aided Geometric Design, v.23 n.7, p.599-611, October 2006 [doi>10.1016/j.cagd.2006.05.002]
• 2: David Baraff , Andrew Witkin , Michael Kass, Untangling cloth, ACM SIGGRAPH 2003 Papers, July 27-31, 2003, San Diego, California
• 3: 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]
• 4: Robert Bridson , Ronald Fedkiw , John Anderson, Robust treatment of collisions, contact and friction for cloth animation, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 5: Sean Curtis , Rasmus Tamstorf , Dinesh Manocha, Fast collision detection for deformable models using representative-triangles, Proceedings of the 2008 symposium on Interactive 3D graphics and games, February 15-17, 2008, Redwood City, California [doi>10.1145/1342250.1342260]
• 6: 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
• 7: Foskey, M., Garber, M., Lin, M., and Manocha, D. 2001. A voronoi-based hybrid planner. Proc. of IEEE/RSJ Int. Conf. on Intelligent Robots and Systems.
• 8: 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]
• 9: Naga K. Govindaraju , Ming C. Lin , Dinesh Manocha, Fast and reliable collision culling using graphics hardware, Proceedings of the ACM symposium on Virtual reality software and technology, November 10-12, 2004, Hong Kong [doi>10.1145/1077534.1077538]
• 10: 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 Transactions on Graphics (TOG), v.24 n.3, July 2005
• 11: Heidelberger, B., Teschner, M., and Gross, M. 2003. Real-time volumetric intersections of deforming objects. Proc. of Vision, Modeling and Visualization, 461--468.
• 12: Heidelberger, B., Teschner, M., and Gross, M. 2004. Detection of collisions and self-collisions using image-space techniques. Journal of WSCG 12, 3, 145--152.
• 13: Hubbard, P. M. 1993. Interactive collision detection. In Proceedings of IEEE Symposium on Research Frontiers in Virtual Reality.
• 14: Hutter, M., and Fuhrmann, A. 2007. Optimized continuous collision detection for deformable triangle meshes. In Proc. WSCG '07, 25--32.
• 15: Doug L. James , Dinesh K. Pai, BD-tree: output-sensitive collision detection for reduced deformable models, ACM SIGGRAPH 2004 Papers, August 08-12, 2004, Los Angeles, California
• 16: Young J. Kim , Gokul Varadhan , Ming C. Lin , Dinesh Manocha, Fast swept volume approximation of complex polyhedral models, Proceedings of the eighth ACM symposium on Solid modeling and applications, June 16-20, 2003, Seattle, Washington, USA [doi>10.1145/781606.781613]
• 17: 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]
• 18: Knott, D., and Pai, D. K. 2003. CInDeR: Collision and interference detection in real-time using graphics hardware. Proc. of Graphics Interface, 73--80.
• 19: Larsson, T., and Akenine-Möller, T. 2006. A dynamic bounding volume hierarchy for generalized collision detection. Computers and Graphics 30, 3, 451--460.
• 20: Lauterbach, C., Yoon, S., Tuft, D., and Manocha, D. 2006. RT-DEFORM: Interactive Ray Tracing of Dynamic Scenes using BVHs. IEEE Symposium on Interactive Ray Tracing, 39--46.
• 21: Lin, M., and Manocha, D. 2003. Collision and proximity queries. In Handbook of Discrete and Computational Geometry.
• 22: Mezger, J., Kimmerle, S., and Etzmubeta;, O. 2003. Hierarchical techniques in cloth detection for cloth animation. Journal of WSCG 11, 1, 322--329.
• 23: Otaduy, M., Chassot, O., Steinemann, D., and Gross, M. 2007. Balanced hierarchies for collision detection between fracturing objects. In IEEE Virtual Reality, 83--90.
• 24: Provot, X. 1997. Collision and self-collision handling in cloth model dedicated to design garment. Graphics Interface, 177--189.
• 25: Redon, S., Kheddar, A., and Coquillart, S. 2002. Fast continuous collision detection between rigid bodies. Proc. of Eurographics (Computer Graphics Forum) 21, 3, 279--288.
• 26: Stephane Redon , Young J. Kim , Ming C. Lin , Dinesh Manocha, Fast continuous collision detection for articulated models, Proceedings of the ninth ACM symposium on Solid modeling and applications, June 09-11, 2004, Genoa, Italy
• 27: Sanna, A., and Milani, M. 2004. CDFast: an algorithm combining different bounding volume strategies for real time collision detection. SCI Proceedings 2, 144--149.
• 28: Sud, A., Otaduy, M. A., and Manocha, D. 2004. DiFi: Fast 3D distance field computation using graphics hardware. Computer Graphics Forum (Proc. Eurographics) 23, 3, 557--566.
• 29: 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
• 30: 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.
• 31: 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
• 32: Volino, P., and Thalmann, N. M. 1994. Efficient self-collision detection on smoothly discretized surface animations using geometrical shape regularity. Computer Graphics Forum (EuroGraphics Proc.) 13, 3, 155--166.
• 33: Pascal Volino , Nadia Magnenat Thalmann, Accurate Collision Response on Polygonal Meshes, Proceedings of the Computer Animation, p.154, May 03-05, 2000
• 34: Weller, R., and Zachmann, G. 2006. Kinetic separation lists for continuous collision detection of deformable objects. In Virtual Reality Interactions and Physical Simulation, 189--196.
• 35: 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]
• 36: 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]
• 37: Sung-Eui Yoon , Sean Curtis , Dinesh Manocha, Ray tracing dynamic scenes using selective restructuring, ACM SIGGRAPH 2007 sketches, August 05-09, 2007, San Diego, California [doi>10.1145/1278780.1278847]
• 38: 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]
• 39: Zhang, L., and Manocha, D. 2008. Motion interpolation with distance constraints. Tech. Rep. TR 08--001, Department of Computer Science, UNC Chapel Hill.
• 40: Xinyu Zhang , Stephane Redon , Minkyoung Lee , Young J. Kim, Continuous collision detection for articulated models using Taylor models and temporal culling, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007

INDEX TERMS

Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism

Keywords:
continuous collision detection, continuous normal cone, deformable models, orphan set, self-collision