Nothing Special   »   [go: up one dir, main page]

skip to main content
research-article

Isotropic ARAP Energy Using Cauchy-Green Invariants

Published: 30 November 2022 Publication History

Abstract

Isotropic As-Rigid-As-Possible (ARAP) energy has been popular for shape editing, mesh parametrisation and soft-body simulation for almost two decades. However, a formulation using Cauchy-Green (CG) invariants has always been unclear, due to a rotation-polluted trace term that cannot be directly expressed using these invariants. We show how this incongruent trace term can be understood via an implicit relationship to the CG invariants. Our analysis reveals this relationship to be a polynomial where the roots equate to the trace term, and where the derivatives also give rise to closed-form expressions of the Hessian to guarantee positive semi-definiteness for a fast and concise Newton-type implicit time integration. A consequence of this analysis is a novel analytical formulation to compute rotations and singular values of deformation-gradient tensors without explicit/numerical factorization which is significant, resulting in up-to 3.5× speedup and benefits energy function evaluation for reducing solver time. We validate our energy formulation by experiments and comparison, demonstrating that our resulting eigendecomposition using the CG invariants is equivalent to existing ARAP formulations. We thus reveal isotropic ARAP energy to be a member of the "Cauchy-Green club", meaning that it can indeed be defined using CG invariants and therefore that the closed-form expressions of the resulting Hessian are shared with other energies written in their terms.

Supplemental Material

MP4 File
presentation

References

[1]
Jernej Barbič. 2012. Exact Corotational Linear FEM Stiffness Matrix. Technical Report. Technical Report, Computer Science Department, USC.
[2]
Jan Bender and Crispin Deul. 2013. Technical Section: Adaptive Cloth Simulation Using Corotational Finite Elements. Comput. Graph. 37, 7 (nov 2013), 820--829.
[3]
Gilbert Louis Bernstein, Chinmayee Shah, Crystal Lemire, Zachary Devito, Matthew Fisher, Philip Levis, and Pat Hanrahan. 2016. Ebb: A DSL for Physical Simulation on CPUs and GPUs. ACM Trans. Graph. 35, 2, Article 21 (may 2016), 12 pages.
[4]
Maurice A. Biot. 1938. Theory of elasticity with large displacements and rotations.
[5]
Javier Bonet and Richard D. Wood. 2008. Nonlinear Continuum Mechanics for Finite Element Analysis (2 ed.). Cambridge University Press.
[6]
Ralph Byers and Hongguo Xu. 2008. A New Scaling for Newton's Iteration for the Polar Decomposition and its Backward Stability. SIAM J. Matrix Anal. Appl. 30, 2 (2008), 822--843.
[7]
Isaac Chao, Ulrich Pinkall, Patrick Sanan, and Peter Schröder. 2010. A Simple Geometric Model for Elastic Deformations. ACM Trans. Graph. 29, 4, Article 38 (jul 2010), 6 pages.
[8]
Timothy A. Davis and Yifan Hu. 2011. The University of Florida Sparse Matrix Collection. ACM Trans. Math. Softw. 38, 1, Article 1 (dec 2011), 25 pages.
[9]
David Eberly. 2020a. A Robust Eigensolver for 2 × 2 Symmetric Matrices. White Paper. Geometric Tools, PO Box 1866, Mountain View, CA 94042, USA. 5 pages. https://www.geometrictools.com/Documentation/RobustEigenSymmetric2x2.pdf
[10]
David Eberly. 2020b. A Robust Eigensolver for 3 × 3 Symmetric Matrices. White Paper. Geometric Tools, PO Box 1866, Mountain View, CA 94042, USA. 18 pages. https://www.geometrictools.com/Documentation/RobustEigenSymmetric3x3.pdf
[11]
Olaf Etzmuß, Michael Keckeisen, and Wolfgang Straßer. 2003. A Fast Finite Element Solution for Cloth Modelling. In Proceedings of the 11th Pacific Conference on Computer Graphics and Applications (PG '03). IEEE Computer Society, USA, 244.
[12]
Michael S Floater. 1997. Parametrization and smooth approximation of surface triangulations. Computer aided geometric design 14, 3 (1997), 231--250.
[13]
L.P. Franca. 1989. An algorithm to compute the square root of a 3 × 3 positive definite matrix. Computers & Mathematics with Applications 18, 5 (1989), 459--466.
[14]
Zhan Gao, Theodore Kim, Doug L. James, and Jaydev P. Desai. 2009. Semi-Automated Soft-Tissue Acquisition and Modeling Forsurgical Simulation (CASE'09). IEEE Press, 268--273.
[15]
Gene H Golub and Charles F Van Loan. 2012. Matrix computations. Vol. 3. JHU Press.
[16]
Eitan Grinspun, Anil N. Hirani, Mathieu Desbrun, and Peter Schröder. 2003. Discrete Shells. In Proceedings of the 2003 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (San Diego, California) (SCA '03). Eurographics Association, Goslar, DEU, 62--67.
[17]
Gaël Guennebaud, Benoît Jacob, et al. 2021. Eigen v3.8.0. http://eigen.tuxfamily.org.
[18]
Berthold K. P. Horn. 1987. Closed-form solution of absolute orientation using unit quaternions. J. Opt. Soc. Am. A 4, 4 (Apr 1987), 629--642.
[19]
B. J. Hsieh. 1977. Nonlinear formulation of finite element by corotational coordinates. (1 1977).
[20]
Yuanming Hu, Tzu-Mao Li, Luke Anderson, Jonathan Ragan-Kelley, and Frédo Durand. 2019. Taichi: A Language for High-Performance Computation on Spatially Sparse Data Structures. ACM Trans. Graph. 38, 6, Article 201 (nov 2019), 16 pages.
[21]
Frédéric Hélein and John C. Wood. 2008. Harmonic maps: Dedicated to the memory of James Eells. In Handbook of Global Analysis, Demeter Krupka and David Saunders (Eds.). Elsevier, Amsterdam, 417--491.
[22]
G. Irving, J. Teran, and R. Fedkiw. 2004. Invertible Finite Elements for Robust Simulation of Large Deformation. In Proceedings of the 2004 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (Grenoble, France) (SCA '04). Eurographics Association, Goslar, DEU, 131--140.
[23]
Couro Kane, Jerrold E Marsden, Michael Ortiz, and Matthew West. 2000. Variational integrators and the Newmark algorithm for conservative and dissipative mechanical systems. International Journal for numerical methods in engineering 49, 10 (2000), 1295--1325.
[24]
Theodore Kim. 2020. A Finite Element Formulation of Baraff-Witkin Cloth. Eurographics Association, Goslar, DEU.
[25]
Theodore Kim and David Eberle. 2020. Dynamic Deformables: Implementation and Production Practicalities. In ACM SIGGRAPH 2020 Courses (Virtual Event, USA) (SIGGRAPH '20). Association for Computing Machinery, New York, NY, USA, Article 23, 182 pages.
[26]
Fredrik Kjolstad, Shoaib Kamil, Jonathan Ragan-Kelley, David I. W. Levin, Shinjiro Sueda, Desai Chen, Etienne Vouga, Danny M. Kaufman, Gurtej Kanwar, Wojciech Matusik, and Saman Amarasinghe. 2016. Simit: A Language for Physical Simulation. ACM Trans. Graph. 35, 2, Article 20 (May 2016), 21 pages.
[27]
Tassilo Kugelstadt, Dan Koschier, and Jan Bender. 2018. Fast Corotated FEM using Operator Splitting. Computer Graphics Forum (SCA) 37, 8 (2018).
[28]
Minchen Li, Zachary Ferguson, Teseo Schneider, Timothy Langlois, Denis Zorin, Daniele Panozzo, Chenfanfu Jiang, and Danny M. Kaufman. 2020. Incremental Potential Contact: Intersection- and Inversion-free Large Deformation Dynamics. ACM Trans. Graph. (SIGGRAPH) 39, 4, Article 49 (2020).
[29]
Jerrold E. Marsden and Thomas JR. Hughes. 1994. Chapter 3. Dover.
[30]
Aleka McAdams, Yongning Zhu, Andrew Selle, Mark Empey, Rasmus Tamstorf, Joseph Teran, and Eftychios Sifakis. 2011. Efficient Elasticity for Character Skinning with Contact and Collisions. In ACM SIGGRAPH 2011 Papers (Vancouver, British Columbia, Canada) (SIGGRAPH '11). Association for Computing Machinery, New York, NY, USA, Article 37, 12 pages.
[31]
Matthias Müller, Jan Bender, Nuttapong Chentanez, and Miles Macklin. 2016. A Robust Method to Extract the Rotational Part of Deformations. In Proceedings of the 9th International Conference on Motion in Games (Burlingame, California) (MIG '16). Association for Computing Machinery, New York, NY, USA, 55--60.
[32]
Matthias Müller, Julie Dorsey, Leonard McMillan, Robert Jagnow, and Barbara Cutler. 2002. Stable Real-Time Deformations (SCA '02). Association for Computing Machinery, New York, NY, USA, 49--54.
[33]
Andriy Myronenko and Xubo Song. 2009. On the closed-form solution of the rotation matrix arising in computer vision problems.
[34]
R. W. Ogden. 1997. Non-linear Elastic Deformations. Dover.
[35]
Julian Panetta. 2018. Optimizing over SO(3). Technical Report. University of California, Davis.
[36]
Julian Panetta. 2019. Analytic Eigensystems for Isotropic Membrane Energies. Technical Report. University of California, Davis.
[37]
K. B. Petersen and M. S. Pedersen. 2012. The Matrix Cookbook. Version 20121115.
[38]
Guillaume Picinbono, Herve Delingette, and Nicholas Ayache. 2000. Real-Time Large Displacement Elasticity for Surgery Simulation: Non-Linear Tensor-Mass Model. In Proceedings of the Third International Conference on Medical Image Computing and Computer-Assisted Intervention (MICCAI '00). Springer-Verlag, Berlin, Heidelberg, 643--652.
[39]
C. C. Rankin and F. A. Brogan. 1986. An Element Independent Corotational Procedure for the Treatment of Large Rotations. Journal of Pressure Vessel Technology 108, 2 (05 1986), 165--174.
[40]
Soheil Sarabandi, Arya Shabani, Josep M. Porta, and Federico Thomas. 2020. On Closed-Form Formulas for the 3-D Nearest Rotation Matrix Problem. IEEE Transactions on Robotics 36, 4 (2020), 1333--1339.
[41]
Jonathan R Shewchuk. 1994. An Introduction to the Conjugate Gradient Method Without the Agonizing Pain. Technical Report. USA.
[42]
Eftychios Sifakis and Jernej Barbic. 2012. FEM Simulation of 3D Deformable Solids: A Practitioner's Guide to Theory, Discretization and Model Reduction. In ACM SIGGRAPH 2012 Courses (Los Angeles, California) (SIGGRAPH '12). Association for Computing Machinery, New York, NY, USA, Article 20, 50 pages.
[43]
Fun Shing Sin, Daniel Schroeder, and Jernej Barbič. 2013. Vega: non-linear FEM deformable object simulator. In Computer Graphics Forum, Vol. 32. Wiley Online Library, 36--48.
[44]
Breannan Smith, Fernando De Goes, and Theodore Kim. 2018. Stable Neo-Hookean Flesh Simulation. ACM Trans. Graph. 37, 2, Article 12 (mar 2018), 15 pages.
[45]
Breannan Smith, Fernando De Goes, and Theodore Kim. 2019. Analytic Eigensystems for Isotropic Distortion Energies. ACM Trans. Graph. 38, 1, Article 3 (feb 2019), 15 pages.
[46]
Jason Smith and Scott Schaefer. 2015. Bijective Parameterization with Free Boundaries. ACM Trans. Graph. 34, 4, Article 70 (jul 2015), 9 pages.
[47]
Olga Sorkine and Marc Alexa. 2007. As-Rigid-as-Possible Surface Modeling. In Proceedings of the Fifth Eurographics Symposium on Geometry Processing (Barcelona, Spain) (SGP '07). Eurographics Association, Goslar, DEU, 109--116.
[48]
Olga Sorkine-Hornung and Michael Rabinovich. 2017. Least-Squares Rigid Motion Using SVD. Technical Report. Technical Note, Department of Computer Science, ETH Zurich.
[49]
Alexey Stomakhin, Russell Howes, Craig Schroeder, and Joseph M. Teran. 2012. Energetically Consistent Invertible Elasticity (EUROSCA'12). Eurographics Association, 25--32.
[50]
Robert W. Sumner and Jovan Popović. 2004. Deformation Transfer for Triangle Meshes. ACM Trans. Graph. 23, 3 (aug 2004), 399--405.
[51]
Joseph Teran, Eftychios Sifakis, Geoffrey Irving, and Ronald Fedkiw. 2005. Robust Quasistatic Finite Elements and Flesh Simulation (SCA '05). Association for Computing Machinery, New York, NY, USA, 181--190.
[52]
Christopher D. Twigg and Zoran Kacic-Alesic. 2010. Point Cloud Glue: Constraining Simulations Using the Procrustes Transform. In Eurographics/ACM SIGGRAPH Symposium on Computer Animation, Zoran Popovic and Miguel Otaduy (Eds.). The Eurographics Association.
[53]
Bohan Wang, George Matcuk, and Jernej Barbič. 2021. Modeling of Personalized Anatomy using Plastic Strains. ACM Trans. on Graphics (TOG) 40, 2 (2021).
[54]
Jin Wu, Ming Liu, Zebo Zhou, and Rui Li. 2018. Simple Fast Vectorial Solution to The Rigid 3D Registration Problem. CoRR abs/1806.00627 (2018).
[55]
Hongyi Xu, Funshing Sin, Yufeng Zhu, and Jernej Barbič. 2015. Nonlinear Material Design Using Principal Stretches. ACM Trans. Graph. 34, 4, Article 75 (jul 2015), 11 pages.
[56]
I-Cheng Yeh, Chao-Hung Lin, Olga Sorkine, and Tong-Yee Lee. 2010. Template-based 3D Model Fitting Using Dual-domain Relaxation. IEEE Transactions on Visualization and Computer Graphics 99, RapidPosts (2010).
[57]
Jiayi Eris Zhang, Alec Jacobson, and Marc Alexa. 2021. Fast Updates for Least-Squares Rotational Alignment. Computer Graphics Forum (2021).

Cited By

View all

Index Terms

  1. Isotropic ARAP Energy Using Cauchy-Green Invariants

    Recommendations

    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 41, Issue 6
    December 2022
    1428 pages
    ISSN:0730-0301
    EISSN:1557-7368
    DOI:10.1145/3550454
    Issue’s Table of Contents
    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: 30 November 2022
    Published in TOG Volume 41, Issue 6

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. ARAP
    2. cauchy-green invariants
    3. corotational methods
    4. geometry optimization
    5. second-order methods

    Qualifiers

    • Research-article

    Funding Sources

    • Research Grant Council of Hong Kong

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)113
    • Downloads (Last 6 weeks)7
    Reflects downloads up to 30 Nov 2024

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)A Cubic Barrier with Elasticity-Inclusive Dynamic StiffnessACM Transactions on Graphics10.1145/368790843:6(1-13)Online publication date: 19-Dec-2024
    • (2024)Trust-Region Eigenvalue Filtering for Projected NewtonSIGGRAPH Asia 2024 Conference Papers10.1145/3680528.3687650(1-10)Online publication date: 3-Dec-2024
    • (2024)Analytic rotation-invariant modelling of anisotropic finite elementsACM Transactions on Graphics10.1145/366608643:5(1-20)Online publication date: 9-Aug-2024
    • (2024)Physically-based Path Tracer using WebGPU and OpenPBRProceedings of the 29th International ACM Conference on 3D Web Technology10.1145/3665318.3677158(1-6)Online publication date: 25-Sep-2024
    • (2024)More Than Killmonger Locs: A Style Guide for Black Hair (in Computer Graphics)ACM SIGGRAPH 2024 Courses10.1145/3664475.3664535(1-251)Online publication date: 27-Jul-2024
    • (2024)Real-Time Path Guiding Using Bounding Voxel SamplingACM Transactions on Graphics10.1145/365820343:4(1-14)Online publication date: 19-Jul-2024
    • (2024)Discrete Federated Multi-behavior Recommendation for Privacy-Preserving Heterogeneous One-Class Collaborative FilteringACM Transactions on Information Systems10.1145/365285342:5(1-50)Online publication date: 29-Apr-2024
    • (2024)GIPC: Fast and Stable Gauss-Newton Optimization of IPC Barrier EnergyACM Transactions on Graphics10.1145/364302843:2(1-18)Online publication date: 23-Mar-2024
    • (2024)Stabler Neo-Hookean Simulation: Absolute Eigenvalue Filtering for Projected NewtonACM SIGGRAPH 2024 Conference Papers10.1145/3641519.3657433(1-10)Online publication date: 13-Jul-2024
    • (2024)EFVAE: Efficient Federated Variational Autoencoder for Collaborative FilteringProceedings of the 33rd ACM International Conference on Information and Knowledge Management10.1145/3627673.3679818(3176-3185)Online publication date: 21-Oct-2024
    • Show More Cited By

    View Options

    Login options

    Full Access

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media