Naga K. Govindaraju
Skip Abstract Section
Skip Supplemental Material SectionAbstract
We present a novel algorithm for accurately detecting all contacts, including self-collisions, between deformable models. We precompute a chromatic decomposition of a mesh into non-adjacent primitives using graph coloring algorithms. The chromatic decomposition enables us to check for collisions between non-adjacent primitives using a linear-time culling algorithm. As a result, we achieve higher culling efficiency and significantly reduce the number of false positives. We use our algorithm to check for collisions among complex deformable models consisting of tens of thousands of triangles for cloth modeling and medical simulation. Our algorithm accurately computes all contacts at interactive rates. We observed up to an order of magnitude speedup over prior methods.
Supplemental Material
- Baciu, G., and Wong, S. 2002. Hardware-assisted self-collision for deformable models. ACM Symposium on VRST, 129--136. Google Scholar
Digital Library
- Baraff, D., and Witkin, A. 1998. Large steps in cloth simulation. Proc. of ACM SIGGRAPH, 43--54. Google ScholarDigital Library
- Baraff, D., Witkin, A., and Kass, M. 2003. Untangling cloth. Proc. of ACM SIGGRAPH, 862--870. Google ScholarDigital Library
- Baraff, D. 1992. Dynamic simulation of non-penetrating rigid body simulation. PhD thesis, Cornell University. Google ScholarDigital Library
- Breen, D., House, D., and Wozny, M. 1994. Predicting the drape of woven cloth using interacting particles. Proc. of ACM SIGGRAPH, 365--372. Google ScholarDigital Library
- Brélaz, D. 1979. New methods to color the vertices of a graph. Communications of the ACM 22, 4, 251--256. Google ScholarDigital Library
- Bridson, R., Fedkiw, R., and Anderson, J. 2002. Robust treatment for collisions, contact and friction for cloth animation. Proc. of ACM SIGGRAPH, 594--603. Google ScholarDigital Library
- Cohen, J., Lin, M., Manocha, D., and Ponamgi, M. 1995. I-COLLIDE: An interactive and exact collision detection system for large-scale environments. In Proc. of ACM Interactive 3D Graphics Conference, 189--196. Google ScholarDigital Library
- Cordier, F., and Magnenat-Thalmann, N. 2002. Real-time animation of dressed virtual humans. Computer Graphics Forum 21, 3, 327--335.Google ScholarCross Ref
- DeRose, T., Kass, M., and Truong, T. 1998. Subdivision surfaces in character animation. Proc. of ACM SIGGRAPH, 85--94. Google ScholarDigital Library
- Eppstein, D., Bern, M., and Hutchings, B. 2002. Algorithms for coloring quadtrees. Algorithmica 32, 1, 87--94.Google ScholarDigital Library
- Fuhrmann, A., Gross. C., and Luckas, V. 2003. Interactive animation of cloth including self collision detection. Journal of WSCG 11, 1, 203--208.Google Scholar
- Gayle, R., Segars, P., Lin, M., and Manocha, D. 2005. Path planning for deformable robots in complex environments. Tech. rep., University of North Carolina-Chapel Hill. To appear in Proc. of Robotics: Science and Systems.Google Scholar
- Govindaraju, N., Redon, S., Lin, M., and Manocha, D. 2003. CULLIDE: Interactive collision detection between complex models in large environments using graphics hardware. Proc. of ACM SIGGRAPH/Eurographics Workshop on Graphics Hardware, 25--32. Google ScholarDigital Library
- Govindaraju, N., Lin, M., and Manocha, D. 2004. Fast and reliable collision detection using graphics hardware. Proc. of ACM VRST. Google ScholarDigital Library
- Govindaraju, N., Lin, M., and Manocha, D. 2005. Quick-CULLIDE: Efficient inter- and intra- object collision culling using GPUs. Proc. of IEEE VR, 59--66. Google ScholarDigital Library
- Heidelberger, B., Teschner, M., and Gross, M. 2003. Real-time volumetric intersections of deforming objects. Proc. of Vision, Modeling and Visualization, 461--468.Google Scholar
- 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.Google Scholar
- Huh, S., Metaxas, D., and Badler, N. 2001. Collision resolutions in cloth simulation. Computer Animation, IEEE, 604--611.Google Scholar
- James, D. L., and Pai, D. K. 2004. BD-Tree: Output-sensitive collision detection for reduced deformable models. Proc. of ACM SIGGRAPH, 393--398. Google ScholarDigital Library
- Jensen, T., and Toft, B. 1995. Graph Coloring Problems. Wiley InterScience.Google Scholar
- Kang, Y., and Cho, H. 2002. Bilayered approximate integration for rapid and plausible animation of virtual cloth with realistic wrinkles. Computer Animation, 604--611.Google Scholar
- Kimmerle, S., Nesme, M., and Faure, F. 2004. Hierarchy accelerated stochastic collision detection. In Proceedings VMV.Google Scholar
- Knott, D., and Pai, D. K. 2003. CInDeR: Collision and interference detection in real-time using graphics hardware. Proc. of Graphics Interface, 73--80.Google Scholar
- Larsson, T., and Akenine-Möller, T. 2001. Collision detection for continuously deforming bodies. In Eurographics, 325--333.Google Scholar
- Larsson, T., and Akenine-Möller, T. 2003. Efficient collision detection for models deformed by morphing. Visual Computer 19, 164--174.Google ScholarCross Ref
- Lin, M. C., and Manocha, D. 2004. Collision and proximity queries. In Handbook of Discrete and Computational Geometry, 2nd Ed., J. E. Goodman and J. O'Rourke, Eds. CRC Press LLC, Boca Raton, FL, ch. 35, 787--807.Google Scholar
- Meyer, M., Debunne, G., Desbrun, M., and Barr, A. 2000. Interactive animation of cloth like objects in virtual reality. Journal of Visualization and Computer Animation 12, 1, 1--12.Google ScholarCross Ref
- Mezger, J., Kimmerle, S., and Etzmuß, O. 2003. Hierarchical techniques in cloth detection for cloth animation. Journal of WSCG 11, 1, 322--329.Google Scholar
- Provot, X. 1997. Collision and self-collision handling in cloth model dedicated to design garment. Graphics Interface, 177--189.Google Scholar
- Rossignac, J., Megahed, A., and Schneider, B. 1992. Interactive inspection of solids: cross-sections and interferences. In Proceedings of ACM SIGGRAPH, 353--60. Google ScholarDigital Library
- Sanders, D., and Zhao, Y. 1998. On d-diagonal colorings of embedded graphs of low maximum face size. Graphs and Combinatorics 14, 81--94.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- Van Den Bergen, G. 1997. Efficient collision detection of complex deformable models using aabb trees. Journal of Graphics Tools 2, 4, 1--14. Google ScholarDigital Library
- Vassilev, T., Spanlang, B., and Chrysanthou, Y. 2001. Fast cloth animation on walking avatars. Computer Graphics Forum (Proc. of Eurographics'01) 20, 3, 260--267.Google Scholar
- 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.Google ScholarCross Ref
- Volino, P., and Thalmann, N. M. 2000. Accurate collision response on polygon meshes. Computer Animation, 154. Google ScholarDigital Library
Index Terms
- Interactive collision detection between deformable models using chromatic decomposition
Recommendations
Fast collision detection for deformable models using representative-triangles
I3D '08: Proceedings of the 2008 symposium on Interactive 3D graphics and gamesWe 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. ...
Interactive collision detection between deformable models using chromatic decomposition
SIGGRAPH '05: ACM SIGGRAPH 2005 PapersWe present a novel algorithm for accurately detecting all contacts, including self-collisions, between deformable models. We precompute a chromatic decomposition of a mesh into non-adjacent primitives using graph coloring algorithms. The chromatic ...
Image-Based Collision Detection for Deformable Cloth Models
Modeling the natural interaction of cloth and garments with objects in a 3D environment is currently one of the most computationally demanding tasks. These highly deformable materials are subject to a very large number of contact points in the proximity ...
Comments