{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T19:27:19Z","timestamp":1783106839171,"version":"3.54.6"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2024,11,19]],"date-time":"2024-11-19T00:00:00Z","timestamp":1731974400000},"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":[[2024,12,19]]},"abstract":"<jats:p>Continuous collision detection (CCD) between parametric surfaces is typically formulated as a five-dimensional constrained optimization problem. In the field of CAD and computer graphics, common approaches to solving this problem rely on linearization or sampling strategies. Alternatively, inclusion-based techniques detect collisions by employing 5D inclusion functions, which are typically designed to represent the swept volumes of parametric surfaces over a given time span, and narrowing down the earliest collision moment through subdivision in both spatial and temporal dimensions. However, when high detection accuracy is required, all these approaches significantly increases computational consumption due to the high-dimensional searching space. In this work, we develop a new time-dependent inclusion-based CCD framework that eliminates the need for temporal subdivision and can speedup conventional methods by a factor ranging from 36 to 138. To achieve this, we propose a novel time-dependent inclusion function that provides a continuous representation of a moving surface, along with a corresponding intersection detection algorithm that quickly identifies the time intervals when collisions are likely to occur. We validate our method across various primitive types, demonstrate its efficacy within the simulation pipeline and show that it significantly improves CCD efficiency while maintaining accuracy.<\/jats:p>","DOI":"10.1145\/3687960","type":"journal-article","created":{"date-parts":[[2024,11,19]],"date-time":"2024-11-19T15:46:04Z","timestamp":1732031164000},"page":"1-11","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["A Time-Dependent Inclusion-Based Method for Continuous Collision Detection between Parametric Surfaces"],"prefix":"10.1145","volume":"43","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9798-4151","authenticated-orcid":false,"given":"Xuwen","family":"Chen","sequence":"first","affiliation":[{"name":"Peking University, Beijing, China"},{"name":"State Key Laboratory of General Artificial Intelligence, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-8639-6850","authenticated-orcid":false,"given":"Cheng","family":"Yu","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, China"},{"name":"State Key Laboratory of General Artificial Intelligence, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1127-2848","authenticated-orcid":false,"given":"Xingyu","family":"Ni","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, China"},{"name":"State Key Laboratory of General Artificial Intelligence, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7358-433X","authenticated-orcid":false,"given":"Mengyu","family":"Chu","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, China"},{"name":"State Key Laboratory of General Artificial Intelligence, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9496-772X","authenticated-orcid":false,"given":"Bin","family":"Wang","sequence":"additional","affiliation":[{"name":"Beijing Institute for General Artificial Intelligence, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4702-036X","authenticated-orcid":false,"given":"Baoquan","family":"Chen","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, China"},{"name":"State Key Laboratory of General Artificial Intelligence, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,11,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/566654.566623"},{"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","unstructured":"Christoph Buchenau and Michael Guthe. 2021. Real-Time Curvature-aware Re-Parametrization and Tessellation of B\u00e9zier Surfaces. In Vision Modeling and Visualization Bjoern Andres Marcel Campen and Michael Sedlmair (Eds.). The Eurographics Association. 10.2312\/vmv.20211370","DOI":"10.2312\/vmv.20211370"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1080\/17797179.2017.1354575"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/9780470749081"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3658191"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1090122.1090144"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588432.3591488"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459802"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"A. Galligo and J. P. Pavone. 2006. A sampling algorithm computing self-intersections of parametric surfaces. In Algebraic Geometry and Geometric Modeling Mohamed Elkadi Bernard Mourrain and Ragni Piene (Eds.). Springer Berlin Heidelberg Berlin Heidelberg 185--204.","DOI":"10.1007\/978-3-540-33275-6_12"},{"key":"e_1_2_1_11_1","unstructured":"Stefan Gottschalk. 1996. Separating axis theorem."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1399504.1360622"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings Computer Animation '96","author":"Hughes M.","unstructured":"M. Hughes, C. DiMattia, M.C. Lin, and D. Manocha. 1996. Efficient and accurate interference detection for polynomial deformation. In Proceedings Computer Animation '96. 155--166."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cma.2004.10.008"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/566282.566289"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459767"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cma.2010.10.001"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cma.2013.09.016"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3478513.3480551"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2024.103734"},{"key":"e_1_2_1_21_1","volume-title":"The NURBS book","author":"Piegl Les","unstructured":"Les Piegl and Wayne Tiller. 1995. The NURBS book. Springer-Verlag, Berlin, Heidelberg."},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Xavier Provot. 1997. Collision and self-collision handling in cloth model dedicated to design garments. In Computer Animation and Simulation. https:\/\/api.semanticscholar.org\/CorpusID:7421415","DOI":"10.1007\/978-3-7091-6874-5_13"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-8659.t01-1-00587"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/133994.134024"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/166117.166158"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2485895.2485914"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661229.2661237"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2005.00829.x"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/97879.97883"},{"key":"e_1_2_1_30_1","volume-title":"Fast and Exact Root Parity for Continuous Collision Detection. Computer Graphics Forum (Proceedings of Eurographics) 41, 2","author":"Wang Bolun","year":"2022","unstructured":"Bolun Wang, Zachary Ferguson, Xin Jiang, Marco Attene, Daniele Panozzo, and Teseo Schneider. 2022. Fast and Exact Root Parity for Continuous Collision Detection. Computer Graphics Forum (Proceedings of Eurographics) 41, 2 (2022), 9 pages."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3460775"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601114"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12767"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3592419"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1201\/9781420035315.CH41"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588432.3591507"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijmecsci.2023.108253"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3687960","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3687960","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:09:58Z","timestamp":1750295398000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3687960"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,19]]},"references-count":37,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,12,19]]}},"alternative-id":["10.1145\/3687960"],"URL":"https:\/\/doi.org\/10.1145\/3687960","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,19]]},"assertion":[{"value":"2024-11-19","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}