Large mesh deformation using the volumetric graph laplacian

• US 20060290693A1
• Filed: 06/22/2005
• Published: 12/28/2006
• Est. Priority Date: 06/22/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhou, Kun, Shum, Heung-Yeung, Guo, Baining, Snyder, John Michael, Liu, Xinguo
• Granted Patent: US 7,286,127 B2
• Time in Patent Office: Days
• US Class Current: 345/420
• CPC Class Codes: G06T 13/20 3D [Three Dimensional] animation
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

Large mesh deformation using the volumetric graph Laplacian is described. In one aspect, information is received from a user, wherein the information indicates how an original mesh is to be deformed. The original mesh is then deformed based on the information and application of a volumetric differential operator to a volumetric graph generated from the original mesh.

Claims

1. A computer-implemented method comprising:

receiving information from a user indicating how an original mesh is to be deformed; and

deforming the original mesh based on the information and a volumetric differential operator applied to a volumetric graph generated from the original mesh.

2. A method of claim 1, wherein the information is one or more 2-D control curves derived from one or more respective 3-D control curves specified with respect to the original mesh.

3. A method of claim 1, wherein the information is one or more new 2-D control curves specified by a user to represent deformation of the original mesh.

4. A method of claim 1, wherein deforming the original mesh is independent of solidly-meshing surface interior of the original mesh.

5. A method of claim 1, wherein the volumetric differential operator is a Laplacian of the volumetric graph.

6. A method of claim 1, wherein the volumetric differential operator is a Laplacian of the volumetric graph, the Laplacian of the volumetric graph encoding volumetric details of the original mesh as a volumetric difference between each point of multiple points in a volumetric graph and a volumetric average of neighbors of each point.

7. A method of claim 1, wherein the volumetric differential operator is a Laplacian of the volumetric graph, the Laplacian of the volumetric graph encoding volumetric details to impose volumetric constraints that prevent unnatural changes in volume when deforming the original mesh, the volumetric details including points outside of the original mesh and a simple lattice-structure of points inside of the original mesh.

8. A method of claim 1, wherein the method further comprises:

allowing a user to specify one or more 3-D control curves on the surface of the original mesh;

presenting a respective 2-D control curve to the user corresponding to at least one of the one or more 3-D control curves; and

allowing the user to modify the 2-D control curve to specify movement of a set of points associated with the 2-D control curve responsive to deformation.

9. A method of claim 1, wherein the method further comprises generating the volumetric graph by:

creating inside and outside graph structures, the inside graph structure being a first lattice constructed to lie within the original mesh, the outside graph structure being a second lattice constructed to lie outside of the original mesh;

building a connection between the inside graph structure and the original mesh; and

connecting details of the outside graph structure with the original mesh.

10. A method of claim 1, wherein the method further comprises generating the volumetric graph by:

creating inside and outside graph structures, the inside graph structure being a first lattice constructed to lie within the original mesh, the outside graph structure being a second lattice constructed to lie outside of the original mesh;

preventing large volume changes during large mesh deformation operations associated with the original mesh using information based on the inside graph structure; and

obviating local self-intersection of vertices during large mesh deformation operations associated with the original mesh based on information based on the outside graph structure.

11. A method of method of claim 1, wherein deforming the original mesh further comprises balancing preservation of original surface details associated with the original mesh, a user'"'"'s chosen deformation locations, and preservation of volumetric details specified by a Laplacian of the volumetric graph.

12. A computer-implemented method comprising:

presenting a user interface to a user, the user interface displaying a 3-D mesh;

allowing the user to specify a 3-D control curve with respect to the 3-D mesh;

projecting the 3-D control curve onto a plane as a 2-D control curve;

allowing the user to edit the 2-D control curve to create a modified control curve that specifies targeted deformation of the 3-D mesh; and

deforming the 3-D mesh based on a volumetric graph Laplacian derived from the 3-D mesh and the modified control curve.

13. A method of claim 12, wherein allowing the user to edit the 2-D control curve further comprises presenting the user with an opportunity to create a new curve, the new curve being the modified control curve.

14. A method of claim 12, wherein allowing the user to edit the 2-D control curve further comprises presenting B-spline control points on the 2-D control curve, the B-spline control points being selectable for manipulating shape and size of the 2-D control curve.

15. A method of claim 12, wherein deforming the 3-D mesh further comprises:

creating a volumetric graph based on vertices of the 3-D mesh, the volumetric graph comprising a simple-lattice of vertices inside of a surface associated with the 3-D mesh and vertices outside of the surface; and

determining a Laplacian of the volumetric graph to encode volumetric details as a difference between each point of multiple points in the volumetric graph and an average of points neighboring the point.

16. A method of claim 12, wherein deforming the 3-D mesh further comprises preventing large volume changes during large mesh deformation of the original mesh using information from a simple lattice formed inside of the 3-D mesh.

17. A method of claim 12, wherein deforming the 3-D mesh further comprises preventing self-intersections of volume during large mesh deformations of the 3-D mesh using information from a graph generated outside of a surface of the 3-D mesh.

18. A method of claim 12, wherein deforming the 3-D mesh further comprises balancing preservation of original surface details associated with the 3-D mesh, a user'"'"'s chosen deformation locations, and preservation of volumetric details specified by the volumetric graph Laplacian.

19. A method of claim 12, further comprising creating a simple-lattice graph structure inside of the 3-D mesh using simplification envelopes to iteratively offset each vertex of multiple vertices of the original mesh in the direction opposite normal of the vertex;

generating an outside graph by iteratively offsetting each vertex of the original mesh outwards of a surface corresponding to the original mesh, the outside graph comprising vertices outside of the 3-D mesh;

building connections between the inside and outside graphs and the original mesh to create a volumetric graph.

20. A method of claim 19, further comprising simplifying the volumetric graph using edge collapse and smoothing operations.