{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:08:11Z","timestamp":1750306091707,"version":"3.41.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,7,20]],"date-time":"2017-07-20T00:00:00Z","timestamp":1500508800000},"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":[[2017,8,31]]},"abstract":"<jats:p>Iterative algorithms are frequently used to resolve simultaneous impacts between rigid bodies in physical simulations. However, these algorithms lack formal guarantees of termination, which is sometimes viewed as potentially dangerous, so failsafes are used in practical codes to prevent infinite loops. We show such steps are unnecessary. In particular, we study the broad class of such algorithms that are conservative and satisfy a minimal set of physical correctness properties, and which encompasses recent methods like Generalized Reflections as well as pairwise schemes. We fully characterize finite termination of these algorithms. The only possible failure cases can be detected, and we describe a procedure for modifying the algorithms to provably ensure termination. We also describe modifications necessary to guarantee termination in the presence of numerical error due to the use of floating-point arithmetic. Finally, we discuss the challenges dissipation introduce for finite termination, and describe how dissipation models can be incorporated while retaining the termination guarantee.<\/jats:p>","DOI":"10.1145\/3072959.3073689","type":"journal-article","created":{"date-parts":[[2017,7,21]],"date-time":"2017-07-21T12:24:07Z","timestamp":1500639847000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["All's well that ends well"],"prefix":"10.1145","volume":"36","author":[{"given":"Etienne","family":"Vouga","sequence":"first","affiliation":[{"name":"University of Texas at Austin"}]},{"given":"Breannan","family":"Smith","sequence":"additional","affiliation":[{"name":"Columbia University"}]},{"given":"Danny M.","family":"Kaufman","sequence":"additional","affiliation":[{"name":"Adobe Research"}]},{"given":"Rasmus","family":"Tamstorf","sequence":"additional","affiliation":[{"name":"Walt Disney Animation Studios"}]},{"given":"Eitan","family":"Grinspun","sequence":"additional","affiliation":[{"name":"Columbia University"}]}],"member":"320","published-online":{"date-parts":[[2017,7,20]]},"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\/74333.74356"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12272"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1088\/0305-4470\/23\/24\/016"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-0557-2"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-008-0222-0"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1115\/1.2791938"},{"key":"e_1_2_2_8_1","volume-title":"Jong Shi Pang, and Richard E. Stone","author":"Cottle Richard W.","year":"1992","unstructured":"Richard W. Cottle , Jong Shi Pang, and Richard E. Stone . 1992 . The Linear Complementarity Problem. Academic Press , New York. Richard W. Cottle, Jong Shi Pang, and Richard E. Stone. 1992. The Linear Complementarity Problem. Academic Press, New York."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.99.248001"},{"key":"e_1_2_2_10_1","unstructured":"J. d'Alembert. 1743. Trait\u00e9 de Dynamique. Paris.  J. d'Alembert. 1743. Trait\u00e9 de Dynamique. Paris."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1119\/1.12547"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.1093010"},{"key":"e_1_2_2_13_1","doi-asserted-by":"crossref","unstructured":"E. Drumwright and D. Shell. 2011. Modeling contact friction and joint friction in dynamic robotic simulation using the principle of maximum dissipation. Springer Berlin Heidelberg 249--266.  E. Drumwright and D. Shell. 2011. Modeling contact friction and joint friction in dynamic robotic simulation using the principle of maximum dissipation. Springer Berlin Heidelberg 249--266.","DOI":"10.1007\/978-3-642-17452-0_15"},{"volume-title":"Arbitrarily Large Neighborly Families of Congruent Symmetric Convex 3-Polytopes","author":"Erickson Jeff","key":"e_1_2_2_14_1","unstructured":"Jeff Erickson and Scott Kim . 2003. Arbitrarily Large Neighborly Families of Congruent Symmetric Convex 3-Polytopes . CRC Press . Jeff Erickson and Scott Kim. 2003. Arbitrarily Large Neighborly Families of Congruent Symmetric Convex 3-Polytopes. CRC Press."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1243980.1243986"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0094-114X(02)00045-9"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00707-004-0076-3"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0043-1648(91)90104-3"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1115\/1.2919206"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-8928(95)00122-0"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364912461539"},{"key":"e_1_2_2_22_1","first-page":"167","article-title":"Simple Linear Impact","volume":"4","author":"Johnson W.","year":"1976","unstructured":"W. Johnson . 1976 . Simple Linear Impact . International Journal of Mechanical Engineering Education 4 , 2 (1976), 167 -- 181 . W. Johnson. 1976. Simple Linear Impact. International Journal of Mechanical Engineering Education 4, 2 (1976), 167--181.","journal-title":"International Journal of Mechanical Engineering Education"},{"key":"e_1_2_2_23_1","volume-title":"Pai","author":"Kaufman Danny M.","year":"2005","unstructured":"Danny M. Kaufman , Timothy Edmunds , and Dinesh K . Pai . 2005 . Fast frictional dynamics for rigid bodies. ACM TOG (SIGGRAPH 05) 24, 3 (2005), 946--956. Danny M. Kaufman, Timothy Edmunds, and Dinesh K. Pai. 2005. Fast frictional dynamics for rigid bodies. ACM TOG (SIGGRAPH 05) 24, 3 (2005), 946--956."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1115\/1.4006202"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.2008.0078"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10852-010-9133-1"},{"volume-title":"A Treatise on Fluxions. T. W. and T","author":"MacLaurin Colin","key":"e_1_2_2_27_1","unstructured":"Colin MacLaurin . 1742. A Treatise on Fluxions. T. W. and T . Ruddimans , Edinburgh . Colin MacLaurin. 1742. A Treatise on Fluxions. T. W. and T. Ruddimans, Edinburgh."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.50.R28"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-7091-2632-5_9"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1115\/1.2712237"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39298-6"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-7091-6874-5_13"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185602"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144599360110"},{"volume-title":"Dynamics with Inequalities: Impacts and Hard Constraints","author":"Stewart David E","key":"e_1_2_2_35_1","unstructured":"David E Stewart . 2011. Dynamics with Inequalities: Impacts and Hard Constraints . Society for Industrial and Applied Mathematics . David E Stewart. 2011. Dynamics with Inequalities: Impacts and Hard Constraints. Society for Industrial and Applied Mathematics."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1115\/1.2788865"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.29.10.1209"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.2014.0859"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.6028\/jres.071B.001"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10035-009-0126-6"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12752"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3072959.3073689","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3072959.3073689","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:23Z","timestamp":1750217423000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3072959.3073689"}},"subtitle":["guaranteed resolution of simultaneous rigid body impact"],"short-title":[],"issued":{"date-parts":[[2017,7,20]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,8,31]]}},"alternative-id":["10.1145\/3072959.3073689"],"URL":"https:\/\/doi.org\/10.1145\/3072959.3073689","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"type":"print","value":"0730-0301"},{"type":"electronic","value":"1557-7368"}],"subject":[],"published":{"date-parts":[[2017,7,20]]},"assertion":[{"value":"2017-07-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}