US6285372B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Multiresolution adaptive parameterization of surfaces
Assignee: California Institute of Technology
•
Filing: 1998-05-08
•
Granted: 2001-09-04
•
Expires: 2018-05-08
Abstract
Abstract An irregular connectivity mesh representative of a surface having an arbitrary topology is processed to generate a parameterization which maps points in a coarse base domain to points in the mesh. An illustrative embodiment uses a multi-level mesh simplification process in conjunction with conformal mapping to efficiently construct a parameterization of a mesh comprising a large number of triangles over a base domain comprising a smaller number of triangles. The parameterization in this embodiment corresponds to the inverse of function mapping each point in the original mesh to one of the triangles of the base domain, such that the original mesh can be reconstructed from the base domain and the parameterization. The mapping function is generated as a combination of a number of sub-functions, each of which relates data points in a mesh of one level in a simplification hierarchy to data points in a mesh of the next coarser level of the simplification hierarchy. The parameterization can also be used to construct, from the original irregular connectivity mesh, an adaptive remesh having a regular connectivity which is substantially easier to process than the original mesh.
Inventors
- 👤 Lawrence C. Cowsar
- 👤 David Dobkin
- 👤 Aaron W. F. Lee
- 👤 Peter Schröder
- 👤 Wim Sweldens
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 21:21
CPC Classifications
G; G06; G06T; G06T17/00; G06T17/20
Claims Analysis
Total Claims: 30
Claim 1
Independent Claim
133 words
A method of processing a set of data points in the form of a first geometric mesh representative of a surface, the method comprising the steps of: processing the data points to generate a plurality of progressively coarser meshes including abase domain mesh, such that the first mesh and each of the progressively coarser meshes each correspond to a different level of coarseness; and generating a mapping function in the form of a bijection which maps at least a subset of the data points from the first mesh to the base domain mesh, wherein the mapping function is generated as a combination of a plurality of sub-functions, each of which relates data points in a mesh of a given level of coarseness to data points in a mesh of the next coarser level.
Claim 2
Independent Claim
133 words
A method of processing a set of data points in the form of a first geometric mesh representative of a surface, the method comprising the steps of: processing the data points to generate a plurality of progressively coarser meshes including abase domain mesh, such that the first mesh and each of the progressively coarser meshes each correspond to a different level of coarseness; and generating a mapping function in the form of a bijection which maps at least a subset of the data points from the first mesh to the base domain mesh, wherein the mapping function is generated as a combination of a plurality of sub-functions, each of which relates data points in a mesh of a given level of coarseness to data points in a mesh of the next coarser level.
Claim 3
Dependent Claim
25 words
The method of claim 1 wherein each of the meshes is a triangular mesh comprising a plurality of triangles having vertices corresponding to data points.
Claim 4
Dependent Claim
21 words
The method of claim 1 wherein the mapping function and at least a subset of the sub-functions each comprise a bijection.
Claim 5
Dependent Claim
59 words
The method of claim 1 wherein the step of generating the mapping function further includes the step of generating a given one of the sub-functions by removing data points in a mesh of a given level of coarseness and assigning barycentric coordinates to the removed points based on data points remaining in the mesh of the next coarser level.
Claim 6
Dependent Claim
31 words
The method of claim 1 further including the step of specifying a subset of the data points in the first mesh which are to be preserved in the base domain mesh.
Claim 7
Dependent Claim
18 words
The method of claim 1 further including the step of applying a smoothing process to the mapping function.
Claim 8
Dependent Claim
37 words
The method of claim 1 wherein the first mesh has an irregular connectivity, and the method further includes the step of utilizing the base domain and the mapping function to generate a mesh having a regular connectivity.
Claim 9
Dependent Claim
24 words
The method of claim 7 further including the step of utilizing a midpoint subdivision process to determine data points in the regular connectivity mesh.
Claim 10
Dependent Claim
28 words
The method of claim 1 further including the step of utilizing the base domain and the mapping function to generate an adaptive mesh representative of the first mesh.
Claim 11
Dependent Claim
94 words
The method of claim 9 wherein the step of utilizing the base domain and the mapping function to generate an adaptive mesh further includes the steps of: computing an error value for each of a plurality of geometric shapes in a current stage of retriangulation; subdividing a given geometric shape in the current stage if its error value is not below a threshold; and repeating the computing and subdividing steps for additional stages of retriangulation until each of a plurality of geometric shapes in the adaptive mesh has an error value below the threshold.
Claim 12
Independent Claim
152 words
An apparatus for processing a set of data points in the form of a first geometric mesh representative of a surface, the apparatus comprising: a memory for storing at least a portion of first mesh; and at least one processor operative (i) to process the data points to generate a plurality of progressively coarser meshes including a base domain mesh, such that the first mesh and each of the progressively coarser meshes each correspond to a different level of coarseness; and (ii) to generate a mapping function in the form of a bijection which maps at least a subset of the data points from the first mesh to the base domain mesh; wherein the mapping function is generated as a combination of a plurality of sub-functions, each of which relates data points in a mesh of a given level of coarseness to data points in a mesh of the ext coarser level.
Claim 13
Independent Claim
152 words
An apparatus for processing a set of data points in the form of a first geometric mesh representative of a surface, the apparatus comprising: a memory for storing at least a portion of first mesh; and at least one processor operative (i) to process the data points to generate a plurality of progressively coarser meshes including a base domain mesh, such that the first mesh and each of the progressively coarser meshes each correspond to a different level of coarseness; and (ii) to generate a mapping function in the form of a bijection which maps at least a subset of the data points from the first mesh to the base domain mesh; wherein the mapping function is generated as a combination of a plurality of sub-functions, each of which relates data points in a mesh of a given level of coarseness to data points in a mesh of the ext coarser level.
Claim 14
Dependent Claim
25 words
The apparatus of claim 11 wherein each of the meshes is a triangular mesh comprising a plurality of triangles having vertices corresponding to data points.
Claim 15
Dependent Claim
21 words
The apparatus of claim 11 wherein the mapping function and at least a subset of the sub-functions each comprise a bijection.
Claim 16
Dependent Claim
53 words
The apparatus of claim 11 wherein the processor is further operative to generate a given one of the sub-functions by removing data points in a mesh of a given level of coarseness and assigning barycentric coordinates to the removed points based on data points remaining in the mesh of the next coarser level.
Claim 17
Dependent Claim
26 words
The apparatus of claim 11 wherein a subset of the data points in the first mesh are specified to be preserved in the base domain mesh.
Claim 18
Dependent Claim
20 words
The apparatus of claim 11 wherein the processor is further operative to apply a smoothing process to the mapping function.
Claim 19
Dependent Claim
36 words
The apparatus of claim 11 wherein the first mesh has an irregular connectivity, and the processor is further operative to utilize the base domain and the mapping function to generate a mesh having a regular connectivity.
Claim 20
Dependent Claim
26 words
The apparatus of claim 17 wherein the processor is further operative to utilize a midpoint subdivision process to determine data points in the regular connectivity mesh.
Claim 21
Dependent Claim
30 words
The apparatus of claim 11 wherein the processor is further operative to utilize the base domain and the mapping function to generate an adaptive mesh representative of the first mesh.
Claim 22
Dependent Claim
84 words
The apparatus of claim 19 wherein the processor is further operative (i) to compute an error value for each of a plurality of geometric shapes in a current stage of retriangulation; (ii) to subdivide a given geometric shape in the current stage if its error value is not below a threshold; and (iii) to repeat the computing and subdividing operations for additional stages of retriangulation until each of a plurality of geometric shapes in the adaptive mesh has an error value below the threshold.
Claim 23
Independent Claim
173 words
A method of processing a set of data points in the form of a first geometric mesh representative of a surface, the method comprising the steps of: processing the data points to generate a plurality of progressively coarser meshes including a base domain mesh, such that the first mesh and each of the progressively coarser meshes each correspond to a different level of coarseness; and generating a mapping function which maps at least a subset of the data points from the first mesh to the base domain mesh, wherein the mapping function is generated as a combination of a plurality of sub-functions, each of which relates data points in a mesh of a given level of coarseness to data points in a mesh of the next coarser level, and further wherein a given one of the sub-functions is generated by removing data points in a mesh of a given level of coarseness and assigning barycentric coordinates to the removed points based on data points remaining in the mesh of the next coarser level.
Claim 24
Independent Claim
173 words
A method of processing a set of data points in the form of a first geometric mesh representative of a surface, the method comprising the steps of: processing the data points to generate a plurality of progressively coarser meshes including a base domain mesh, such that the first mesh and each of the progressively coarser meshes each correspond to a different level of coarseness; and generating a mapping function which maps at least a subset of the data points from the first mesh to the base domain mesh, wherein the mapping function is generated as a combination of a plurality of sub-functions, each of which relates data points in a mesh of a given level of coarseness to data points in a mesh of the next coarser level, and further wherein a given one of the sub-functions is generated by removing data points in a mesh of a given level of coarseness and assigning barycentric coordinates to the removed points based on data points remaining in the mesh of the next coarser level.
Claim 25
Independent Claim
189 words
An apparatus for processing a set of data points in the form of a first geometric mesh representative of a surface, the apparatus comprising: a memory for storing at least a portion of first mesh; and at least one processor operative (i) to process the data points to generate a plurality of progressively coarser meshes including a base domain mesh, such that the first mesh and each of the progressively coarser meshes each correspond to a different level of coarseness; and (ii) to generate a mapping function which maps at least a subset of the data points from the first mesh to the base domain mesh; wherein the mapping function is generated as a combination of a plurality of sub-functions, each of which relates data points in a mesh of a given level of coarseness to data points in a mesh of the next coarser level, and a given one of the sub-functions is generated by removing data points in a mesh of a given level of coarseness and assigning barycentric coordinates to the removed points based on data points remaining in the mesh of the next coarser level.—
Claim 26
Independent Claim
189 words
An apparatus for processing a set of data points in the form of a first geometric mesh representative of a surface, the apparatus comprising: a memory for storing at least a portion of first mesh; and at least one processor operative (i) to process the data points to generate a plurality of progressively coarser meshes including a base domain mesh, such that the first mesh and each of the progressively coarser meshes each correspond to a different level of coarseness; and (ii) to generate a mapping function which maps at least a subset of the data points from the first mesh to the base domain mesh; wherein the mapping function is generated as a combination of a plurality of sub-functions, each of which relates data points in a mesh of a given level of coarseness to data points in a mesh of the next coarser level, and a given one of the sub-functions is generated by removing data points in a mesh of a given level of coarseness and assigning barycentric coordinates to the removed points based on data points remaining in the mesh of the next coarser level.—
Claim 27
Dependent Claim
197 words
An article of manufacture comprising a computer-readable storage medium for storing one or more software programs for processing a set of data points in the form of a first geometric mesh representative of a surface, wherein the one or more software programs when executed by a processor implement the steps of: processing the data points to generate a plurality of progressively coarser meshes including a base domain mesh, such that the first mesh and each of the progressively coarser meshes each correspond to a different level of coarseness; and generating a mapping function which maps at least a subset of the data points from the first mesh to the base domain mesh, wherein the mapping function is generated as a combination of a plurality of sub-functions, each of which relates data points in a mesh of a given level of coarseness to data points in a mesh of the next coarser level, and further wherein a given one of the sub-functions is generated by removing data points in a mesh of a given level of coarseness and assigning barycentric coordinates to the removed points based on data points remaining in the mesh of the next coarser level.
Claim 28
Dependent Claim
197 words
An article of manufacture comprising a computer-readable storage medium for storing one or more software programs for processing a set of data points in the form of a first geometric mesh representative of a surface, wherein the one or more software programs when executed by a processor implement the steps of: processing the data points to generate a plurality of progressively coarser meshes including a base domain mesh, such that the first mesh and each of the progressively coarser meshes each correspond to a different level of coarseness; and generating a mapping function which maps at least a subset of the data points from the first mesh to the base domain mesh, wherein the mapping function is generated as a combination of a plurality of sub-functions, each of which relates data points in a mesh of a given level of coarseness to data points in a mesh of the next coarser level, and further wherein a given one of the sub-functions is generated by removing data points in a mesh of a given level of coarseness and assigning barycentric coordinates to the removed points based on data points remaining in the mesh of the next coarser level.
Claim 29
Dependent Claim
158 words
An article of manufacture comprising a computer-readable storage medium for storing one or more software programs for processing a set of data points in the form of a first geometric mesh representative of a surface, wherein the one or more software programs when executed by a processor implement the steps of: processing the data points to generate a plurality of progressively coarser meshes including a base domain mesh, such that the first mesh and each of the progressively coarser meshes each correspond to a different level of coarseness; and generating a mapping function in the form of a bijection which maps at least a subset of the data points from the first mesh to the base domain mesh, wherein the mapping function is generated as a combination of a plurality of sub-functions, each of which relates data points in a mesh of a given level of coarseness to data points in a mesh of the next coarser level.
Claim 30
Dependent Claim
158 words
An article of manufacture comprising a computer-readable storage medium for storing one or more software programs for processing a set of data points in the form of a first geometric mesh representative of a surface, wherein the one or more software programs when executed by a processor implement the steps of: processing the data points to generate a plurality of progressively coarser meshes including a base domain mesh, such that the first mesh and each of the progressively coarser meshes each correspond to a different level of coarseness; and generating a mapping function in the form of a bijection which maps at least a subset of the data points from the first mesh to the base domain mesh, wherein the mapping function is generated as a combination of a plurality of sub-functions, each of which relates data points in a mesh of a given level of coarseness to data points in a mesh of the next coarser level.
References Cited (Backward Citations)
US5602979A
Cited
US5966133A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-09-03 | 2005-03-05 | 2005-09-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-09-03 | 2009-03-05 | 2009-09-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-09-03 | 2013-03-05 | 2013-09-04 | $7700.00 | Window Closed / Lapsed |