{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T22:49:19Z","timestamp":1776725359313,"version":"3.51.2"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,3,14]],"date-time":"2019-03-14T00:00:00Z","timestamp":1552521600000},"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":[[2019,4,30]]},"abstract":"<jats:p>Simulating (elastically) deformable models that can collide with each other and with the environment remains a challenging task. The resulting contact problems can be elegantly approached using Lagrange multipliers to represent the unknown magnitude of the response forces. Typical methods construct and solve a Linear Complementarity Problem (LCP) to obtain the response forces. This requires the inverse of the generalized mass matrix, which is generally hard to obtain for deformable-body problems. In this article, we tackle such contact problems by directly solving the Mixed Linear Complementarity Problem (MLCP) and omitting the construction of an LCP matrix. Since a convex quadratic program with linear constraints is equivalent to an MLCP, we propose to use a Conjugate Residual (CR) solver as the backbone of our collision response system. By dynamically updating the set of active constraints, the MLCP with inequality constraints can be solved efficiently. We also propose a simple yet efficient preconditioner that ensures faster convergence. Finally, our approach is faster than existing methods (at the same accuracy), and it allows accurate treatment of friction.<\/jats:p>","DOI":"10.1145\/3209887","type":"journal-article","created":{"date-parts":[[2019,3,14]],"date-time":"2019-03-14T17:11:58Z","timestamp":1552583518000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":39,"title":["Efficient and Accurate Collision Response for Elastically Deformable Models"],"prefix":"10.1145","volume":"38","author":[{"given":"Mickeal","family":"Verschoor","sequence":"first","affiliation":[{"name":"Eindhoven University of Technology and Universidad Rey Juan Carlos, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrei C.","family":"Jalba","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,3,14]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1778765.1778819"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0535-6"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/74333.74356"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/192161.192168"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/237170.237226"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/133994.134084"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/280814.280821"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1272690.1272714"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12272"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1899404.1899410"},{"key":"e_1_2_2_11_1","volume-title":"Convex Optimization","author":"Boyd Stephen","unstructured":"Stephen Boyd and Lieven Vandenberghe . 2004. Convex Optimization . Cambridge University Press . Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/566654.566623"},{"key":"e_1_2_2_13_1","volume-title":"Proc. of the 2005 Game Developer Conf.","author":"Catto Erin","year":"2005","unstructured":"Erin Catto . 2005 . Iterative dynamics with temporal coherence . In Proc. of the 2005 Game Developer Conf. Erin Catto. 2005. Iterative dynamics with temporal coherence. In Proc. of the 2005 Game Developer Conf."},{"key":"e_1_2_2_14_1","volume-title":"Stone","author":"Cottle Richard","year":"1992","unstructured":"Richard Cottle , Jong-Shi Pang , and Richard E . Stone . 1992 . The Linear Complementarity Problem. Academic Press . Richard Cottle, Jong-Shi Pang, and Richard E. Stone. 1992. The Linear Complementarity Problem. Academic Press."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2070781.2024173"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2006.13"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0720023"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1243980.1243986"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2504435.2504443"},{"key":"e_1_2_2_20_1","volume-title":"Fong and Michael Saunders","author":"David","year":"2011","unstructured":"David C. Fong and Michael Saunders . 2011 . CG Versus MINRES: An Empirical Comparison. Technical Report. Stanford University , Stanford, CA. David C. Fong and Michael Saunders. 2011. CG Versus MINRES: An Empirical Comparison. Technical Report. Stanford University, Stanford, CA."},{"key":"e_1_2_2_21_1","volume-title":"Proc. of the 2006 ACM SIGGRAPH\/Eurographics Symp. on Computer Animation (SCA\u201906)","author":"Galoppo Nico","unstructured":"Nico Galoppo , Miguel A. Otaduy , Paul Mecklenburg , Markus Gross , and Ming C. Lin . 2006. Fast simulation of deformable models in contact using dynamic deformation textures . In Proc. of the 2006 ACM SIGGRAPH\/Eurographics Symp. on Computer Animation (SCA\u201906) . 73--82. Nico Galoppo, Miguel A. Otaduy, Paul Mecklenburg, Markus Gross, and Ming C. Lin. 2006. Fast simulation of deformable models in contact using dynamic deformation textures. In Proc. of the 2006 ACM SIGGRAPH\/Eurographics Symp. on Computer Animation (SCA\u201906). 73--82."},{"key":"e_1_2_2_22_1","volume-title":"Van Loan","author":"Golub Gene H.","year":"1996","unstructured":"Gene H. Golub and Charles F . Van Loan . 1996 . Matrix Computations (3rd ed.). Johns Hopkins University Press , Baltimore, MD. Gene H. Golub and Charles F. Van Loan. 1996. Matrix Computations (3rd ed.). Johns Hopkins University Press, Baltimore, MD."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/882262.882358"},{"key":"e_1_2_2_24_1","volume-title":"Proc. of the 5th China-Japan Seminar on Numerical Mathematics. 117--126","author":"Hayami Ken","year":"2002","unstructured":"Ken Hayami . 2002 . On the behaviour of the conjugate residual method for singular systems . In Proc. of the 5th China-Japan Seminar on Numerical Mathematics. 117--126 . Ken Hayami. 2002. On the behaviour of the conjugate residual method for singular systems. In Proc. of the 5th China-Japan Seminar on Numerical Mathematics. 117--126."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/nme.4513"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276394"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1028523.1028541"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0305-0548(94)90106-6"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1409060.1409117"},{"key":"e_1_2_2_30_1","volume-title":"Proc. of the 2nd Berkeley Symp. on Mathematical Statistics and Probability. 481--492","author":"Kuhn H. W.","unstructured":"H. W. Kuhn and A. W. Tucker . 1950. Nonlinear programming . In Proc. of the 2nd Berkeley Symp. on Mathematical Statistics and Probability. 481--492 . H. W. Kuhn and A. W. Tucker. 1950. Nonlinear programming. In Proc. of the 2nd Berkeley Symp. on Mathematical Statistics and Probability. 481--492."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12765"},{"key":"e_1_2_2_32_1","volume-title":"Proc. of the 2017 IEEE World Haptics Conf. (WHC\u201917)","author":"Lobo D.","unstructured":"D. Lobo , M. Sara\u00e7 , M. Verschoor , M. Solazzi , A. Frisoli , and M. A. Otaduy . 2017. Proxy-based haptic rendering for underactuated haptic devices . In Proc. of the 2017 IEEE World Haptics Conf. (WHC\u201917) . 48--53. D. Lobo, M. Sara\u00e7, M. Verschoor, M. Solazzi, A. Frisoli, and M. A. Otaduy. 2017. Proxy-based haptic rendering for underactuated haptic devices. In Proc. of the 2017 IEEE World Haptics Conf. (WHC\u201917). 48--53."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/0707032"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00935189"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2735627"},{"key":"e_1_2_2_36_1","volume-title":"Otaduy","author":"Miguel Eder","year":"2011","unstructured":"Eder Miguel and Miguel A . Otaduy . 2011 . Efficient simulation of contact between rigid and deformable objects. In ECCOMAS\u2014Multibody Dynamics 2011. Eder Miguel and Miguel A. Otaduy. 2011. Efficient simulation of contact between rigid and deformable objects. In ECCOMAS\u2014Multibody Dynamics 2011."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/54852.378528"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/1006058.1006087"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jvcir.2007.01.005"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2009.01396.x"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/0712047"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1028523.1028539"},{"key":"e_1_2_2_43_1","volume-title":"Numerical Recipes: The Art of Scientific Computing","author":"Press W. H.","year":"1992","unstructured":"W. H. Press , B. P. Flannery , S. A. Teukolsky , and W. T. Vetterling . 1992 . Numerical Recipes: The Art of Scientific Computing ( 2 nd ed.). Cambridge University Press . W. H. Press, B. P. Flannery, S. A. Teukolsky, and W. T. Vetterling. 1992. Numerical Recipes: The Art of Scientific Computing (2nd ed.). Cambridge University Press.","edition":"2"},{"key":"e_1_2_2_44_1","volume-title":"QP-collide: A new approach to collision treatment. In journ\u00e9es du groupe de travail Animation et Simulation","author":"Raghupathi Laks","unstructured":"Laks Raghupathi and Fran\u00e7ois Faure . 2006. QP-collide: A new approach to collision treatment. In journ\u00e9es du groupe de travail Animation et Simulation ( GTAS) (Annual French Working Group on Animation and Simulation). Institut de Recherche en Informatique de Toulouse, 91--101. Laks Raghupathi and Fran\u00e7ois Faure. 2006. QP-collide: A new approach to collision treatment. In journ\u00e9es du groupe de travail Animation et Simulation (GTAS) (Annual French Working Group on Animation and Simulation). Institut de Recherche en Informatique de Toulouse, 91--101."},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1002\/fld.1650190106"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2002.1013411"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cma.2004.07.009"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/0907058"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/1632592.1632607"},{"key":"e_1_2_2_50_1","volume-title":"Proc. of the Int. Conf. on Computer Graphics Theory and Applications (GRAPP\u201910)","volume":"1","author":"Silcowitz-Hansen Morten","year":"2010","unstructured":"Morten Silcowitz-Hansen , Sarah Maria Niebe Abel , and Kenny Erleben . 2010 a. Projected Gauss-Seidel subspace minimization method for interactive rigid body dynamics: Improving animation quality using a projected Gauss--Seidel subspace minimization method . In Proc. of the Int. Conf. on Computer Graphics Theory and Applications (GRAPP\u201910) , Vol. 1 . 38--45. Morten Silcowitz-Hansen, Sarah Maria Niebe Abel, and Kenny Erleben. 2010a. Projected Gauss-Seidel subspace minimization method for interactive rigid body dynamics: Improving animation quality using a projected Gauss--Seidel subspace minimization method. In Proc. of the Int. Conf. on Computer Graphics Theory and Applications (GRAPP\u201910), Vol. 1. 38--45."},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-010-0502-6"},{"key":"e_1_2_2_52_1","volume-title":"Proc. of the ACM SIGGRAPH\/Eurographics Symp. on Computer Animation (Posters).","author":"Sin Funshing","year":"2011","unstructured":"Funshing Sin , Yufeng Zhu , Yongqiang Li , and Daniel Schroeder . 2011 . Invertible isotropic hyperelasticity using SVD gradients . In Proc. of the ACM SIGGRAPH\/Eurographics Symp. on Computer Animation (Posters). Funshing Sin, Yufeng Zhu, Yongqiang Li, and Daniel Schroeder. 2011. Invertible isotropic hyperelasticity using SVD gradients. In Proc. of the ACM SIGGRAPH\/Eurographics Symp. on Computer Animation (Posters)."},{"key":"e_1_2_2_53_1","volume-title":"WSCG 14","author":"Spillmann J.","year":"2007","unstructured":"J. Spillmann , M. Becker , and M. Teschner . 2007. Non-iterative computation of contact forces for deformable objects. J . WSCG 14 , ( 2007 ), 1--3. J. Spillmann, M. Becker, and M. Teschner. 2007. Non-iterative computation of contact forces for deformable objects. J. WSCG 14, (2007), 1--3."},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0207(19960815)39:15<2673::AID-NME972>3.0.CO;2-I"},{"key":"e_1_2_2_55_1","volume-title":"Proc. of the ACM SIGGRAPH\/Eurographics Symp. on Computer Animation (SCA\u201912)","author":"Stomakhin Alexey","unstructured":"Alexey Stomakhin , Russell Howes , Craig Schroeder , and Joseph M. Teran . 2012. Energetically consistent invertible elasticity . In Proc. of the ACM SIGGRAPH\/Eurographics Symp. on Computer Animation (SCA\u201912) . 25--32. Alexey Stomakhin, Russell Howes, Craig Schroeder, and Joseph M. Teran. 2012. Energetically consistent invertible elasticity. In Proc. of the ACM SIGGRAPH\/Eurographics Symp. on Computer Animation (SCA\u201912). 25--32."},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185603"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2005.00829.x"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185601"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2012.07.002"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-8659.1330155"},{"key":"e_1_2_2_61_1","volume-title":"Computational Contact Mechanics","author":"Wriggers P.","unstructured":"P. Wriggers . 2002. Computational Contact Mechanics . Wiley . P. Wriggers. 2002. Computational Contact Mechanics. Wiley."},{"key":"e_1_2_2_62_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\/10.1145\/3209887","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3209887","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:13:09Z","timestamp":1750212789000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3209887"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,14]]},"references-count":62,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,4,30]]}},"alternative-id":["10.1145\/3209887"],"URL":"https:\/\/doi.org\/10.1145\/3209887","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,3,14]]},"assertion":[{"value":"2017-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-03-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}