{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,24]],"date-time":"2026-07-24T21:53:28Z","timestamp":1784930008943,"version":"3.55.0"},"reference-count":70,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2023,7,28]],"date-time":"2023-07-28T00:00:00Z","timestamp":1690502400000},"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":[[2023,10,31]]},"abstract":"<jats:p>Step-and-project is a popular method to simulate non-penetrating deformable bodies in physically based animation. The strategy is to first integrate the system in time without considering contacts and then resolve potential intersections, striking a good balance between plausibility and efficiency. However, existing methods can be defective and unsafe when using large time steps, taking risks of failure or demanding repetitive collision testing and resolving that severely degrade performance. In this article, we propose a novel two-way method for fast and reliable continuous collision handling. Our method launches an optimization from both ends of the intermediate time-integrated state and the previous intersection-free state. It progressively generates a piecewise linear path and eventually obtains a feasible solution for the next time step. The algorithm efficiently alternates between a forward step and a backward step until the result is conditionally converged. Thanks to a set of unified volume-based contact constraints, our method offers flexible and reliable handling of various codimensional deformable bodies, including volumetric bodies, cloth, hair, and sand. Experimental results demonstrate the safety, robustness, physical fidelity, and numerical efficiency of our method, making it particularly suitable for scenarios involving large deformations or large time steps.<\/jats:p>","DOI":"10.1145\/3604551","type":"journal-article","created":{"date-parts":[[2023,6,14]],"date-time":"2023-06-14T02:41:02Z","timestamp":1686710462000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["Fast GPU-based Two-way Continuous Collision Handling"],"prefix":"10.1145","volume":"42","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1520-5837","authenticated-orcid":false,"given":"Tianyu","family":"Wang","sequence":"first","affiliation":[{"name":"FaceUnity, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9411-1689","authenticated-orcid":false,"given":"Jiong","family":"Chen","sequence":"additional","affiliation":[{"name":"LIX, Ecole Polytechnique, IP Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-9967-1145","authenticated-orcid":false,"given":"Dongping","family":"Li","sequence":"additional","affiliation":[{"name":"FaceUnity, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-2957-3473","authenticated-orcid":false,"given":"Xiaowei","family":"Liu","sequence":"additional","affiliation":[{"name":"FaceUnity, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8153-2337","authenticated-orcid":false,"given":"Huamin","family":"Wang","sequence":"additional","affiliation":[{"name":"Style3D, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4243-6112","authenticated-orcid":false,"given":"Kun","family":"Zhou","sequence":"additional","affiliation":[{"name":"State Key Lab of CAD&amp;CG, Zhejiang University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,7,28]]},"reference":[{"key":"e_1_3_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2366145.2366170"},{"key":"e_1_3_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3532720.3535640"},{"key":"e_1_3_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/882262.882357"},{"key":"e_1_3_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1833349.1778818"},{"key":"e_1_3_2_6_1","first-page":"227","volume-title":"Proceedings of the 4th Eurographics Symposium on Geometry Processing (SGP\u201906)","author":"Bergou Miklos","year":"2006","unstructured":"Miklos Bergou, Max Wardetzky, David Harmon, Denis Zorin, and Eitan Grinspun. 2006. A quadratic bending model for inextensible surfaces. In Proceedings of the 4th Eurographics Symposium on Geometry Processing (SGP\u201906). Eurographics Association, Goslar, DEU, 227\u2013230."},{"key":"e_1_3_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1899404.1899410"},{"key":"e_1_3_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/566654.566623"},{"key":"e_1_3_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1198555.1198573"},{"key":"e_1_3_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3528223.3530076"},{"key":"e_1_3_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/566654.566624"},{"key":"e_1_3_2_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0725029"},{"key":"e_1_3_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392439"},{"key":"e_1_3_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/311535.311576"},{"key":"e_1_3_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2504435.2504443"},{"key":"e_1_3_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/PCCGA.2003.1238266"},{"key":"e_1_3_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459757"},{"key":"e_1_3_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980179.2982437"},{"key":"e_1_3_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3272127.3275044"},{"key":"e_1_3_2_20_1","first-page":"62","volume-title":"Proceedings of the ACM SIGGRAPH\/Eurographics Symposium on Computer Animation (SCA\u201903)","author":"Grinspun Eitan","year":"2003","unstructured":"Eitan Grinspun, Anil N. Hirani, Mathieu Desbrun, and Peter Schr\u00f6der. 2003. Discrete shells. In Proceedings of the ACM SIGGRAPH\/Eurographics Symposium on Computer Animation (SCA\u201903). Eurographics Association, Goslar, DEU, 62\u201367."},{"key":"e_1_3_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1531326.1531393"},{"key":"e_1_3_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1360612.1360622"},{"key":"e_1_3_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2019406.2019439"},{"key":"e_1_3_2_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0045-7825(99)00034-1"},{"key":"e_1_3_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3528223.3530069"},{"key":"e_1_3_2_26_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2009.01611.x"},{"key":"e_1_3_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3414685.3417763"},{"key":"e_1_3_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392425"},{"key":"e_1_3_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459767"},{"key":"e_1_3_2_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623498345075"},{"key":"e_1_3_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392396"},{"key":"e_1_3_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3338695"},{"key":"e_1_3_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3487983.3488289"},{"key":"e_1_3_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1964921.1964967"},{"key":"e_1_3_2_35_1","unstructured":"Stan Melax. 2017. 3x3 Matrix Diagonalization. Retrieved from http:\/\/melax.github.io\/diag.html."},{"key":"e_1_3_2_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-05105-4_2"},{"key":"e_1_3_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/344779.344866"},{"key":"e_1_3_2_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/215074.215111"},{"key":"e_1_3_2_39_1","volume-title":"Proceedings of Virtual Reality Interactions and Physical Simulations","author":"M\u00fcller Matthias","year":"2008","unstructured":"Matthias M\u00fcller. 2008. Hierarchical position based dynamics. In Proceedings of Virtual Reality Interactions and Physical Simulations. Grenoble."},{"key":"e_1_3_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766907"},{"key":"e_1_3_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2366145.2366171"},{"key":"e_1_3_2_42_1","volume-title":"Numerical Optimization","author":"Nocedal Jorge","year":"2006","unstructured":"Jorge Nocedal and Stephen J. Wright. 2006. Numerical Optimization. Springer."},{"key":"e_1_3_2_43_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2010.01769.x"},{"key":"e_1_3_2_44_1","doi-asserted-by":"publisher","DOI":"10.1080\/10586458.1993.10504266"},{"key":"e_1_3_2_45_1","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1007\/978-3-7091-6874-5_13","volume-title":"Computer Animation and Simulation","author":"Provot Xavier","year":"1997","unstructured":"Xavier Provot. 1997. Collision and self-collision handling in cloth model dedicated to design garments. In Computer Animation and Simulation. 177\u2013189."},{"key":"e_1_3_2_46_1","first-page":"147","volume-title":"Proceedings of the ACM SIGGRAPH\/Eurographics Symposium on Computer Animation (SCA\u201908)","author":"Sifakis Eftychios","year":"2008","unstructured":"Eftychios Sifakis, Sebastian Marino, and Joseph Teran. 2008. Globally coupled collision handling using volume preserving impulses. In Proceedings of the ACM SIGGRAPH\/Eurographics Symposium on Computer Animation (SCA\u201908). Eurographics Association, Goslar, DEU, 147\u2013153."},{"key":"e_1_3_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3241041"},{"key":"e_1_3_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766947"},{"key":"e_1_3_2_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/CADCG.2009.5246818"},{"key":"e_1_3_2_50_1","doi-asserted-by":"crossref","first-page":"4016","DOI":"10.1109\/ROBOT.2010.5509210","volume-title":"Proceedings of the IEEE Robotics & Automation Society Conference (ICRA\u201910)","author":"Tang Min","year":"2010","unstructured":"Min Tang, Young J. Kim, and Dinesh Manocha. 2010. Continuous collision detection for non-rigid contact computations using local advancement. In Proceedings of the IEEE Robotics & Automation Society Conference (ICRA\u201910). 4016\u20134021."},{"key":"e_1_3_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3203188"},{"key":"e_1_3_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1944745.1944756"},{"key":"e_1_3_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2019627.2019630"},{"key":"e_1_3_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661229.2661237"},{"key":"e_1_3_2_55_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12851"},{"key":"e_1_3_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3272127.3275005"},{"key":"e_1_3_2_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073368.1073394"},{"key":"e_1_3_2_58_1","first-page":"47","volume-title":"Proceedings of Vision, Modeling, Visualization","volume":"3","author":"Teschner Matthias","year":"2003","unstructured":"Matthias Teschner, Bruno Heidelberger, Matthias M\u00fcller, Danat Pomerantes, and Markus H. Gross. 2003. Optimized spatial hashing for collision detection of deformable objects. In Proceedings of Vision, Modeling, Visualization, Vol. 3. 47\u201354."},{"key":"e_1_3_2_59_1","volume-title":"Proceedings of Computer Graphics International","author":"Thomaszewski Bernhard","year":"2008","unstructured":"Bernhard Thomaszewski, Simon Pabst, and Wolfgang Stra\u00dfer. 2008. Asynchronous cloth simulation. In Proceedings of Computer Graphics International."},{"key":"e_1_3_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209887"},{"key":"e_1_3_2_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/1179352.1142007"},{"key":"e_1_3_2_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/97880.97883"},{"key":"e_1_3_2_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/3460775"},{"key":"e_1_3_2_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601114"},{"key":"e_1_3_2_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818063"},{"key":"e_1_3_2_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980179.2980236"},{"key":"e_1_3_2_67_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.13095"},{"key":"e_1_3_2_68_1","first-page":"349","volume-title":"Proceedings of the Conference on Vision, Modeling, and Visualization","author":"Wicke Martin","year":"2006","unstructured":"Martin Wicke, Hermes Lanker, and Markus Gross. 2006. Untangling cloth with boundaries. In Proceedings of the Conference on Vision, Modeling, and Visualization. 349\u2013356."},{"issue":"1","key":"e_1_3_2_69_1","first-page":"5","article-title":"A safe and fast repulsion method for GPU-based cloth self collisions","volume":"40","author":"Wu Longhua","year":"2020","unstructured":"Longhua Wu, Botao Wu, Yin Yang, and Huamin Wang. 2020. A safe and fast repulsion method for GPU-based cloth self collisions. ACM Trans. Graph. 40, 1, Article 5 (Dec. 2020), 18 pages.","journal-title":"ACM Trans. Graph."},{"key":"e_1_3_2_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/3532836.3536266"},{"key":"e_1_3_2_71_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\/3604551","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3604551","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:19Z","timestamp":1750178839000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3604551"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,28]]},"references-count":70,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,10,31]]}},"alternative-id":["10.1145\/3604551"],"URL":"https:\/\/doi.org\/10.1145\/3604551","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,28]]},"assertion":[{"value":"2022-07-23","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-05-17","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-07-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}