$\supseteq$

Projective Dynamics: Fast Simulation of Hyperelastic Models with Dynamic Constraints | IEEE Transactions on Visualization and Computer Graphics"/>

More Web Proxy on the site http://driver.im/

research-article

ADMM <inline-formula><tex-math notation="LaTeX">$\supseteq$</tex-math><alternatives><inline-graphic xlink:href="overby-ieq1-2730875.gif"/></alternatives></inline-formula> Projective Dynamics: Fast Simulation of Hyperelastic Models with Dynamic Constraints

Authors:

Matthew Overby,

George E. Brown,

Rahul NarainAuthors Info & Claims

IEEE Transactions on Visualization and Computer Graphics, Volume 23, Issue 10

Pages 2222 - 2234

https://doi.org/10.1109/TVCG.2017.2730875

Published: 01 October 2017 Publication History

Abstract

We apply the alternating direction method of multipliers (ADMM) optimization algorithm to implicit time integration of elastic bodies, and show that the resulting method closely relates to the recently proposed projective dynamics algorithm. However, as ADMM is a general purpose optimization algorithm applicable to a broad range of objective functions, it permits the use of nonlinear constitutive models and hard constraints while retaining the speed, parallelizability, and robustness of projective dynamics. We further extend the algorithm to improve the handling of dynamically changing constraints such as sliding and contact, while maintaining the benefits of a constant, prefactored system matrix. We demonstrate the benefits of our algorithm on several examples that include cloth, collisions, and volumetric deformable bodies with nonlinear elasticity and skin sliding effects.

References

[1]

B. Bickel, M. Bächer, M. A. Otaduy, W. Matusik, H. Pfister, and M. Gross, “Capture and modeling of non-linear heterogeneous soft tissue,” ACM Trans. Graph., vol. 28, no. 3, pp. 89:1–89:9, Jul. 2009.

[2]

H. Wang, J. F. O’Brien, and R. Ramamoorthi, “Data-driven elastic models for cloth: Modeling and measurement,” ACM Trans. Graph., vol. 30, no. 4, pp. 71:1–71:12, Jul. 2011.

[3]

E. Miguel, et al., “Data-driven estimation of cloth simulation models,” Comput. Graph. Forum, vol. 31, no. 2.2, pp. 519–528, 2012.

Digital Library

[4]

E. Miguel, D. Miraut, and M. A. Otaduy, “Modeling and estimation of energy-based hyperelastic objects,” Comput. Graph. Forum, vol. 35, no. 2, pp. 385–396, 2016.

[5]

M. Müller, B. Heidelberger, M. Hennix, and J. Ratcliff, “Position based dynamics,” J. Vis. Commun. Image Representation, vol. 18, no. 2, pp. 109–118, 2007.

Digital Library

[6]

J. Bender, M. Müller, M. A. Otaduy, M. Teschner, and M. Macklin, “A survey on position-based simulation methods in computer graphics,” Comput. Graph. Forum, vol. 33, no. 6, pp. 228–251, 2014.

Digital Library

[7]

S. Bouaziz, S. Martin, T. Liu, L. Kavan, and M. Pauly, “Projective dynamics: Fusing constraint projections for fast simulation,” ACM Trans. Graph., vol. 33, no. 4, pp. 154:1–154:11, Jul. 2014.

[8]

R. Narain, M. Overby, and G. E. Brown, “ADMM $\supseteq$ projective dynamics: Fast simulation of general constitutive models,” in Proc. ACM SIGGRAPH/Eurographics Symp. Comput. Animation, 2016, pp. 21–28.

[9]

S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, “Distributed optimization and statistical learning via the alternating direction method of multipliers,” Found. Trends Mach. Learn., vol. 3, no. 1, pp. 1–122, Jan. 2011.

Digital Library

[10]

H. Xu, F. Sin, Y. Zhu, and J. Barbič, “Nonlinear material design using principal stretches,” ACM Trans. Graph., vol. 34, no. 4, pp. 75:1–75:11, Jul. 2015.

[11]

O. Rémillard and P. G. Kry, “Embedded thin shells for wrinkle simulation,” ACM Trans. Graph., vol. 32, no. 4, pp. 50:1–50:8, Jul. 2013.

[12]

P. Li and P. G. Kry, “Multi-layer skin simulation with adaptive constraints,” in Proc. 7th Int. Conf. Motion Games, 2014, pp. 171–176.

[13]

D. Li, S. Sueda, D. R. Neog, and D. K. Pai, “Thin skin elastodynamics,” ACM Trans. Graph., vol. 32, no. 4, pp. 49:1–49:10, Jul. 2013.

[14]

M. Müller, N. Chentanez, T.-Y. Kim, and M. Macklin, “Strain based dynamics,” in Proc. ACM SIGGRAPH/Eurographics Symp. Comput. Animation, 2014, pp. 149–157.

[15]

D. Terzopoulos, J. Platt, A. Barr, and K. Fleischer, “Elastically deformable models,” in Proc. Conf. Comput. Graph. Interactive Tech., 1987, pp. 205–214.

[16]

D. Baraff and A. Witkin, “Large steps in cloth simulation,” in Proc. Conf. Comput. Graph. Interactive Tech., 1998, pp. 43–54.

[17]

L. Kharevych, et al., “Geometric, variational integrators for computer animation,” in Proc. ACM SIGGRAPH/Eurographics Symp. Comput. Animation, 2006, pp. 43–51.

[18]

S. Martin, B. Thomaszewski, E. Grinspun, and M. Gross, “Example-based elastic materials,” ACM Trans. Graph., vol. 30, no. 4, pp. 72:1–72:8, Jul. 2011.

[19]

T. F. Gast, C. Schroeder, A. Stomakhin, C. Jiang, and J. M. Teran, “Optimization integrator for large time steps,” IEEE Trans. Vis. Comput. Graph., vol. 21, no. 10, pp. 1103–1115, Oct. 2015.

Digital Library

[20]

T. Liu, A. W. Bargteil, J. F. O’Brien, and L. Kavan, “Fast simulation of mass-spring systems,” ACM Trans. Graph., vol. 32, no. 6, pp. 214:1–214:7, Nov. 2013.

[21]

S. Bouaziz, M. Deuss, Y. Schwartzburg, T. Weise, and M. Pauly, “Shape-up: Shaping discrete geometry with projections,” Comput. Graph. Forum, vol. 31, no. 5, pp. 1657–1667, Aug. 2012.

Digital Library

[22]

M. Weiler, D. Koschier, and J. Bender, “Projective fluids,” in Proc. 9th Int. Conf. Motion Games, 2016, pp. 79–84.

[23]

M. Fratarcangeli, V. Tibaldo, and F. Pellacini, “Vivace: A practical gauss-seidel method for stable soft body dynamics,” ACM Trans. Graph., vol. 35, no. 6, pp. 214:1–214:9, Nov. 2016.

[24]

M. Macklin, M. Müller, and N. Chentanez, “XPBD: Position-based simulation of compliant constrained dynamics,” in Proc. 9th Int. Conf. Motion Games, 2016, pp. 49–54.

[25]

H. Wang, “A chebyshev semi-iterative approach for accelerating projective and position-based dynamics,” ACM Trans. Graph., vol. 34, no. 6, pp. 246:1–246:9, Oct. 2015.

[26]

T. Liu, S. Bouaziz, and L. Kavan, “Quasi-Newton methods for real-time simulation of hyperelastic materials,” ACM Trans. Graph., vol. 36, no. 3, pp. 23:1–23:16, May 2017.

[27]

J. Nocedal and S. Wright, Numerical Optimization. New York, NY, USA: Springer, 2006.

[28]

E. Esser, X. Zhang, and T. F. Chan, “A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science,” SIAM J. Imag. Sci., vol. 3, no. 4, pp. 1015–1046, Dec. 2010.

Digital Library

[29]

D. O’Connor and L. Vandenberghe, “Primal-dual decomposition by operator splitting and applications to image deblurring,” SIAM J. Imag. Sci., vol. 7, no. 3, pp. 1724–1754, 2014.

[30]

P. Tseng, “Applications of a splitting algorithm to decomposition in convex programming and variational inequalities,” SIAM J. Control Optimization, vol. 29, no. 1, pp. 119–138, 1991. [Online]. Available: https://doi.org/10.1137/0329006

[31]

M. Zhu and T. Chan, “An efficient primal-dual hybrid gradient algorithm for total variation image restoration,” University of California, Los Angeles, Los Angeles, Report 34, CA, USA, 2008.

[32]

D. Goldfarb, S. Ma, and K. Scheinberg, “Fast alternating linearization methods for minimizing the sum of two convex functions,” Math. Program., vol. 141, no. 1, pp. 349–382, 2012.

[33]

T. Goldstein, B. O’Donoghue, S. Setzer, and R. Baraniuk, “Fast alternating direction optimization methods,” SIAM J. Imag. Sci., vol. 7, no. 3, pp. 1588–1623, 2014.

Digital Library

[34]

M. Kadkhodaie, K. Christakopoulou, M. Sanjabi, and A. Banerjee, “Accelerated alternating direction method of multipliers,” in Proc. ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining, 2015, pp. 497–506.

[35]

P. A. Forero, A. Cano, and G. B. Giannakis, “Distributed clustering using wireless sensor networks,” IEEE J. Sel. Topics Signal Process., vol. 5, no. 4, pp. 707–724, Aug. 2011.

[36]

Z. Wen, C. Yang, X. Liu, and S. Marchesini, “Alternating direction methods for classical and ptychographic phase retrieval,” Inverse Problems, vol. 28, no. 11, 2012, Art. no.

[37]

D. L. Sun and C. Fvotte, “Alternating direction method of multipliers for non-negative matrix factorization with the beta-divergence,” in Proc. IEEE Int. Conf. Acoust. Speech Signal Process., May 2014, pp. 6201–6205.

[38]

M. Hong, Z.-Q. Luo, and M. Razaviyayn, “Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems,” in Proc. IEEE Int. Conf. Acoust. Speech Signal Proc., Apr. 2015, pp. 3836–3840.

[39]

G. Li and T. K. Pong, “Global convergence of splitting methods for nonconvex composite optimization,” SIAM J. Optimization, vol. 25, no. 4, pp. 2434–2460, 2015.

[40]

S. Magnsson, P. C. Weeraddana, M. G. Rabbat, and C. Fischione, “On the convergence of alternating direction Lagrangian methods for nonconvex structured optimization problems,” IEEE Trans. Control Netw. Syst., vol. 3, no. 3, pp. 296–309, Sep. 2016.

[41]

J. Gregson, I. Ihrke, N. Thuerey, and W. Heidrich, “From capture to simulation: Connecting forward and inverse problems in fluids,” ACM Trans. Graph., vol. 33, no. 4, pp. 139:1–139:11, Jul. 2014.

[42]

R. Narain, A. Samii, and J. F. O’Brien, “Adaptive anisotropic remeshing for cloth simulation,” ACM Trans. Graph., vol. 31, no. 6, pp. 152:1–152:10, Nov. 2012.

[43]

R. Narain, R. A. Albert, A. Bulbul, G. J. Ward, M. S. Banks, and J. F. O’Brien, “Optimal presentation of imagery with focus cues on multi-plane displays,” ACM Trans. Graph., vol. 34, no. 4, pp. 59:1–59:12, Jul. 2015.

[44]

D. M. Kaufman, R. Tamstorf, B. Smith, J.-M. Aubry, and E. Grinspun, “Adaptive nonlinearity for collisions in complex rod assemblies,” ACM Trans. Graph., vol. 33, no. 4, pp. 123:1–123:12, Jul. 2014.

[45]

N. Parikh and S. Boyd, “Proximal algorithms,” Found. Trends Optimization, vol. 1, no. 3, pp. 127–239, Jan. 2014.

Digital Library

[46]

G. Irving, J. Teran, and R. Fedkiw, “Invertible finite elements for robust simulation of large deformation,” in Proc. ACM SIGGRAPH/Eurographics Symp. Comput. Animation, 2004, pp. 131–140.

[47]

A. Stomakhin, R. Howes, C. Schroeder, and J. M. Teran, “Energetically consistent invertible elasticity,” in Proc. ACM SIGGRAPH/Eurographics Symp. Comput. Animation, 2012, pp. 25–32.

[48]

Y.-C. Fung, Biomechanics: Mechanical Properties of Living Tissues. Berlin, Germany: Springer, 2013.

[49]

I. Karamouzas, N. Sohre, R. Narain, and S. J. Guy, “Implicit crowds: Optimization integrator for robust crowd simulation,” ACM Trans. Graph., vol. 36, no. 4, pp. 136:1–136:13, Jul. 2017.

[50]

H. Uzawa, “Iterative methods for concave programming,” in Studies in Linear and Nonlinear Programming. Palo Alto, CA, USA: Stanford Univ. Press, 1958, pp. 154–165.

[51]

F. Bertrand and P. A. Tanguy, “Krylov-based Uzawa algorithms for the solution of the stokes equations using discontinuous-pressure tetrahedral finite elements,” J. Comput. Physics, vol. 181, no. 2, pp. 617–638, 2002.

Digital Library

[52]

Z. Chen, Finite Element Methods and Their Applications. Berlin, Germany: Springer, 2005.

[53]

M. Benzi, G. H. Golub, and J. Liesen, “Numerical solution of saddle point problems,” Acta Numerica, vol. 14, pp. 1–137, 2005.

[54]

J. H. Bramble, J. E. Pasciak, and A. T. Vassilev, “Analysis of the inexact Uzawa algorithm for saddle point problems,” SIAM J. Numerical Anal., vol. 34, no. 3, pp. 1072–1092, 1997.

Digital Library

[55]

M. Deuss, A. H. Deleuran, S. Bouaziz, B. Deng, D. Piker, and M. Pauly, “ShapeOp—a robust and extensible geometric modelling paradigm,” in Modelling Behaviour: Design Modelling Symposium, R. M. Thomsen, M. Tamke, C. Gengnagel, B. Faircloth, and F. Scheurer, Eds. Berlin, Germany: Springer, 2015, pp. 505–515.

[56]

H. Wang and A. Banerjee, “Online alternating direction method,” in Proc. Int. Conf. Mach. Learn., 2013, pp. 1119–1126.

[57]

C. G. Petra, O. Schenk, and M. Anitescu, “Real-time stochastic optimization of complex energy systems on high-performance computers,” IEEE Comput. Sci. Eng., vol. 16, no. 5, pp. 32–42, Sep./Oct. 2014.

Cited By

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-Nov-2024
https://doi.org/10.1145/3687988
Trusty TFei YLevin DKaufman D(2024)Trading Spaces: Adaptive Subspace Time Integration for Contacting ElastodynamicsACM Transactions on Graphics10.1145/368794643:6(1-16)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687946
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
Show More Cited By

Index Terms

ADMM $\supseteq$ Projective Dynamics: Fast Simulation of Hyperelastic Models with Dynamic Constraints

Index terms have been assigned to the content through auto-classification.

Recommendations

Robust PCA via $\ell _{0}$-$\ell _{1}$ Regularization
We study the problem of low-rank and sparse decomposition from possibly noisy observations, known as Robust PCA, where the sparse component can be seen as outliers. We first propose a modified objective function where the nuclear norm captures the low-...
Upper Bound of Null Space Constant $\rho(p,t,A,k)$ and High-Order Restricted Isometry Constant $\delta_{tk}$ for Sparse Recovery via $\ell_{p}$ Minimization
The <inline-formula><tex-math notation="LaTeX">$\boldsymbol{\ell_{p}}$</tex-math></inline-formula> null space property (<inline-formula><tex-math notation="LaTeX">$\boldsymbol{\ell_{p}}$</tex-math></inline-formula>-NSP) and restricted isometry property (...
$NP/CMP$ Equivalence: A Phenomenon Hidden Among Sparsity Models $l_{0}$ Minimization and $l_{p}$ Minimization for Information Processing
In this paper, we have proved that in every underdetermined linear system Ax = b, there corresponds a constant p*(A, b) > 0 such that every solution to the l p-norm minimization problem also solves the l0-norm minimization problem whenever 0 <; p &...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Visualization and Computer Graphics

IEEE Transactions on Visualization and Computer Graphics Volume 23, Issue 10

Oct. 2017

158 pages

ISSN:1077-2626

Issue’s Table of Contents

1077-2626 © 2017 IEEE.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 October 2017

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

34
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

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-Nov-2024
https://doi.org/10.1145/3687988
Trusty TFei YLevin DKaufman D(2024)Trading Spaces: Adaptive Subspace Time Integration for Contacting ElastodynamicsACM Transactions on Graphics10.1145/368794643:6(1-16)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687946
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
Li XLi MHan XWang HYang YJiang C(2024)A Dynamic Duo of Finite Elements and Material PointsACM SIGGRAPH 2024 Conference Papers10.1145/3641519.3657449(1-11)Online publication date: 13-Jul-2024
https://dl.acm.org/doi/10.1145/3641519.3657449
Leng AZeng BChen YTu PTao BChen X(2024)Development of a virtual reality-based zygomatic implant surgery training system with global collision detection and optimized finite element method modelComputer Methods and Programs in Biomedicine10.1016/j.cmpb.2023.107940243:COnline publication date: 4-Mar-2024
https://dl.acm.org/doi/10.1016/j.cmpb.2023.107940
Flor AAanjaneya M(2024)Spectral reordering for faster elasticity simulationsThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-024-03513-040:7(5067-5077)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1007/s00371-024-03513-0
Gurtner MZemánek JHurák Z(2023)Alternating direction method of multipliers-based distributed control for distributed manipulation by shaping physical force fieldsInternational Journal of Robotics Research10.1177/0278364923115395842:1-2(3-20)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1177/02783649231153958
Qu ZLi MYang YJiang CDe Goes F(2023)Power Plastics: A Hybrid Lagrangian/Eulerian Solver for Mesoscale Inelastic FlowsACM Transactions on Graphics10.1145/361834442:6(1-11)Online publication date: 5-Dec-2023
https://dl.acm.org/doi/10.1145/3618344
Löschner FFernández-Fernández JJeske SLongva ABender J(2023)Micropolar Elasticity in Physically-Based AnimationProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/36069226:3(1-24)Online publication date: 24-Aug-2023
https://dl.acm.org/doi/10.1145/3606922
Daviet G(2023)Interactive Hair Simulation on the GPU using ADMMACM SIGGRAPH 2023 Conference Proceedings10.1145/3588432.3591551(1-11)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.1145/3588432.3591551
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents