{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T19:27:12Z","timestamp":1783106832836,"version":"3.54.6"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2021,9,24]],"date-time":"2021-09-24T00:00:00Z","timestamp":1632441600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF CAREER","award":["1652515"],"award-info":[{"award-number":["1652515"]}]},{"name":"NSF","award":["OAC-1835712, OIA-1937043, CHS-1908767, and CHS-1901091"],"award-info":[{"award-number":["OAC-1835712, OIA-1937043, CHS-1908767, and CHS-1901091"]}]},{"name":"National Key Research and Development Program of China","award":["2020YFA0713700"],"award-info":[{"award-number":["2020YFA0713700"]}]},{"name":"EU ERC Advanced","award":["694515"],"award-info":[{"award-number":["694515"]}]},{"name":"Sloan Fellowship"},{"name":"Adobe Research"},{"name":"nTopology"},{"DOI":"10.13039\/100004311","name":"Advanced Micro Devices, Inc.","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100004311","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2021,10,31]]},"abstract":"<jats:p>\n            We introduce a large-scale benchmark for\n            <jats:bold>continuous collision detection (CCD)<\/jats:bold>\n            algorithms, composed of queries manually constructed to highlight challenging degenerate cases and automatically generated using existing simulators to cover common cases. We use the benchmark to evaluate the accuracy, correctness, and efficiency of state-of-the-art continuous collision detection algorithms, both with and without minimal separation.\n          <\/jats:p>\n          <jats:p>We discover that, despite the widespread use of CCD algorithms, existing algorithms are (1) correct but impractically slow; (2) efficient but incorrect, introducing false negatives that will lead to interpenetration; or (3) correct but over conservative, reporting a large number of false positives that might lead to inaccuracies when integrated in a simulator.<\/jats:p>\n          <jats:p>By combining the seminal interval root finding algorithm introduced by Snyder in 1992 with modern predicate design techniques, we propose a simple and efficient CCD algorithm. This algorithm is competitive with state-of-the-art methods in terms of runtime while conservatively reporting the time of impact and allowing explicit tradeoff between runtime efficiency and number of false positives reported.<\/jats:p>","DOI":"10.1145\/3460775","type":"journal-article","created":{"date-parts":[[2021,9,24]],"date-time":"2021-09-24T16:04:21Z","timestamp":1632499461000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":45,"title":["A Large-scale Benchmark and an Inclusion-based Algorithm\u00a0for Continuous Collision Detection"],"prefix":"10.1145","volume":"40","author":[{"given":"Bolun","family":"Wang","sequence":"first","affiliation":[{"name":"Beihang University and New York University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zachary","family":"Ferguson","sequence":"additional","affiliation":[{"name":"New York University, New York, NY"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Teseo","family":"Schneider","sequence":"additional","affiliation":[{"name":"New York University and University of Victoria, Victoria BC, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xin","family":"Jiang","sequence":"additional","affiliation":[{"name":"Beihang University and Peng Cheng Laboratory in Shenzhen, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marco","family":"Attene","sequence":"additional","affiliation":[{"name":"IMATI - CNR, Genova, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniele","family":"Panozzo","sequence":"additional","affiliation":[{"name":"New York University, New York, NY"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,9,24]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2020.102856"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185592"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.1986.4767773"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1342250.1342260"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3096239"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073301"},{"key":"e_1_2_1_7_1","volume-title":"GNU MP: The GNU Multiple Precision Arithmetic Library (5.0.5 ed.).","author":"Granlund Torbj\u00f6rn","year":"2012","unstructured":"Torbj\u00f6rn Granlund and the GMP Development Team . 2012 . GNU MP: The GNU Multiple Precision Arithmetic Library (5.0.5 ed.). Retrieved from http:\/\/gmplib.org\/. Torbj\u00f6rn Granlund and the GMP Development Team. 2012. GNU MP: The GNU Multiple Precision Arithmetic Library (5.0.5 ed.). Retrieved from http:\/\/gmplib.org\/."},{"key":"e_1_2_1_8_1","volume-title":"et\u00a0al","author":"Guennebaud Ga\u00ebl","year":"2010","unstructured":"Ga\u00ebl Guennebaud , Beno\u00eet Jacob , et\u00a0al . 2010 . Eigen v3. Retrieved from http:\/\/eigen.tuxfamily.org. Ga\u00ebl Guennebaud, Beno\u00eet Jacob, et\u00a0al. 2010. Eigen v3. Retrieved from http:\/\/eigen.tuxfamily.org."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2070781.2024171"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1360612.1360622"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/2945.466717"},{"key":"e_1_2_1_12_1","volume-title":"Optimized continuous collision detection for deformable triangle meshes. J. WSCG 15 (Jul","author":"Hutter Marco","year":"2007","unstructured":"Marco Hutter and Arnulph Fuhrmann . 2007. Optimized continuous collision detection for deformable triangle meshes. J. WSCG 15 (Jul . 2007 ), 25\u201332. Marco Hutter and Arnulph Fuhrmann. 2007. Optimized continuous collision detection for deformable triangle meshes. J. WSCG 15 (Jul. 2007), 25\u201332."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/781606.781612"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392425"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3295500.3356203"},{"key":"e_1_2_1_16_1","first-page":"322","article-title":"Hierarchical techniques in collision detection for cloth animation.J","volume":"11","author":"Mezger Johannes","year":"2003","unstructured":"Johannes Mezger , Stefan Kimmerle , and Olaf Etzmuss . 2003 . Hierarchical techniques in collision detection for cloth animation.J . WSCG 11 (2003), 322 \u2013 329 . Johannes Mezger, Stefan Kimmerle, and Olaf Etzmuss. 2003. Hierarchical techniques in collision detection for cloth animation.J. WSCG 11 (2003), 322\u2013329.","journal-title":"WSCG"},{"key":"e_1_2_1_18_1","volume-title":"Fast and scalable CPU\/GPU collision detection for rigid and deformable surfaces. Comput. Graph. Forum 29 (Jul","author":"Pabst Simon","year":"2010","unstructured":"Simon Pabst , Artur Koch , and Wolfgang Stra\u00dfer . 2010. Fast and scalable CPU\/GPU collision detection for rigid and deformable surfaces. Comput. Graph. Forum 29 (Jul . 2010 ), 1605\u20131612. Simon Pabst, Artur Koch, and Wolfgang Stra\u00dfer. 2010. Fast and scalable CPU\/GPU collision detection for rigid and deformable surfaces. Comput. Graph. Forum 29 (Jul. 2010), 1605\u20131612."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364912453186"},{"key":"e_1_2_1_20_1","volume-title":"Computer Animation and Simulation","author":"Provot Xavier","unstructured":"Xavier Provot . 1997. Collision and self-collision handling in cloth model dedicated to design garments . In Computer Animation and Simulation . Springer , 177\u2013189. Xavier Provot. 1997. Collision and self-collision handling in cloth model dedicated to design garments. In Computer Animation and Simulation. Springer, 177\u2013189."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-8659.t01-1-00587"},{"key":"e_1_2_1_22_1","volume-title":"The Boost C++ Libraries","author":"Schling Boris","unstructured":"Boris Schling . 2011. The Boost C++ Libraries . XML Press . Boris Schling. 2011. The Boost C++ Libraries. XML Press."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1778765.1778817"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/133994.134024"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH'93)","author":"Snyder John M.","unstructured":"John M. Snyder , Adam R. Woodbury , Kurt Fleischer , Bena Currin , and Alan H. Barr . 1993. Interval methods for multi-point collisions between time-dependent curved surfaces . In Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH'93) . Association for Computing Machinery, New York, NY, 321\u2013334. John M. Snyder, Adam R. Woodbury, Kurt Fleischer, Bena Currin, and Alan H. Barr. 1993. Interval methods for multi-point collisions between time-dependent curved surfaces. In Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH'93). Association for Computing Machinery, New York, NY, 321\u2013334."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/CADCG.2009.5246818"},{"key":"e_1_2_1_27_1","article-title":"ICCD: Interactive continuous collision detection between deformable models using connectivity-based culling","author":"Tang Min","year":"2009","unstructured":"Min Tang , Sean Curtis , Sung-eui Yoon, and Dinesh Manocha . 2009 a. ICCD: Interactive continuous collision detection between deformable models using connectivity-based culling . IEEE Trans. Vis. Comput. Graph. 15 ( Jul. 2009), 544\u201357. Min Tang, Sean Curtis, Sung-eui Yoon, and Dinesh Manocha. 2009a. ICCD: Interactive continuous collision detection between deformable models using connectivity-based culling. IEEE Trans. Vis. Comput. Graph. 15 (Jul. 2009), 544\u201357.","journal-title":"IEEE Trans. Vis. Comput. Graph. 15"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of International Conference on Robotics and Automation, 849\u2013854","author":"Tang Min","year":"2009","unstructured":"Min Tang , Young Kim , and Dinesh Manocha . 2009 b. CA: Controlled conservative advancement for continuous collision detection of polygonal models . In Proceedings of International Conference on Robotics and Automation, 849\u2013854 . Min Tang, Young Kim, and Dinesh Manocha. 2009b. CA: Controlled conservative advancement for continuous collision detection of polygonal models. In Proceedings of International Conference on Robotics and Automation, 849\u2013854."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1730804.1730806"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2019627.2019630"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661229.2661237"},{"key":"e_1_2_1_32_1","volume-title":"Adjacency-based culling for continuous collision detection. Vis. Comput. 24 (Jul","author":"Tang Min","year":"2008","unstructured":"Min Tang , Sung-eui Yoon, and Dinesh Manocha . 2008. Adjacency-based culling for continuous collision detection. Vis. Comput. 24 (Jul . 2008 ), 545\u2013553. Min Tang, Sung-eui Yoon, and Dinesh Manocha. 2008. Adjacency-based culling for continuous collision detection. Vis. Comput. 24 (Jul. 2008), 545\u2013553."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209887"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-8659.1330155"},{"key":"e_1_2_1_35_1","first-page":"4","article-title":"Geometric collisions for time-dependent parametric surfaces","volume":"24","author":"Herzen Brian Von","year":"1990","unstructured":"Brian Von Herzen , Alan H. Barr , and Harold R. Zatz . 1990 . Geometric collisions for time-dependent parametric surfaces . Comput. Graph. 24 , 4 (Sept. 1990), 39\u201348. Brian Von Herzen, Alan H. Barr, and Harold R. Zatz. 1990. Geometric collisions for time-dependent parametric surfaces. Comput. Graph. 24, 4 (Sept. 1990), 39\u201348.","journal-title":"Comput. Graph."},{"key":"e_1_2_1_36_1","volume-title":"Asynchronous variational contact mechanics. Comput. Methods Appl. Mech. Eng. 200 (Jul","author":"Vouga Etienne","year":"2010","unstructured":"Etienne Vouga , David Harmon , Rasmus Tamstorf , and Eitan Grinspun . 2010. Asynchronous variational contact mechanics. Comput. Methods Appl. Mech. Eng. 200 (Jul . 2010 ), 2181\u20132194. Etienne Vouga, David Harmon, Rasmus Tamstorf, and Eitan Grinspun. 2010. Asynchronous variational contact mechanics. Comput. Methods Appl. Mech. Eng. 200 (Jul. 2010), 2181\u20132194."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601114"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12767"},{"key":"e_1_2_1_39_1","unstructured":"Wolfram Research Inc.2020. Mathematica 12.0. Retrieved from http:\/\/www.wolfram.com.  Wolfram Research Inc.2020. Mathematica 12.0. Retrieved from http:\/\/www.wolfram.com."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1128923.1128954"},{"key":"e_1_2_1_41_1","volume-title":"Finite element algorithms for contact problems. Arch. Comput. Methods Eng. 2 (Dec","author":"Wriggers Peter","year":"1995","unstructured":"Peter Wriggers . 1995. Finite element algorithms for contact problems. Arch. Comput. Methods Eng. 2 (Dec . 1995 ), 1\u201349. Peter Wriggers. 1995. Finite element algorithms for contact problems. Arch. Comput. Methods Eng. 2 (Dec. 1995), 1\u201349."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276396"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185594"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3460775","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3460775","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3460775","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:28Z","timestamp":1750195468000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3460775"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,24]]},"references-count":42,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,10,31]]}},"alternative-id":["10.1145\/3460775"],"URL":"https:\/\/doi.org\/10.1145\/3460775","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,24]]},"assertion":[{"value":"2020-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}