IP Library › Granted Patent US 12,216,969
Granted Patent B2
US 12,216,969 · App. 17/012,709 · Granted Feb 4, 2025

Methods of contact for simulation

Inventors: Miles Macklin (Auckland, NZ); Matthias Mueller-Fischer (Zürich, CH); Nuttapong Chentanez (Bangkok, TH); Stefan Jeschke (Vienna, AT); Tae-Yong Kim (San Jose, CA)
Assignee: NVIDIA Corporation
G06F30/23G06F17/16G06F30/27G06N3/08G06T1/20G06T15/005G06T15/06G06T17/20G06F2111/04G06F2113/12
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,216,969
App. No.
17/012,709
Granted
Feb 4, 2025
Kind
B2
Abstract

Apparatuses, systems, and techniques apply to a force-based (e.g., primal) formulation for object simulation. In at least one embodiment, updates to the force-based formulation is determined by solving for constraints that are to be satisfied when simulating rigid bodies (e.g., contact rich scenarios).

Claims (45)

1. A system, comprising:

one or more computers having one or more processors to:

determine one or more forces in a simulation of one or more objects to determine a set of constraints to be satisfied for the simulation where the one or more objects are to be simulated using a force-based formulation, wherein the set of constraints include at least one of velocity approximations, contact forces, or friction coefficients between the one or more objects;

apply a preconditioner to the force-based formulation to perform a gradient descent;

solve an energy minimization problem, using a primal formulation, to solve one or more constraints of the set of constraints for simulation; and

simulate the one or more objects to satisfy the set of constraints of the simulation by updating states of the one or more objects based on results from performing the gradient descent.

2. The system of claim 1 , wherein the preconditioner comprises a Hessian approximation.

3. The system of claim 1 , wherein the set of constraints for the simulation are satisfied at two or more frames of the simulation using an implicit penalty formulation.

4. The system of claim 1 , wherein the force-based formulation with the preconditioner is a differentiable contact model using Coulomb friction.

5. The system of claim 1 , wherein the one or more processors are further to perform collision detection of the one or more objects, during simulation, to determine the set of constraints.

6. The system of claim 1 , wherein the one or more processors are further to compute contact forces in the force-based formulation that satisfy the set of constraints for the simulation.

7. The system of claim 1 , wherein the one or more objects are modeled by a triangle mesh.

8. A processor, comprising:

one or more arithmetic logic units (ALUs) to:

determine one or more forces in a simulation of one or more objects to determine a set of constraints;

perform collision detection of the one or more objects that are to be simulated using a primal formulation;

generate a preconditioner for the primal formulation to perform a gradient descent;

solve an energy minimization problem, using the primal formulation, to simulate the one or more objects; and

update states of the one or more objects, based on results from the gradient descent and the set of constraints, to simulate collisions between the one or more objects.

9. The processor of claim 8 , wherein the one or more ALUs are to generate the preconditioner for the primal formulation using approximations of second derivatives.

10. The processor of claim 9 , wherein the one or more ALUs are to generate the preconditioner by dropping higher order terms corresponding to a geometric stiffness.

11. The processor of claim 8 , wherein the primal formulation with the preconditioner is based on a differentiable contact model using Coulomb friction.

12. The processor of claim 8 , wherein the collision detection comprises determining the set of constraints when simulating the one or more objects, wherein the set of constraints include friction coefficients.

13. The processor of claim 12 , wherein the one or more ALUs are to satisfy the set of constraints at each frame, during simulation, using an implicit penalty formulation.

14. A method, comprising:

using one or more graphics processing units (GPUs) to execute code that performs a set of instructions that:

determines one or more constraints by at least determining one or more forces in a simulation of one or more objects;

performs a gradient descent by applying a preconditioner for a primal formulation;

solve an energy minimization problem, using the primal formulation, to solve the one or more constraints for simulation; and

uses one or more gradients resulting from performing the gradient descent to update states of the one or more objects to satisfy the one or more constraints for the simulation.

15. The method of claim 14 , wherein the one or more GPUs are further to execute code to:

generate a square matrix of second-order partial derivatives of a multivariable function associated with the energy minimization problem; and

use the generated matrix as the preconditioner to perform the gradient descent.

16. The method of claim 15 , wherein the preconditioner is a diagonally invertible preconditioner.

17. The method of claim 15 , wherein the primal formulation with the preconditioner is a differentiable contact model using Coulomb friction.

18. The method of claim 14 , wherein the one or more objects comprise triangle meshes that, when simulated, experience contact forces.

19. The method of claim 14 , wherein the one or more GPUs are further to execute code to use the updated states of the one or more objects when performing a simulation for rigid body contacts.

20. The method of claim 14 , wherein the one or more GPUs are further to execute code to use the updated states of the one or more objects when performing simulation for at least one of:

generation of data for training a neural network of a control stack of an autonomous or semi-autonomous machine;

generation of data for training a neural network of a perception stack of an autonomous or semi-autonomous machine;

validation of a control stack of an autonomous or semi-autonomous machine;

validation of a perception stack of an autonomous or semi-autonomous machine;

generation of graphical output using ray-tracing for simulating lighting conditions in a rendered scene;

generation of data for a dataset used to train a deep learning model; or

generation of data for augmenting a dataset used to train a deep learning model.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Oct 13, 2020
From: MACKLIN, MILES; MUELLER-FISCHER, MATTHIAS; CHENTANEZ, NUTTAPONG; JESCHKE, STEFAN; KIM, TAE-YONG
To: NVIDIA CORPORATION
Reel/Frame 054042/0243 →
Continuity (1)
Related Publication 20220075914A1 · Mar 10, 2022
References Cited (67)
US 20200082589A1 · Teran · 2020 [cited by examiner]
Baraff, David et al. “Large Steps in Cloth Simulation”, 1998, Siggraph. (Year: 1998). [cited by examiner]
Wang, Huamin et al., “Descent Methods for Elastic Body Simulation on the GPU”, Nov. 2016, ACM Trans. Graph. 35, 6, Article 212, ACM. (Year: 2016). [cited by examiner]
Baraff, David, “Fast Contact Force Computation for Nonpenetrating Rigid Bodies”, Jul. 24-29, 1994, Siggraph '94, ACM. (Year: 1994). [cited by examiner]
Ding, Ounan et al., “Penalty Force of Coupling Materials with Coulomb Friction”, Jul. 2020, IEEE Transactions on Visualization and Computer Graphics, vol. 26, No. 7, IEEE. (Year: 2020). [cited by examiner]
Wong. S.-K. et al., “Modeling and Simulation Techniques for Garments”, 2011, Woodhead Publishing Limited. (Year: 2011). [cited by examiner]
Jeon, Inyong et al., “Constrainable Multigrid for Cloth”, 2013, Pacific Graphics, vol. 32, No. 7, The Eurographics Association and John Wiley and Sons Ltd. (Year: 2013). [cited by examiner]
Pan, Zherong et al., “GPU-Based Contact-Aware Trajectory Optimization Using a Smooth Force Model”, Jul. 26-28, 2019, SCA '19, Association for Computing Machinery. (Year: 2019). [cited by examiner]
Andrews et al., “Geometric Stiffness for Real-time Constrained Multibody Dynamics,” Computer Graphics Forum, vol. 36, Wiley Online Library, 2017, 12 pages. [cited by applicant]
Baraff et al., “Large Steps in Cloth Simulation,” Proceedings of the 25th Annual Conference on Computer graphics and Interactive Techniques, ACM, Jul. 19-24, 1998, 12 pages. [cited by applicant]
Batty et al., “A Fast Variational Framework for Accurate Solid-Fluid Coupling,” ACM Transactions on Graphics, 26(3): Jul. 2007, 7 pages. [cited by applicant]
Bell et al., “Particle-Based Simulation of Granular Materials,” Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer animation, 2005, 10 pages. [cited by applicant]
Bender et al., “Interactive Simulation of Rigid Body Dynamics in Computer Graphics,” Computer Graphics Forum 33(1): Feb. 2014, 25 pages. [cited by applicant]
Bertsekas, “Nonlinear Programming,” Athena Scientific, 1995, 372 pages. [cited by applicant]
Bouaziz et al., “Projective Dynamics: Fusing Constraint Projections for Fast Fimulation,” ACM Transactions on Graphics, 33(4): 2014, 11 pages. [cited by applicant]
Boyd et al., “Convex Optimization,” Cambridge University Press, 2004, 730 pages. [cited by applicant]
Chen et al., “EigenFit for Consistent Elastodynamic Simulation Across Mesh Resolution,” Proceedings of the 18th annual ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 2019, 13 pages. [cited by applicant]
Daviet et al., “A Hybrid Iterative Solver for Robustly Capturing Coulomb Friction in Hair Dynamics,” ACM Transactions on Graphics, vol. 30, 2011, 12 pages. [cited by applicant]
Desbrun et al., “Interactive Animation of Structured Deformable Objects,” 1999, 8 pages. [cited by applicant]
Ding et al., “Penalty Force for Coupling Materials with Coulomb Friction,” IEEE Transactions on Visualization and Computer Graphics, 2019, 13 pages. [cited by applicant]
Drumwright, “A Fast and Stable Penalty Method for Rigid Body Simulation,” IEEE Transactions on Visualization and Computer Graphics 14(1): 2007, 12 pages. [cited by applicant]
Ebert et al., “Texturing & Modeling: A Procedural Approach,” Morgan Kaufmann, 2003, 721 pages. [cited by applicant]
Erleben, “Methodology for Assessing Mesh-Based Contact Point Methods,” ACM Transactions on Graphics, 37(3): Article 39, Jul. 2018, 30 pages. [cited by applicant]
Erleben, “Numerical Methods for Linear Complementarity Problems in Physics-Based Animation, ” ACM SIGGRAPH 2013 Courses, Feb. 2013, 42 pages. [cited by applicant]
Erleben, “Rigid Body Contact Problems using Proximal Operators, ” Proceedings of the ACM Symposium on Computer Animation, 2017, 12 pages. [cited by applicant]
Featherstone, “Rigid Body Dynamics Algorithms, ” Springer, 2014, 276 pages. [cited by applicant]
Gast et al., “Optimization Integrator for Large Time Steps,” IEEE transactions on Visualization and Computer Graphics, 21(10): 2015, 13 pages. [cited by applicant]
Goldenthal et al., “Efficient Simulation of Inextensible Cloth,” ACM Transactions on Graphics, vol. 26, 2007, 7 pages. [cited by applicant]
Guendelman et al., “Nonconvex Rigid Bodies with Stacking,” ACM Transactions on Graphics, 22(3): Jul. 2003, 8 pages. [cited by applicant]
Horak et al., “On the Similarities and Differences Among Contact Models in Robot Simulation,” IEEE Robotics and Automation Letters, 4(2): Apr. 2019. [cited by applicant]
IEEE, “IEEE Standard 754-2008 (Revision of IEEE Standard 754-1985): IEEE Standard for Floating-Point Arithmetic,” Aug. 29, 2008, 70 pages. [cited by applicant]
Johnson, “Contact Mechanics,” Cambridge University Press, 1985, 462 pages. [cited by applicant]
Kang et al., “Fast and Stable Animation of Cloth with an Approximated Implicit Method,” Proceedings Computer Graphics International, IEEE, 2000, 9 pages. [cited by applicant]
Kaufman et al., “Staggered Projections for Frictional Contact in Multibody Systems,” ACM Transactions on Graphics, vol. 27, 2008, 11 pages. [cited by applicant]
Lee et al., “Angle of Repose and Angle of Marginal Stability: Molecular Dynamics of Granular Particles,” Journal of Physics A: Mathematical and General 26, 1993, 11 pages. [cited by applicant]
Li et al., “Fast Simulation of Deformable Characters with Articulated Skeletons in Projective Dynamics,” Proceedings of the 18th Annual ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 2019, 10 pages. [cited by applicant]
Liu et al., “Fast Simulation of Mass-Spring Systems,” ACM Transactions on Graphics, 32(6): 2013, 7 pages. [cited by applicant]
Liu et al., “On the Limited Memory BFGS Method for Large Scale Optimization,” Mathematical Programming 45, 1989, 27 pages. [cited by applicant]
Liu et al., “Quasi-newton Methods for Real-Time Simulation of Hyperelastic Materials,” ACM Transactions on Graphics, 36(3): 2017, 16 pages. [cited by applicant]
Macklin et al., “XPBD: Position-Based Simulation of Compliant Constrained Dynamics,” Proceedings of the 9th International Conference on Motion in Games, 2016, 6 pages. [cited by applicant]
Marhefka et al., “Simulation of Contact using a Nonlinear Damping Model,” Proceedings of IEEE International Conference on Robotics and Automation, vol. 2, 1996, 7 pages. [cited by applicant]
Martin et al., “Unified Simulation of Elastic Rods, Shells, and Solids,” ACM, Article 39, Mar. 2010, 10 pages. [cited by applicant]
Mazhar et al., “An Analysis of Several Methods for Handling Hard-Sphere Frictional Contact in Rigid Multibody Dynamics,” 2014, 25 pages. [cited by applicant]
Müller et al., “Position Based Dynamics”, Journal of Visual Communication and Image Representation, 18(2): 2007, 10 pages. [cited by applicant]
Narain et al., “Adaptive Anisotropic Remeshing for Cloth Simulation,” ACM Transactions on Graphics 31(6): Nov. 2012, 10 pages. [cited by applicant]
Narain et al., ADMM ? Projective Dynamics: Fast Simulation of General Constitutive Models. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 2016, 8 pages. [cited by applicant]
Niebe et al., “Numerical Methods for Linear Complementarity Problems in Physics-Based Animation,” Synthesis Lectures on Computer Graphics and Animation 7(1): 2015, 155 pages. [cited by applicant]
Overby et al., ADMM ? Projective Dynamics: Fast Simulation of Hyperelastic Models with Dynamic Constraints. IEEE Transactions on Visualization and Computer Graphics 23(10): 2017, 14 pages. [cited by applicant]
Pan et al., “GPU-Based Contact-Aware Trajectory Optimization Using a Smooth Force Model,” Association for Computing Machinery, Article 4, 2019, 12 pages. [cited by applicant]
Servin et al., “Interactive Simulation of Elastic Deformable Materials,” Proceedings of SIGRAD Conference, 2006, 11 pages. [cited by applicant]
Smith et al., “Reflections on Simultaneous Impact,” ACM Transactions on Graphics, 31(4): 2012, 12 pages. [cited by applicant]
Soler et al., “Cosserat Rods with Projective Dynamics,” Computer Graphics Forum, 37(8): Wiley Online Library, 2018, 11 pages. [cited by applicant]
Stam, “Nucleus: Towards a Unified Dynamics Solver for Computer Graphics,” Computer-Aided Design and Computer Graphics, IEEE International Conference, 2009, 11 pages. [cited by applicant]
Stewart, “An Implicit Time-Stepping Scheme for Rigid Body Dynamics with Inelastic Collisions and Coulomb Friction,” 39(15): 1996, 8 pages. [cited by applicant]
Stewart, “Rigid-Body Dynamics with Friction and Impact,” SIAM Review, 42(1): 2000, 37 pages. [cited by applicant]
Tang et al., “Continuous Penalty Forces,” ACM Transactions on Graphics, 31(4): 2012, 9 pages. [cited by applicant]
Tang et al., “I-Cloth: Incremental Collision Handling for GPU-Based Interactive Cloth Simulation,” ACM Transactions on Graphics, 37(6): 2018, 10 pages. [cited by applicant]
Todorov et al., “MuJoCo : A Physics Engine for Model-Based Control,” 2012, 8 pages. [cited by applicant]
Todorov, Convex and Analytically-Invertible Dynamics with Contacts and Constraints: Theory and Implementation in MuJoCo, IEEE International Conference on Robotics and Automation, 2014, 8 pages. [cited by applicant]
Tonge et al., “Mass Splitting for Jitter-Free Parallel Rigid Body Simulation,” ACM Transactions on Graphics, 31(4): Jul. 2012, 8 pages. [cited by applicant]
Tournier et al., Stable Constrained Dynamics, ACM Transactions on Graphics, 34(4): 2015, 10 pages. [cited by applicant]
Wang et al., “Descent Methods for Elastic Body Simulation on the GPU,” ACM Transactions on Graphics, 35(6): 2016, 10 pages. [cited by applicant]
Wang, “A Chebyshev Semi-Iterative Approach for Accelerating Projective and Position-Based Dynamics,” ACM Transactions on Graphics, 34(6): 2015, 9 pages. [cited by applicant]
Xu et al., “Implicit Multibody Penaltybaseddistributed Contact,” IEEE Transactions on Visualization and Computer Graphics, 20(9): 2014, 14 pages. [cited by applicant]
Yamane et al., “Stable Penalty-Based Model of Frictional Contacts,” Proceedings IEEE International Conference on Robotics and Automation, 2006, 6 pages. [cited by applicant]
Zhang et al., “Accelerating ADMM for Efficient Simulation and Optimization,” ACM Transactions on Graphics, 38(6): 2019, 21 pages. [cited by applicant]
Zheng et al., “Toward High-Quality Modal Contact Sound,” ACM Transactions on Graphics, 30(4): Aug. 2011, 11 pages. [cited by applicant]