Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1998-06-11
2001-07-03
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S419000
Reexamination Certificate
active
06256041
ABSTRACT:
CROSS-REFERENCE TO RELATED APPLICATIONS
U.S. application Ser. No. 08/511,294, entitled “Method And Apparatus For Geometric Compression Of Three-Dimensional Graphics Data” by Michael F. Deering, filed Aug. 4, 1995.
U.S. application Ser. No. 08/511,326, entitled “Method and Apparatus for Decompression of Compressed Geometric Three-Dimensional Graphics Data” by Michael F. Deering and Aaron S. Wynn, filed Aug. 4, 1995.
U.S. application Ser. No. 08/885,279, entitled “System and Method for Generalized Geometric Compression of Three-Dimensional Graphics Data Having Regular Vertex Structures” by Michael F. Deering, filed on Jun. 30, 1997.
U.S. application Ser. No. 08/988,202, entitled “Compression of Three-Dimensional Geometry Data Representing a Regularly Tiled Surface Portion of a Graphical Object” by Michael F. Deering, filed Sep. 18, 1997.
U.S. application entitled “Compression of Three-Dimensional Geometry Data Representing a Regularly Tiled Surface Portion of a Graphical Object” by Michael F. Deering filed concurrently herewith application Ser. No. 09/095,777 filed Jun. 11, 1998 now U.S. Pat. No. 6,215,500.
FIELD OF THE INVENTION
The present invention relates generally to compressing and decompressing three-dimensional graphics data, and more particularly to compressing and decompressing three-dimensional geometry data corresponding to regularly tiled surface portions of graphical objects.
DESCRIPTION OF THE RELATED ART
Three-dimensional (3-D) computer graphics systems employing large geometric models find wide use in applications such as computer-aided design (CAD), virtual reality environments, training and simulation programs, games, and location-based entertainment. Such systems typically include a 3-D graphics accelerator, a specialized rendering subsystem which is designed to off-load graphics processing functions from the host processor, thereby improving system performance. In a system with a 3-D graphics accelerator, an application program executing on the host processor generates three-dimensional geometry data including information corresponding to points on the surface of a three-dimensional graphical object. These points are usable as vertices of polygons which, when connected, may be rendered to form a representation of the graphical object. The application program causes the host processor to transfer this 3-D geometry data to the graphics accelerator, along with corresponding control and connectivity information. The graphics accelerator receives this stream of compressed 3-D geometry data, and renders the encoded polygons on an attached display device.
The process of connecting three-dimensional vertices to form a representation of a graphical object is referred to as “tiling”.
FIGS. 1A and 1B
each illustrate graphical objects which have been tiled into component polygons. As shown,
FIG. 1A
depicts a 3-D lion
60
, while
FIG. 1B
depicts a 3-D giraffe
70
. It is noted that lion
60
is primarily tiled into triangles, while giraffe
70
is tiled using quadrilaterals. Tiling may be performed using a variety of different polygons.
This transmission of graphics primitives and commands from the host processor to the graphics accelerator over the system bus is one of the major bottlenecks in computer graphics. This bottleneck is becoming more problematic as users of graphics applications programs require an ever-increasing amount of complexity (and hence, size) in the geometric models used to produce visualization effects. The result is that slow memory subsystems or slow bus subsystems may not be able to adequately supply geometry data to the relatively fast real-time rendering hardware, thereby compromising system performance. The size requirements for a large set of geometric data may also cause memory constraints.
For example, rendering a large geometric data set with one million triangles at 30 Hz requires a system bus throughput of approximately 720 MB/sec (at a ratio of 24 bytes/triangle). While such high bus bandwidths may be attainable for high-end systems, low-end to mid-range systems typically have bandwidths on the order of 250-320 MB/sec. The performance of lower cost systems is thus effected by the throughput of the system bus as geometry processing requirements increase.
Techniques such as polygon simplification and visibility culling have been used to manage such large sets of geometry data. Polygon simplification allows an object to be viewed at different levels of detail, in relation to the viewing distance from the object. Visibility culling involves stripping away invisible portions of an object from the drawing loop. These techniques, however, are not efficient when most of a given object is visible and high resolution is desired. In such cases, the full amount of geometry data must be transferred from the host processor to the rendering hardware on the graphics accelerator.
Applicant's co-pending U.S. application Ser. No. 08/511,294, however, discloses methods and systems for compression and decompression of 3-D geometry data. If the compression is performed as a pre-process, the geometry data may be stored in main memory of the computer system in compressed format. Upon rendering, geometry data is transferred directly to graphics hardware in this compressed format. Decompression may be performed off-line in software or real-time in hardware or software.
Compression performed according to the manner described in the Applicant's parent patent application may result in a 6× to 10× reduction in size of the geometry data. The bus bandwidth required to transfer this data is therefore reduced as well. High-performance graphics thus becomes much more attainable for lower-cost graphics platforms.
However, Applicant's previously disclosed compression techniques are generalized to support compression of 3-D geometry data for surface portions which are tiled in an irregular fashion. Although this patent application discloses efficient compression techniques and devices, no provisions are made for taking advantage of greater compression efficiency possible for surfaces where polygons are connected in a regular manner. That is, while the compression techniques previously disclosed may be applied to regularly tiled surface portions, the compression efficiency achieved is not optimal.
Consider the 3-D lion
60
depicted in FIG.
1
A. The surface of the lion
60
(comprising triangles and rectangles) is tiled such that little regularity exists between neighboring primitives. Accordingly, the compression techniques disclosed in patent application Ser. No. 08/511,294 achieve a suitable or near-optimal level of compression for triangle strips arranged in an irregular fashion.
Consider the 3-D giraffe
70
of
FIG. 1B
, however. While portions such as the head of giraffe
70
are irregularly tiled (and thus suited to the previously disclosed compression techniques), the neck and parts of the body of the giraffe
70
are tiled in a fairly regular fashion. For such regularly tiled surface portions, there is a need for techniques and devices which take advantage of the regular arrangement of surface polygons to achieve greater compression efficiency. Such compression techniques and devices should preferably be compatible or usable with existing compression/decompression techniques.
SUMMARY OF THE INVENTION
The present invention comprises a system and method for compressing 3-D geometry data corresponding to a regularly tiled surface portion of a three-dimensional object. In one embodiment, the method comprises receiving 3-D geometry data which includes vertex parameter values corresponding to vertices within the regularly tiled surface portion. These vertex parameter values may include position, color (including specular color), normals, bump and displacement mapping basis vectors, quad split information, and texture mapping coordinates. The method next includes representing the surface portion in a compressed format referred to as a “vertex raster”.
Representing a surface portion as a vertex raster first includes encoding an extent va
Conley Rose & Tayon PC
Sun Microsystems Inc.
Vo Cliff N.
Zimmerman Mark
LandOfFree
Decompression of three-dimensional geometry data... 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 geometry data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decompression of three-dimensional geometry data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2475891