research-article

Efficient and Accurate Collision Response for Elastically Deformable Models

Authors:

Mickeal Verschoor,

Andrei C. JalbaAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 38, Issue 2

Article No.: 17, Pages 1 - 20

https://doi.org/10.1145/3209887

Published: 14 March 2019 Publication History

Abstract

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.

Supplementary Material

verschoor (verschoor.zip)

Supplemental movie, appendix, image and software files for, Efficient and Accurate Collision Response for Elastically Deformable Models

Download
258.65 MB

References

[1]

Jérémie Allard, François Faure, Hadrien Courtecuisse, Florent Falipou, Christian Duriez, and Paul G. Kry. 2010. Volume contact constraints at arbitrary resolution. ACM Trans. Graph. 29, 4 (2010), 82:1--82:10.

Digital Library

[2]

Mihai Anitescu and Gary D. Hart. 2004. A fixed-point iteration approach for multibody dynamics with contact and small friction. Math. Program. 101, 1 (2004), 3--32.

Digital Library

[3]

David Baraff. 1989. Analytical methods for dynamic simulation of non-penetrating rigid bodies. In Proc. of the 16th Annual Conf. on Computer Graphics and Interactive Techniques (SIGGRAPH’89). ACM, New York, NY, 223--232.

Digital Library

[4]

David Baraff. 1994. Fast contact force computation for nonpenetrating rigid bodies. In Proc. of the 21st Annual Conf. on Computer Graphics and Interactive Techniques (SIGGRAPH’94). ACM, New York, NY, 23--34.

Digital Library

[5]

David Baraff. 1996. Linear-time dynamics using Lagrange multipliers. In Proc. of the 23rd Annual Conf. on Computer Graphics and Interactive Techniques (SIGGRAPH’96). ACM, New York, NY, 137--146.

Digital Library

[6]

David Baraff and Andrew Witkin. 1992. Dynamic simulation of non-penetrating flexible bodies. In Proc. of the 19th Annual Conf. on Computer Graphics and Interactive Techniques (SIGGRAPH’92). ACM, New York, NY, 303--308.

Digital Library

[7]

David Baraff and Andrew Witkin. 1998. Large steps in cloth simulation. In Proc. of the 25th Annual Conf. on Computer Graphics and Interactive Techniques (SIGGRAPH’98). ACM, New York, NY, 43--54.

Digital Library

[8]

Jernej Barbič and Doug James. 2007. Time-critical distributed contact for 6-DoF haptic rendering of adaptively sampled reduced deformable models. In Proc. of the 2007 ACM SIGGRAPH/Eurographics Symp. on Computer Animation (SCA’07). 171--180.

Digital Library

[9]

Jan Bender, Kenny Erleben, and Jeff Trinkle. 2014. Interactive simulation of rigid body dynamics in computer graphics. Comput. Graph. Forum 33, 1 (2014), 246--270.

Digital Library

[10]

Florence Bertails-Descoubes, Florent Cadoux, Gilles Daviet, and Vincent Acary. 2011. A nonsmooth Newton solver for capturing exact Coulomb friction in fiber assemblies. ACM Trans. Graph. 30, 1 (2011), 6:1--6:14.

Digital Library

[11]

Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press.

Digital Library

[12]

Robert Bridson, Ronald Fedkiw, and John Anderson. 2002. Robust treatment of collisions, contact and friction for cloth animation. ACM Trans. Graph. 21, 3 (2002), 594--603.

Digital Library

[13]

Erin Catto. 2005. Iterative dynamics with temporal coherence. In Proc. of the 2005 Game Developer Conf.

[14]

Richard Cottle, Jong-Shi Pang, and Richard E. Stone. 1992. The Linear Complementarity Problem. Academic Press.

[15]

Gilles Daviet, Florence Bertails-Descoubes, and Laurence Boissieux. 2011. A hybrid iterative solver for robustly capturing Coulomb friction in hair dynamics. ACM Trans. Graph. 30, 6 (2011), 139:1--139:12.

Digital Library

[16]

Christian Duriez, Frederic Dubois, Abderrahmane Kheddar, and Claude Andriot. 2006. Realistic haptic rendering of interacting deformable objects in virtual environments. IEEE Trans. Vis. Comput. Graph. 12, 1 (2006), 36--47.

Digital Library

[17]

Stanley C. Eisenstat, Howard C. Elman, and Martin H. Schultz. 1983. Variational iterative methods for nonsymmetric systems of linear equations. SIAM J. Numer. Anal. 20, 2 (1983), 345--357.

Digital Library

[18]

Kenny Erleben. 2007. Velocity-based shock propagation for multibody dynamics animation. ACM Trans. Graph. 26, 2 (2007), Article 12.

Digital Library

[19]

Kenny Erleben. 2013. Numerical methods for linear complementarity problems in physics-based animation. In ACM SIGGRAPH 2013 Courses (SIGGRAPH’13). ACM, New York, NY, 8:1--8:42.

Digital Library

[20]

David C. Fong and Michael Saunders. 2011. CG Versus MINRES: An Empirical Comparison. Technical Report. Stanford University, Stanford, CA.

[21]

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’06). 73--82.

Digital Library

[22]

Gene H. Golub and Charles F. Van Loan. 1996. Matrix Computations (3rd ed.). Johns Hopkins University Press, Baltimore, MD.

Digital Library

[23]

Eran Guendelman, Robert Bridson, and Ronald Fedkiw. 2003. Nonconvex rigid bodies with stacking. ACM Trans. Graph. 22, 3 (2003), 871--878.

Digital Library

[24]

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.

[25]

T. Heyn, M. Anitescu, A. Tasora, and D. Negrut. 2012. Using Krylov subspace and spectral methods for solving complementarity problems in many-body contact dynamics simulation. Int. J. Numer. Meth. Eng. 95, 7 (2012), 541--561.

[26]

Geoffrey Irving, Craig Schroeder, and Ronald Fedkiw. 2007. Volume conserving finite element simulations of deformable models. ACM Trans. Graph. 26, 3 (2007), Article 13.

Digital Library

[27]

G. Irving, J. Teran, and R. Fedkiw. 2004. Invertible finite elements for robust simulation of large deformation. In Proc. of the 2004 ACM SIGGRAPH/Eurographics Symp. on Computer Animation (SCA’04). 131--140.

Digital Library

[28]

J. Judice and F. Pires. 1994. A block principal pivoting algorithm for large-scale strictly monotone linear complementarity problems. Comput. Oper. Res. 21, 5 (1994), 587--596.

Digital Library

[29]

Danny M. Kaufman, Shinjiro Sueda, Doug L. James, and Dinesh K. Pai. 2008. Staggered projections for frictional contact in multibody systems. ACM Trans. Graph. 27, 5 (2008), 164:1--164:11.

Digital Library

[30]

H. W. Kuhn and A. W. Tucker. 1950. Nonlinear programming. In Proc. of the 2nd Berkeley Symp. on Mathematical Statistics and Probability. 481--492.

[31]

Siwang Li, Zherong Pan, Jin Huang, Hujun Bao, and Xiaogang Jin. 2015. Deformable objects collision handling with fast convergence. Comput. Graph. Forum 34, 7 (2015), 269--278.

Digital Library

[32]

D. Lobo, M. Saraç, 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’17). 48--53.

[33]

David G. Luenberger. 1970. The conjugate residual method for constrained minimization problems. SIAM J. Numer. Anal. 7, 3 (1970), 390--398.

Digital Library

[34]

David G. Luenberger. 1973. An approach to nonlinear programming. J. Optimiz. Theory App. 11, 3 (1973), 219--227.

[35]

H. Mazhar, T. Heyn, D. Negrut, and A. Tasora. 2015. Using Nesterov’s method to accelerate multibody dynamics with friction and contact. ACM Trans. Graph. 34, 3 (2015), 32:1--32:14.

Digital Library

[36]

Eder Miguel and Miguel A. Otaduy. 2011. Efficient simulation of contact between rigid and deformable objects. In ECCOMAS—Multibody Dynamics 2011.

[37]

Matthew Moore and Jane Wilhelms. 1988. Collision detection and response for computer animation. In Proc. of the 15th Annual Conf. on Computer Graphics and Interactive Techniques (SIGGRAPH’88). ACM, New York, NY, 289--298.

Digital Library

[38]

Matthias Müller and Markus Gross. 2004. Interactive virtual materials. In Proc. of Graphics Interface 2004 (GI’04). 239--246.

Digital Library

[39]

Matthias Müller, Bruno Heidelberger, Marcus Hennix, and John Ratcliff. 2007. Position based dynamics. J. Vis. Comun. Image Represent. 18, 2 (2007), 109--118.

Digital Library

[40]

Miguel A. Otaduy, Rasmus Tamstorf, Denis Steinemann, and Markus Gross. 2009. Implicit contact handling for deformable objects. Comput. Graph. Forum 28, 2 (2009), 559--568.

[41]

C. C. Paige and M. A. Saunders. 1975. Solution of sparse indefinite systems of linear equations. SIAM J. Numer. Anal. 12, 4 (1975), 617--629.

Digital Library

[42]

Mark Pauly, Dinesh K. Pai, and Leonidas J. Guibas. 2004. Quasi-rigid objects in contact. In Proc. of the 2004 ACM SIGGRAPH/Eurographics Symp. on Computer Animation (SCA’04). 109--119.

Digital Library

[43]

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.

Digital Library

[44]

Laks Raghupathi and François Faure. 2006. QP-collide: A new approach to collision treatment. In journées 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.

[45]

Alison Ramage and Andrew J. Wathen. 1994. Iterative solution techniques for the stokes and Navier-Stokes equations. Int. J. Numer. Methods Fluids 19 (1994), 67--83.

[46]

Stéphane Redon, Abderrahmane Kheddar, and Sabine Coquillart. 2002. Gauss’ least constraints principle and rigid body simulations. In Proc. of the IEEE Int. Conf. on Robotics and Automation. 11--15.

[47]

Mathieu Renouf and Pierre Alart. 2005. Conjugate gradient type algorithms for frictional multi-contact problems: Applications to granular materials. Comput. Methods Appl. Mech. Eng. 194, 18--20 (2005), 2019--2041.

[48]

Youcef Saad and Martin H. Schultz. 1986. GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Stat. Comput. 7, 3 (1986), 856--869.

[49]

Tamar Shinar, Craig Schroeder, and Ronald Fedkiw. 2008. Two-way coupling of rigid and deformable bodies. In Proc. of the 2008 ACM SIGGRAPH/Eurographics Symp. on Computer Animation (SCA’08). 95--103.

Digital Library

[50]

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’10), Vol. 1. 38--45.

[51]

Morten Silcowitz-Hansen, Sarah Niebe, and Kenny Erleben. 2010b. A nonsmooth nonlinear conjugate gradient method for interactive contact force problems. Vis. Comput. 26, 6--8 (2010), 893--901.

Digital Library

[52]

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).

[53]

J. Spillmann, M. Becker, and M. Teschner. 2007. Non-iterative computation of contact forces for deformable objects. J. WSCG 14, (2007), 1--3.

[54]

D. Stewart and J. C. Trinkle. 1996. An implicit time-stepping scheme for rigid body dynamics with coulomb friction. Int. J. Numer. Meth. Eng. 39 (1996), 2673--2691.

[55]

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’12). 25--32.

Digital Library

[56]

Min Tang, Dinesh Manocha, Miguel A. Otaduy, and Ruofeng Tong. 2012. Continuous penalty forces. ACM Trans. Graph. 31, 4 (2012), 107:1--107:9.

Digital Library

[57]

M. Teschner, S. Kimmerle, B. Heidelberger, G. Zachmann, L. Raghupathi, A. Fuhrmann, et al. 2004. Collision detection for deformable objects. Comput. Graph. Forum 24, 1 (2004), 61--81.

[58]

Richard Tonge, Feodor Benevolenski, and Andrey Voroshilov. 2012. Mass splitting for jitter-free parallel rigid body simulation. ACM Trans. Graph. 31, 4 (2012), 105:1--105:8.

Digital Library

[59]

Mickeal Verschoor and Andrei C. Jalba. 2012. Analysis and performance estimation of the conjugate gradient method on multiple GPUs. Parallel Comput. 38, 10--11 (2012), 552--575.

Digital Library

[60]

Pascal Volino and Nadia Magnenat Thalmann. 1994. Efficient self-collision detection on smoothly discretized surface animations using geometrical shape regularity. Comput. Graph. Forum 13, 3 (1994), 155--166.

[61]

P. Wriggers. 2002. Computational Contact Mechanics. Wiley.

[62]

H. Xu, Y. Zhao, and J. Barbič. 2014. Implicit multibody penalty-based distributed contact. IEEE Trans. Vis. Comput. Graph. 20, 9 (2014), 1266--1279.

Cited By

Bai LTao CChen JYu SYu W(2024)Modeling of virtual clothing and its contact with the human bodyAUTEX Research Journal10.1515/aut-2023-003924:1Online publication date: 10-Jul-2024
https://doi.org/10.1515/aut-2023-0039
Qian XZhou YRuan JYu C(2024)Withdrawal model for fiber motions in the tuft disentanglementTextile Research Journal10.1177/0040517523122375894:9-10(1111-1125)Online publication date: 6-Feb-2024
https://doi.org/10.1177/00405175231223758
Guo DLi MYang YLi SWang G(2024)Barrier-Augmented Lagrangian for GPU-based Elastodynamic ContactACM Transactions on Graphics10.1145/368798843:6(1-17)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687988
Show More Cited By

Index Terms

Efficient and Accurate Collision Response for Elastically Deformable Models
1. Computing methodologies
  1. Computer graphics
    1. Animation
      1. Physical simulation

Recommendations

Non-smooth Newton Methods for Deformable Multi-body Dynamics

We present a framework for the simulation of rigid and deformable bodies in the presence of contact and friction. Our method is based on a non-smooth Newton iteration that solves the underlying nonlinear complementarity problems (NCPs) directly. This ...
Improved algorithms for linear complementarity problems arising from collision response
Collision Detection and Response for Computer Animation

When several objects are moved about by computer animation, there is the chance that they will interpenetrate. This is often an undesired state, particularly if the animation is seeking to model a realistic world. Two issues are involved: detecting that ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 38, Issue 2

April 2019

112 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/3313807

Editor:
Marc Alexa
TU Berlin, Germany

Issue’s Table of Contents

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 March 2019

Accepted: 01 January 2019

Revised: 01 October 2018

Received: 01 November 2017

Published in TOG Volume 38, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

40
Total Citations
View Citations
913
Total Downloads

Downloads (Last 12 months)69
Downloads (Last 6 weeks)7

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bai LTao CChen JYu SYu W(2024)Modeling of virtual clothing and its contact with the human bodyAUTEX Research Journal10.1515/aut-2023-003924:1Online publication date: 10-Jul-2024
https://doi.org/10.1515/aut-2023-0039
Qian XZhou YRuan JYu C(2024)Withdrawal model for fiber motions in the tuft disentanglementTextile Research Journal10.1177/0040517523122375894:9-10(1111-1125)Online publication date: 6-Feb-2024
https://doi.org/10.1177/00405175231223758
Guo DLi MYang YLi SWang G(2024)Barrier-Augmented Lagrangian for GPU-based Elastodynamic ContactACM Transactions on Graphics10.1145/368798843:6(1-17)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687988
Ando R(2024)A Cubic Barrier with Elasticity-Inclusive Dynamic StiffnessACM Transactions on Graphics10.1145/368790843:6(1-13)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687908
Huang ZTozoni DGjoka AFerguson ZSchneider TPanozzo DZorin D(2024)Differentiable solver for time-dependent deformation problems with contactACM Transactions on Graphics10.1145/3657648Online publication date: 26-Apr-2024
https://dl.acm.org/doi/10.1145/3657648
Huang KChitalu FLin HKomura T(2024)GIPC: Fast and Stable Gauss-Newton Optimization of IPC Barrier EnergyACM Transactions on Graphics10.1145/364302843:2(1-18)Online publication date: 27-Jan-2024
https://dl.acm.org/doi/10.1145/3643028
Shen XCai RBi MLv T(2024)Preconditioned Nonlinear Conjugate Gradient Method for Real-time Interior-point HyperelasticityACM SIGGRAPH 2024 Conference Papers10.1145/3641519.3657490(1-11)Online publication date: 13-Jul-2024
https://dl.acm.org/doi/10.1145/3641519.3657490
Ferreira SMueller-Roemer JWeber D(2024)Projection-Based Handling of Contact ConstraintsACM SIGGRAPH 2024 Posters10.1145/3641234.3671075(1-2)Online publication date: 25-Jul-2024
https://dl.acm.org/doi/10.1145/3641234.3671075
Du YLi YCoros SThomaszewski B(2024)Robust and Artefact‐Free Deformable Contact with Smooth Surface RepresentationsComputer Graphics Forum10.1111/cgf.15187Online publication date: 17-Oct-2024
https://doi.org/10.1111/cgf.15187
Zhu SFang CYu PZhai XHao APan J(2024)Efficient frictional contacts for soft body dynamics via ADMMThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-024-03438-840:7(4569-4583)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1007/s00371-024-03438-8
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Issue’s Table of Contents