“Interactive collision detection between deformable models using chromatic decomposition” by Govindaraju, Knott, Jain, Kabul, Tamstorf, et al. …

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.

1. Baciu, G., and Wong, S. 2002. Hardware-assisted self-collision for deformable models. ACM Symposium on VRST, 129–136. Google ScholarDigital Library
2. Baraff, D., and Witkin, A. 1998. Large steps in cloth simulation. Proc. of ACM SIGGRAPH, 43–54. Google ScholarDigital Library
3. Baraff, D., Witkin, A., and Kass, M. 2003. Untangling cloth. Proc. of ACM SIGGRAPH, 862–870. Google ScholarDigital Library
4. Baraff, D. 1992. Dynamic simulation of non-penetrating rigid body simulation. PhD thesis, Cornell University. Google ScholarDigital Library
5. 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
6. Brélaz, D. 1979. New methods to color the vertices of a graph. Communications of the ACM 22, 4, 251–256. Google ScholarDigital Library
7. 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
8. 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
9. Cordier, F., and Magnenat-Thalmann, N. 2002. Real-time animation of dressed virtual humans. Computer Graphics Forum 21, 3, 327–335.Google ScholarCross Ref
10. DeRose, T., Kass, M., and Truong, T. 1998. Subdivision surfaces in character animation. Proc. of ACM SIGGRAPH, 85–94. Google ScholarDigital Library
11. Eppstein, D., Bern, M., and Hutchings, B. 2002. Algorithms for coloring quadtrees. Algorithmica 32, 1, 87–94.Google ScholarDigital Library
12. 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
13. 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
14. 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
15. Govindaraju, N., Lin, M., and Manocha, D. 2004. Fast and reliable collision detection using graphics hardware. Proc. of ACM VRST. Google ScholarDigital Library
16. 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
17. 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
18. 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
19. Huh, S., Metaxas, D., and Badler, N. 2001. Collision resolutions in cloth simulation. Computer Animation, IEEE, 604–611.Google Scholar
20. 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
21. Jensen, T., and Toft, B. 1995. Graph Coloring Problems. Wiley InterScience.Google Scholar
22. 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
23. Kimmerle, S., Nesme, M., and Faure, F. 2004. Hierarchy accelerated stochastic collision detection. In Proceedings VMV.Google Scholar
24. 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
25. Larsson, T., and Akenine-Möller, T. 2001. Collision detection for continuously deforming bodies. In Eurographics, 325–333.Google Scholar
26. Larsson, T., and Akenine-Möller, T. 2003. Efficient collision detection for models deformed by morphing. Visual Computer 19, 164–174.Google ScholarCross Ref
27. 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
28. 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
29. 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
30. Provot, X. 1997. Collision and self-collision handling in cloth model dedicated to design garment. Graphics Interface, 177–189.Google Scholar
31. 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
32. 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
33. 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
34. 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
35. 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
36. 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
37. Volino, P., and Thalmann, N. M. 2000. Accurate collision response on polygon meshes. Computer Animation, 154. Google ScholarDigital Library