EP0784295A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Mesh simplification and construction of meshes
Assignee: Microsoft Corp
•
Filing: 1997-01-07
•
Granted: —
•
Expires: 2017-01-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
- 👤 Hughes H. Hoppe
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-09 14:10
CPC Classifications
G; G06; G06T; G06T9/00; G06T9/001; G06T17/00; G06T17/20
Claims Analysis
Total Claims: 17
Claim 1
Independent Claim
110 words
In a computer, a method of simplifying an arbitrary initial mesh having a plurality of vertices and a connectivity of the vertices defining edges between connected pairs of the vertices and faces defined by plural connected edges for representing multi-dimensional objects with computer graphics, comprising: (a) choosing an edge of the mesh; (b) performing an edge collapse transformation on the edge to produce a simpler mesh wherein the pair of vertices connected by the edge is replaced by the edge collapse transformation with a single vertex; and (c) performing a plurality of iterations of the steps (a) and (b) to produce a base mesh having a desired level of detail.
Claim 2
Dependent Claim
110 words
In a computer, a method of simplifying an arbitrary initial mesh having a plurality of vertices and a connectivity of the vertices defining edges between connected pairs of the vertices and faces defined by plural connected edges for representing multi-dimensional objects with computer graphics, comprising: (a) choosing an edge of the mesh; (b) performing an edge collapse transformation on the edge to produce a simpler mesh wherein the pair of vertices connected by the edge is replaced by the edge collapse transformation with a single vertex; and (c) performing a plurality of iterations of the steps (a) and (b) to produce a base mesh having a desired level of detail.
Claim 3
Dependent Claim
40 words
The method of claim 1 further comprising: (d) performing the iterations of the steps (a) and (b) until the simpler mesh has a level of detail equal to a simplest mesh of a same topological type as the initial mesh.
Claim 4
Dependent Claim
150 words
In a computer, a method of constructing a variable resolution representation of a multi-dimensional object from an arbitrary initial mesh representation of the object for displaying computer graphics views of the object, the arbitrary initial mesh having a plurality of vertices and a connectivity of the vertices defining a plurality of edges between connected pairs of the vertices, the method comprising: choosing a succession of mesh simplifying transformations that, when applied successively beginning with the arbitrary initial mesh, yield a succession of progressively simpler meshes, and a last in the succession of mesh simplifying transformations yielding a base mesh; and recording the base mesh and a succession of mesh refining transformations which are an inverse of the mesh simplifying transformations and in a reverse order of the succession of mesh simplifying transformations, the mesh refining transformations exactly reproducing the arbitrary initial mesh when applied successively beginning with the base mesh.
Claim 5
Dependent Claim
150 words
In a computer, a method of constructing a variable resolution representation of a multi-dimensional object from an arbitrary initial mesh representation of the object for displaying computer graphics views of the object, the arbitrary initial mesh having a plurality of vertices and a connectivity of the vertices defining a plurality of edges between connected pairs of the vertices, the method comprising: choosing a succession of mesh simplifying transformations that, when applied successively beginning with the arbitrary initial mesh, yield a succession of progressively simpler meshes, and a last in the succession of mesh simplifying transformations yielding a base mesh; and recording the base mesh and a succession of mesh refining transformations which are an inverse of the mesh simplifying transformations and in a reverse order of the succession of mesh simplifying transformations, the mesh refining transformations exactly reproducing the arbitrary initial mesh when applied successively beginning with the base mesh.
Claim 6
Dependent Claim
82 words
The method of claim 5 wherein the mesh simplifying transformations are all edge collapse transformations, the method further comprising, for each of the succession of progressively simpler meshes beginning with the arbitrary initial mesh: choosing a current edge collapse transformation out of a plurality of candidate edge collapse transformations on a current mesh of the succession of progressively simpler meshes; and applying the edge collapse transformation to the current mesh to yield a next mesh in the succession of progressively simpler meshes.
Claim 7
Dependent Claim
47 words
The method of claim 6 wherein the step of choosing the current edge collapse transformation comprises: calculating an appearance metric for each of the candidate edge collapse transformations; and choosing the current edge collapse transformation out of the candidate edge collapse transformations to optimize the appearance metric.
Claim 8
Dependent Claim
25 words
The method of claim 7 further comprising: imposing a predetermined maximum dihedral angle restriction and a manifold preservation restriction on the candidate edge collapse transformations.
Claim 9
Dependent Claim
46 words
The method of claim 7 wherein the step of calculating the appearance metric for each of the candidate edge collapse transformations comprises: measuring a geometric deviation between the initial arbitrary mesh and a mesh resulting from applying the candidate edge collapse transformation to the current mesh.
Claim 10
Dependent Claim
112 words
The method of claim 7 wherein the step of calculating the appearance metric for each of the candidate edge collapse transformations comprises: sampling geometric attributes at a plurality of points on a surface of the initial arbitrary mesh; measuring a geometric deviation between the geometric attributes of the initial arbitrary mesh at the points and a resultant mesh resulting from applying the candidate edge collapse transformation to the current mesh; accumulating the geometric deviation with a spring term having an adaptive spring constant; and setting the adaptive spring constant according to a ratio of a number of the points to a number of faces in a neighborhood of the edge collapse transformation.
Claim 11
Independent Claim
53 words
The method according to any one of claims 7 or 9 wherein the step of calculating the appearance metric for each of the candidate edge collapse transformations comprises: measuring a scalar attribute deviation between the initial arbitrary mesh and a mesh resulting from applying the candidate edge collapse transformation to the current mesh.
Claim 12
Dependent Claim
68 words
The method of claim 7 wherein the step of calculating the appearance metric for each of the candidate edge collapse transformations comprises: sampling geometric attributes at a plurality of points on sharp edges of the initial arbitrary mesh; and measuring a geometric deviation between the geometric attributes at the points and sharp edges of a mesh resulting from applying the candidate edge collapse transformation to the current mesh.
Claim 13
Dependent Claim
47 words
The method of claim 7 wherein the step of choosing the current edge collapse transformation comprises: checking whether a choice for the current edge collapse transformation modifies a discontinuity curve topology of the current mesh; and disallowing the choice if the choice modifies the discontinuity curve topology.
Claim 14
Dependent Claim
47 words
The method of claim 7 wherein the step of choosing the current edge collapse transformation comprises: checking whether a choice for the current edge collapse transformation modifies a discontinuity curve topology of the current mesh; and penalizing the choice if the choice modifies the discontinuity curve topology.
Claim 15
Dependent Claim
170 words
A computer based system for constructing a variable resolution representation of a multi-dimensional object from an arbitrary initial mesh representation of the object for displaying computer graphics views of the object, the arbitrary initial mesh having a plurality of vertices and a connectivity of the vertices defining a plurality of edges between connected pairs of the vertices, the system comprising: a mesh transformation processor for iteratively choosing a mesh simplifying transformation, and applying the chosen mesh simplifying transformation to a current mesh in a succession of progressively simpler meshes beginning with the initial arbitrary mesh to yield a next mesh in the succession, a last in the succession of mesh simplifying transformations yielding a base mesh; and an encoder for recording the base mesh and a succession of mesh refining transformations which are an inverse of the mesh simplifying transformations and in a reverse order of the succession of mesh simplifying transformations, the mesh refining transformations exactly reproducing the arbitrary initial mesh when applied successively beginning with the base mesh.
Claim 16
Dependent Claim
170 words
A computer based system for constructing a variable resolution representation of a multi-dimensional object from an arbitrary initial mesh representation of the object for displaying computer graphics views of the object, the arbitrary initial mesh having a plurality of vertices and a connectivity of the vertices defining a plurality of edges between connected pairs of the vertices, the system comprising: a mesh transformation processor for iteratively choosing a mesh simplifying transformation, and applying the chosen mesh simplifying transformation to a current mesh in a succession of progressively simpler meshes beginning with the initial arbitrary mesh to yield a next mesh in the succession, a last in the succession of mesh simplifying transformations yielding a base mesh; and an encoder for recording the base mesh and a succession of mesh refining transformations which are an inverse of the mesh simplifying transformations and in a reverse order of the succession of mesh simplifying transformations, the mesh refining transformations exactly reproducing the arbitrary initial mesh when applied successively beginning with the base mesh.
Claim 17
Dependent Claim
62 words
The computer based system of claim 15 comprising: a user interface control for selecting a desired level of detail; and the mesh transformation processor performing iterations of choosing and applying the mesh simplifying transformations until applying a last of the mesh simplifying transformation yields a next mesh having a level of detail at least as simple as the desired level of detail.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.