US6046744A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Selective refinement of progressive meshes
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1997-02-07
•
Granted: 2000-04-04
•
Expires: 2017-02-07
Abstract
Abstract An efficient, lossless, continuous-resolution representation (the "PM representation") of highly detailed geometric models for computer graphics specifies a succession of progressively more detailed polygonal meshes (i.e., "progressive meshes") as a base polygonal mesh and a sequence of complete mesh refinement transformations (e.g., the vertex split transformation) that approximate the model at progressively finer levels of detail. Procedures for storing and transmitting geometric models using the PM representation address several practical problems in computer graphics: smooth geomorphing of level-of-detail approximations, progressive transmission, mesh compression, and selective refinement. An optimized mesh simplification procedure constructs the PM representation of a model from an arbitrary polygonal mesh, while preserving the geometry of the original mesh as well as its overall appearance as defined by its discrete and scalar appearance attributes such as material identifiers, color values, normals, and texture coordinates. In particular, the PM representation and these procedures preserve discontinuity curves such as creases and material boundaries of the geometric model.
Inventors
- 👤 Hugues H. Hoppe
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 21:12
CPC Classifications
G; G06; G06T; G06T9/00; G06T9/001; G06T17/00; G06T17/20
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
213 words
A method of displaying selectively refined computer graphics views of a multi-dimensional object represented in a progressive resolution data structure having a base mesh record and a stream of mesh refinement records, the base mesh record defining a base mesh representative of the object at a low level of detail, the mesh refinement records defining a sequence of mesh refinement transformations for refining the base mesh into an arbitrary mesh representative of the object at a high level of detail, the mesh refinement transformations being complete, the method comprising: forming a selectively refined mesh at an initial coarse level of detail from the base mesh record; for each of a plurality of the mesh refinement records in the stream, performing the steps of: (a) checking whether the mesh refinement transformation defined by the mesh refinement record meets a selection criteria for limiting refinement to a desired portion of the object; and (b) if the mesh refinement transformation defined by the mesh refinement record meets the selection criteria, applying such mesh refinement transformation to the selectively refined mesh and thereby increasing the level of detail of the selectively refined mesh in the desired portion of the object; and rendering and displaying a computer graphics view of the object based on the selectively refined mesh.
Claim 2
Independent Claim
213 words
A method of displaying selectively refined computer graphics views of a multi-dimensional object represented in a progressive resolution data structure having a base mesh record and a stream of mesh refinement records, the base mesh record defining a base mesh representative of the object at a low level of detail, the mesh refinement records defining a sequence of mesh refinement transformations for refining the base mesh into an arbitrary mesh representative of the object at a high level of detail, the mesh refinement transformations being complete, the method comprising: forming a selectively refined mesh at an initial coarse level of detail from the base mesh record; for each of a plurality of the mesh refinement records in the stream, performing the steps of: (a) checking whether the mesh refinement transformation defined by the mesh refinement record meets a selection criteria for limiting refinement to a desired portion of the object; and (b) if the mesh refinement transformation defined by the mesh refinement record meets the selection criteria, applying such mesh refinement transformation to the selectively refined mesh and thereby increasing the level of detail of the selectively refined mesh in the desired portion of the object; and rendering and displaying a computer graphics view of the object based on the selectively refined mesh.
Claim 3
Dependent Claim
36 words
The method of claim 1 wherein the mesh refinement transformations are vertex split transformations, each of which modify a split vertex having two side vertices to introduce a new vertex and at least one new face.
Claim 4
Dependent Claim
51 words
The method of claim 2 wherein the step of checking whether the mesh refinement transformation meets the selection criteria comprises: checking whether the split vertex and the two side vertices are present in the selectively refined mesh; and checking whether the split vertex is within the desired portion of the object.
Claim 5
Dependent Claim
55 words
The method of claim 2 wherein the step of checking whether the mesh refinement transformation meets the selection criteria comprises: checking whether closest living ancestors of the two side vertices are adjacent to the split vertex in the selectively refined mesh; and checking whether the split vertex is within the desired portion of the object.
Claim 6
Dependent Claim
39 words
The method of claim 2 wherein the computer graphics view is a view of a portion of the object within a view frustrum, and the selection criteria limits refinement to the portion of the object within the view frustrum.
Claim 7
Dependent Claim
43 words
The method of claim 5 comprising: determining that a mesh refinement transformation meets the selection criteria if both the split vertex and the two side vertices are all present in the selectively refined mesh, and the split vertex is within the view frustrum.
Claim 8
Dependent Claim
47 words
The method of claim 5 comprising: determining that a mesh refinement transformation meets the selection criteria if both the split vertex is adjacent to closest living ancestor vertices of the two side vertices in the selectively refined mesh, and the split vertex is within the view frustrum.
Claim 9
Dependent Claim
45 words
The method of claim 5 wherein the step of checking whether the mesh refinement transformation meets the selection criteria comprises: checking whether any of a plurality of faces of the selectively refined mesh that are adjacent to the split vertex are within the view frustrum.
Claim 10
Dependent Claim
73 words
The method of claim 5 wherein the step of checking whether the mesh refinement transformation meets the selection criteria comprises: calculating a signed projected screen area of each of a plurality of faces of the selectively refined mesh that are adjacent to the split vertex, the signed projected screen area of each face having a sign and a magnitude; and checking whether the faces all have signed projected screen areas with equal signs.
Claim 11
Dependent Claim
81 words
The method of claim 5 wherein the step of checking whether the mesh refinement transformation meets the selection criteria comprises: calculating a signed projected screen area of each of a plurality of faces of the selectively refined mesh that are adjacent to the split vertex, the signed projected screen area of each face having a sign and a magnitude; and checking whether a sum of the signed projected screen areas of the faces is greater than a predetermined screen area threshold.
Claim 12
Dependent Claim
43 words
The method of claim 5 comprising: determining that a mesh refinement transformation does not meet the selection criteria if the mesh refinement transformation modifies a portion of the selectively refined mesh within the view frustrum, but not visible in the computer graphics view.
Claim 13
Dependent Claim
72 words
The method of claim 5 comprising: constructing a geomorph for interpolating between two levels of detail of the selectively refined mesh according to a blend parameter; evaluating the geomorph at a plurality of values of the blend parameter; and rendering and displaying computer graphics views of the object based on the geomorph evaluated at the values whereby the computer graphics views form a smooth visual transition between the two levels of detail.
Claim 14
Dependent Claim
212 words
A computer graphics system for displaying selectively refined views of a multi-dimensional object, comprising: a data storage memory for storing a progressive resolution data structure having a base mesh record and a stream of mesh refinement records, the base mesh record defining a base mesh representative of the object at a low level of detail, the mesh refinement records defining a sequence of mesh refinement transformations for refining the base mesh into an arbitrary mesh representative of the object at a high level of detail, the mesh refinement transformations being complete; a selective refinement processor for forming a selectively refined mesh at an initial coarse level of detail from the base mesh record, for checking whether the mesh refinement transformation defined by each of a plurality of the mesh refinement records in the stream meets a selection criteria for limiting refinement to a desired portion of the object, and applying those of the mesh refinement transformations that meet the selection criteria to the selectively refined mesh thereby increasing the level of detail of the selectively refined mesh in the desired portion of the object; a graphics engine for rendering a computer graphics view of the object based on the selectively refined mesh; and a display device for displaying the computer graphics view.
Claim 15
Dependent Claim
212 words
A computer graphics system for displaying selectively refined views of a multi-dimensional object, comprising: a data storage memory for storing a progressive resolution data structure having a base mesh record and a stream of mesh refinement records, the base mesh record defining a base mesh representative of the object at a low level of detail, the mesh refinement records defining a sequence of mesh refinement transformations for refining the base mesh into an arbitrary mesh representative of the object at a high level of detail, the mesh refinement transformations being complete; a selective refinement processor for forming a selectively refined mesh at an initial coarse level of detail from the base mesh record, for checking whether the mesh refinement transformation defined by each of a plurality of the mesh refinement records in the stream meets a selection criteria for limiting refinement to a desired portion of the object, and applying those of the mesh refinement transformations that meet the selection criteria to the selectively refined mesh thereby increasing the level of detail of the selectively refined mesh in the desired portion of the object; a graphics engine for rendering a computer graphics view of the object based on the selectively refined mesh; and a display device for displaying the computer graphics view.
Claim 16
Dependent Claim
38 words
The computer graphics system of claim 13 wherein the mesh refinement transformations are vertex split transformations, each of which modify a split vertex having two side vertices to introduce a new vertex and at least one new face.
Claim 17
Dependent Claim
30 words
The computer graphics system of claim 14 wherein the selection criteria comprises the condition that the split vertex and the two side vertices are present in the selectively refined mesh.
Claim 18
Dependent Claim
26 words
The computer graphics system of claim 14 wherein the selection criteria comprises the condition that the split vertex is within the desired portion of the object.
Claim 19
Dependent Claim
34 words
The computer graphics system of claim 14 wherein the selection criteria comprises the condition that closest living ancestors of the two side vertices are adjacent to the split vertex in the selectively refined mesh.
Claim 20
Dependent Claim
41 words
The computer graphics system of claim 14 wherein the computer graphics view is a view of a portion of the object within a view frustrum, and the selection criteria limits refinement to the portion of the object within the view frustrum.
Claim 21
Dependent Claim
23 words
The computer graphics system of claim 18 wherein the selection criteria comprises the condition that the split vertex is within the view frustrum.
Claim 22
Dependent Claim
38 words
The computer graphics system of claim 18 wherein the selection criteria comprises the condition that any of a plurality of faces of the selectively refined mesh that are adjacent to the split vertex are within the view frustrum.
Claim 23
Dependent Claim
43 words
The computer graphics system of claim 18 wherein the selection criteria comprises the condition that a signed projected screen area of each of a plurality of faces of the selectively refined mesh that are adjacent to the split vertex all have equal signs.
Claim 24
Dependent Claim
47 words
The computer graphics system of claim 18 wherein the selection criteria comprises the condition that a sum of signed projected screen areas of a plurality of faces of the selectively refined mesh that are adjacent to the split vertex is greater than a predetermined screen area threshold.
Claim 25
Dependent Claim
35 words
The computer graphics system of claim 18 wherein the selection criteria comprises the condition that the mesh refinement transformation modifies a portion of the selectively refined mesh that is visible in the computer graphics view.
Claim 26
Dependent Claim
76 words
The computer graphics system of claim 13 comprising: a geomorph processor for constructing a geomorph which interpolates between two levels of detail of the selectively refined mesh according to a blend parameter, and for evaluating the geomorph at a plurality of values of the blend parameter; and the graphics engine rendering computer graphics views of the object based on the geomorph evaluated at the values for a smooth visual transition between the two levels of detail.
References Cited (Backward Citations)
US5590248A
Cited
US5619625A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-04-04 | 2003-10-04 | 2004-04-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-04-04 | 2007-10-04 | 2008-04-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-04-04 | 2011-10-04 | 2012-04-04 | $7700.00 | Window Closed / Lapsed |