Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-06-24
2002-03-26
Vo, Cliff N. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S419000
Reexamination Certificate
active
06362820
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to computer graphics systems using mesh representations of three-dimensional objects, and more particularly to improved mesh simplification techniques. Still more particularly, the present invention relates to an edge collapse transformation employing a new quadric error metric (QEM) for use in determining the geometric position of a new vertex created by the edge collapse, the values of appearance attributes associated with the new vertex, and the order in which edges are collapsed.
BACKGROUND OF THE INVENTION
In a computer graphics system, it is desirable to represent an object as efficiently as possible to preserve memory and system bandwidth, and to enhance rendering speed. Computer graphics, such as in computer generated images, animations and effects for motion pictures, television, computer multi-media, computer games, print and other media, often employ detailed geometric models for rendering images of three-dimensional (3D) objects. These models are typically created using commercially available computer-aided modeling and 3D scanning systems. Although some geometric models may be initially defined using high level primitives, for efficient rendering they are typically converted to their lowest common denominator form, polygonal approximations called meshes.
In the simplest case, a mesh consists of a set of vertices and a set of faces. Each vertex specifies the (x, y, z) coordinates of a point in space, and each face defines a polygon by connecting together an ordered subset of the vertices. These conjoined polygons approximate the surface geometry of the modeled object. The polygons may in general have arbitrary numbers of vertices (and even holes). For convenience, the special case of a mesh (called a “triangle mesh”) in which all faces have exactly three vertices is commonly used. Arbitrary meshes composed of polygons having faces with any number of vertices equal to or greater than three can be easily converted to triangle meshes through known triangulation processes. Complex triangle meshes occur extensively in computer graphics as the result of geometric modeling operations, global illumination simulations, and reconstructions from 3D scans.
In the following discussion, the geometry of a triangle mesh is denoted by a tuple (K,V), where K is a simplicial complex specifying the connectivity of the mesh simplices (i.e., the adjacency of the vertices, edges, and faces), and V={v
l
, . . . , v
m
} is the set of vertex positions v
j
=(x
j
,y
j
,z
j
) defining the shape of the mesh in R
3
. (See, e.g., Hoppe et al., Mesh Optimization, Computer Graphics (SIGGRAPH '93 Proceedings) (1993), 19-26 (hereinafter referred to as Hoppe93)). An exemplary mesh
80
is shown in FIG.
1
. The vertices of a triangle mesh (e.g., vertices
82
-
89
of the mesh
80
) are denoted as v
l
, . . . , v
m
; the edges (e.g.,
92
-
95
) are denoted by pairs of adjacent vertices as e={v
j
,v
k
}; and the faces (e.g., faces
100
-
107
) are denoted by triples of interconnected vertices as f={v
j
,v
k
,v
l
}.
Complex (i.e., highly detailed) triangle meshes are notoriously difficult to render, store, and transmit. The meshes created by modeling and scanning systems are typically not optimized for display performance. In most applications, these initial meshes can usually be replaced by nearly indistinguishable approximations with far fewer faces, thereby improving rendering efficiency. One approach to speed up rendering is to replace a complex mesh by a set of level-of-detail (LOD) approximations. A detailed mesh is used when the object is close to the viewer, and coarser approximations (i.e., meshes with fewer vertices and faces) are substituted as the object recedes from the viewer in the image. These LOD approximations can be precomputed automatically using known mesh simplification methods. Thus, a fully detailed mesh is used when the object is close, and coarser approximations are substituted as the object recedes.
Because such meshes are difficult to store, transmit, and render, several techniques have been developed for geometrically simplifying them (see, e.g., Garland and Heckbert, Surface Simplification Using Quadric Error Metrics, Computer Graphics (SIGGRAPH '97 Proceedings) (1997), 209-216 (hereinafter referred to as Garland97); and Hoppe, Progressive Meshes, Computer Graphics (SIGGRAPH '96 Proceedings) (1996), 99-108 (hereinafter referred to as Hoppe96), both of which are incorporated herein by reference). Recent geometric simplification schemes coarsen a mesh through a sequence of edge collapse transformations
110
, as shown in FIG.
1
. These transformations have the advantage that their inverses can be stored concisely to form a progressive mesh representation as described in Hoppe96. Moreover, co-pending application titled Progressive Meshes, U.S. patent application Ser. No. 08/586,953, filed Jan. 11, 1996, commonly assigned and incorporated herein by reference (hereinafter referred to as Hoppe'953), describes a progressive mesh (PM) representation which provides a unified solution to the problems of efficiently storing, transmitting and rendering a mesh of arbitrary complexity. In short, the PM representation of an arbitrary mesh
M
is stored as a coarse or base mesh M
0
together with a sequence of n refinement records that indicate how to incrementally refine M
0
back up to the arbitrary mesh
M
. Each refinement record encodes information associated with a vertex split transformation
116
that transforms the mesh by splitting a vertex
86
′ or v
s
(positioned between side vertices v
l
and v
r
) to add one vertex
89
or v
t
and up to two faces (f
l
={v
s
, v
t
, v
l
} and f
r
={v
s
, v
t
, v
r
}) to the mesh. The PM representation thus defines a continuous sequence of LOD approximations to the arbitrary mesh that are produced by applying the vertex split transformation defined by successive refinement records successively to the base mesh M
0
, resulting in a sequence of progressively more detailed meshes M
0
. . . M
n
, M
n
=
M
. In other words, the PM representation of
M
thus defines a continuous sequence of meshes M
0
,M
1
, . . . ,M
n
of increasing accuracy from which LOD approximations with a desired complexity can be efficiently retrieved.
Thus,
FIG. 1
shows the vertex split transformation
116
and its inverse, the edge collapse transformation
110
. As shown in
FIG. 1
, each edge collapse transformation unifies two adjacent vertices into one (e.g., vertex
86
′ in mesh
112
), thereby removing two faces (
100
and
101
) from the mesh. For the purpose of level-of-detail control, edge collapses are selected to best preserve the appearance of the mesh during simplification. Several appearance metrics have been developed and are described in, for example, Cohen et al., Appearance-Preserving Simplication, Computer Graphics (SIGGRAPH '98 Proceedings) (1998), 115-122; Garland97; and Hoppe96.
In a simplification scheme based on edge collapses, two issues are to be addressed: (1) the position and attributes values v to assign to the unified, or new, vertex v
s
86', and (2) the order in which to perform edge collapses. A common approach is to define a single cost metric C to determine both. The unified vertex is assigned the value v that minimizes C(v), and the same cost C(v) is used to order the candidate edge collapses. Previous approaches to defining C(v) are described below.
Gueziec, Surface Simplification With Variable Tolerance, Proceedings of the Second International Symposium on Medical Robotics and Computer Assisted Surgery (November 1995), 132-139, constrains edge collapses to preserve mesh volume, and bounds the maximum geometric approximation error through a framework of tolerance volumes. Hoppe93 and Hoppe96 sample a set of points on the original mesh, and define C(v) as the sum of their squared distances to the approximating mesh. One drawback is th
Microsoft Corporation
Vo Cliff N.
Woodcock & Washburn LLP
LandOfFree
Quadric metric for simplifying meshes with appearance... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Quadric metric for simplifying meshes with appearance..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quadric metric for simplifying meshes with appearance... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2870404