TECHNIQUE FOR FILLING HOLES IN A THREE-DIMENSIONAL MODEL

• US 20140253551A1
• Filed: 03/05/2013
• Published: 09/11/2014
• Est. Priority Date: 03/05/2013
• Status: Active Grant

• Current Assignee: Autodesk, Inc.
• Original Assignee: Autodesk, Inc.
• Inventors: SCHMIDT, Ryan Michael
• Granted Patent: US 9,135,750 B2
• Time in Patent Office: Days
• US Class Current: 345/427
• CPC Class Codes: G06T 15/00 3D [Three Dimensional] image rendering
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

A mesh repair engine is configured to repair a hole in a three-dimensional (3D) model by (i) filling the hole with a rough mesh, (ii) refining the rough mesh, (iii) collapsing the refined mesh, (iv) refining the collapsed mesh, (v) flattening the refined, collapsed mesh, and then (vi) deforming the flattened mesh into a 3D surface that smoothly fills the hole in the 3D model. One advantage of the disclosed repair engine and associated hole repair technique is that the mesh repair engine is capable of generating polygons that fill regions of a 3D model that are not defined. Consequently, an end-user of the mesh repair tool is able to generate watertight 3D models from previously incomplete and non-watertight 3D models.

Claims

1. A computer-implemented method for filling a hole in a three-dimensional (3D) model, the method comprising:

identifying the hole in the 3D model;

generating a refined quasi-developable surface that is disposed within the hole in the 3D model;

generating a two-dimensional (2D) surface based on the refined quasi-developable surface; and

deforming the 2D surface into a 3D surface that fills the hole in the 3D model.

2. The computer-implemented method of claim 1, wherein generating the refined quasi-developable surface comprises:

generating a triangle fan that covers the hole in the 3D model;

generating a refined surface by decomposing each triangle associated with the triangle fan into a first set of refined triangles, wherein each refined triangle in the first set of refined triangles complies with a first geometric criterion;

generating a quasi-developable surface by flattening the refined surface; and

generating the refined quasi-developable surface by decomposing each triangle associated with the quasi-developable surface into a second set of refined triangles, wherein each refined triangle in the second set of refined triangles complies with a second geometric criterion.

3. The computer-implemented method of claim 2, wherein the triangle fan comprises a central vertex located approximately equidistant from each boundary vertex that surrounds the hole in the 3D model, and a set of edges that connects the central vertex to each boundary vertex that surrounds the hole in the 3D model.

4. The computer-implemented method of claim 2, wherein the first geometric criterion indicates that each triangle in the first set of refined triangles is substantially equilateral and has a first size, and the second geometric criterion indicates that each triangle in the second set of refined triangles is substantially equilateral and has a second size.

5. The computer-implemented method of claim 2, wherein generating the quasi-developable surface by flattening the refined surface comprises:

collapsing a first subset of refined triangles included within the first set of refined triangles into a first triangle, wherein triangles in the first subset of triangles reside adjacent to one another within the refined surface;

collapsing a second subset of refined triangles included within the first set of refined triangles into a second triangle, wherein triangles in the second subset of refined triangles reside adjacent to one another within the refined surface;

determining that inverting the second triangle decreases an angle between a surface normal associated with the first triangle and a surface normal associated with the second triangle; and

inverting the second triangle.

6. The computer-implemented method of claim 1, wherein generating the 2D surface based on the refined quasi-developable surface comprises computing a planar parameterization of the quasi-developable surface via a conformal map.

7. The computer-implemented method of claim 1, wherein deforming the 2D surface into the 3D surface that fills the hole in the 3D model comprises:

transforming the 2D surface into a flat 3D surface;

positioning each boundary vertex associated with the flat 3D surface at a location corresponding to a boundary vertex associated with the hole in the 3D model;

generating the 3D surface by projecting each interior vertex associated with the flat 3D surface to a different 3D coordinate based on the locations of the boundary vertices associated with the flat 3D surface.

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

generating a scaled 2D surface by scaling one or more edges included within the 2D surface; and

deforming the scaled 2D surface into a scaled 3D surface that fills the hole in the 3D model.

9. A non-transitory computer-readable medium storing program instructions that, when executed by a processing unit, cause the processing unit to fill a hole in a three-dimensional (3D) model by performing the steps of:

identifying the hole in the 3D model;

generating a refined quasi-developable surface that is disposed within the hole in the 3D model;

generating a two-dimensional (2D) surface based on the refined quasi-developable surface; and

deforming the 2D surface into a 3D surface that fills the hole in the 3D model.

10. The non-transitory computer-readable medium of claim 9, wherein the step of generating the refined quasi-developable surface comprises:

generating a triangle fan that covers the hole in the 3D model;

generating a refined surface by decomposing each triangle associated with the triangle fan into a first set of refined triangles, wherein each refined triangle in the first set of refined triangles complies with a first geometric criterion;

generating a quasi-developable surface by flattening the refined surface; and

generating the refined quasi-developable surface by decomposing each triangle associated with the quasi-developable surface into a second set of refined triangles, wherein each refined triangle in the second set of refined triangles complies with a second geometric criterion.

11. The non-transitory computer-readable medium of claim 10, wherein the triangle fan comprises a central vertex located approximately equidistant from each boundary vertex that surrounds the hole in the 3D model, and a set of edges that connects the central vertex to each boundary vertex that surrounds the hole in the 3D model.

12. The non-transitory computer-readable medium of claim 10, wherein the first geometric criterion indicates that each triangle in the first set of refined triangles is substantially equilateral and has a first size, and the second geometric criterion indicates that each triangle in the second set of refined triangles is substantially equilateral and has a second size.

13. The non-transitory computer-readable medium of claim 10, wherein the step of generating the quasi-developable surface by flattening the refined surface comprises:

collapsing a first subset of refined triangles included within the first set of refined triangles into a first triangle, wherein triangles in the first subset of triangles reside adjacent to one another within the refined surface;

collapsing a second subset of refined triangles included within the first set of refined triangles into a second triangle, wherein triangles in the second subset of refined triangles reside adjacent to one another within the refined surface;

determining that inverting the second triangle decreases an angle between a surface normal associated with the first triangle and a surface normal associated with the second triangle; and

inverting the second triangle.

14. The non-transitory computer-readable medium of claim 9, wherein the step of generating the 2D surface based on the refined quasi-developable surface comprises computing a planar parameterization of the quasi-developable surface via a conformal map.

15. The non-transitory computer-readable medium of claim 9, wherein the step of deforming the 2D surface into the 3D surface that fills the hole in the 3D model comprises:

transforming the 2D surface into a flat 3D surface;

positioning each boundary vertex associated with the flat 3D surface at a location corresponding to a boundary vertex associated with the hole in the 3D model;

generating the 3D surface by projecting each interior vertex associated with the flat 3D surface to a different 3D coordinate based on the locations of the boundary vertices associated with the flat 3D surface.

16. The non-transitory computer-readable medium of claim 9, further comprising the steps of:

generating a scaled 2D surface by scaling one or more edges included within the 2D surface; and

deforming the scaled 2D surface into a scaled 3D surface that fills the hole in the 3D model.

17. A computing device configured to fill a hole in a three-dimensional (3D) model, including:

a processing unit configured to

identify the hole in the 3D model;

generate a refined quasi-developable surface that is disposed within the hole in the 3D model;

generate a two-dimensional (2D) surface based on the refined quasi-developable surface; and

deform the 2D surface into a 3D surface that fills the hole in the 3D model.

18. The computing device of claim 17, further including:

a memory unit coupled to the processing unit and storing program instruction that, when executed by the processing unit, cause the processing unit to;

identify the hole in the 3D model;

generate the refined quasi-developable surface;

generate the two-dimensional (2D) surface; and

deform the 2D surface into the 3D surface that fills the hole in the 3D model.

19. The computing device of claim 17, wherein the processing unit is configured to generate the refined quasi-developable surface by:

generating a triangle fan that covers the hole in the 3D model;

generating a refined surface by decomposing each triangle associated with the triangle fan into a first set of refined triangles, wherein each refined triangle in the first set of refined triangles complies with a first geometric criterion;

generating a quasi-developable surface by flattening the refined surface; and

generating the refined quasi-developable surface by decomposing each triangle associated with the quasi-developable surface into a second set of refined triangles, wherein each refined triangle in the second set of refined triangles complies with a second geometric criterion.

20. The computing device of claim 17, wherein the processing unit is configured to deform the 2D surface into the 3D surface that fills the hole in the 3D model by:

transforming the 2D surface into a flat 3D surface;

positioning each boundary vertex associated with the flat 3D surface at a location corresponding to a boundary vertex associated with the hole in the 3D model; and

generating the 3D surface by projecting each interior vertex associated with the flat 3D surface to a different 3D coordinate based on the locations of the boundary vertices associated with the flat 3D surface.