Method and system for repairing triangulated surface meshes

• US 7,825,925 B2
• Filed: 03/09/2007
• Issued: 11/02/2010
• Est. Priority Date: 03/09/2007
• Status: Active Grant

• Current Assignee: St. Jude Medical, Atrial Fibrillation Division, Inc. (Abbott Laboratories)
• Original Assignee: St. Jude Medical, Atrial Fibrillation Division, Inc. (Abbott Laboratories)
• Inventors: Voth, Eric Jon
• Primary Examiner(s): Nguyen; Kimbinh T
• Application Number:
  US11/715,922
• Publication Number:
  US 20080218509A1
• Time in Patent Office: 1,334 Days
• Field of Search: 345/419, 345/421, 345/428, 345/619, 700/29, 382/254
• US Class Current: 345/419
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

A method of repairing a three dimensional surface mesh model to be watertight and manifold generally includes identifying a plurality of hole edges in the surface mesh model, selecting one of the hole edges, creating a cycle of hole edges that defines a hole in the surface mesh model, converting the cycle of hole edges into two or more cycles of exactly three edges each, and adding a triangular facet to the surface mesh model for each of the cycles of exactly three edges. The process may be repeated until the model is substantially watertight. Non-manifold vertices may be repaired by selecting a vertex of the model, identifying a number of independent cycles of triangular facets sharing the selected vertex, and redefining the selected vertex for at least all but one of the number of independent cycles. This process may be repeated until the model is manifold.

Claims

1. A method of using one or more computer processors running on one or more computer system to repair a surface mesh model including a plurality of triangular facets, the method comprising:

obtaining a surface mesh model for a three dimensional object comprising a plurality of triangular facets, each of the facets being defined by three edges that connect three vertices;

identifying a hole in the surface mesh model, the hole being defined by a plurality of hole edges;

determining a plurality of hole vertices that define the plurality of hole edges that define the hole;

filling the hole using a plurality of triangular facets, comprising;

selecting a pair of the hole vertices, wherein the selected pair of the hole vertices is not connected by a hole edge;

defining a fabricated edge connecting the selected pair of the hole vertices; and

checking to see if one or more triangles are formed using the newly defined fabricated edge, and if so, defining the newly formed one or more triangles as one or more new triangular facets, and adding the one or more new triangular facets to the plurality of triangular facets of the surface mesh model.

2. The method according to claim 1, wherein the step of filling the hole using a plurality of triangular facets further comprises:

if one or more triangles are not formed, continuing to define fabricated edges until one or more triangles are formed, and defining the newly formed one or more triangles as one or more new triangular facets, and adding the one or more new triangular facets to the plurality of triangular facets of the surface mesh model.

3. The method according to claim 1, wherein the step of selecting a pair of the hole vertices comprises selecting a closest pair of the hole vertices.

4. The method according to claim 1, wherein the step of selecting a pair of the hole vertices comprises:

locating a smallest interior angle of the plurality of hole edges that define the hole; and

selecting a pair of the hole vertices that define a pair of the plurality of hole edges that intersect at the smallest interior angle of the plurality of hole edges that define the hole.

5. The method according to claim 1, further comprising repeating the steps of identifying a hole in the surface mesh model, determining a plurality of hole vertices that define the plurality of hole edges that define the hole, and filling the hole using a plurality of triangular facets until the surface mesh model is substantially watertight.

6. A method of using one or more computer processors running on one or more computer system to repair a surface mesh model including a plurality of triangular facets, the method comprising:

obtaining a three dimensional surface mesh model for a three dimensional object comprising a plurality of triangular facets, each of the triangular facets being defined by three edges that connect three vertices;

identifying a plurality of hole edges in the surface mesh model;

selecting one of the plurality of hole edges;

creating a cycle of hole edges that define a hole in the surface mesh model, wherein the cycle of hole edges includes the selected one of the plurality of hole edges;

converting the cycle of hole edges into two or more cycles of exactly three edges, each of the two or more cycles of exactly three edges including at least one of the plurality of hole edges, thereby defining a plurality of hole-filling triangles; and

adding a triangular facet to the surface mesh model for each of the plurality of hole-filling triangles.

7. The method according to claim 6, wherein the step of selecting one of the plurality of hole edges comprises:

creating a prioritized queue of hole edges using triangle counts for each hole edge in the queue, assigning a higher priority to any hole edge having a triangle count less than two, and assigning a lower priority to any hole edge having a triangle count greater than two; and

selecting one of the plurality of hole edges from the prioritized queue of hole edges in accordance with the assigned priority.

8. The method according to claim 6, wherein the step of creating a cycle of hole edges that define a hole in the surface mesh model comprises creating a shortest possible cycle of hole edges including the selected hole edge.

9. The method according to claim 6, wherein the step of converting the cycle of hole edges into two or more cycles comprises defining one or more fabricated edges connecting non-neighboring vertices of the cycle of hole edges.

10. The method according to claim 9, wherein the step of defining one or more fabricated edges connecting non-neighboring vertices of the cycle of hole edges comprises:

a) identifying a closest pair of non-neighboring vertices of the cycle of hole edges; and

b) defining a fabricated edge connecting the closest pair of non-neighboring vertices of the cycle of hole edges, thereby splitting the cycle of hole edges into two cycles of edges.

11. The method according to claim 10, further comprising repeating steps a) and b) for at least one of the two cycles of edges into which the cycle of hole edges was split.

12. The method according to claim 10, further comprising iteratively repeating steps a) and b) until the cycle of hole edges is converted into two or more cycles of exactly three edges.

13. The method according to claim 9, wherein the step of defining one or more fabricated edges connecting non-neighboring vertices of the cycle of hole edges comprises:

a) identifying a smallest interior angle of the cycle of hole edges; and

b) defining a fabricated edge that completes a triangle with a pair of hole edges that intersect at the smallest interior angle of the cycle of hole edges, thereby splitting the cycle of hole edges into two cycles of edges, at least one of which has exactly three edges.

14. The method according to claim 13, further comprising repeating steps a) and b) for at least one of the two cycles of edges into which the cycle of hole edges was split.

15. The method according to claim 13, further comprising iteratively repeating steps a) and b) until the cycle of hole edges is converted into two or more cycles of exactly three edges.

16. The method according to claim 6, further comprising orienting the plurality of triangular facets comprising the surface mesh model by listing the vertices of each triangular facet in a counterclockwise order when viewed from outside the three dimensional mesh surface.

17. The method according to claim 6, further comprising orienting the plurality of triangular facets comprising the surface mesh model by listing the vertices of each triangular facet in an order such that any two of the plurality of triangular facets having a shared edge list the vertices defining the shared edge in opposite orders.

18. The method according to claim 6, further comprising:

identifying one or more non-manifold triangular facets of the plurality of triangular facets; and

removing the identified one or more non-manifold triangular facets from the plurality of triangular facets.

19. The method according to claim 18, wherein the step of identifying one or more non-manifold triangular facets of the plurality of triangular facets comprises identifying one or more triangular facets of the plurality of triangular facets having two edges with a triangle count greater than two.

20. The method according to claim 18, wherein the step of identifying one or more non-manifold triangular facets of the plurality of triangular facets comprises identifying one or more triangular facets of the plurality of triangular facets having one edge with a triangle count greater than two and two edges with a triangle count of one.

21. The method according to claim 18, wherein the step of identifying one or more non-manifold triangular facets of the plurality of triangular facets comprises identifying one or more triangular facets of the plurality of triangular facets having one edge with a triangle count greater than two.

22. The method according to claim 6, further comprising filtering the surface mesh model to eliminate one or more duplicate vertices.

23. The method according to claim 22, wherein the step of filtering the surface mesh model to eliminate one or more duplicate vertices comprises:

selecting an existing vertex of one of the plurality of triangular facets;

analyzing a plurality of vertices of the plurality of triangular facets to identify one or more duplicate vertices closer than a preset distance to the selected existing vertex; and

redefining one or more of the plurality of triangular facets defined by one or more duplicate vertices to be defined by the selected existing vertex rather than the identified one or more duplicate vertices.

24. The method according to claim 23, wherein the preset distance is defined as a multiple of machine epsilon.

25. The method according to claim 23, further comprising:

identifying one or more degenerate triangular facets of the plurality of triangular facets; and

removing the identified one or more degenerate triangular facets from the plurality of triangular facets.

26. A method of using one or more computer processors running on one or more computer system to repair a surface mesh model of a three dimensional object including a plurality of triangular facets to be substantially both watertight and manifold, the method comprising:

a) identifying a plurality of hole edges in the surface mesh model;

b) arranging the plurality of hole edges in an edge queue from a highest priority hole edge to a lowest priority hole edge, wherein a hole edge having a triangle count less than two has a higher priority than a hole edge having a triangle count greater than two;

c) selecting the highest priority hole edge within the edge queue;

d) determining a cycle of hole edges including the selected hole edge;

e) converting the cycle of hole edges to one or more fabricated triangular facets; and

f) adding the one or more fabricated triangular facets to the surface mesh model.

27. The method according to claim 26, further comprising:

g) updating the edge queue.

28. The method according to claim 27, further comprising repeating steps c), d), e), f), and g) until the edge queue is empty.

29. The method according to claim 26, wherein the step of converting the cycle of hole edges to one or more fabricated triangular facets comprises:

defining a fabricated triangular facet corresponding to the cycle of hole edges when the cycle of hole edges contains exactly three hole edges; and

splitting the cycle of hole edges into two or more cycles of exactly three edges and defining two or more corresponding fabricated triangular facets when the cycle of hole edges contains four or more hole edges.

30. The method according to claim 29, wherein the step of splitting the cycle of hole edges into two or more cycles of exactly three edges comprises defining n fabricated edges connecting non-neighboring vertices of the cycle of hole edges, n being given by an equation n=s−

3, wherein the cycle of hole edges includes s hole edges.

31. The method according to claim 26, further comprising:

selecting a vertex of one of the plurality of triangular facets;

determining a number of independent cycles of triangular facets sharing the selected vertex; and

if the number of independent cycles of triangular facets sharing the selected vertex is two or more, redefining the selected vertex for at least one of the two or more independent cycles of triangular facets sharing the selected vertex.

32. The method according to claim 31, wherein the step of redefining the selected vertex comprises:

g) selecting one of the two or more independent cycles of triangular facets sharing the selected vertex;

h) defining a new vertex a short distance from the selected vertex in a direction normal to and towards the selected independent cycle of triangular facets; and

i) redefining the selected independent cycle of triangular facets to share the new vertex rather than the selected vertex.

33. The method according to claim 32, further comprising repeating steps g), h), and i) for at least all but one of the two or more independent cycles of triangular facets sharing the selected vertex.

34. The method according to claim 26, further comprising removing one or more non-manifold triangular facets from the surface mesh model, each of the one or more non-manifold triangular facets meeting one of the following criteria:

one edge having a triangle count greater than two;

two edges having triangle counts greater than two;

or

one edge having a triangle count greater than two and two edges having triangle counts equal to one.

35. A method of using one or more computer processors running on one or more computer system to repair a surface mesh model of a three dimensional object including a plurality of triangular facets, the method comprising:

creating a cycle of hole edges having s edges, wherein s is greater than or equal to three, the cycle of hole edges defining a hole in the surface mesh model;

defining n fabricated edges connecting non-neighboring vertices of the cycle of hole edges, wherein n=s−

3, such that the hole in the surface mesh model is defined by (n+1) cycles of exactly three edges each; and

adding a triangular facet to the surface mesh model for each of the (n+1) cycles of exactly three hole edges defining the hole in the surface mesh model.

36. The method according to claim 35, further comprising repeating the steps of creating a cycle of hole edges having s edges, defining n fabricated edges connecting non-neighboring vertices of the cycle of hole edges, and adding a triangular facet to the surface mesh model for each of the (n+1) cycles of exactly three edges until the surface mesh model is watertight.

37. A method of using one or more computer processors running on one or more computer system to repair a surface mesh model including a plurality of triangular facets, the method comprising:

obtaining a three dimensional surface mesh model of a three dimensional object comprising a plurality of triangular facets, each of the triangular facets being defined by three edges that connect three vertices;

selecting a vertex of one of the plurality of triangular facets;

identifying a subset of the plurality of triangular facets including the selected vertex;

creating a cycle of triangular facets from the subset of the plurality of triangular facets; and

redefining the selected vertex for all triangular facets in the cycle of triangular facets if every triangular facet within the subset of the plurality of triangular facets is not included in the cycle of triangular facets.

38. The method according to claim 37, wherein the step of redefining the selected vertex for all triangular facets in the cycle of triangular facets comprises:

defining a new vertex a short distance from the selected vertex; and

redefining all triangular facets in the cycle of triangular facets to include the new vertex instead of the selected vertex.

39. The method according to claim 38, wherein the step of defining a new vertex a short distance from the selected vertex comprises defining the new vertex a short distance from the selected vertex in a direction normal to and towards the cycle of triangular facets.

40. The method according to claim 37, further comprising repeating the steps of identifying a subset of the plurality of triangular facets including the selected vertex, creating a cycle of triangular facets from the subset of the plurality of triangular facets, and redefining the selected vertex for all triangular facets in the cycle of triangular facets if every triangular facet within the subset of the plurality of triangular facets is not included in the cycle of triangular facets until the surface mesh model is manifold at the selected vertex.

41. A system for repairing a surface mesh model for a three dimensional object, the surface mesh model including a plurality of triangular facets, the system comprising:

a hole identification processor configured to identify a cycle of hole edges that defines a hole in the surface mesh model, the cycle of hole edges being defined by three or more vertices; and

a facet fabrication processor configured to fabricate one or more triangular facets that fill the hole in the surface mesh model by interconnecting the three or more vertices of the cycle of hole edges.

42. The system according to claim 41, wherein the hole identification processor is configured to identify a shortest possible cycle of hole edges that defines a hole in the surface mesh model.

43. The system according to claim 41, wherein the facet fabrication processor fabricates one or more triangular facets that fill the hole in the surface mesh model by:

defining a fabricated triangular facet corresponding to the cycle of hole edges when the cycle of hole edges contains exactly three hole edges defined by exactly three vertices; and

splitting the cycle of hole edges into two or more cycles of exactly three edges and defining two or more corresponding fabricated triangular facets when the cycle of hole edges contains four or more hole edges defined by four or more vertices.

44. The system according to claim 43, wherein the facet fabrication processor splits the cycle of hole edges into two or more cycles of exactly three hole edges by defining n fabricated edges interconnecting non-neighboring vertices of the cycle of hole edges, n being given by an equation n=s−

3, wherein the cycle of hole edges includes s hole edges.

45. The system according to claim 41, further comprising a facet checking processor configured to identify and discard one or more non-manifold triangular facets of the plurality of triangular facets.

46. The system according to claim 45, wherein each of the one or more non-manifold triangular facets meets one of the following criteria:

one edge having a triangle count greater than two;

two edges having triangle counts greater than two;

or

one edge having a triangle count greater than two and two edges having triangle counts equal to one.