Computer graphics processing and selective visual display system – Computer graphics processing – Shape generating
Reexamination Certificate
1997-06-12
2001-01-09
Zimmerman, Mark (Department: 2772)
Computer graphics processing and selective visual display system
Computer graphics processing
Shape generating
Reexamination Certificate
active
06172684
ABSTRACT:
BACKGROUND OF THE INVENTION
(1) Field of the Invention
The invention relates to computer graphics. More specifically, the invention relates to storing display lists of three-dimensional primitives.
(2) Related Art
One of the well-known forms of storing data required for rendering of computer images is a display list. The display list contains a list of rendering primitives described by parameters of vertices of each primitive such as coordinates of the vertices in three-dimensional space, color intensity, texture maps, etc. (collectively, vertex data). Triangles are one of the most used primitives. Thus, for example, a display list will contain a number of triangle descriptions. In addition to triangle descriptions, the display list will typically contain one or more state variables one or more different types (blending mode, texture addressing mode, etc.). A state set by the variable of each type remains valid until changed by the next variable of the same type. When primitive is rendered, its rendering procedures are defined by the collection of current rendering states; each rendering state is set by a corresponding state variable in the display list before the primitive description. Commonly, a state variable is used for a large number of primitive descriptions. Existing systems permit only a single state variable of each type to be applied to any single primitive. For instance, blending mode is valid for the whole primitive described as a collection of vertex data.
In an effort to reduce the size of display lists particularly in view of the fact that vertices are often shared between triangles, the vertex data has been removed from the display list to its own vertex array. In such systems, the triangle description in the display list merely indexes into the vertex array, which then supplies the necessary vertex data to rendering hardware. Particularly when vertices are shared, this can result in a significant reduction of the space required to store vertex data and in the bus traffic from the main memory to the local video memory, where vertices can be stored for subsequent use by rendering hardware. In the best case, one instance of vertex data can be shared by two or more triangles. In such indexing, a tension exists between use of large and small indices. Particularly, the index must then be large enough to access the vertex array, and small enough not to require excessive space dedicated to store the triangle description which includes three descriptors, one for each vertex. In the prior art, a typical size for the indices (descriptors) is 16 bits, which permits addressing of 64K of vertices.
FIG. 1
shows a prior art calculation of vertex array address from indices in a display list. A persistent state variable, starting address A1, is introduced into the display list followed by a triangle description consisting of three vertex indices V1-V3 of 16 bits each. By “persistent” state variable, it is meant that the state remains in effect until the state variable is replaced with a corresponding state variable. To access the vertex data stored in the vertex array, the 16-bit index multiplied by the size of the vertex data (Vsize) is added to the starting address to yield the vertex address. All three indices are used to index the single state allowing a maximum addressing range of 64K of vertices. Unfortunately, some sets of data may have more than 64K of vertices. For example, a well-defined human body will typically have more than 100K of vertices. Moreover, 16-bit indices requires 6 bytes per triangle to specify all three vertices. Thus, even if we assume only 50K vertices at 6 bytes per vertex, 300 kilo bytes are required to store the indexes. While the data size of a single vertex in the vertex array is 32 bytes and, thus, this prior art indexing reduces display list length over having the vertex data in the display list, it is still desirable to reduce further the display list size both because of negative system bus bandwidth effects and internal storage limitations imposed by long display lists.
While many prior art architectures render triangles based on the space on the screen it will occupy, some architectures employ what is known as chunking or tiling to break the screen into non-overlapping chunks which may be of relatively small size, for example, 32-by-32 pixels. Examples of such chunking architecture are Power VR created by NEC/Video Logic and Talisman created by Microsoft Corporation. This necessitates breaking the master display list into parts, i.e., for each chunk, a derivative display list is maintained that only retains the triangles intersecting that chunk. These derivative display lists are also required to maintain state coherency. Chunking provides a speed advantage because rendering small chunks can be done faster and uses a smaller z-buffer. However, because a triangle may intersect multiple chunks, it is necessary to repeat the triangle descriptions in the derivative display list of each chunk that triangle intersects. This duplication of triangle descriptions further increases the need to reduce the index size in the display list.
One way that prior art systems have attempted to reduce the space required to describe the geometry is to use the internal coherency and, rather than store the indices, such systems only store the differences between the adjacent indices. This reduces space because the difference between adjacent indices is likely to be small relative to the indices themselves which are likely to be 16 bits or even 24 bits in length. This works reasonably well with a master display list, but has two distinct disadvantages. The first disadvantage is common to all systems employing this technique. That is, while it may be relatively rare that the differences are greater than can be expressed in an allotted number of bits, it is nevertheless likely that at least in some cases it will occur. Therefore, the systems have to accommodate large and unknown differences. This is done using some sort of encoding such as Huffman encoding to handle variable length inputs. Handling variable length inputs substantially increases the complexity of the hardware. The second disadvantage is unique to chunking architectures. Specifically, if the index is based on history, breaking the master display list into derivative display lists will result in different codings of the same triangle in different display lists. This also necessitates that information about more than one predecessor be obtained for every triangle that appears in more than one display list, thus increasing bus traffic and coding complexity.
In view of the foregoing, it would be desirable to be able to decrease the size of the triangle description while maintaining or increasing the number of addressable vertices without increasing the complexity of the underlying rendering hardware.
BRIEF SUMMARY OF THE INVENTION
A method and apparatus for creating a display list permitting multiple states of the same type for a single primitive is disclosed. By introducing a plurality of state variables of the same type in a predetermined order in a display list before a primitive description, different state variables of the same type are applied to different vertex descriptors of the primitive. In one embodiment, the state variables introduced are starting addresses of the groups of vertices addressable by vertex indices of the primitive. In a case where the primitive is a triangle, up to three different starting addresses might be introduced into the display list (one corresponding to each vertex of the triangle). By introducing multiple starting addresses, the vertex indices of the triangle description can be significantly shortened, the concern about variable length inputs can be eliminated, and each index is independent of its predecessor in the master display list. Moreover, these advantages can be achieved without significantly increasing the hardware complexity.
REFERENCES:
patent: 4930091 (1990-05-01), Schroeder et al.
patent: 5572634 (1996-11-01), Duluk, Jr.
patent: 5581673 (1996-12-01
Blakely Sokoloff Taylor & Zaffman
Cao Huedung X.
Silicon Engineering, Inc.
Zimmerman Mark
LandOfFree
Method and apparatus for storing display lists of 3D primitives 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 storing display lists of 3D primitives, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for storing display lists of 3D primitives will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2459017