Method to convert non-manifold polyhedral surfaces into manifold surfaces

• US 6,016,153 A
• Filed: 04/24/1997
• Issued: 01/18/2000
• Est. Priority Date: 07/30/1996
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Taubin, Gabriel, Gueziec, Andre Pierre
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US08/840,001
• Time in Patent Office: 999 Days
• Field of Search: 345/441, 345/419, 345/420, 345/421, 345/433, 345/434, 345/435
• US Class Current: 345/441
• CPC Class Codes: G06T 9/40 Tree coding, e.g. quadtree, octree

Abstract

A is a computer implemented method for converting a non-manifold surface to a manifold surface. The method includes the steps of (a) providing data in a memory of a computer for representing a non-manifold polyhedral surface comprised of a plurality of triangles each bounded by edges and having vertices; (b) analyzing the data to determine and record singular edges and singular vertices; and (c) cutting through the singular edges and singular vertices, and optionally other edges and vertices, to provide a plurality of connected polygonal surfaces that are free of singularities. The step of analyzing may include the initial steps of analyzing the data to remove isolated vertices and repeated triangles. The step of cutting operates in accordance with one of a local cutting method or a global cutting method, and may further include a step of stitching the cut surface along boundary edges.

Claims

1. A computer implemented method for converting a non-manifold surface to a manifold surface, comprising steps of:

providing data in a memory of a computer for representing a non-manifold polyhedral surface comprised of a plurality of polygons each bounded by edges and having vertices, the non-manifold polyhedral surface comprising singular vertices and edges;

analyzing the data that represents the non-manifold polyhedral surface to determine and mark the presence of the singular edges and singular vertices; and

cutting through all of the singular edges and singular vertices of the non-manifold polyhedral surface to provide a plurality of connected polyhedral surfaces that are free of singularities.

2. A method as in claim 1, wherein the step of analyzing includes the initial steps of analyzing the data to remove isolated vertices, repeated polygons, and polygons that are incident to invalid vertices.

3. A method as in claim 2, wherein the step of removing isolated vertices includes the steps of:

determining a vertex valence by counting a number of triangles incident to each vertex;

identifying an isolated vertex as one having zero valence; and

assigning new indices to non-isolated vertices.

4. A method as in claim 2, wherein the step of removing isolated polygons includes the steps of:

sorting the vertices within each polygon;

sorting the polygons; and

identifying and removing those polygons that are repeated.

5. A method as in claim 2, wherein the step of removing polygons that are incident to invalid vertices includes the steps of:

looping through a polygon face list;

determining if a particular polygon is incident to an invalid vertex; and

removing those polygons that are determined to be incident to an invalid vertex.

6. A method as in claim 1, wherein the step of cutting also cuts through other edges that are specified for cutting.

7. A method as in claim 1, wherein the step of analyzing the data to determine and mark the presence of singular edges includes the steps of:

counting a number of polygons incident to each edge; and

identifying as a singular edge any edge having three or more incident polygons.

8. A method as in claim 7, and further comprising the step of:

identifying as a boundary edge any edge having only one incident polygon.

9. A method as in claim 1, wherein the step of analyzing the data to determine and mark the presence of singular vertices includes the steps of:

identifying as a singular vertex any vertex that is an end point of a singular edge; and

identifying as a singular vertex any vertex having a polygon star that has more than one connected component.

10. A method as in claim 1, and further comprising a step of orienting a particular one of the polygonal surfaces by reversing its constituent polygons.

11. A method as in claim 1, wherein the step of cutting operates in accordance with a local cutting method.

12. A method as in claim 11, wherein the local cutting method includes steps of:

establishing a set of marked edges, comprising singular edges and other edges; and

cutting through the marked edges by the steps of, determining a set of marked vertices from the set of marked edges and by marking all vertices whose vertex star includes more than one component;

determining a set of faces incident to each marked vertex;

partitioning the set of faces into one or more groups connected by non-marked edges, while maintaining for each of the faces of the set a representative group to which the face belongs;

for a case wherein more than one group has been established, multiplying vertices to obtain nG-1 additional vertices, where nG indicates a number of groups that were established; and

selectively replacing a multiplied vertex by one of the additional multiplied vertices.

13. A method as in claim 12, wherein the step of selectively replacing a multiplied vertex is performed in accordance with the following criteria, wherein the method creates nG-1 vertices w1, w2, . . . ,

if a face belongs to a group g0, then the vertex is not replaced;

if a face belongs to a group g1, then the vertex is replaced with w1;

if a face belongs to a group g2, then the vertex is replaced with w2, and so on.

14. A method as in claim 1, wherein the step of cutting operates in accordance with a global cutting method.

15. A method as in claim 14, wherein the global cutting method includes steps of:

establishing a set of marked edges, comprising singular edges and other edges; and

cutting through the marked edges by the steps of,

building a set of face corners by cutting through all edges, considering each face to be disconnected from other faces, and for each vertex creating a corner;

partitioning the set of face corners into one or more corner groups connected by non-marked edges;

determining if the number of corner groups is larger than the original number of vertices;

if the number of corner groups is not larger than the number of vertices, then the global cutting method is terminated;

else

replacing each corner with a corresponding corner group number;

creating a list of new vertices from the face corners;

creating a new look-up table to establish correspondence between the new vertices that are corner groups and previous vertices; and

identifying a face list with the set of face corners.

16. A method as in claim 1, and further comprising a step of stitching the cut surface along boundary edges.

17. A method as in claim 16, wherein the step of stitching includes a preliminary step of testing edges to determine if they are stitchable.

18. A method as in claim 16, wherein the step of stitching occurs through one of boundary edges or vertices of the same boundary.

19. A method as in claim 16, wherein the step of stitching occurs through boundary edges and comprises the steps of:

creating a first set A of stitched edge pairs;

identifying a set of boundary edges B1 of the cut surface;

constructing a set of boundary vertices B2;

creating an array R of representative boundary vertices;

determining a set B of marked edges that satisfy the condition that each edge of B corresponds to two or more edges of the set of boundary edges B1;

determining if the set B is empty, and if it is not, selecting a marked edge from set B and creating a second set of stitched edge pairs D;

selecting a pair of boundary edges that correspond to the selected marked edge and that exhibit a consistent boundary orientation property;

performing one or more tests to determine if the pair of selected boundary edges are stitchable and, if they are determined to be stitchable, performing the steps of,

adding the pair of selected boundary edges to the second set of stitched edge pairs D, updating the array R, removing the pair of selected boundary edges from the sets B1 and B;

determining a set F of pairs of boundary edges that are adjacent to edges in set D; and

determining if the set F is empty and, if it is,

appending the second set of stitched edge pairs D to the first set A, and testing to determine if set B is empty, else, if the set F is determined not to be empty,

selecting a pair of edges of set F and determining if the selected pair of edges correspond to the same marked edge in set B, if they do correspond, performing the step of testing with the selected pair of edges from set F, else removing the pair of selected edges from the set F;

wherein, when the set B is determined to be empty, the method performs a step of,

stitching each edge pair in the set A by replacing vertices associated with one edge by vertices associated with the other edge.

20. A method as in claim 19, wherein the step of performing one or more tests performs at least one of a same face test, an adjacency test, or a common vertex in star test.

21. A method as in claim 16, wherein the step of stitching occurs through boundary vertices and comprises the steps of:

creating a set S of stitched vertex pairs and an array R of representative boundary vertices;

determining a set B of surface boundaries;

determining if the set B is empty, and if it is, stitching the vertices of S, else

selecting and removing a boundary C from the set B;

determining a set E of vertices of C;

determining if the set E is empty, and if it is, determining if the set B is empty, and if it is, stitching the vertices of S, else if the set E is not empty,

selecting and removing a vertex v from set E;

determining vertices of C that are adjacent to v and determining if the vertices of C are stitchable;

if they are stitchable, updating the array of boundary vertices R and adding the vertices of C to the set S.

22. A method as in claim 1, wherein the polygons are triangles.

23. A computer implemented method for converting a non-manifold surface to a manifold surface, comprising steps of:

providing data in a memory of a computer for representing a non-manifold polyhedral surface comprised of a plurality of polygons each bounded by edges and having vertices and a face, the non-manifold polyhedral surface comprising singular vertices and edges;

analyzing the data that represents the non-manifold polyhedral surface to determine and mark the presence of the singular edges;

classifying edges of all faces as being one of a boundary edge, an interior edge, or a singular edge; and

cutting along the singular edges of the non-manifold polyhedral surface.

24. A method as in claim 23, wherein the step of classifying includes a step of:

examining all edges classified as interior edges and, if two faces sharing an interior edge have incompatible orientations, or if the two faces share three or more consecutive vertices, reclassifying the interior edge as a singular edge.

25. A computer implemented method for converting a non-manifold surface to an oriented manifold surface, comprising steps of:

providing data in a memory of a computer for representing a non-manifold polyhedral surface comprised of a plurality of polygons each bounded by

edges and having vertices and a face, the non-manifold polyhedral surface comprising singular vertices and edges;

analyzing the data that represents the non-manifold polyhedral surface to determine and mark the presence of the singular edges;

classifying edges of all faces as being one of a boundary edge, an interior edge, or a singular edge;

building a rooted spanning tree whose vertices are faces and whose edges are non-marked edges;

traversing the spanning tree and re-orienting child faces consistently with their parent face;

marking all non-marked edges that are not consistently oriented; and

cutting along the singular edges of the non-manifold polyhedral surface.

26. A method as in claim 25, wherein the step of classifying includes a step of:

examining all edges classified as interior edges and, if two faces sharing an interior edge have incompatible orientations, or if the two faces share three or more consecutive vertices, reclassifying the interior edge as a singular edge.

27. A graphics processing system, comprising:

a memory storing data for representing a non-manifold polyhedral surface comprised of a plurality of polygons each bounded by edges and having vertices, the non-manifold polyhedral surface comprising singular vertices and edges; and

a data processor coupled to the memory for analyzing the data that represents the non-manifold polyhedral surface to determine and mark the presence of the singular edges and singular vertices, said data processor further operating to cut through all of the singular edges and singular vertices of the non-manifold polyhedral surface to provide a plurality of connected polyhedral surfaces that are free of singularities, thereby converting a non-manifold surface to a manifold surface.

28. A graphics processing system as in claim 27, wherein said data processor operates to cut through all of the singular edges and singular vertices with one of a local cutting method or a global cutting method.

29. A graphics processing system as in claim 27, wherein said data processor further operates to test boundaries to determine if they are joinable and to join together boundaries through one of boundary edges or vertices of the same boundary.

30. A computer program embodied on a computer-readable medium for providing a graphics processing program, comprising:

a graphics data analysis code segment for analyzing data stored in a memory readable by the computer, the stored data representing a non-manifold polyhedral surface comprised of a plurality of polygons bounded by edges and having vertices, the non-manifold polyhedral surface comprising singular vertices and edges, said graphics data analysis code segment operating to determine and mark a presence of the singular edges and singular vertices in the stored data that represents the non-manifold polyhedral surface; and

a cutting code segment for cutting through marked singular edges and singular vertices of the non-manifold polyhedral surface to provide a plurality of connected polyhedral surfaces.

31. A computer program as in claim 30, wherein said cutting code segment operates in accordance with a global cutting procedure.

32. A computer program as in claim 30, wherein said cutting code segment operates in accordance with a global cutting procedure.

33. A computer implemented method for operating on graphics data, comprising steps of:

providing data in a memory of a computer for representing a non-simple mesh comprised of a plurality of polygons bounded by edges and having vertices, the non-simple mesh comprising singular vertices and edges;

analyzing the data that represents the non-simple mesh to detect the presence of the singular edges and vertices;

marking a set of detected singular edges and vertices; and

using one of a local cutting procedure or a global cutting procedure for cutting through the set of marked singular edges and vertices of the non-simple mesh.

34. A computer implemented method as in claim 33, wherein the step of marking also marks a set comprised of other edges and vertices, and where the step of cutting also cuts through the set comprised of other edges and vertices.

35. A computer implemented method as in claim 33, wherein the step of using one of the local cutting procedure or the global cutting procedure is followed by a step of transmitting a resulting partition of a surface represented by the non-simple mesh through a data communications network.