US5590248A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for reducing the complexity of a polygonal mesh
Assignee: General Electric Co
•
Filing: 1995-02-24
•
Granted: 1996-12-31
•
Expires: 2015-02-24
Abstract
Abstract A method for reducing the complexity of a polygonal mesh representative of the surface of an object to be displayed such as for medical imaging purposes systematically removes features from the mesh and reconnects the modified mesh in such a way as to preserve the original shape and topology of the mesh. The procedure removes both vertices and polygons from a polygonal mesh either alone or in combination. In order to reduce the number of polygons in an object for which a mesh has been generated, the method of the present invention repeats the decimation process until a desired number of polygons is achieved.
Inventors
- 👤 Jonathan A. Zarge
- 👤 William J. Schroeder
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 05:40
CPC Classifications
G; G06; G06T; G06T17/00; G06T17/20
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
62 words
A method for reducing complexity of a polygonal mesh while preserving shape and topology, the method comprising the steps of: analyzing each vertex in said mesh to determine if regions around the vertex are substantially co-planar; removing said vertex from said mesh if regions around the vertex are substantially co-planar; and triangulating an opening left by removing said vertex from said mesh.
Claim 2
Independent Claim
62 words
A method for reducing complexity of a polygonal mesh while preserving shape and topology, the method comprising the steps of: analyzing each vertex in said mesh to determine if regions around the vertex are substantially co-planar; removing said vertex from said mesh if regions around the vertex are substantially co-planar; and triangulating an opening left by removing said vertex from said mesh.
Claim 3
Dependent Claim
28 words
The method of claim 1 further comprising the step of: removing polygons from said triangulated mesh if said polygons have an area smaller than a first predetermined threshold.
Claim 4
Dependent Claim
53 words
The method of claim 2 wherein said step of removing a polygon includes computing a ratio of the area of said polygon to a sum of areas of adjacent polygons and comparing said ratio to said first predetermined threshold, said polygon being removed if said ratio is greater than said first predetermined threshold.
Claim 5
Dependent Claim
32 words
The method of claim 1 further comprising the step of: analyzing each vertex in said mesh to determine if any edge connected to said vertex is co-linear: and removing the co-linear edges.
Claim 6
Dependent Claim
49 words
The method of claim 4 wherein said analyzing includes computing a ratio of average edge length of said vertex to its shortest edge length and comparing said ratio to a predetermined short edge threshold, the edge being co-linear if said ratio is less than said predetermined short edge threshold.
Claim 7
Dependent Claim
82 words
The method of claim 1 wherein the step of triangulating said opening comprises the steps of: calculating an angle value for each remaining vertex defining said opening; removing a vertex with a smallest of said angle values from said opening; connecting vertices adjacent to said removed vertex forming a triangle; determining whether a ratio of the triangle height to base length is less than a second predetermined threshold; and replacing said vertex removed if said ratio is less than said second threshold.
Claim 8
Dependent Claim
45 words
The method of claim 1 wherein said analyzing includes determining an average distance between the vertex and each plane formed by adjacent vertices and comparing the distance to a third predetermined threshold, the vertex being substantially co-planar for distances less than the third predetermined threshold.
Claim 9
Independent Claim
133 words
A method for reducing complexity of a polygonal mesh while preserving shape and topology, the method comprising the steps of: analyzing each vertex in said mesh to determine if regions around the vertex are substantially co-planar; removing said vertex from said mesh if regions around the vertex are substantially co-planar; and triangulating an opening left by removing said vertex from said mesh, wherein said triangulating comprises calculating an angle value for each remaining vertex defining said opening; removing a vertex with a smallest of said angle values from said opening; connecting vertices adjacent to said removed vertex forming a triangle; determining whether a ratio of the triangle height to base length is less than a first predetermined threshold; and replacing said vertex removed if said ratio is less than said first predetermined threshold.
Claim 10
Independent Claim
133 words
A method for reducing complexity of a polygonal mesh while preserving shape and topology, the method comprising the steps of: analyzing each vertex in said mesh to determine if regions around the vertex are substantially co-planar; removing said vertex from said mesh if regions around the vertex are substantially co-planar; and triangulating an opening left by removing said vertex from said mesh, wherein said triangulating comprises calculating an angle value for each remaining vertex defining said opening; removing a vertex with a smallest of said angle values from said opening; connecting vertices adjacent to said removed vertex forming a triangle; determining whether a ratio of the triangle height to base length is less than a first predetermined threshold; and replacing said vertex removed if said ratio is less than said first predetermined threshold.
Claim 11
Dependent Claim
28 words
The method of claim 8 further comprising the step of: removing polygons from said triangulated mesh if said polygons have an area smaller than a second predetermined threshold.
Claim 12
Dependent Claim
53 words
The method of claim 9 wherein said step of removing a polygon includes computing a ratio of the area of said polygon to a sum of areas of adjacent polygons and comparing said ratio to said second predetermined threshold, said polygon being removed if said ratio is greater than said second predetermined threshold.
Claim 13
Dependent Claim
32 words
The method of claim 8 further comprising the step of: analyzing each vertex in said mesh to determine if any edge connected to said vertex is co-linear; and removing the co-linear edges.
Claim 14
Dependent Claim
49 words
The method of claim 11 wherein said analyzing includes computing a ratio of average edge length of said vertex to its shortest edge length and comparing said ratio to a predetermined short edge threshold, the edge being co-linear if said ratio is less than said predetermined short edge threshold.
Claim 15
Dependent Claim
45 words
The method of claim 8 wherein said analyzing includes determining an average distance between the vertex and each plane formed by adjacent vertices and comparing the distance to a third predetermined threshold, the vertex being substantially co-planar for distances less than the third predetermined threshold.
Claim 16
Independent Claim
102 words
A method for reducing complexity of a polygonal mesh while preserving shape and topology, the method comprising the steps of: analyzing each vertex in said mesh to determine if regions around the vertex are substantially co-planar, wherein said analyzing includes determining an average distance between the vertex and each plane formed by adjacent vertices and comparing the distance to a first predetermined threshold, the vertex being substantially co-planar for distances less than the first predetermined threshold; removing said vertex from said mesh if regions around the vertex are substantially co-planar; and triangulating an opening left by removing said vertex from said mesh.
Claim 17
Independent Claim
102 words
A method for reducing complexity of a polygonal mesh while preserving shape and topology, the method comprising the steps of: analyzing each vertex in said mesh to determine if regions around the vertex are substantially co-planar, wherein said analyzing includes determining an average distance between the vertex and each plane formed by adjacent vertices and comparing the distance to a first predetermined threshold, the vertex being substantially co-planar for distances less than the first predetermined threshold; removing said vertex from said mesh if regions around the vertex are substantially co-planar; and triangulating an opening left by removing said vertex from said mesh.
Claim 18
Dependent Claim
28 words
The method of claim 14 further comprising the step of: removing polygons from said triangulated mesh if said polygons have an area smaller than a second predetermined threshold.
Claim 19
Dependent Claim
53 words
The method of claim 15 wherein said step of removing a polygon includes computing a ratio of the area of said polygon to a sum of areas of adjacent polygons and comparing said ratio to said second predetermined threshold, said polygon being removed if said ratio is greater than said second predetermined threshold.
Claim 20
Dependent Claim
32 words
The method of claim 14 further comprising the step of: analyzing each vertex in said mesh to determine if any edge connected to said vertex is co-linear; and removing the co-linear edges.
Claim 21
Dependent Claim
49 words
The method of claim 17 wherein said analyzing includes computing a ratio of average edge length of said vertex to its shortest edge length and comparing said ratio to a predetermined short edge threshold, the edge being co-linear if said ratio is less than said predetermined short edge threshold.
Claim 22
Dependent Claim
82 words
The method of claim 14 wherein the step of triangulating said opening comprises the steps of: calculating an angle value for each remaining vertex defining said opening; removing a vertex with a smallest of said angle values from said opening; connecting vertices adjacent to said removed vertex forming a triangle; determining whether a ratio of the triangle height to base length is less than a predetermined thinness threshold; and replacing said vertex removed if said ratio is less than said thinness threshold.
References Cited (Backward Citations)
US4631690A
Cited
USRE33973E
Cited
US5010501A
Cited
US4912664A
Cited
US5107444A
Cited
US5454068A
Cited
US5440674A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-12-31 | 2000-07-01 | 2000-12-31 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-12-31 | 2004-07-01 | 2004-12-31 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-12-31 | 2008-07-01 | 2008-12-31 | $7700.00 | Window Closed / Lapsed |