Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-06-07
2003-06-03
Vo, Cliff N. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S418000
Reexamination Certificate
active
06573890
ABSTRACT:
This patent application is related to co-pending patent applications filed concurrently herewith entitled COMPRESSION OF ANIMATED GEOMETRY USING BASIS DECOMPOSITION by Jerome E. Lengyel, Brian K. Guenter, and Henrique S. Malvar, and COMPRESSION OF ANIMATED GEOMETRY USING A HIERARCHICAL LEVEL OF DETAIL CODER by Jerome E. Lengyel, which are hereby incorporated by reference in their entirety.
FIELD OF THE INVENTION
The invention relates to computer generated graphics and more specifically relates to compression of time dependent geometric data.
BACKGROUND OF THE INVENTION
In three-dimensional (3D) graphics, moving objects are modeled using 3D geometric models. These models are typically represented as sets of 3D coordinates that define the position of a mesh of surface elements representing the surface of an object in a 3D space. To render a scene containing 3D object models, the graphics rendering pipeline first performs a series of geometric transformations to transform models from their local coordinate space to global or “world” coordinates of the scene and then to viewing or “camera” coordinates of a 2D view space. It then converts the transformed geometry and its attributes (color, shading) to an array of pixel values representing an output image. This process is typically repeated for each image frame in an animation sequence as the object models move about the scene.
A moving graphical object is expressed in terms of time-dependent geometry. The mesh representing the 3D positions of a model moves and deforms over time to simulate the motion of a 3D object. There are a number of motion models used to describe the motion of 3D geometry in animation. Relatively simple objects can be modeled using geometric transformations on rigid bodies. However, increased computing capacity and the demand for more realistic animation has increased the demand for applications involving real-time playback of complex animated models.
Sophisticated authoring tools and modeling programs such as the Softimage modeling tool from Avid Technology, Inc., are capable of creating extremely complex time-dependent geometry. Free-formed deformation lattices, joint envelopes, and physical simulation, and other manipulations can create complex moving geometry sequences. As real-time applications demand more than simple rigid models with animated transformations, it becomes more critical to develop ways to efficiently store and playback complex animated models with real-time performance.
In addition to increasingly sophisticated authoring tools, advances in 3D capture systems are also likely to increase the complexity of time-dependent geometry used in 3D graphics applications. The term “3D capture” refers to the process of generating a digitized 3D model of a real object. Range scanners currently produce static geometry sets. However, as range-scanner accuracy and speed improves, there will be more sources of large time-dependent geometric meshes. Simulation is another source of rich animated geometry. Finite-element methods produce realistic and complex animations that are too expensive to compute in real time.
As the sources for complex time-dependent geometry become more prevalent, there is an increasing need for more efficient ways to store and transmit time-dependent geometry to reduce memory and bandwidth requirements. Researchers have studied ways to compress static geometry. Please see “Geometric Compression,” Michael F. Deering, pp. 13-20, SIGGRAPH '95; “Optimized Geometry Compression for Real-Time Rendering,” Mike M. Chow, pp. 347-354, Proceedings of IEEE Visualization, '97; “Real Time Compression of Triangle Mesh Connectivity”, Stefan Gumhold and Wolfgang Stra&bgr;er, pp. 133-140, SIGGRAPH 98; “Geometric Compression Through Topological Surgery”, Gabriel Taubin and Jarek Rossignac, ACM Transactions on Graphics, Vol. 17, No. 2, April 1998, pp. 84-115; “Progressive Forest Split Compression”, Gabriel Taubin, Andre Gueziec, William Horn, and Francis Lazarus, pp. 123-132, SIGGRAPH 98; “Triangle Mesh Compression”, Costa Touma and Crag Gotsman, Proceedings of Graphics Interface '98, pp. 26-34; and “Description of Core Experiments on 3D Model Coding”, Frank Bossen (editor), ISO/IEC JTC!/SC29/WG11 MPEG98/N244rev1, Atlantic City, October 1998. While this research addresses compression of static geometry, more work needs to be done to develop ways to compress a moving 3D geometry stream.
In contrast to compression of 3D geometry, the fields of still image and moving image compression are well developed. A variety of techniques can be used to compress still images, such as run-length encoding, JPEG coding, etc. There are also many techniques for compressing image sequences such as MPEG, AVI, etc. Researchers have even presented techniques to use 3D geometry to assist in movie compression. See “Motion Compensated Compression of Computer Animated Frames,” Brian K. Guenter, Hee Cheol Yun, and Russell M. Mersereau, pp. 297-304, SIGGRAPH '93; “Polygon-Assisted JPEG and MPEG Compression of Synthetic Images,” Mark Levoy, pp. 21-28, SIGGRAPH '95; and “Accelerated MPEG Compression of Dynamic Polygonal Scenes,” Dan S. Wallach, Sharma Kunapalli, and Michael F. Cohen, pp. 193-197, SIGGRAPH '94.
In one respect, the traditional graphics rendering pipeline provides a form of compression of animated geometry in the case where an animated object is represented as a static, rigid body that is transformed using a series of animated transformation matrices. In this case, the time-dependent geometric model is reduced to a single mesh representing the rigid body and a series of animated transformation matrices that describe the rigid body's motion over time. This simple separation into coherent parts allows the encoding of a large family of time-dependent animations because moving objects can be constructed as hierarchies of rigid objects. While this is an effective way to compress a limited class of time-dependent geometry, it does not fully address the need for a more general and flexible approach for compressing more complex animated models. Some forms of complex motion are not well simulated using a hierarchy of rigid bodies and associated transformation matrices. In addition, some models are not constructed from rigid bodies, but instead, originate from a geometry source such as an authoring tool or 3D capture tool where the geometry is not expressed in terms of rigid bodies.
SUMMARY OF THE INVENTION
The invention provides methods for coding time-dependent geometry and animation. Aspects of these methods can be implemented in encoders and decoders of time-dependent meshes representing animated 3D objects as well as 3D animation that varies over a dimension other than time. These techniques can be used to store and transfer a 3D geometry stream more efficiently. This is useful within a computer system to reduce bandwidth between a host processor or storage device and a graphics rendering engine. It is also useful for reducing transmission bandwidth between computers on a local or wide area network. In addition, these techniques are useful in dynamic compression contexts, where a geometry stream is encoded within time constraints, such as applications where the geometry stream is generated, coded and then decoded for immediate playback.
In general, the compression methods of the invention code a geometry stream by solving for low-parameter models of the stream and encoding the residual. A compressor operates on a time-dependent geometry structure representing 3D positions of an object at selected time samples. In particular, the coders described below focus on compressing a matrix of vertex positions that represents the 3D positions of a mesh (the columns of the matrix) for series of time samples in an animation sequence (the rows in the matrix represent meshes at selected time samples). The compressor approximates the mesh for each time sample and encodes the residual between the approximated mesh and the actual mesh from a row in the matrix. The compressor encodes a coherent portion o
Klarquist & Sparkman, LLP
Microsoft Corporation
Vo Cliff N.
LandOfFree
Compression of animated geometry using geometric transform... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Compression of animated geometry using geometric transform..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compression of animated geometry using geometric transform... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3094557