{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,14]],"date-time":"2026-01-14T00:08:26Z","timestamp":1768349306462,"version":"3.49.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2012,11,1]],"date-time":"2012-11-01T00:00:00Z","timestamp":1351728000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CAREER Award CCF-06-43268IIS-09-16129IIS-10-48948IIS-11-17257CMMI-11-29917"],"award-info":[{"award-number":["CAREER Award CCF-06-43268IIS-09-16129IIS-10-48948IIS-11-17257CMMI-11-29917"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000147","name":"Division of Civil, Mechanical and Manufacturing Innovation","doi-asserted-by":"publisher","award":["CAREER Award CCF-06-43268IIS-09-16129IIS-10-48948IIS-11-17257CMMI-11-29917"],"award-info":[{"award-number":["CAREER Award CCF-06-43268IIS-09-16129IIS-10-48948IIS-11-17257CMMI-11-29917"]}],"id":[{"id":"10.13039\/100000147","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["CAREER Award CCF-06-43268IIS-09-16129IIS-10-48948IIS-11-17257CMMI-11-29917"],"award-info":[{"award-number":["CAREER Award CCF-06-43268IIS-09-16129IIS-10-48948IIS-11-17257CMMI-11-29917"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2012,11]]},"abstract":"<jats:p>We extend the Asynchronous Contact Mechanics algorithm [Harmon et al. 2009] and improve its performance by two orders of magnitude, using only optimizations that do not compromise ACM's three guarantees of safety, progress, and correctness. The key to this speedup is replacing ACM's timid, forward-looking mechanism for detecting collisions---locating and rescheduling separating plane kinetic data structures---with an optimistic speculative method inspired by Mirtich's rigid body Time Warp algorithm [2000]. Time warp allows us to perform collision detection over a window of time containing many of ACM's asynchronous trajectory changes; in this way we cull away large intervals as being collision free. Moreover, by replacing force processing intermingled with KDS rescheduling by windows of pure processing followed by collision detection, we transform an algorithm that is very difficult to parallelize into one that is embarrassingly parallel.<\/jats:p>","DOI":"10.1145\/2366145.2366170","type":"journal-article","created":{"date-parts":[[2012,11,14]],"date-time":"2012-11-14T20:36:17Z","timestamp":1352925377000},"page":"1-8","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":37,"title":["Speculative parallel asynchronous contact mechanics"],"prefix":"10.1145","volume":"31","author":[{"given":"Samantha","family":"Ainsley","sequence":"first","affiliation":[{"name":"Columbia University"}]},{"given":"Etienne","family":"Vouga","sequence":"additional","affiliation":[{"name":"Columbia University"}]},{"given":"Eitan","family":"Grinspun","sequence":"additional","affiliation":[{"name":"Columbia University"}]},{"given":"Rasmus","family":"Tamstorf","sequence":"additional","affiliation":[{"name":"Walt Disney Animation Studios"}]}],"member":"320","published-online":{"date-parts":[[2012,11]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Proceedings of VRIPhys.","author":"Bender J.","unstructured":"Bender , J. , and Bayer , D . 2008. Parallel simulation of inextensible cloth . In Proceedings of VRIPhys. Bender, J., and Bayer, D. 2008. Parallel simulation of inextensible cloth. In Proceedings of VRIPhys."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1941487.1941507"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/566654.566623"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185592"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/800195.805928"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/383259.383262"},{"key":"e_1_2_2_8_1","volume-title":"Proceedings of the 3rd Workshop on Algorithmic Foundations of Robotics (WAFR), 191--209","author":"Guibas L.","year":"1998","unstructured":"Guibas , L. 1998 . Kinetic data structures: a state of the art report . In Proceedings of the 3rd Workshop on Algorithmic Foundations of Robotics (WAFR), 191--209 . Guibas, L. 1998. Kinetic data structures: a state of the art report. In Proceedings of the 3rd Workshop on Algorithmic Foundations of Robotics (WAFR), 191--209."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1531326.1531393"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2133806.2133828"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2019406.2019439"},{"key":"e_1_2_2_12_1","unstructured":"Harmon D. 2010. Robust Efficient and Accurate Contact Algorithms. PhD thesis Columbia University.   Harmon D. 2010. Robust Efficient and Accurate Contact Algorithms . PhD thesis Columbia University."},{"key":"e_1_2_2_13_1","volume-title":"Proceedings of the 2007 summer computer simulation conference, 691--697","author":"Huang J.-C.","unstructured":"Huang , J.-C. , Jiao , X. , Fujimoto , R. M. , and Zha , H . 2007. DAG-guided parallel asynchronous variational integrators with super-elements . In Proceedings of the 2007 summer computer simulation conference, 691--697 . Huang, J.-C., Jiao, X., Fujimoto, R. M., and Zha, H. 2007. DAG-guided parallel asynchronous variational integrators with super-elements. In Proceedings of the 2007 summer computer simulation conference, 691--697."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3916.3988"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/nme.1880"},{"key":"e_1_2_2_16_1","first-page":"7","article-title":"HPCCD: Hybrid parallel continuous collision detection using cpus and gpus","volume":"28","author":"Kim D.","year":"2009","unstructured":"Kim , D. , Heo , J.-P. , Huh , J. , Kim , J. , and Yoon , S.-E. 2009 . HPCCD: Hybrid parallel continuous collision detection using cpus and gpus . Computer Graphics Forum (Pacific Graphics) 28 , 7 . Kim, D., Heo, J.-P., Huh, J., Kim, J., and Yoon, S.-E. 2009. HPCCD: Hybrid parallel continuous collision detection using cpus and gpus. Computer Graphics Forum (Pacific Graphics) 28, 7.","journal-title":"Computer Graphics Forum (Pacific Graphics)"},{"key":"e_1_2_2_17_1","volume-title":"Proceedings of WSCG","volume":"3","author":"Kone\u010dn\u00fd P.","year":"1997","unstructured":"Kone\u010dn\u00fd , P. , and Zikan , K . 1997. Lower bound of distance in 3D . In Proceedings of WSCG 1997 , vol. 3 , 640--649. Kone\u010dn\u00fd, P., and Zikan, K. 1997. Lower bound of distance in 3D. In Proceedings of WSCG 1997, vol. 3, 640--649."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00205-002-0212-y"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/344779.344866"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2010.01769.x"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993498.1993501"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2008.79"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/CADCG.2009.5246818"},{"key":"e_1_2_2_24_1","unstructured":"Sutter H. and Alexandrescu A. 2004. C++ Coding Standards: 101 Rules Guidelines and Best Practices. Pearson Education Inc.   Sutter H. and Alexandrescu A. 2004. C++ Coding Standards: 101 Rules Guidelines and Best Practices . Pearson Education Inc."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.gmod.2010.01.001"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1944745.1944756"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/2386124.2386130"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2007.11.003"},{"key":"e_1_2_2_29_1","unstructured":"Thomaszewski B. Pabst S. and Strasser W. 2008. Asynchronous cloth simulation. Computer Graphics International.  Thomaszewski B. Pabst S. and Strasser W. 2008. Asynchronous cloth simulation. Computer Graphics International ."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cma.2011.03.010"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073278"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964933"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2366145.2366170","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2366145.2366170","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:34:44Z","timestamp":1750239284000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2366145.2366170"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,11]]},"references-count":31,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2012,11]]}},"alternative-id":["10.1145\/2366145.2366170"],"URL":"https:\/\/doi.org\/10.1145\/2366145.2366170","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,11]]},"assertion":[{"value":"2012-11-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}