Geometric multigrid on incomplete linear octrees for simulating deformable animated characters

Patent metadata

Field	Value
Publication number	US-2016292902-A1
Application number	US-201615002312-A
Country	US
Kind code	A1
Filing date	Jan 20, 2016
Priority date	Apr 3, 2015
Publication date	Oct 6, 2016
Grant date	—

Abstract

A method and system for simulation of deformation of elastic materials are disclosed herein. A matrix-free geometric multigrid method utilizing a direct coarse grid discretization is presented for the solution of linear systems resulting from an octree discretization of the equations of corotational linear elasticity. The diagonal component of the stiffness matrix needed for the multigrid smoother is calculated without generating the stiffness matrix. The use of an incomplete linear octree data structure supports the efficient simulation of objects with complicated boundaries. Furthermore, the method is robust to large deformations, making it suitable for character skinning applications in computer animation.

First claim

What is claimed is:

1 . A method for deforming computer-generated objects, the method comprising:
receiving at one or more computer systems, information identifying a computer-generated object; receiving information identifying a space partitioning tree grid associated with the computer-generated object; receiving information identifying a set of material properties for the first computer generated object; receiving kinematic information associated with the computer-generated object; determining a response of a continuum representation of a material at one or more cells forming the space partitioning tree grid according to the set of material properties and the kinematic information associated with the computer-generated object based on a calculated diagonal component of a stiffness matrix associated with a stabilized energy discretization over the one or more cells of the space partitioning tree grid utilizing a one point quadrature at each of the one or more cells; and generating information configured to deform the first object from a first configuration to a second configuration based on the determined response of the continuum representation of the material.

2 . The method of claim 1 , wherein the space partitioning tree grid comprises an octree grid.

3 . The method of claim 2 , wherein the octree grid is formed by a plurality of hexahedral cells having different sizes, and wherein each of the cells forming the octree grid has eight nodes.

4 . The method of claim 3 , wherein the diagonal component of the stiffness matrix is calculated without generation of the stiffness matrix.

5 . The method of claim 4 , further comprising storing the information configured to deform the first object from the first configuration to the second configuration in a storage device associated with the one or more computer systems.

6 . The method of claim 3 , wherein determining the response of the continuum representation of a material at one or more of the cells forming the octree grid according to the set of material properties and the kinematic information associated with the computer-generated object based on a calculated diagonal component of a stiffness matrix further comprises:
identifying a first cell of the octree grid having a first size; identifying a second cell of the octree grid having a second size, wherein the second cell is smaller than the first cell, and wherein the first cell and the second cell are adjacent; and identifying a hanging node of the second cell, wherein the hanging node is at a location on the first cell but not co-located with a node of the first cell.

7 . The method of claim 6 , further comprising:
identifying a plurality of shape functions, wherein a location of each of the nodes of the second cell are associated with some of the plurality of shape functions; generating a matrix of a derivative of the some of the shape functions associated with each of the nodes of the second cell; modifying the some of the shape functions defining the location of the hanging node of the second cell; and generating a modified matrix including a derivative of the modified some of the shape functions.

8 . The method of claim 7 , wherein modifying the some of the shape functions defining the location of the hanging node of the second cell comprises;
identifying at least one non-hanging node of the first cell adjacent to the hanging node; determining shape functions of the at least one non-hanging node adjacent to the hanging node; and interpolating the value of the hanging node from the shape functions of the at least one non-hanging node adjacent to the hanging node.

9 . The method of claim 8 , wherein the diagonal component of the stiffness matrix is calculated with the modified matrix.

10 . The method of claim 9 , wherein the diagonal component is calculated as the combination of an auxiliary component and a Laplacian component.

11 . A non-transitory computer-readable medium storing computer-executable code for deforming computer-generated objects, the non-transitory computer-readable medium comprising:
code for receiving at one or more computer systems, information identifying a computer-generated object; code for receiving information identifying a space partitioning tree grid associated with the computer-generated object; code for receiving information identifying a set of material properties for the first computer generated object; code for receiving kinematic information associated with the computer-generated object; code for determining a response of a continuum representation of a material at one or more cells forming the space partitioning tree grid according to the set of material properties and the kinematic information associated with the computer-generated object based on a calculated diagonal component of a stiffness matrix associated with a stabilized energy discretization over the one or more cells of the space partitioning tree grid utilizing a one point quadrature at each of the one or more cells; and code for generating information configured to deform the first object from a first configuration to a second configuration based on the determined response of the continuum representation of the material.

12 . The non-transitory computer-readable medium of claim 11 , wherein the space partitioning tree grid comprises an octree grid.

13 . The non-transitory computer-readable medium of claim 12 , wherein the octree grid is formed by a plurality of hexahedral cells having different sizes, and wherein each of the cells forming the octree grid has eight nodes.

14 . The non-transitory computer-readable medium of claim 13 , wherein the diagonal component of the stiffness matrix is calculated without generation of the stiffness matrix.

15 . The non-transitory computer-readable medium of claim 14 , further comprising code for storing the information configured to deform the first object from the first configuration to the second configuration in a storage device associated with the one or more computer systems.

16 . The non-transitory computer-readable medium of claim 13 , wherein determining the response of the continuum representation of a material at one or more of the cells forming the octree grid according to the set of material properties and the kinematic information associated with the computer-generated object based on a calculated diagonal component of a stiffness matrix further comprises:
identifying a first cell of the octree grid having a first size; identifying a second cell of the octree grid having a second size, wherein the second cell is smaller than the first cell, and wherein the first cell and the second cell are adjacent; and identifying a hanging node of the second cell, wherein the hanging node is at a location on the first cell but not co-located with a node of the first cell.

17 . The non-transitory computer-readable medium of claim 16 , further comprising:
code for identifying a plurality of shape functions, wherein a location of each of the nodes of the second cell are associated with some of the plurality of shape functions; code for generating a matrix of a derivative of the some of the shape functions associated with each of the nodes of the second cell; code for modifying the some of the shape functions defining the location of the hanging node of the second cell; and code for generating a modified matrix including a derivative of the modified some of the shape functions.

18 . The non-transitory computer-readable medium of claim 17 , wherein
modi

Assignees

• Disney Entpr Inc

Inventors

• Milne Andrew
• Tamstorf Rasmus
• Stomakhin Alexey
• Mclaughlin Mark

Classifications

• G06T13/00

  Animation · CPC title

• G06T17/005

  Tree description, e.g. octree, quadtree · CPC title

• G06T2219/2021

  Shape modification · CPC title

• G06T19/20

  Editing of three-dimensional [3D] images, e.g. changing shapes or colours, aligning objects or positioning parts · CPC title

• G06T9/40 Primary

  Tree coding, e.g. quadtree, octree · CPC title