Patent US6879324B1 successfully refreshed from Google Patents.
US6879324B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Regional progressive meshes
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1998-07-14
•
Granted: 2005-04-12
•
Expires: 2018-07-14
Abstract
Abstract A regional progressive mesh provides support for real-time rendering of large-scale surfaces with locally adapting surface geometric complexity according to changing view parameters. The regional progressive mesh is constructed by subdividing an initial detailed mesh one or more times into multiple sub-regions as an iterative or recursive process. Each sub-region is separately simplified, and the localized transformations recorded in separate segments in a sequence of mesh refinement transformations that form the progressive mesh representation. The resulting regionalized organization of mesh refinement transformations reduces the working set of memory pages containing progressive mesh data needed for real-time view-dependent adaptation and rendering of the mesh surface. An exact approximate error measurement of a vertex split transformation also is defined as the maximum height deviation at enumerated vertices in the open neighborhood of the transformation relative to a regular triangulation of grid points, where the enumerated vertices include the grid points internal to the faces adjacent the split vertex and the grid line crossings internal to edges adjacent the split vertex.
Inventors
- 👤 Hugues H. Hoppe
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 14:17
CPC Classifications
G; G06; G06T; G06T17/00; G06T17/20; G06T17/205
Claims Analysis
Total Claims: 30
Claim 1
Independent Claim
95 words
A computer-implemented method for generating a representation having a hierarchical region-based organization for a mesh, such method receiving an input mesh, the method comprising: sub-dividing the input mesh into plural sub-regions; identifying a plurality of operations per sub-region simplifying the sub-regions; and storing, in the representation having a hierarchical region-based organization, data indicating a plurality of refinement operations derived from the plurality of operations per sub-region simplifying the sub-regions, wherein the storing comprises grouping the data indicating the plurality of refinement operations according to the sub-region within the input mesh whereat the refinement operations operate.
Claim 2
Dependent Claim
95 words
A computer-implemented method for generating a representation having a hierarchical region-based organization for a mesh, such method receiving an input mesh, the method comprising: sub-dividing the input mesh into plural sub-regions; identifying a plurality of operations per sub-region simplifying the sub-regions; and storing, in the representation having a hierarchical region-based organization, data indicating a plurality of refinement operations derived from the plurality of operations per sub-region simplifying the sub-regions, wherein the storing comprises grouping the data indicating the plurality of refinement operations according to the sub-region within the input mesh whereat the refinement operations operate.
Claim 3
Dependent Claim
29 words
The method of claim 1 , in which the input mesh is initially broken into plural arbitrarily-shaped regions, and the method is separately performed on each such arbitrarily-shaped region.
Claim 4
Dependent Claim
29 words
The method of claim 1 , wherein the input mesh is initially simplified into a simplified mesh having a predetermined quality level, and the simplified mesh is further simplified.
Claim 5
Dependent Claim
24 words
The method of claim 1 , further comprising the steps of: combining the plural sub-regions into a single region; and simplifying the single region.
Claim 6
Dependent Claim
55 words
The method of claim 1 , in which an encoding of the mesh includes plural vertices interconnected by plural edges, and the identifying comprises simplification of the mesh via performing an edge collapse operation on an edge joining a first and a second vertex, wherein simplification is effected by an in-place update of the encoding.
Claim 7
Dependent Claim
36 words
The method of claim 1 , further comprising: testing for a stop state; and repeatedly performing the sub-dividing until the stop state is met; wherein the testing for the stop state includes detecting a mesh shape.
Claim 8
Dependent Claim
55 words
The method of claim 1 , further comprising: testing for a stop state; and repeatedly performing the sub-dividing until the stop state is met; wherein the testing for the stop state comprises detecting a size of at least one of the sub-regions, where size is determined at least in part by a number of vertices.
Claim 9
Dependent Claim
46 words
The method of claim 1 , further comprising: testing for a stop state; and repeatedly performing the sub-dividing until the stop state is true; wherein the stop state is true when at least one of the sub-regions has a level of detail below a predetermined threshold.
Claim 10
Dependent Claim
34 words
The method of claim 1 wherein the representation represents a plurality of levels of detail; and the data indicating the operations is further grouped according to a level of detail generated by the operations.
Claim 11
Dependent Claim
32 words
The method of claim 1 wherein the operations are edge collapses; and the data indicating the operations comprises information indicating vertex splits, wherein the vertex splits are inverses of the edge collapses.
Claim 12
Dependent Claim
14 words
A computer-readable medium comprising computer-executable instructions for performing the method of claim 1 .
Claim 13
Dependent Claim
136 words
A computer-implemented method for generating a representation for a recursion input mesh, such method receiving a fully detailed mesh as an initial input, in which the recursion input mesh is stored in a memory having a size, the method comprising: testing for a recursion stop state, such state being true or false, and wherein the stop state is determined at least in part by the size of the memory required to store the recursion input mesh; if the state is true, then simplifying an input mesh of a current recursion of the method and falling back in the recursion; and if the state is false, then sub-dividing the recursion input mesh into plural sub-regions, and recursing on each of the plural sub-regions wherein a plurality of mesh operations operate within at least one of the subregions.
Claim 14
Dependent Claim
136 words
A computer-implemented method for generating a representation for a recursion input mesh, such method receiving a fully detailed mesh as an initial input, in which the recursion input mesh is stored in a memory having a size, the method comprising: testing for a recursion stop state, such state being true or false, and wherein the stop state is determined at least in part by the size of the memory required to store the recursion input mesh; if the state is true, then simplifying an input mesh of a current recursion of the method and falling back in the recursion; and if the state is false, then sub-dividing the recursion input mesh into plural sub-regions, and recursing on each of the plural sub-regions wherein a plurality of mesh operations operate within at least one of the subregions.
Claim 15
Dependent Claim
53 words
The method of claim 12 , in which a host computing system having a memory and a corresponding memory page size is used to implement the method, and wherein the stop state is true when the memory required to store the recursion input mesh is less than or equal to such page size.
Claim 16
Independent Claim
71 words
A method comprising: identifying a plurality of operations that, when applied to a simplified mesh, generate a more refined version of the simplified mesh; and organizing representations of the operations into groups of plural operations according to within which region out of a plurality of regions of the simplified mesh the operations refine the mesh; wherein at least two of the plurality of regions have a plurality of operations associated therewith.
Claim 17
Independent Claim
71 words
A method comprising: identifying a plurality of operations that, when applied to a simplified mesh, generate a more refined version of the simplified mesh; and organizing representations of the operations into groups of plural operations according to within which region out of a plurality of regions of the simplified mesh the operations refine the mesh; wherein at least two of the plurality of regions have a plurality of operations associated therewith.
Claim 18
Dependent Claim
14 words
A computer-readable medium comprising computer-executable instructions for performing the method of claim 14 .
Claim 19
Dependent Claim
27 words
The method of claim 14 wherein the organizing further organizes the representations of the operations into groups based on a level of detail generated by the groups.
Claim 20
Dependent Claim
38 words
The method of claim 14 further comprising: generating a simplified base mesh; storing the simplified base mesh in a data structure; and storing the representations of the operations in the data structure according to a hierarchical region-based organization.
Claim 21
Independent Claim
85 words
A method of generating a progressive mesh representation having a hierarchical region-based organization based on a mesh, the method comprising: for a plurality of sub-regions of the mesh at a level of detail: identifying a plurality of operations for regenerating the sub-regions from simplified versions of the sub-regions; and storing, as a group by sub-region, representations indicating the plurality of operations for regenerating the sub-regions from the simplified versions in the representation at a hierarchical level related to the level of detail for the sub-regions.
Claim 22
Independent Claim
85 words
A method of generating a progressive mesh representation having a hierarchical region-based organization based on a mesh, the method comprising: for a plurality of sub-regions of the mesh at a level of detail: identifying a plurality of operations for regenerating the sub-regions from simplified versions of the sub-regions; and storing, as a group by sub-region, representations indicating the plurality of operations for regenerating the sub-regions from the simplified versions in the representation at a hierarchical level related to the level of detail for the sub-regions.
Claim 23
Dependent Claim
30 words
The method of claim 18 wherein: the operations are edge collapses; and the representations indicating the operations represent vertex splits, wherein the vertex splits are inverses of the edge collapses.
Claim 24
Independent Claim
85 words
A method of generating a mesh representation having a hierarchical region-based organization based on a mesh, the method comprising: repeatedly subdividing the mesh into plural sub-regions until a stop state is met for at least a plurality of the sub-regions; simplifying the plurality of the sub-regions of the mesh; combining a plurality of the simplified sub-regions into a composite simplified mesh; and storing the composite simplified mesh in the mesh representation wherein a plurality of mesh operations operate within at least one of the subregions.
Claim 25
Independent Claim
85 words
A method of generating a mesh representation having a hierarchical region-based organization based on a mesh, the method comprising: repeatedly subdividing the mesh into plural sub-regions until a stop state is met for at least a plurality of the sub-regions; simplifying the plurality of the sub-regions of the mesh; combining a plurality of the simplified sub-regions into a composite simplified mesh; and storing the composite simplified mesh in the mesh representation wherein a plurality of mesh operations operate within at least one of the subregions.
Claim 26
Dependent Claim
12 words
The method of claim 20 further comprising: simplifying the composite simplified mesh.
Claim 27
Independent Claim
121 words
A method of producing a simplified version of a mesh, the method comprising, based on the overall detailed mesh as an initial input: if a stop state has not been met for an input mesh: subdividing the input meshing a plurality of sub-regions; processing the sub-regions as input meshes, the processing comprising simplifying the input sub-regions; combining the simplified sub-regions into a composite simplified mesh; and processing the composite simplified mesh as an input mesh, the processing comprising simplifying the composite simplified mesh; whereby the simplified version of the overall detailed mesh is generated without allocating storage based on the size of the overall detailed mesh and wherein a plurality of mesh operations operate within at least one of the subregions.
Claim 28
Independent Claim
121 words
A method of producing a simplified version of a mesh, the method comprising, based on the overall detailed mesh as an initial input: if a stop state has not been met for an input mesh: subdividing the input meshing a plurality of sub-regions; processing the sub-regions as input meshes, the processing comprising simplifying the input sub-regions; combining the simplified sub-regions into a composite simplified mesh; and processing the composite simplified mesh as an input mesh, the processing comprising simplifying the composite simplified mesh; whereby the simplified version of the overall detailed mesh is generated without allocating storage based on the size of the overall detailed mesh and wherein a plurality of mesh operations operate within at least one of the subregions.
Claim 29
Dependent Claim
105 words
A computer-readable medium comprising a data structure built via the following computer-implemented method for generating a representation having a hierarchical region-based organization for a mesh, such method receiving an input mesh, the method comprising: sub-dividing the input mesh into plural sub-regions; identifying a plurality of operations per sub-region simplifying the sub-regions; and storing, in the representation having a hierarchical region-based organization, data indicating a plurality of refinement operations derived from the plurality of operations per sub-region simplifying the sub-regions, wherein the storing comprises grouping the data indicating the plurality of refinement operations according to the sub-region within the input mesh whereat the refinement operations operate.
Claim 30
Dependent Claim
105 words
A computer-readable medium comprising a data structure built via the following computer-implemented method for generating a representation having a hierarchical region-based organization for a mesh, such method receiving an input mesh, the method comprising: sub-dividing the input mesh into plural sub-regions; identifying a plurality of operations per sub-region simplifying the sub-regions; and storing, in the representation having a hierarchical region-based organization, data indicating a plurality of refinement operations derived from the plurality of operations per sub-region simplifying the sub-regions, wherein the storing comprises grouping the data indicating the plurality of refinement operations according to the sub-region within the input mesh whereat the refinement operations operate.
References Cited (Backward Citations)
US5883629A
Cited
US6009435A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2008-04-11 | 2008-10-11 | 2009-04-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2012-04-11 | 2012-10-11 | 2013-04-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2016-04-11 | 2016-10-11 | 2017-04-12 | $7700.00 | Window Closed / Lapsed |