3D transformation matrix compression and decompression

Details 3D transformation matrix compression and decompression 3D transformation matrix compression and decompression

2000-01-28

2003-07-08

Tran, Phuoc (Department: 2621)

Image analysis

Image compression or coding

Transform coding

C345S419000, C345S473000

Reexamination Certificate

active

06591019

ABSTRACT:

FIELD OF THE INVENTION
The invention relates to computer graphics simulation and animation, and more particularly, to a method and apparatus for efficiently compressing and decompressing 3D transformation data to conserve storage space.
BACKGROUND AND SUMMARY OF THE INVENTION
Many of us have seen films containing remarkably realistic dinosaurs, aliens, animated toys and other fanciful creatures. Such animations are made possible by 3D computer graphics. A computer is used to model objects in three dimensions, and to display them on a computer screen. An artist can completely specify how each object will look as well as how it will change in appearance over time. The computer takes care of performing the many millions of tasks required to make sure that each part of the moving image is colored just right based on distance from the viewer, the direction in which light strikes the object, the object's surface texture, and many other factors.
Because of the complexity of the 3D graphics generation process, just a few years ago computer-generated three-dimensional graphics was mostly limited to expensive specialized flight simulators, graphics workstations or supercomputers. The public saw the results of computer generated 3D graphics in movies and advertisements, but never actually interacted with computer systems doing the graphics generation. All that has changed with the availability of relatively inexpensive 3D graphics platforms such as the Nintendo 64®, the Sony Playstation® and various 3D graphics cards available for personal computers. It is now possible to produce exciting real time interactive 3D animations and simulations interactively in real time on relatively inexpensive computer graphics systems in your home or office.
Good quality computer animations are often based on complicated models with articulated structures and sophisticated motions. For example, such computer simulation and video game three dimensional articulated objects are often modeled as a hierarchical system of N nodes, where each node represents a jointed part of the object (for example, an arm, a leg or a head of a human). Motions such as standing, walking, running, or using a weapon are specified to the articulated system by defining a set of animations represented by sequence of transformations. Because it is computationally intensive to compute such transformations in real time, they are usually computed ahead of time and then stored in the computer graphic systems memory so the system can simply read and use them as needed. When the video game player runs the animation, the computer graphics system reads the precomputed transformations from memory and applies them to change the position, orientation and/or size of the objects on the screen in real time.
Especially in resource-constrained computing environments such as inexpensive home video game and personal computer systems, character animations in three dimensional computer simulations and video games heavily rely on a large number of such precomputed, prestored 3D transformations. For example, a relatively complex animation may contain tens of thousands of pre-constructed transformations. The large memory space required to store the transformation data has become one of major hurdles limiting the complexity of character animations with realistic motions in computer video games. Consider, for example, an animation in which a preconstructed transformation matrix is defined to update each node each frame. As one example, a human body can be modeled using 14 articulated nodes. If 10 animated motions are define for it, each animation takes 2 seconds to finish and the computer generates 30 images per second, the memory space required for storing the transformation data (e.g., in the form of 4×4 real number matrices) would be over one megabyte. A sophisticated application usually has more than one animated characters, which dramatically multiplies the number of matrices and the associated memory space required to store all this transformation data.
It is generally known to use data compression and decompression to reduce the size of computer data. Such compression/decompression relies on redundancy within the data itself. The compression process encodes the data prior to storage. Then, when the data is read from storage, decompression decodes the data and recovers the data in its original form. However, further improvements for efficiently compressing and decompressing transformation matrix data are needed and desirable.
We have developed a compression/decompression technique particularly suited for compressing and decompressing the mathematical descriptions (i.e., 4×4 real number matrices) computer graphics systems use to represent object transformations. The present invention reduces the space complexity required by a transformation matrix by providing an efficient compression algorithm so the transformation data occupies substantially less storage room in computer or video game devices. Although the invention has a special advantage when used for 4×4 arrays for three-dimensional homogenous transformation data in 3D graphics, the general concept is mathematically applicable to any arbitrary M×N matrix.
Briefly, we compress the transformation data off-line and decompress it when loading it from the storage media to the graphics system memory. In accordance with one aspect of a non-limiting exemplary embodiment of the invention, we replace the entire transformation matrix structure with a compact bitmap structure including a small number of bits for each matrix element. Since a homogeneous 3D transformation matrix contains some 0's and 1's, we can eliminate the storage room for those 0's and 1's in the compressed data by using the separate bitmap table to keep information on their locations. The encoding of such 0 and 1 integer values as bit values effectively bypasses the penchant of many compilers to compile all numerical values as double-precision floating point numbers—thus conserving a significant amount of storage space.
In addition, based on the fact that most video game processors and display hardware are constrained by their resolutions and an original transformation matrix often stores data that is more accurate than necessary, we convert some real numbers in the matrix into integers by scaling them by a constant when the compression takes place (integers can typically be stored in one-half to one-quarter the size of floating-point numerical values). One approach is to scale numbers within the range of −1 and 1 so that only some least-significant decimal digits of the numbers will be lost when decompressing the data. In the preferred embodiment, all numbers within the scale range [−1, 1] are processed by their absolute value and a separate table is used to keep the sign of scaled values. In certain circumstances, more than one scale factors can be used for the same set of data to provide different levels of accuracy and save more space. Truncation resulting from this type of floating-to-fixed point conversion may be negligible depending on the resolution of the 3D computer graphics platform.
Exemplary non-limiting embodiments of the present invention thus provides a compression/decompression technique that compensates for the behavior of commonly used compilers (which tend to try to treat all numbers as double precision floating point values unless declared differently) and commonly used programming techniques (which may not declare all numbers and variables appropriately to maximize storage space savings) while also taking advantage of the high incidence of integer 0, integer 1 and fractional signed values commonly found in homogenous 3D transformation matrices commonly used for 3D graphics animation and simulation. While the present invention is particularly adapted for use with such 3D transformation matrices, the techniques of the present invention are useful with any M×N matrix.


REFERENCES:
patent: 4580782 (1986-04-01), Ochi
patent: 5119442 (1992-06-01),

Affiliated with

Also associated with

Rating

3D transformation matrix compression and decompression does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with 3D transformation matrix compression and decompression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and 3D transformation matrix compression and decompression will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3042129