Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-06-29
2002-12-17
Nguyen, Phu K. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06496185
ABSTRACT:
TECHNICAL FIELD
This invention relates to image processing. More particularly, the invention relates to a system and method of processing a list of triangles that represent a surface of a three-dimensional object image.
BACKGROUND OF THE INVENTION
Image processing systems are capable of converting graphical object data into an image that is viewed by a user or observer of the image processing system. Graphical object data may be stored in a variety of different formats, including various compressed formats. The type of data format used to store the graphical object data varies depending on the type of image processing system that receives and processes the data, the type of image being produced (e.g., two-dimensional or three-dimensional), and the type of equipment used to generate and store the graphical object data.
In three-dimensional graphics applications, graphical objects are typically defined, processed, and provided to the rendering hardware as a series of adjoining triangles. Each triangle is defined by three points or vertices. Because the triangles adjoin each other, a single point might be a vertex of several different triangles.
Each point or vertex of each triangle may have various associated information, such as location coordinates (i.e., coordinates in the x, y, and z directions), ambient color, reflective color, texture coordinates, fogging and alpha blending components, etc. Since each vertex may have a significant amount of associated data, operations such as moving, storing, and reading vertices can become a significant part of the image rendering process.
FIG. 1
illustrates an exemplary rendering module
10
that receives graphical object data and generates a rendered image. Rendering module
10
receives graphical object data
12
from a data source. The rendering module
10
processes the graphical object data
12
and generates a rendered image
14
. The rendered image
14
can be displayed on a computer monitor or other display device or may be transmitted to another location for display.
FIG. 2A
illustrates a series of five triangles, labeled T
1
-T
5
. Each triangle has three vertices, labeled “
1
”, “
2
”, and “
3
”. Adjacent triangles share vertices with one another. For example, triangles T
1
and T
2
share two vertices—vertex
2
of triangle T
1
is shared with vertex
2
of triangle T
2
and vertex
3
of triangle T
1
is shared with vertex
1
of triangle T
2
.
A series of triangles, such as the series shown in
FIG. 2A
, can be represented in several formats: a non-indexed list, a non-indexed strip, an indexed list, and an indexed strip. A non-indexed list identifies three separate vertices for each triangle in the series. For example, in the series of triangles shown in
FIG. 2A
, a non-indexed list is represented as:
T
1
: T
1
V
1
, T
1
V
2
, T
1
V
3
T
2
: T
2
V
1
, T
2
V
2
, T
2
V
3
T
3
: T
3
V
1
, T
3
V
2
, T
3
V
3
T
4
: T
4
V
1
, T
4
V
2
, T
4
V
3
T
5
: T
5
V
1
, T
5
V
2
, T
5
V
3
Where, for example, T
1
V
1
defines vertex “
1
” of triangle T
1
and T
1
V
2
is vertex “
2
” of triangle T
1
. Each entry in the list (T
1
V
1
, T
1
V
2
, etc.) represents a triangle vertex and has associated information, as discussed above (i.e., screen coordinates, color, etc.). This non-indexed list requires three separate vertex entries to define each triangle. Further, the non-indexed list does not consider the common relationships between certain vertices (e.g., in
FIG. 2A
, T
1
V
2
is the same vertex as T
2
V
2
, and T
1
V
3
is the same vertex as T
2
V
1
). Thus, when processing the non-indexed list, the system will process both vertices T
1
V
2
and T
2
V
2
, even though they are the same vertex. This results in unnecessary vertex processing, which reduces the performance of the image processing system. However, the list format is advantageous in that a single list is able to store an entire mesh of triangles (discussed below).
In a non-indexed strip of triangles, a list of vertices represents a single triangle strip. Each vertex in the non-indexed strip (starting with the third vertex) defines a triangle along with the two previous vertices.
FIG. 2B
illustrates the same five triangles illustrated in
FIG. 2A
, but each of the seven vertices has a single identifier (labeled
1
-
7
). The five triangles in
FIG. 2B
can be represented by the following triangle strip:
V
1
, V
2
, V
3
, V
4
, V
5
, V
6
, V
7
where V
1
through V
7
each define a single vertex. This triangle strip represents triangles (V
1
, V
2
, V
3
), (V
3
, V
2
, V
4
), (V
3
, V
4
, V
5
), (V
5
, V
4
, V
6
), and (V
5
, V
6
, V
7
). A strip of triangles is an efficient way to represent a series of adjacent triangles. However, the triangle strip format cannot generally represent an entire mesh of triangles as a single strip. Instead, multiple strips are required to represent the triangle mesh. Each time the strip reaches a triangle with no other adjoining triangle, the current strip terminates and a new strip is started.
Using an indexed list notation, a list of three indices is associated with each triangle and a pool of vertices is referred to by the indices. For example, using an indexed list to identify the five triangles in
FIG. 2B
, the indexed list is represented as:
V
1
, V
2
, V
3
, V
4
, V
5
, V
6
, V
7
and the associated indices:
i
1
, i
2
, i
3
i
3
, i
2
, i
4
i
3
, i
4
, i
5
i
5
, i
4
, i
6
i
5
, i
6
, i
7
In this notation, “V
1
” defines a first vertex and the indices “i
1
i
2
, i
3
” define the first triangle as having vertices V
1
, V
2
, and V
3
. The indexed list vertices can be processed once into a separate buffer so that the indexed accesses can read pre-processed vertices. Using this process, each distinct vertex is processed exactly once. Another advantage of the indexed list is its reduction in storage size (an index is very small (e.g., two bytes) compared to a vertex (e.g., 32 bytes).
Finally, an indexed strip of triangles identifies a strip of indices and a pool of vertices referred to by the indices. For example, using an indexed strip to represent the five triangles in
FIG. 2B
produces a sequence of vertices:
V
1
, V
2
, V
3
, V
4
, V
5
, V
6
, V
7
and associated indices:
i
1
, i
2
, i
3
, i
4
, i
5
, i
6
, i
7
Using this notation, “V
1
” defines a first vertex of a triangle in the strip and the first three indices “i
1
, i
2
, i
3
” define the first triangle in the strip. The indexed strip of triangles provides a simplified notation for representing triangle strips.
FIG. 3
illustrates an example mesh of triangles
20
(also referred to as a “triangle mesh”). In a typical mesh of triangles, each vertex is usually shared by six triangles. Rather than processing the same vertex six times (once for each triangle associated with the vertex), known techniques simplify the processing by: (1) processing the mesh of triangles using indices to refer to vertices in a pool of unique vertices so that each vertex only needs to be transformed (or processed) once, and (2) if a sequence of adjacent triangles exists (such as a mesh), treating the sequence as a “triangle strip” instead of a “triangle list.” Using the second technique, the first triangle is defined by three vertices. All subsequent triangles are defined by a single new vertex and the last two vertices of the previous triangle in the strip. These two techniques can be used separately or together so that existing graphics systems can handle the following combinations: Non-Indexed List, Non-Indexed Strip, Indexed List, and Indexed Strip.
Using these known techniques, many vertices are processed only once for all associated triangles, rather than repeatedly processing the same vertex for different associated triangles. Thus, many existing systems attempt to process triangles in strips instead of individual triangle lists. However, in many situations, it is easier to define and maintain the triangles in a triangle list format instead of a strip format. For example, a mesh may include physically disconnected groups of triangles that otherwise share similar features (such as similar texture). These t
Lee & Hayes PLLC
Microsoft Corporation
Nguyen Phu K.
LandOfFree
Method and apparatus for processing a mesh of triangles does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for processing a mesh of triangles, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for processing a mesh of triangles will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2952200