Decompression of three-dimensional graphics data using mesh...

Details Decompression of three-dimensional graphics data using mesh... Decompression of three-dimensional graphics data using mesh...

1999-06-14

2003-09-30

Jankus, Almis R. (Department: 2671)

Computer graphics processing and selective visual display system

Computer graphics processing

Three-dimension

Reexamination Certificate

active

06628277

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to computer graphics systems, and more particularly, to decompressing and rendering compressed three-dimensional geometry data.
DESCRIPTION OF THE RELATED ART
In recent years, demand for high performance graphics systems that can render complex three-dimensional (3D) objects and scenes has increased substantially. This increase is at least in part due to new applications such as computer-generated animation for motion pictures, virtual reality simulators/trainers, and interactive computer games. These new applications place tremendous demands upon graphics systems. One area in which particularly high demands are placed on graphics systems is bandwidth. This is because 3D graphics data may be several orders of magnitude larger than comparable 2D graphics data. For example, simple 2D graphics data may simply include color information for each pixel displayed. In contrast, 3D graphics data may include x,y,z position information, normal information, color information, transparency information, texture map information, reflectivity information, and additional information. This information is collectively referred to herein as “vertex component information”.
A number of different techniques have been proposed to reduce the bandwidth requirements of 3D graphics data. One such technique is known as geometry compression. One type of geometry compression is described in detail in U.S. Pat. No. 5,793,371, issued on Aug. 11, 1998, entitled “Method and Apparatus for Geometric Compression of Three-Dimensional Graphics Data” by Michael F. Deering, which is incorporated herein by reference in its entirety. Generally speaking, geometry compression relies upon reusing vertices (among other techniques) to reduce the size of the 3D graphics data. To describe a 3D object, a number of points (called vertices) are specified. Each vertex may have a number of attributes associated with it. For example, each vertex may have color information associated with it. Other attribute that may be associated with vertices are texture map coordinates, normals, color, and transparency information. For example, if a texture of marble is texture-mapped onto a sphere, each vertex on the sphere may have a texture map coordinate specifying how the texture should be applied (i.e., which part of the sample texture should be mapped to that particular vertex). A normal is a vector from the vertex that is perpendicular to the surface of the object at the vertex. This is illustrated in the 3D object of FIG.
1
. The 3D object may be represented by a number of vertices (represented as dots in the figure). Normals for the object are represented by arrows that extend perpendicularly from the object's surface at each vertex point.
Normals are vectors or directions in three-dimensional space. In the context of 3D graphics, normals (also called surface normals) may each indicate the local orientation of the surface of a 3D graphics object. Since the starting point of the vector is known from the xyz coordinates of the vertex, the normal may be specified with an x-component, a y-component, and a z-component (referred to as Nx, Ny, and Nz, respectively). In some embodiments, these components may be specified relative to the vertex. This embodiment is illustrated in FIG.
2
. However, other forms for specifying normals are also possible. Furthermore, in some implementations the normal components are themselves normalized. A normalized normal is one in which the sum of the squares of Nx, Ny, and Nz equals a constant one.
In 3D graphics, vertices are typically grouped together to form polygons such as triangles, as shown in FIG.
3
. By definition, a triangle has three vertices. However, many times triangles share vertices. In
FIG. 3
, vertices
1
-
2
-
3
form a first triangle and vertices
2
-
3
-
4
form a second triangle. Thus, vertices
2
and
3
are shared between the two triangles. 3D objects may be represented by specifying a number of triangles. This is shown in FIG.
4
.
However, specifying all of the information associated with each vertex (e.g., xyz location, color, normal, etc.) every time a vertex is referenced as part of a triangle is inefficient. Instead, the information about a vertex can be stored (e.g., when it is first transmitted) for later use. Then, when the vertex is needed again for another triangle, the vertex may be read from storage instead of having to be re-transmitted. The vertex information may be stored in a “mesh buffer” and then reused. This may advantageously reduce the amount of information that must be transmitted and may thus save bandwidth. This is illustrated in FIG.
5
.
To efficiently reuse vertices, the triangles may be organized into a mesh (e.g., a predetermined number of neighboring vertices. The mesh may then be encoded as one or more “triangle-strips”. For example, in
FIG. 6
of the application, the triangle strip may start with the following triangles:
6
,
1
,
7
;
1
,
7
,
2
;
7
,
2
,
3
;
7
,
3
,
4
;
7
,
4
,
8
;
4
,
8
,
5
; et seq.
As this pattern shows, once the triangle strip is started many subsequent triangles may be specified using only a single new vertex. For example, after triangle
6
,
1
,
7
has been constructed, triangle
1
,
7
,
2
may be constructed using only one new vertex (i.e., vertex
2
). Thus, each vertex in the triangle strip may describe from ⅓ to one triangle. For example, in the list above, vertex
6
describes ⅓ of triangle
6
,
1
,
7
. Vertex
2
describes one triangle
1
,
7
,
2
. In some cases, a vertex may even describe two or even more triangles.
While a number of different formats are possible, one type of generalized triangle strip may be defined as follows (encoding the 3D object from FIG.
6
):
R
6
, O
1
,O
7
,O
2
,O
3
, M
4
, M
8
, O
5
,O
9
,O
10
, M
11
O
17
, M
16
, M
9
, O
15
, O
8
, O
7
, M
14
, O
13
, M
6
, O
12
, M
18
, M
19
, M
20
, M
14
, O
21
, O
15
, O
22
, O
16
, O
23
, O
17
, O
24
, M
30
, M
29
, M
28
, M
22
, O
21
, M
20
, M
27
, O
26
, M
19
, O
25
, O
18
In the notation above, R is a restart tag (indicating that a new mesh is beginning), O denotes replace oldest, and M denotes replace middle. The operation of this type of generalized triangle strip is illustrated in
FIGS. 7A-7H
.
In some embodiments, the terms “oldest” and “middle” may be visualized as representing three registers that are used in forming triangles from the triangle strip representation. The sample encoding above is merely one nomenclature that may be used to represent how the vertices of the mesh are being encoded. Different implementations may use other nomenclatures. The example nomenclature uses letters (O and M) to indicate which vertex should be discarded from the three registers when forming a new triangle. O indicates the oldest vertex should be discarded. M indicates the middle vertex should be discarded. R indicates that a section of mesh is being started. This is used to clear the oldest, middle, and newest registers and the mesh buffer, if desired.
While this method reuses vertices, when vertex
8
is referenced a second time (i.e., by the command O
8
), the vertex is transmitted again. This retransmission of vertices may be reduced or avoided altogether by using a mesh buffer.
Using a similar nomenclature as in the previous example, a generalized triangle mesh utilizing a mesh buffer may be defined as follows (once again encoding the 3D object of FIG.
6
):
R
6
p, O
1
, O
7
p, O
2
,O
3
, M
4
, M
8
p, O
5
, O
9
p, O
10
, M
11
, O
17
p, M
16
p, M−3, O
15
p, O−5, O−6, M
14
p, O
13
p, M−9, O
12
, M
18
p, M
19
p, M
20
p, M−5, O
21
p, O−24, O
22
p, O−9, O
23
, O−10, O−7, M
30
, M
29
, M
28
, M−1, O−2, M−3, M
27
, O
26
, M−4, O
25
, O−5
In this implementation, a trailing letter “p” denotes “push into mesh buffer”. The number following a capital letter is a vertex number, and a negative number is the mesh buffer reference, in which “−1” denotes the most recent pushed vertex.
Thus, geometry compres

Affiliated with

Also associated with

Rating

Decompression of three-dimensional graphics data using mesh... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Decompression of three-dimensional graphics data using mesh..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decompression of three-dimensional graphics data using mesh... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3044289