Surface simplification preserving a solid volume

• US 6,414,683 B1
• Filed: 01/04/1999
• Issued: 07/02/2002
• Est. Priority Date: 11/01/1996
• Status: Expired due to Term

• Current Assignee: Pendragon Networks LLC (Pendrell Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Gueziec, Andre Pierre
• Primary Examiner(s): Zimmerman, Mark
• Assistant Examiner(s): MANCUSO, HUEDUNG XUAN CAO
• Application Number:
  US09/225,084
• Time in Patent Office: 1,275 Days
• Field of Search: 345/433, 345/420, 345/422, 345/423, 345/421, 345/419, 345/418, 345/619, 345/428
• US Class Current: 345/428
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

Computer systems may be used to generate and display objects represented by triangles defined by coordinates of vertices. The present invention generates coordinates of a simplified vertex based upon coordinates of vertices adjacent to a first vertex and to a second vertex that define an edge of the triangles. First, a set of triangles that are adjacent to the edge is identified, Second, a first volume associated with the set of triangles is calculated. Finally, the coordinates of the simplified vertex are calculated such that a second volume associated with the simplified vertex corresponds to the first volume.

In addition, a technique is presented that generates a second object which is a simplified representation of a first object. The technique begins by identifying first and second vertices that define an edge. The coordinates of a simplified vertex that corresponds to first and second vertices of the edge is determined. Error values and tolerance values are assigned to vertices. First error volumes corresponding to the vertices of a second vertices of the edge. The first error volumes are based upon the error values assigned to vertices of the first set of triangles. A second set of triangles that share the simplified vertex is identified and partitioned into a set of planar polygons. Second error volumes corresponding to vertices of the set of planar polygons are derived based upon the first error volumes. The second error volumes enclose the first error volumes. Third error volumes corresponding to vertices of the second set of triangles are derived. The third error volumes are based upon the first and second error volumes. The third volumes enclose both the first error volumes and the second error volumes. A tolerance volume corresponding to the simplified vertex is derived. Fianllym, the coordinates of the simplified vertex is stored in memory for subsequent reuse based upon a comparison operation of the third error volume corresponding to the simplified vertex and the tolerance volume.

Claims

1. In a computer system wherein an object is represented by a plurality of triangles, a method for generating a second object which is a simplified representation of the first object by collapsing at least one edge of said first object, the method comprising the steps of:

i) identifying a first vertex and a second vertex of a candidate edge;

ii) determining a first set of triangles that are adjacent to said candidate edge;

iii) determining coordinates of a simplified vertex replacing said first vertex and second vertex in the event that said edge collapse is performed;

iv) determining properties of said simplified vertex, said properties representing at least one of coordinates, color and texture of said simplified vertex,

v) assigning error values to said properties for said vertices of first set of triangles;

vi) assigning at least one tolerance value to said properties for said vertices of said first set of triangles, and

vii) selectively performing said edge collapse based upon a comparison operation of said error values and said at least one tolerance value.

2. The method of claim 1, wherein steps iii) through step vii) are not performed if at least one preliminary collapsibility test for said candidate edge fails.

3. The method of claim 2, wherein said at least one preliminary collapsibility test comprises the step of determining whether valence of said candidate edge satisfies a predetermined criterion.

4. The method of claim 3, wherein valence of said candidate edge satisfies said predetermined criterion when said valence falls within a range having an upper bound based upon user input.

5. The method of claim 2, wherein said at least one preliminary collapsibility test comprises the step of verifying that there are no shared vertices in a link of an edge star for said candidate edge.

6. The method of claim 1, further comprising the step of.

viii) selectively performing said edge collapse based upon at least one secondary collapsibility test.

7. The method of claim 6, wherein a second set of triangles share said simplified vertex, and wherein said secondary collapsibility verifies that the angular rotation of normals of said first set of triangles with respect to normals of corresponding triangles of said second set of triangles is less than a predetermined threshold value.

8. The method of claim 6, wherein a second set of triangles share said simplified vertex, and wherein said secondary collapsibility verifies that a narrowness coefficient for each triangle in said second set of triangles is less than a predetermined threshold value.

9. A program storage device for use in a computer system wherein an object is represented by a plurality of triangles, the program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for generating a second object which is a simplified representation of the first object by collapsing at least one edge of said first object, said method steps comprising:

i) identifying a first vertex and a second vertex of a candidate edge;

ii) determining a first set of triangles that are adjacent to said candidate edge;

iii) determining coordinates of a simplified vertex replacing said first vertex and second vertex in the event that said edge collapse is performed;

iv) determining properties of said simplified vertex, said properties representing at least one of coordinates, color and texture of said simplified vertex;

v) assigning error values to said properties for said vertices of first set of triangles;

vi) assigning at least one tolerance value to said properties for said vertices of said first set of triangles; and

vii) selectively performing said edge collapse based upon a comparison operation of said error values and said at least one tolerance value.

10. The program storage device of claim 9, wherein steps iii) through step vii) are not performed if at least one preliminary collapsibility test for said candidate edge fails.

11. The program storage device of claim 10, wherein said at least one preliminary collapsibility test comprises the step of determining whether valence of said candidate edge satisfies a predetermined criterion.

12. The program storage device of claim 11, wherein valence of said candidate edge satisfies said predetermined criterion when said valence falls within a range having an upper bound based upon user input.

13. The program storage device of claim 10, wherein said at least one preliminary collapsibility test comprises the step of verifying that there are no shared vertices in a link of an edge star for said candidate edge.

14. The program storage device of claim 9, said method steps further comprising:

viii) selectively performing said edge collapse based upon at least one secondary collapsibility test.

15. The program storage device of claim 14, wherein a second set of triangles share said simplified vertex, and wherein said secondary collapsibility verifies that the angular rotation of normals of said first set of triangles with respect to normals of corresponding triangles of said second set of triangles is less than a predetermined threshold value.

16. The program storage device of claim 14, wherein a second set of triangles share said simplified vertex, and wherein said secondary collapsibility verifies that a narrowness coefficient for each triangle in said second set of triangles is less than a predetermined threshold value.

17. In a computer system wherein an object is represented by a plurality of triangles, a method for generating a second object which is a simplified representation of the first object by collapsing at least one edge of said first object, the method comprising the steps of:

i) identifying a first vertex and a second vertex of a candidate edge;

ii) determining coordinates of a simplified vertex replacing said first vertex and second vertex in the event that said edge collapse is performed;

iii) generating a first set of triangles that share said simplified vertex;

iv) for each triangle in said first set, generating a coefficient C characteristic of narrowness of said triangle as;

$C=\frac{4<br><br>\sqrt{3}<br><br>\text{\hspace{1em}<br><br>}<br><br>A}{\sqrt{{\left(l_0\right)}^2+{\left(l_1\right)}^2+{\left(l_2\right)}^2}}$

where A is area of said triangle, and

l₀, l₁, l₂ are lengths of respective sides of said triangle, and

v) in the event that said coefficient C for each triangle in said first set satisfies a predetermined criterion, performing said edge collapse.

18. The method of claim 17, wherein said predetermined criterion is based upon a coefficient characteristic of narrowness of a corresponding triangle belonging to a second set of triangles.

19. The method of claim 18, wherein said second set of triangles comprises an edge star for said candidate edge.

20. The method of claim 17, wherein said set of triangles comprises a star of said simplified vertex.

21. A program storage device for use in a computer system wherein an object is represented by a plurality of triangles, the program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for generating a second object which is a simplified representation of the first object by collapsing at least one edge of said first object, said method steps comprising:

i) identifying a first vertex and a second vertex of a candidate edge;

ii) determining coordinates of a simplified vertex replacing said first vertex and second vertex in the event that said edge collapse is performed;

iii) generating a first set of triangles that share said simplified vertex;

iv) for each triangle in said first set, generating a coefficient C characteristic of narrowness of said triangle as;

$C=\frac{4<br><br>\sqrt{3}<br><br>\text{\hspace{1em}<br><br>}<br><br>A}{\sqrt{{\left(l_0\right)}^2+{\left(l_1\right)}^2+{\left(l_2\right)}^2}}$

where A is area of said triangle, and

l₀, l₁, l₂ are lengths of respective sides of said triangle, and

v) in the event that said coefficient C for each triangle in said first set satisfies a predetermined criterion, performing said edge collapse.

22. The program storage device of claim 21, wherein said predetermined criterion is based upon a coefficient characteristic of narrowness of a corresponding triangle belonging to a second set of triangles.

23. The program storage device of claim 22, wherein said second set of triangles comprises an edge star for said candidate edge.

24. The program storage device of claim 21, wherein said set of triangles comprises a star of said simplified vertex.