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. Bradshaw, G., and O'Sullivan, C. 2004. Adaptive medial-axis approximation for sphere-tree construction. ACM Trans. on Graphics 23, 1.
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. Ericson, C. 2004. Real-Time Collision Detection. Morgan Kaufmann.
4. Gottschalk, S., Lin, M., and Manocha, D. 1996. OBB-Tree: A hierarchical structure for rapid interference detection. Proc. of ACM Siggraph'96, 171--180.
5. Govindaraju, N., Knott, D., Jain, N., Kabal, 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.
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. 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.
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. Mirtich, B. 1998. V-Clip: Fast and robust polyhedral collision detection. ACM Transactions on Graphics 17, 3 (July), 177--208.
13. Moller, T. 1997. A fast triangle-triangle intersection test. Journal of Graphics Tools 2, 2.
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. 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.
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. Tropp, O., Tal, A., Shimshoni, I. 2006. A fast triangle to triangle intersection test for collision detection. Computer Animation and Virtual Worlds 17, 5, 527--535.
21. van den Bergen, G. 1997. Efficient collision detection of complex deformable models using AABB trees. Journal of Graphics Tools 2, 4, 1--14.
22. 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.
23. Wong, W. S.-K. 2005. Dynamic interaction between deformable surfaces and nonsmooth objects. IEEE Tran. on Visualization and Computer Graphics.
24. Yoon, S., Curtis, S., and Manocha, D. 2007. Ray tracing dynamic scenes using selective restructuring. Proc. of Eurographics Symposium on Rendering.
25. 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.

Index Terms

• Computing methodologies

  • Computer graphics

    • Graphics systems and interfaces

      • Graphics file formats