Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1998-07-31
2001-07-17
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06262737
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention pertains generally to the field of computer graphics. More particularly, the present invention pertains to coding of information representing an image of a three dimensional model.
2. Description of Prior Art
Three dimensional (“3-D”) graphic models have become increasingly popular since the advent of 3-D laser scanning systems and the boom of VRML (Virtual Reality Modeling Language) models. Laser scanning systems, for example, routinely produce geometric models with hundreds of thousands of vertices and triangles, each of which may contain additional information such as color and normal. Highly detailed models are also commonly adopted in computer graphics.
Three dimensional graphic models are often represented as complex polyhedral meshes composed of two types of data, i.e., topological and geometrical data. Topological data provide connectivity information among vertices (e.g., adjacency of vertices, edges and faces) while geometrical attributes describe the position, normal, color, and application dependent information for each individual vertex. In terms of implementation, most 3-D graphic file formats consist of a list of polygons each of which is specified by its vertex indices and a vertex attribute list. The terms vertex and node are used interchangeably herein.
Generally speaking, 3-D models are expensive to render, awkward to edit, and costly to transmit through a network. Wider application of 3-D graphics potentially could be limited due to these obstacles. To reduce storage requirements and transmission bandwidth it is desirable to compress these models with lossy compression methods which keep the distortion within a tolerable level while maximizing data reduction. Another important consideration is to apply graphic coding in a progressive fashion to allow easier control of data such as progressive display, level-of-detail control and multi-scale editing. This functionality demands that the mesh be approximated with different resolutions, which is vital for real-time applications. To achieve this goal, it is required for the mesh to be reduced to a coarse approximation (i.e. the base mesh) through a sequence of graphic simplifications.
Simplification and compression of 3-D mesh data has been studied by quite a few researchers. Most early work focused on the simplification of graphic models. In W. J. Schroeder, “Decimation of Triangle Meshes,” Computer Graphics Proceedings, Annual Conference Series, pp. 65-70, ACM SIGGRAPH, July 1992, the author proposed a decimation algorithm that significantly reduced the number of polygons required to represent an object. Turk, in “Re-tiling Polygon Surfaces,” Computer Graphics Proceedings, Annual Conference Series, pp. 55-64, ACM SIGGRAPH, July 1992, presented an automatic method of creating surface models at several levels of detail from an original polyhedral description of a given object. Hoppe et al., in “Mesh Optimization,” Computer Graphics Proceedings, Annual Conference Series, pp. 19-26, ACM SIGGRAPH, August 1992, address the mesh optimization problem of approximating a given point set by using smaller number of vertices under certain topological constraints.
Recent work has emphasized the compression of graphic models. Deering, in “Geometry Compression,” Computer Graphics Proceedings, Annual Conference Series, pp. 13-20, ACM SIGGRAPH, August 1995, discusses the concept of the generalized triangle mesh which compresses a triangle mesh structure. Eck et al. in “Multiresolution Analysis of Arbitrary Meshes,” propose a wavelet transformation defined on an arbitrary domain to compress 3-D models of subdivision connectivity. Taubin, in “Geometric Compression Through Topological Surgery,” Tech. Rep. RC-20340, IBM Watson Research Center, January 1996, presented a topological surgery algorithm which utilized two interleaving vertex and triangle trees to compress a model. More recently, Cohen et al., in “Simplification Envelopes,” Computer Graphics Proceedings, Annual Conference Series, pp. 119-28, ACM SIGGRAPH, August 1996, introduced the concept of simplification envelopes so that a hierarchy of level-of detail approximations for a given polyhedral model could be generated automatically. Hoppe in “Progressive Meshes,” Computer Graphics Proceedings, Annual Conference Series, pp. 99-108, ACM SIGGRAPH, August 1996, proposed a progressive mesh compression algorithm that is applicable to arbitrary meshes.
SUMMARY OF THE INVENTION
The present invention provides a new compression algorithm for 3-D meshes operating with both single and progressive resolution modes. The single resolution mode compresses the topological data through a constructive traversal and encodes geometrical data by local prediction. The progressive resolution mode represents the mesh by a base mesh and a sequence of refinement steps. Both the base mesh and the refinement sequence are entropy coded into a single bit stream in such a way that, along the encoding process, every output bit contributes to the reduction of coding distortion, and the contribution of bits decreases according to their order of position in the bit stream. At the receiver end the decoder can stop at any point while generating a reconstruction of the original model with the best rate distortion tradeoff. A series of models of continuously varying resolutions can thus be constructed from the single bit stream. This property, often referred to as the embedding property, since the coding of a coarser model is embedded in the coding of a finer model, can be widely used in robust error control, progressive transmission and display, and level-of-detail control.
REFERENCES:
patent: 5929860 (1999-07-01), Hoppe
patent: 5933153 (1999-08-01), Deering et al.
patent: 5966140 (1999-10-01), Popovic et al.
patent: 6009435 (1999-02-01), Taubin et al.
Kuo Chung-Chieh Jay
Li Jienkun
Cao Huedung X.
Farjami & Farjami LLP
University of Southern California
Zimmerman Mark
LandOfFree
3D mesh compression and coding 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 mesh compression and coding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and 3D mesh compression and coding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2452472