{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,24]],"date-time":"2026-07-24T21:52:39Z","timestamp":1784929959180,"version":"3.55.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2005,7]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/1073204.1073301","type":"journal-article","created":{"date-parts":[[2005,11,7]],"date-time":"2005-11-07T16:00:45Z","timestamp":1131379245000},"page":"991-999","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":95,"title":["Interactive collision detection between deformable models using chromatic decomposition"],"prefix":"10.1145","volume":"24","author":[{"given":"Naga K.","family":"Govindaraju","sequence":"first","affiliation":[{"name":"University of North Carolina at Chapel Hill"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Knott","sequence":"additional","affiliation":[{"name":"University of North Carolina at Chapel Hill"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nitin","family":"Jain","sequence":"additional","affiliation":[{"name":"University of North Carolina at Chapel Hill"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ilknur","family":"Kabul","sequence":"additional","affiliation":[{"name":"University of North Carolina at Chapel Hill"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rasmus","family":"Tamstorf","sequence":"additional","affiliation":[{"name":"Walt Disney Feature Animation"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Russell","family":"Gayle","sequence":"additional","affiliation":[{"name":"University of North Carolina at Chapel Hill"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ming C.","family":"Lin","sequence":"additional","affiliation":[{"name":"University of North Carolina at Chapel Hill"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dinesh","family":"Manocha","sequence":"additional","affiliation":[{"name":"University of North Carolina at Chapel Hill"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2005,7]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/585740.585762"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/280814.280821"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1201775.882357"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/192161.192259"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/359094.359101"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/566570.566623"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/199404.199437"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-8659.t01-1-00592"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/280814.280826"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0054-2"},{"key":"e_1_2_2_12_1","first-page":"203","article-title":"Interactive animation of cloth including self collision detection","volume":"11","author":"Fuhrmann A.","year":"2003","unstructured":"Fuhrmann , A. , Gross . C. , and Luckas , V. 2003 . Interactive animation of cloth including self collision detection . Journal of WSCG 11 , 1, 203 -- 208 . Fuhrmann, A., Gross. C., and Luckas, V. 2003. Interactive animation of cloth including self collision detection. Journal of WSCG 11, 1, 203--208.","journal-title":"Journal of WSCG"},{"key":"e_1_2_2_13_1","doi-asserted-by":"crossref","unstructured":"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.  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.","DOI":"10.15607\/RSS.2005.I.030"},{"key":"e_1_2_2_14_1","volume-title":"Proc. of ACM SIGGRAPH\/Eurographics Workshop on Graphics Hardware, 25--32","author":"Govindaraju N.","unstructured":"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 . 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."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1077534.1077538"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/VR.2005.62"},{"key":"e_1_2_2_17_1","volume-title":"Proc. of Vision, Modeling and Visualization, 461--468","author":"Heidelberger B.","unstructured":"Heidelberger , B. , Teschner , M. , and Gross , M . 2003. Real-time volumetric intersections of deforming objects . Proc. of Vision, Modeling and Visualization, 461--468 . Heidelberger, B., Teschner, M., and Gross, M. 2003. Real-time volumetric intersections of deforming objects. Proc. of Vision, Modeling and Visualization, 461--468."},{"key":"e_1_2_2_18_1","first-page":"145","article-title":"Detection of collisions and self-collisions using image-space techniques","volume":"12","author":"Heidelberger B.","year":"2004","unstructured":"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 . 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.","journal-title":"Journal of WSCG"},{"key":"e_1_2_2_19_1","unstructured":"Huh S. Metaxas D. and Badler N. 2001. Collision resolutions in cloth simulation. Computer Animation IEEE 604--611.  Huh S. Metaxas D. and Badler N. 2001. Collision resolutions in cloth simulation. Computer Animation IEEE 604--611."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015706.1015735"},{"key":"e_1_2_2_21_1","doi-asserted-by":"crossref","unstructured":"Jensen T. and Toft B. 1995. Graph Coloring Problems. Wiley InterScience.  Jensen T. and Toft B. 1995. Graph Coloring Problems. Wiley InterScience.","DOI":"10.1002\/9781118032497"},{"key":"e_1_2_2_22_1","unstructured":"Kang Y. and Cho H. 2002. Bilayered approximate integration for rapid and plausible animation of virtual cloth with realistic wrinkles. Computer Animation 604--611.  Kang Y. and Cho H. 2002. Bilayered approximate integration for rapid and plausible animation of virtual cloth with realistic wrinkles. Computer Animation 604--611."},{"key":"e_1_2_2_23_1","volume-title":"Proceedings VMV.","author":"Kimmerle S.","unstructured":"Kimmerle , S. , Nesme , M. , and Faure , F . 2004. Hierarchy accelerated stochastic collision detection . In Proceedings VMV. Kimmerle, S., Nesme, M., and Faure, F. 2004. Hierarchy accelerated stochastic collision detection. In Proceedings VMV."},{"key":"e_1_2_2_24_1","volume-title":"Proc. of Graphics Interface, 73--80","author":"Knott D.","unstructured":"Knott , D. , and Pai , D. K . 2003. CInDeR: Collision and interference detection in real-time using graphics hardware . Proc. of Graphics Interface, 73--80 . Knott, D., and Pai, D. K. 2003. CInDeR: Collision and interference detection in real-time using graphics hardware. Proc. of Graphics Interface, 73--80."},{"key":"e_1_2_2_25_1","unstructured":"Larsson T. and Akenine-M\u00f6ller T. 2001. Collision detection for continuously deforming bodies. In Eurographics 325--333.  Larsson T. and Akenine-M\u00f6ller T. 2001. Collision detection for continuously deforming bodies. In Eurographics 325--333."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-002-0190-y"},{"key":"e_1_2_2_27_1","unstructured":"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.  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."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1002\/vis.244"},{"key":"e_1_2_2_29_1","first-page":"322","article-title":"Hierarchical techniques in cloth detection for cloth animation","volume":"11","author":"Mezger J.","year":"2003","unstructured":"Mezger , J. , Kimmerle , S. , and Etzmu\u00df , O. 2003 . Hierarchical techniques in cloth detection for cloth animation . Journal of WSCG 11 , 1, 322 -- 329 . Mezger, J., Kimmerle, S., and Etzmu\u00df, O. 2003. Hierarchical techniques in cloth detection for cloth animation. Journal of WSCG 11, 1, 322--329.","journal-title":"Journal of WSCG"},{"key":"e_1_2_2_30_1","doi-asserted-by":"crossref","unstructured":"Provot X. 1997. Collision and self-collision handling in cloth model dedicated to design garment. Graphics Interface 177--189.  Provot X. 1997. Collision and self-collision handling in cloth model dedicated to design garment. Graphics Interface 177--189.","DOI":"10.1007\/978-3-7091-6874-5_13"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/133994.134092"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s003730050017"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2005.00829.x"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1080\/10867651.1997.10487480"},{"key":"e_1_2_2_35_1","doi-asserted-by":"crossref","unstructured":"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.  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.","DOI":"10.1111\/1467-8659.00518"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-8659.1330155"},{"key":"e_1_2_2_37_1","doi-asserted-by":"crossref","unstructured":"Volino P. and Thalmann N. M. 2000. Accurate collision response on polygon meshes. Computer Animation 154.   Volino P. and Thalmann N. M. 2000. Accurate collision response on polygon meshes. Computer Animation 154.","DOI":"10.1007\/978-3-642-57278-4_4"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1073204.1073301","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,4]],"date-time":"2023-09-04T13:55:36Z","timestamp":1693835736000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1073204.1073301"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,7]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2005,7]]}},"alternative-id":["10.1145\/1073204.1073301"],"URL":"https:\/\/doi.org\/10.1145\/1073204.1073301","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,7]]},"assertion":[{"value":"2005-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}