{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T18:55:38Z","timestamp":1774637738489,"version":"3.50.1"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"name":"Hillbot Inc.","award":["Hillbot Embodied AI Fund"],"award-info":[{"award-number":["Hillbot Embodied AI Fund"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2025,8,1]]},"abstract":"<jats:p>In physics-based simulation of rigid or nearly rigid objects, collisions often become the primary performance bottleneck, particularly when enforcing intersection-free constraints. Previous simulation frameworks rely on primitive-level CCD algorithms. Due to the large number of colliding surface primitives to process, those methods are computationally intensive and heavily dependent on advanced parallel computing resources such as GPUs, which are often inaccessible due to competing tasks or capped threading capacity in applications like policy training for robotics. To address these limitations, we propose a sequential CCD algorithm for convex shapes undergoing constant affine motion. This approach uses the conservative advancement method to iteratively refine a lower-bound estimate of the TOI, exploiting the linearity of affine motion and the efficiency of convex shape distance computation. Our CCD algorithm integrates seamlessly into the ABD framework, achieving a 10-fold speed-up over primitive-level CCD. Its high single-threaded efficiency further enables significant throughput improvements via scene-level parallelism, making it well-suited for resource-constrained environments.<\/jats:p>","DOI":"10.1145\/3731151","type":"journal-article","created":{"date-parts":[[2025,7,27]],"date-time":"2025-07-27T04:02:22Z","timestamp":1753588942000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["C\n                    <sup>5<\/sup>\n                    D: Sequential Continuous Convex Collision Detection Using Cone Casting"],"prefix":"10.1145","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-2320-2297","authenticated-orcid":false,"given":"Xiaodi","family":"Yuan","sequence":"first","affiliation":[{"name":"University of California San Diego, La Jolla, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-5335-873X","authenticated-orcid":false,"given":"Fanbo","family":"Xiang","sequence":"additional","affiliation":[{"name":"Hillbot Inc., La Jolla, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7645-5931","authenticated-orcid":false,"given":"Yin","family":"Yang","sequence":"additional","affiliation":[{"name":"University of Utah, Salt Lake City, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1796-2682","authenticated-orcid":false,"given":"Hao","family":"Su","sequence":"additional","affiliation":[{"name":"University of California San Diego, La Jolla, USA"},{"name":"Hillbot Inc., La Jolla, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,7,27]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008292328909"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/192161.192168"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/38.376615"},{"key":"e_1_2_2_4_1","volume-title":"An introduction to physically based modeling: rigid body simulation I\u2014unconstrained rigid body dynamics. SIGGRAPH course notes 82","author":"Baraff David","year":"1997","unstructured":"David Baraff. 1997. An introduction to physically based modeling: rigid body simulation I\u2014unconstrained rigid body dynamics. SIGGRAPH course notes 82 (1997)."},{"key":"e_1_2_2_5_1","unstructured":"Klaus-J\u00fcrgen Bathe. 2006. Finite element procedures. Klaus-Jurgen Bathe."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12272"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.1986.4767773"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3528223.3530076"},{"key":"e_1_2_2_9_1","unstructured":"Erwin Coumans and Yunfei Bai. 2016\u20132021. PyBullet a Python module for physics simulation for games robotics and machine learning. http:\/\/pybullet.org."},{"key":"e_1_2_2_10_1","volume-title":"A fast and stable penalty method for rigid body simulation","author":"Drumwright Evan","year":"2007","unstructured":"Evan Drumwright. 2007. A fast and stable penalty method for rigid body simulation. IEEE transactions on visualization and computer graphics 14, 1 (2007), 231\u2013240."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1243980.1243986"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459802"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2001.973379"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/56.2083"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(99)00042-5"},{"key":"e_1_2_2_16_1","unstructured":"Runlin (Kolin) Guo Xinsong Lin Minghua Liu Jiayuan Gu and Hao Su. 2021. MPlib: a Lightweight Motion Planning Library. https:\/\/github.com\/haosulab\/MPlib"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.9746\/sicetr1965.40.122"},{"key":"e_1_2_2_18_1","unstructured":"Kemeng Huang Xinyu Lu Huancheng Lin Taku Komura and Minchen Li. 2024. Advancing GPU IPC for stiff affine-deformable simulation. arXiv:2411.06224 [cs.GR] https:\/\/arxiv.org\/abs\/2411.06224"},{"key":"e_1_2_2_19_1","unstructured":"Daniel W. Johnson. 1987. The optimization of robot motion in the presence of obstacles. Ph. D. Dissertation. USA. AAI8720285."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1186822.1073295"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3528223.3530064"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392425"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459767"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2994258.2994272"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/199404.199436"},{"key":"e_1_2_2_26_1","volume-title":"Impulse-based Dynamic Simulation of Rigid Body Systems. Ph. D. Dissertation","author":"Mirtich Brian Vincent","unstructured":"Brian Vincent Mirtich. 1996. Impulse-based Dynamic Simulation of Rigid Body Systems. Ph. D. Dissertation. University of California Berkeley. https:\/\/people.eecs.berkeley.edu\/~jfc\/mirtich\/thesis\/mirtichThesis.pdf"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3083724"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jvcir.2007.01.005"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-7091-6874-5_13"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2000.845313"},{"key":"e_1_2_2_31_1","series-title":"SIAM review 42, 1","volume-title":"Rigid-body dynamics with friction and impact","author":"Stewart David E","year":"2000","unstructured":"David E Stewart. 2000. Rigid-body dynamics with friction and impact. SIAM review 42, 1 (2000), 3\u201339."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2009.5152234"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661229.2661237"},{"key":"e_1_2_2_34_1","first-page":"47","article-title":"Optimized spatial hashing for collision detection of deformable objects","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 Vmv, Vol. 3. 47\u201354.","journal-title":"Vmv"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2012.6386109"},{"key":"e_1_2_2_36_1","series-title":"Series A: Mathematical, Physical and Engineering Sciences 359, 1789","volume-title":"Dynamic multi-rigid-body systems with concurrent distributed contacts. Philosophical Transactions of the Royal Society of London","author":"Trinkle Jeffrey C","year":"2001","unstructured":"Jeffrey C Trinkle, JA Tzitzouris, and Jong-Shi Pang. 2001. Dynamic multi-rigid-body systems with concurrent distributed contacts. Philosophical Transactions of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 359, 1789 (2001), 2575\u20132593."},{"key":"e_1_2_2_37_1","volume-title":"Collison detection in interactive 3D environments","author":"van den Bergen Gino","unstructured":"Gino van den Bergen. 2004. Collison detection in interactive 3D environments. Elsevier\/Morgan Kaufman, Amsterdam; Boston."},{"key":"e_1_2_2_38_1","doi-asserted-by":"crossref","unstructured":"Gino van den Bergen and Dirk Gregorius. 2010. Game physics pearls. A.K. Peters Natick Mass. 99\u2013123 pages.","DOI":"10.1201\/b11324"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3460775"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.13356"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3528223.3530103"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2014.2312013"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3731151","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T17:56:48Z","timestamp":1774634208000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3731151"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,27]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,8,1]]}},"alternative-id":["10.1145\/3731151"],"URL":"https:\/\/doi.org\/10.1145\/3731151","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,7,27]]},"assertion":[{"value":"2025-07-27","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}