Geometry compression for regular and irregular mesh structures

Details Geometry compression for regular and irregular mesh structures Geometry compression for regular and irregular mesh structures

1999-06-14

2003-02-25

Jankus, Almis R. (Department: 2671)

Computer graphics processing and selective visual display system

Computer graphics processing

Three-dimension

C382S241000

Reexamination Certificate

active

06525722

ABSTRACT:

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 and irregularly tiled surface portions of graphical objects.
DESCRIPTION OF THE RELATED ART
Three-dimensional (3D) 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 3D graphics accelerator with a specialized rendering subsystem designed to off-load graphics processing functions from the host processor and thereby improving system performance. In a system with a 3D graphics accelerator, an application program executing on the host processor generates data which defines three-dimensional graphics elements for output on a display device. The application program causes the host processor to transfer this data to the graphics accelerator. The graphics accelerator then receives the data and renders the corresponding graphics elements on the display device.
To improve rendering speed and increase the realism of rendered images, techniques such as level of detail (LOD) switching may be used. LOD switching typically involves using more detailed images or textures for objects in the foreground of a scene and using less detailed images of textures for objects in the background.
For example, when a wall that is in foreground, surface texture details such as a pattern of brick may be used. In contrast, for a wall that is in the distant background, less detail may be used. The details of the background wall may be removed to mimic the actual blurred appearance of distance walls in the real world. One way to implement LOD switching is to use polygon simplification. Polygon simplification involves reducing the number of polygons used to represent an object.
To further improve rendering speeds, many graphics accelerators implement a technique called visibility culling. Visibility culling involves removing invisible objects or portions of objects from the scene being rendered. This technique, however, is not efficient when most objects are visible. In such cases, the full amount of geometry data are transferred from the host processor to the rendering hardware on the graphics accelerator.
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. This compromises system performance. In addition, 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 may require 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 affected by the throughput of the system bus as geometry processing requirements increase.
Many prior art systems utilize algorithms that reduce the number of vertices present in the geometric data One such algorithm is vertex decimation. Vertex decimation attempts to reduce the total number of polygons in a surface portion without loss of important detail. A paper by Schroeder, William J. and Jonathan A. Zarge, and William E. Lorensen entitled, “Decimation of Triangle Meshes,”
Proceedings of SIGGRAPH '
92 (Chicago, Ill., Jul. 26-31, 1992), in
ACM Computer Graphics
, vol. 26, no. 2, pp. 65-70, July 1992, describes one form of vertex decimation in greater detail, and is hereby incorporated by reference in its entirety. However, the compression achievable by reducing the number of vertices is limited. In particular, once the number of vertices drops below a certain level, image quality may drop quickly. Thus, graphics professionals have sought ways to compress the graphics data remaining after the number of vertices have been reduced to desired levels.
Applicant's above-referenced parent patent applications disclose two such methods for compressing three-dimensional graphics data. The first application (Ser. No. 08/511,294) discloses a method and system for compression of 3D geometry, preferably compression of strips of three-dimensional triangles. The second application (Ser. No. 08/988,202) discloses a method and system optimized for geometry compression of regular surface portions in the 3D geometry data With either system, if the compression is performed as a pre-process, the geometry may be stored in main memory of the computer system in a compressed format. The geometry data is then transferred to the computer system's graphics hardware in compressed format to reduce memory and bus bandwidth requirement. Decompression may then be performed by the graphics hardware either off-line (e.g., using software decompression) or in real-time (e.g., using hardware or software decompression).
Applicant's above-referenced parent patent applications disclose two different methods for compressing geometry data, one optimized for regular surfaces and one optimized for irregular surfaces. However, no provisions are made for dealing with three-dimensional graphics data that comprises both regularly tiled and irregular tiled surfaces. For example,
FIG. 1
illustrates a 3D object (a refrigerator) having mostly regularly tiled surfaces, while
FIG. 2
illustrates a 3D object (a lion) having mostly irregularly tiled surfaces.
FIG. 3
, however, illustrates a 3D object (a bear) having a mixture of regularly tiled and irregularly tiled surfaces.
Due to the mixture of both regularly tiled and irregularly tiled surfaces in
FIG. 3
, neither method disclosed in the parent applications is optimized for this data. Thus, a new method for efficiently compressing 3D geometric data comprising both regular and irregular surfaces is needed.
SUMMARY OF THE INVENTION
The problems outlined above may in part be solved by a method for compressing 3D geometry data that is capable of efficiently compressing both regularly tiled and irregularly tiled surfaces. In one embodiment, the method comprises examining 3D geometry data to detect the presence of regularly tiled surface portions. The regularly tiled surface portions may then be compressed using a first encoding method, while the remaining irregularly tiled surface portions may be compressed using a second encoding method, wherein the second encoding method is different from the first encoding method. Advantageously, the first encoding method may be optimized for regularly tiled surface portions, while the second encoding method may be optimized for irregularly-tiled surface portions. Note as used herein the term “irregularly tiled” refers to any tiled surface portion that does not meet predetermined qualifications for being classified as a regularly tiled surface portion.
In one embodiment, the first encoding method may encode the regularly tiled surface portions as vertex rasters. Thus, the vertices are arranged in a scan pattern (e.g., in rows and columns that form a rectangular array of vertices) which is scanned in a predetermined pattern (e.g., from side to side in lines from top to bottom). As part of the vertex raster, an “extent value” may be encoded for each regularly tiled surface portion. The extent values may be used to define the particular arrangement of the vertices within the regularly tiled surface portion. For example, the extent

Affiliated with

Also associated with

Rating

Geometry compression for regular and irregular mesh structures does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Geometry compression for regular and irregular mesh structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Geometry compression for regular and irregular mesh structures will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3123031