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. Andersson, L.-E., Stewart, N. F., and Zidani, M. 2006. Conditions for use of a non-selfintersection conjecture. Comput. Aided Geom. Des. 23, 7, 599--611.
2. Baraff, D., Witkin, A., and Kass, M. 2003. Untangling cloth. Proc. of ACM SIGGRAPH, 862--870.
3. Bradshaw, G., and O'Sullivan, C. 2004. Adaptive medial-axis approximation for sphere-tree construction. ACM Trans. on Graphics 23, 1, 1--26.
4. Bridson, R., Fedkiw, R., and Anderson, J. 2002. Robust treament for collisions, contact and friction for cloth animation. Proc. of ACM SIGGRAPH, 594--603.
5. Curtis, S., Tamstorf, R., and Manocha, D. 2008. Fast collision detection for deformable models using representative-triangles. In SI3D '08: Proceedings of the 2008 Symposium on Interactive 3D graphics and games, 61--69.
6. Ericson, C. 2004. Real-Time Collision Detection. Morgan Kaufmann.
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. Gottschalk, S., Lin, M., and Manocha, D. 1996. OBB-Tree: A hierarchical structure for rapid interference detection. Proc. of ACM Siggraph '96, 171--180.
9. Govindaraju, N., Lin, M., and Manocha, D. 2004. Fast and reliable collision detection using graphics hardware. Proc. of ACM VRST.
10. Govindaraju, N., Knott, D., Jain, N., Kabul, I., Tamstorf, R., Gayle, R., Lin, M., and Manocha, D. 2005. Collision detection between deformable models using chromatic decomposition. ACM Trans. on Graphics (Proc. of ACM SIGGRAPH) 24, 3, 991--999.
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. James, D. L., and Pai, D. K. 2004. BD-Tree: Output-sensitive collision detection for reduced deformable models. Proc. of ACM SIGGRAPH, 393--398.
16. Kim, Y., Varadhan, G., Lin, M., and Manocha, D. 2003. Efficient swept volume approximation of complex polyhedral models. Proc. of ACM Symposium on Solid Modeling and Applications, 11--22.
17. Klosowski, J., Held, M., Mitchell, J., Sowizral, H., and Zikan, K. 1998. Efficient collision detection using bounding volume hierarchies of k-dops. IEEE Trans. on Visualization and Computer Graphics 4, 1, 21--37.
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. Redon, S., Kim, Y. J., Lin, M. C., and Manocha, D. 2004. Fast continuous collision detection for articulated models. In Proceedings of ACM Symposium on Solid Modeling and Applications, 145--156.
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. Sud, A., Govindaraju, N., Gayle, R., Kabul, I., and Manocha, D. 2006. Fast proximity computation among deformable models using discrete voronoi diagrams. Proc. of ACM SIGGRAPH, 1144--1153.
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. Van Den Bergen, G. 1997. Efficient collision detection of complex deformable models using AABB trees. Journal of Graphics Tools 2, 4, 1--14.
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. Volino, P., and Thalmann, N. M. 2000. Accurate collision response on polygon meshes. In Proc. of Computer Animation, 154--163.
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. Wong, W. S.-K., and Baciu, G. 2005. Dynamic interaction between deformable surfaces and nonsmooth objects. IEEE Tran. on Visualization and Computer Graphics 11, 3, 329--340.
36. Wong, W. S.-K., and Baciu, G. 2006. A randomized marking scheme for continuous collision detection in simulation of deformable surfaces. Proc. of ACM VRCIA, 181--188.
37. Yoon, S., Curtis, S., and Manocha, D. 2007. Ray tracing dynamic scenes using selective restructuring. Proc. of Eurographics Symposium on Rendering.
38. Zachmann, G., and Weller, R. 2006. Kinetic bounding volume hierarchies for deforming objects. In ACM Int'l Conf. on Virtual Reality Continuum and its Applications.
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. Zhang, X., Redon, S., Lee, M., and Kim, Y. J. 2007. Continuous collision detection for articulated models using taylor models and temporal culling. ACM Transactions on Graphics (Proceedings of SIGGRAPH 2007) 26, 3, 15.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Computer vision

      • Image and video acquisition

        • 3D imaging

  • Computer graphics

    • Animation

• Mathematics of computing

  • Probability and statistics