{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T07:34:07Z","timestamp":1778657647386,"version":"3.51.4"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2006,7,1]],"date-time":"2006-07-01T00:00:00Z","timestamp":1151712000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2006,7]]},"abstract":"<jats:p>\n            We present novel algorithms to perform collision and distance queries among multiple deformable models in dynamic environments. These include inter-object queries between different objects as well as intra-object queries. We describe a unified approach to compute these queries based on N-body distance computation and use properties of the 2\n            <jats:sup>nd<\/jats:sup>\n            order discrete Voronoi diagram to perform N-body culling. Our algorithms involve no preprocessing and also work well on models with changing topologies. We can perform all proximity queries among complex deformable models consisting of thousands of triangles in a fraction of a second on a high-end PC. Moreover, our Voronoi-based culling algorithm can improve the performance of separation distance and penetration queries by an order of magnitude.\n          <\/jats:p>","DOI":"10.1145\/1141911.1142006","type":"journal-article","created":{"date-parts":[[2006,7,25]],"date-time":"2006-07-25T14:14:26Z","timestamp":1153836866000},"page":"1144-1153","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":46,"title":["Fast proximity computation among deformable models using discrete Voronoi diagrams"],"prefix":"10.1145","volume":"25","author":[{"given":"Avneesh","family":"Sud","sequence":"first","affiliation":[{"name":"University of North Carolina at Chapel Hill"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Naga","family":"Govindaraju","sequence":"additional","affiliation":[{"name":"University of North Carolina at Chapel Hill"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Russell","family":"Gayle","sequence":"additional","affiliation":[{"name":"University of North Carolina at Chapel Hill"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ilknur","family":"Kabul","sequence":"additional","affiliation":[{"name":"University of North Carolina at Chapel Hill"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dinesh","family":"Manocha","sequence":"additional","affiliation":[{"name":"University of North Carolina at Chapel Hill"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,7]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.03.008"},{"key":"e_1_2_2_2_1","unstructured":"Baraff D. and Witkin A. 2001. Physically Based Modeling. ACM SIGGRAPH Course Notes.  Baraff D. and Witkin A. 2001. Physically Based Modeling. ACM SIGGRAPH Course Notes."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1201775.882357"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/566570.566623"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/199404.199437"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01190153"},{"key":"e_1_2_2_7_1","doi-asserted-by":"crossref","unstructured":"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.  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.","DOI":"10.1111\/1467-8659.00543"},{"key":"e_1_2_2_8_1","doi-asserted-by":"crossref","unstructured":"Ericson C. 2004. Real-Time Collision Detection. Morgan Kaufmann.   Ericson C. 2004. Real-Time Collision Detection. Morgan Kaufmann.","DOI":"10.1201\/b14581"},{"key":"e_1_2_2_9_1","unstructured":"Fischer I. and Gotsman C. 2005. Fast approximation of high order Voronoi diagrams and distance transforms on the GPU. Technical report CS TR-07-05 Harvard University.  Fischer I. and Gotsman C. 2005. Fast approximation of high order Voronoi diagrams and distance transforms on the GPU. Technical report CS TR-07-05 Harvard University."},{"key":"e_1_2_2_10_1","volume-title":"Proc. of EG Workshop on Computer Animation and Simulation, 99--111","author":"Fisher S.","unstructured":"Fisher , S. , and Lin , M. C . 2001. Deformed distance fields for simulation of non-penetrating flexible bodies . Proc. of EG Workshop on Computer Animation and Simulation, 99--111 . Fisher, S., and Lin, M. C. 2001. Deformed distance fields for simulation of non-penetrating flexible bodies. Proc. of EG Workshop on Computer Animation and Simulation, 99--111."},{"key":"e_1_2_2_11_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_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073301"},{"key":"e_1_2_2_13_1","volume-title":"Proc. of Vision, Modeling and Visualization, 315--322","author":"Heidelberger B.","unstructured":"Heidelberger , B. , Teschner , M. , Keisner , R. , Mueller , M. , and Gross , M . 2004. Consistent penetration depth estimation for deformable collision response . Proc. of Vision, Modeling and Visualization, 315--322 . Heidelberger, B., Teschner, M., Keisner, R., Mueller, M., and Gross, M. 2004. Consistent penetration depth estimation for deformable collision response. Proc. of Vision, Modeling and Visualization, 315--322."},{"key":"e_1_2_2_14_1","volume-title":"Tech. Rep. TR02-004, Department of Computer Science","author":"Hoff K.","year":"2002","unstructured":"Hoff , K. , Zaferakis , A. , Lin , M. , and Manocha , D . 2002 . Fast 3d geometric proximity queries between rigid and deformable models using graphics hardware acceleration. Tech. Rep. TR02-004, Department of Computer Science , University of North Carolina . Hoff, K., Zaferakis, A., Lin, M., and Manocha, D. 2002. Fast 3d geometric proximity queries between rigid and deformable models using graphics hardware acceleration. Tech. Rep. TR02-004, Department of Computer Science, University of North Carolina."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1186562.1015735"},{"key":"e_1_2_2_16_1","doi-asserted-by":"crossref","unstructured":"Johnson D. E. and Cohen E. 2004. Unified distance queries in a heterogeneous model environment. In ASME DETC.  Johnson D. E. and Cohen E. 2004. Unified distance queries in a heterogeneous model environment. In ASME DETC.","DOI":"10.1115\/DETC2004-57461"},{"key":"e_1_2_2_17_1","doi-asserted-by":"crossref","unstructured":"Kawachi K. and Suzuki H. 2000. Distance computation between non-convex polyhedra at short range based on discrete Voronoi diagrams. IEEE Geometric Modeling and Processing 123--128.   Kawachi K. and Suzuki H. 2000. Distance computation between non-convex polyhedra at short range based on discrete Voronoi diagrams. IEEE Geometric Modeling and Processing 123--128.","DOI":"10.1109\/GMAP.2000.838244"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/545261.545266"},{"key":"e_1_2_2_19_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_20_1","volume-title":"Proc. of IEEE Int. Conference on Robotics and Automation, 3719--3726","author":"Larsen E.","unstructured":"Larsen , E. , Gottschalk , S. , Lin , M. , and Manocha , D . 2000. Distance queries with rectangular swept sphere volumes . Proc. of IEEE Int. Conference on Robotics and Automation, 3719--3726 . Larsen, E., Gottschalk, S., Lin, M., and Manocha, D. 2000. Distance queries with rectangular swept sphere volumes. Proc. of IEEE Int. Conference on Robotics and Automation, 3719--3726."},{"key":"e_1_2_2_21_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_22_1","volume-title":"IEEE Conference on Robotics and Automation, 1008--1014","author":"Lin M.","unstructured":"Lin , M. , and Canny , J. F . 1991. Efficient algorithms for incremental distance computation . In IEEE Conference on Robotics and Automation, 1008--1014 . Lin, M., and Canny, J. F. 1991. Efficient algorithms for incremental distance computation. In IEEE Conference on Robotics and Automation, 1008--1014."},{"key":"e_1_2_2_23_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_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/285857.285860"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1186822.1073216"},{"key":"e_1_2_2_26_1","volume-title":"Spatial Tessellations: Concepts and Applications of Voronoi Diagrams","author":"Okabe A.","year":"1992","unstructured":"Okabe , A. , Boots , B. , and Sugihara , K . 1992 . Spatial Tessellations: Concepts and Applications of Voronoi Diagrams . John Wiley & Sons , Chichester, UK . Okabe, A., Boots, B., and Sugihara, K. 1992. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. John Wiley & Sons, Chichester, UK."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1994.351059"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1080\/2151237X.2006.10129216"},{"key":"e_1_2_2_29_1","volume-title":"Proceedings of ACM Symposium on Solid Modeling and Applications.","author":"Redon S.","unstructured":"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. 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."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/VISUAL.2003.1250358"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2004.00787.x"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1111411.1111432"},{"key":"e_1_2_2_33_1","volume-title":"Tech. Rep. TR06-011, Dept of Computer Science","author":"Sud A.","year":"2006","unstructured":"Sud , A. , Govindaraju , N. , Gayle , R. , and Manocha , D . 2006 . Surface distance maps. Tech. Rep. TR06-011, Dept of Computer Science , University of North Carolina . Sud, A., Govindaraju, N., Gayle, R., and Manocha, D. 2006. Surface distance maps. Tech. Rep. TR06-011, Dept of Computer Science, University of North Carolina."},{"key":"e_1_2_2_34_1","volume-title":"Proc. of IEEE Int. Conference on Control, Automation, Robotics and Vision.","author":"Sundaraj K.","unstructured":"Sundaraj , K. , and Laugier , C . 2000. Fast contact localization of moving deformable polyhedra . In Proc. of IEEE Int. Conference on Control, Automation, Robotics and Vision. Sundaraj, K., and Laugier, C. 2000. Fast contact localization of moving deformable polyhedra. In Proc. of IEEE Int. Conference on Control, Automation, Robotics and Vision."},{"key":"e_1_2_2_35_1","volume-title":"Proc. of Vision, Modeling and Visualization, 47--54","author":"Teschner M.","unstructured":"Teschner , M. , Heidelberger , B. , Muller , M. , Pomeranets , D. , and Gross , M . 2003. Optimized spatial hashing for collision detection of deformable objects . Proc. of Vision, Modeling and Visualization, 47--54 . Teschner, M., Heidelberger, B., Muller, M., Pomeranets, D., and Gross, M. 2003. Optimized spatial hashing for collision detection of deformable objects. Proc. of Vision, Modeling and Visualization, 47--54."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2005.00829.x"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1080\/10867651.1997.10487480"},{"key":"e_1_2_2_38_1","volume-title":"Proc. of Computer Animation, 154","author":"Volino P.","unstructured":"Volino , P. , and Thalmann , N. M . 2000. Accurate collision response on polygon meshes . In Proc. of Computer Animation, 154 . Volino, P., and Thalmann, N. M. 2000. Accurate collision response on polygon meshes. In Proc. of Computer Animation, 154."}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1141911.1142006","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1141911.1142006","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:06:11Z","timestamp":1750259171000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1141911.1142006"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,7]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,7]]}},"alternative-id":["10.1145\/1141911.1142006"],"URL":"https:\/\/doi.org\/10.1145\/1141911.1142006","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,7]]},"assertion":[{"value":"2006-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}