Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-06-04
2002-07-30
Vo, Cliff N (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06426747
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to geometric modeling using polygonal meshes for computer graphics, and more particularly relates to systems in which the connectivity of the mesh, but not the geometry, is fixed. Still more particularly, the present invention relates to methods for vertex caching to decrease geometry bandwidth and to reduce bus traffic between a graphics subsystem and memory.
BACKGROUND OF THE INVENTION
Graphics performance in low-end computer systems has recently experienced significant growth due to the integration of 3D graphics functions into custom graphics processors. The graphics subsystem now shares many similarities with the central processing unit (CPU). Both consist of a massively integrated processing unit, a local memory cache, and a bus to main memory. Reducing the von Neumann bottleneck between the CPU and main memory has been a fundamental problem in computer architecture. The graphics subsystem now experiences a similar bottleneck.
In the traditional polygon-rendering pipeline, the graphics processor accesses two types of information from memory: (1) a model geometry and (2) raster images (e.g., texture map, bump map, environment map) used in shading this geometry. The problem of reducing texture image bandwidth is described in Hakura and Gupta,
The Design And Analysis Of A Cache Architecture For Texture Mapping
, Proceedings of the 24th International Symposium on Computer Architecture (June 1997), 108-120.
Models in computer graphics are often represented using triangle meshes. FIG.
1
(
a
) is a diagram of portions of example triangle meshes. Geometrically, a triangle mesh (e.g., example portion of a triangle mesh
80
) is a piecewise linear surface consisting of triangular faces joined together along their edges. The vertices of a triangle mesh (e.g., vertices
82
-
89
of the mesh
80
of FIG.
1
(
a
)) are denoted as &ngr;
1
, . . . , &ngr;
m
; the edges (e.g.,
92
-
95
) are denoted by pairs of adjacent vertices as e={&ngr;
j
, &ngr;
k
}; and the faces (e.g., faces
100
-
107
) are denoted by triples of interconnected vertices as f={&ngr;
j
, &ngr;
k
, &ngr;
l
}. Typically, a model is converted into a triangle mesh using conventional triangulation processes (e.g., edges are added to subdivide polygonal faces of the mesh having more than three sides into triangle faces).
More particularly, the model geometry is usually described as a mesh of triangle faces sharing a common set of vertices, as shown in, for example, FIG.
1
(
b
). On average, each mesh vertex is shared by six adjacent triangles. Vertex data, which may include position, normal, colors, and texture coordinates, uses on the order of 32 bytes, so it is desirable to minimize the number of times this data must be read from memory. One common technique for reducing the geometry bandwidth (by a factor of almost three) is to organize faces into triangle strips, so that two vertices are re-used between successive faces as described in Evans et al.,
Optimizing Triangle Strips For Fast Rendering
, Visualization '96 Proceedings (1996), IEEE, 319-326, and Neider et al.,
OpenGL Programming Guide
, Addison-Wesley (1993). Implementing such triangle strips uses a set of three vertex registers in the graphics processor.
The use of a larger vertex register set has the potential to further reduce geometry bandwidth by another factor of nearly two. The key is to reorder the faces within the triangle mesh to maximize references to vertices already loaded in registers. Such an approach is described in Deering,
Geometry Compression
, Computer Graphics (SIGGRAPH '95 Proceedings) (1995), 13-20, and further described in Chow,
Optimized Geometry Compression For Real
-
Time Rendering
, Visualization '97 Proceedings (1997), IEEE, 347-354. In Deering and Chow, the vertex data is quantized and delta-encoded into a compressed geometry stream. This geometry stream includes“push bits” to explicitly specify which vertices should be loaded into a first-in-first-out (FIFO) vertex buffer. Deering and Chow report compression rates of 3 to 8 bytes per triangle.
Various memory organizations have been used for representing triangle meshes. The memory organizations are described below, letting n denote the number of vertices in the mesh, and m denote the number of triangle faces. Often, the approximation m≈2n is used. Vertex data is assumed to use 32 bytes (three words for position, three words for normal, and two words for texture coordinates). Vertex data may be more compact if the normal or texture coordinates are omitted. However, to support multi-texturing, several graphics application programming interfaces (APIs) now allow specification of multiple texture coordinates per vertex, so vertex data may also be larger. Some of the representations refer to vertices through indices; each index is assumed to occupy two bytes. Although this constrains the maximum mesh size to approximately 128 K faces, more complex models are commonly represented as collections of smaller, independent meshes. The mesh representations are illustrated in FIGS.
2
(
a
)-
2
(
e
) with respect to an exemplary mesh shown in FIG.
2
(
g
). FIG.
2
(
f
) shows an exemplary strip formation using triangle strips, and a summary of the analysis appears in Table 1 in which b represents a strip “bloat” factor, described below.
TABLE 1
Memory and transfer requirements for various organizations of meshes
Mesh Organization
Memory Size (bytes)
Transfer Size (bytes)
Independent Triangles
96 m
96 m
Triangle Strips
32 bm
32 bm
Indexed Triangles
≈22 m
102 m
Indexed Triangle Strips
≈(16 + 2 b)m
34 bm
In independent triangles, as shown in FIG.
2
(
a
), the mesh is organized as an array of m faces, each containing data for its three face vertices, for a total of m·3·32≈96 m bytes. Although this organization is seldom used in memory, many graphics drivers convert other representations such as indexed triangles into such a stream when sending the data to the graphics system.
In triangle strips, the mesh faces are organized into sequences of contiguous faces called strips, as shown for example in FIGS.
2
(
b
) and
2
(
f
). The first face in the strip is specified by three vertices, and each subsequent face uses one additional vertex. Some interfaces (e.g., IRIS GL) allow explicit control over the direction of strip formation in generalized triangle strips. More recent memory-based representations define sequential triangle strips, in which the direction of strip formation alternates left/right, as described in Neider et al. The default strip direction can be overriden by duplicating a vertex in the data stream, for instance vertex
3
in FIGS.
2
(
b
),
2
(
d
), and
2
(
f
). The overall size of the representation is 32 bm bytes, where b is a strip “bloat” factor to account for the costs of restarting strips and overriding strip direction. Typically, strip bloat factor is in the range between about 1.1<b<1.5. A review of several techniques for generating good triangle strips, that is, minimizing b, is described in Evans et al. and in Xiang et al.,
Fast And Effective Stripification Of Polygonal Surface Models
, Symposium on Interactive 3D Graphics (1999), ACM, 71-78.
In indexed triangles, as shown in FIG.
2
(
c
), the mesh is organized as an array of vertices, and an array of faces where each face refers to its three vertices through indices. The memory representation has size n·3+m·3·2≈22 m bytes. Although this representation is more concise than triangle strips, the graphics processor must read more data from memory, a total of m·3·(2+32)=102 m bytes.
In indexed triangle strips, as shown in FIG.
2
(
d
), again, the mesh consists of a vertex array and faces that refer to vertices through indices, but here the faces are organized into strips. A special vertex index, denoted −1, forces a strip restart. Alternatively, a strip can be restarted by duplicating two indices, as shown in the lower right corner of FIG.
2
(
d
). Memory
Hoppe Hugues
Miller John W.
Vo Cliff N
Woodcock & Washburn LLP
LandOfFree
Optimization of mesh locality for transparent vertex caching does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Optimization of mesh locality for transparent vertex caching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimization of mesh locality for transparent vertex caching will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2906521