Method for computing frictional contacts of topologically different bodies in a graphical system

1. A computer-implemented method, comprising:

receiving a representation of a plurality of virtual objects of a model, the plurality of virtual objects comprising a first interacting object and a second interacting object;

receiving a first degree of freedom associated with the first interacting object;

receiving a second degree of freedom associated with the second interacting object;

computing an initial condition using the first degree of freedom and second degree of freedom;

detecting, using the initial condition, a set of contact points between the first interacting object and the second interacting object, the set of contact points comprising one or more contact points;

computing a resultant relative velocity between the first interacting object and second interacting object, given the first degree of freedom and the second degree of freedom by performing at least one iteration of:

(1) computing an updated first relative velocity by minimizing an elastic relaxation energy of the model using a previously computed second velocity and a previously computed error term;

(2) computing an updated second relative velocity by minimizing a frictional contact projection using the set of contact points and the updated first relative velocity and the previously computed error term; and

(3) updating the previously computed error term to produce an updated error term; and

computing the resultant relative velocity based on at least one of the updated first relative velocity and the updated second relative velocity.

2. The computer-implemented method of claim 1 , wherein the first interacting object and/or the second interacting object comprise tessellated meshes.

3. The method of claim 1 , wherein the first interacting object and/or the second interacting object represent soft bodies.

4. The method of claim 1 , wherein the first interacting object and the second interacting object are portions of a larger object.

5. The computer-implemented method of claim 1 , wherein the frictional contact projection corresponds to a frictional displacement based on a normal portion and a tangential portion of the updated second relative velocity at the one or more contact points.

6. The computer-implemented method of claim 1 , wherein an interacting object of the plurality of virtual objects has associated degrees of freedom including a velocity and a force.

7. The computer-implemented method of claim 1 , wherein detecting the set of contact points comprises computing a proximity of the first interacting object and the second interacting object.

8. The computer-implemented method of claim 1 , wherein computing the resultant relative velocity comprises assigning the resultant relative velocity a value of the at least one of the updated first relative velocity and the updated second relative velocity from a final iteration of computing the resultant relative velocity.

9. The computer-implemented method of claim 1 , further comprising:

linearizing the model to obtain a symmetric operator approximating a square matrix of second-order partial derivatives representing a total energy of the model;

from the symmetric operator, computing a diagonal stiffness matrix;

computing a linear solver preconditioner based on the diagonal stiffness matrix and the symmetric operator; and

computing the updated first relative velocity by minimizing the elastic relaxation energy using the linear solver preconditioner.

10. The computer-implemented method of claim 1 , wherein the updated error term is computed using an alternating directions method of multipliers.

11. A non-transitory computer-readable storage medium storing instructions, which when executed by at least one processor of a computer system, causes the computer system to carry out the computer-implemented method of claim 1 .

12. A computer-implemented method, comprising:

obtaining a model, wherein the model includes degrees of freedom of a plurality of simulated dynamic objects encoded in a plurality of positions in the model;

detecting proximity and collisions in the model;

linearizing the model to obtain a symmetric operator approximating a square matrix of second-order partial derivatives representing a total energy of the model;

from the symmetric operator, computing a diagonal stiffness matrix;

computing a linear solver preconditioner based on the diagonal stiffness matrix and the symmetric operator; and

performing at least one iteration of:

1) iteratively updating a first velocity by conducting a first series of iterations to solve an elastic relaxation model to form an updated first velocity;

2) iteratively updating a second velocity by conducting a second series of iterations to solve a frictional contact projection to form an updated second velocity; and

3) updating an error term computed from the first velocity and the second velocity; and

computing, based on at least one of the first velocity and second velocity, a resultant velocity.

13. The computer-implemented method of claim 12 , wherein iteratively updating the first velocity to solve the elastic relaxation model comprises:

determining an exit criterion;

concluding iterations of updating if the exit criterion is met;

computing an interim velocity using the linear solver preconditioner by solving an elastic relaxation problem based on the symmetric operator, the diagonal stiffness matrix, and a previously computed second velocity; and

updating the second velocity to the updated second velocity based on the interim velocity and the error term.

14. The computer-implemented method of claim 13 , wherein the exit criterion corresponds to a number of iterations being equal to or greater than a predetermined maximum number of iterations.

15. The computer-implemented method of claim 13 , wherein the exit criterion corresponds to the updated first velocity being approximately equal to the first velocity and the updated second velocity being approximately equal to the second velocity.

16. The computer-implemented method of claim 13 , wherein iteratively updating the second velocity to solve the frictional contact projection comprises:

detecting a plurality of contacts in the model;

for a given contact of the plurality of contacts, computing the interim velocity based on a previously computed first velocity and the error term;

for the given contact, computing a frictional displacement based on the interim velocity and the diagonal stiffness matrix, producing a plurality of frictional displacements; and

applying the plurality of frictional displacements to the frictional contact projection to update the second velocity.

17. A non-transitory computer-readable storage medium storing instructions, which when executed by at least one processor of a computer system, causes the computer system to carry out the computer-implemented method of claim 12 .