Progressive hulls

Details Progressive hulls Progressive hulls

1999-09-30

2003-07-01

Zimmerman, Mark (Department: 2671)

Computer graphics processing and selective visual display system

Computer graphics processing

Three-dimension

C345S441000

Reexamination Certificate

active

06587104

ABSTRACT:

FIELD OF THE INVENTION
This invention relates generally to geometric modeling using polygonal meshes for computer graphics, and more particularly to a progressive hulls data structure for modeling the outer surface geometry of a three-dimensional object in varying degrees of resolution, with the property that each lower resolution hull encompasses the higher resolution hull(s) from which it was derived.
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.
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
1
, . . . , 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
. More precisely, a parametric domain, |K|⊂R
m
, is constructed by identifying each vertex of K with a canonical basis vector of R
m
, and the mesh is defined as the image, &phgr;
v
(|K|), where &phgr;
v
:R
m
→R
3
is a linear map. (See, e.g., H. Hoppe et al.,
Mesh Optimization
, 1993 Computer Graphics Proceedings 19-26; hereinafter referred to as Hoppe93.) An exemplary mesh
80
is shown in FIG.
2
. The vertices of a triangle mesh (e.g., vertices
82
-
89
of the mesh
80
) are denoted as v
1
, . . . , 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. Instantaneous switching between two LOD approximations of a given model can lead to a perceptible “popping” display effect. For this reason, the capability of constructing smooth visual transitions, called geomorphs, between meshes having different levels of detail is desirable.
A model should be stored in the smallest amount of memory or disk space. Two schemes have been developed to deal with this problem. One is to use mesh simplification, as described earlier, to reduce the number of faces in the model as much as possible while preserving its appearance. The other is mesh compression: minimizing the space taken to store the model, given that a particular mesh has been selected.
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 that transforms the mesh by splitting a vertex v
s
(positioned between side vertices v
l
and v
r
, as shown, for example, in
FIG. 2
) to add one vertex 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.
FIG. 2
shows the vertex split transformation and its inverse, the edge collapse transformation. As shown in
FIG. 2
, each edge collapse transformation unifies two adjacent vertices into one, thereby removing two faces from the mesh. For the purpose of level-of-detail control, edge collapses are selected so as 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 Simplification
, Computer Graphics (SIGGRAPH '98 Proceedings) (1998), 115-122, Garland and Heckbert,
Surface Simplification Using Quadric Error Metrics
, Computer Graphics (SIGGRAPH '97 Proceedings) (1997), 209-216, and Hoppe,
Progressive Meshes
, Computer Graphics (SIGGRAPH '96 Proceedings) (1996), 99-108.
The PM representation also supports smooth visual transitions, or geomorphs, between any two of these approximations, as well as allowing progressive transmission and efficient compression of the sequence of LOD approximations of the arbitrary mesh. In addition, the PM representation naturally supports progressive transmission, offers a concise encoding of
M
itself, and supports efficient selective refinement. In short, the PM representation offers an efficient, lossless, continuous-resolution representation. Thus, when rendering an image of a three-dimensional object, it is possible to reduce the amount of data needed to represent the geometry of the object without sacrificing much in terms of the quality of the resulting image, by using a simplified mesh created by collapsing selected edges of a higher resolution mesh.
For realistic rendering of an object, meshes in computer graphics (including the continuous sequence of LOD meshes defined by the PM representation) often have numerous other appearance attributes in addition to th

Affiliated with

Also associated with

Rating

Progressive hulls does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Progressive hulls, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Progressive hulls will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3065141