Geometric compression through topological surgery

被引:373
作者
Taubin, G
Rossignac, J
机构
[1] IBM Corp, Thomas J Watson Res Ctr, Yorktown Hts, NY 10598 USA
[2] Georgia Inst Technol, GVU, Atlanta, GA 30332 USA
来源
ACM TRANSACTIONS ON GRAPHICS | 1998年 / 17卷 / 02期
关键词
geometry compression; 3D mesh compression; VRML;
D O I
10.1145/274363.274365
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
The abundance and importance of complex 3-D data bases in major industry segments, the affordability of interactive 3-D rendering for office and consumer use, and the exploitation of the Internet to distribute and share 3-D data have intensified the need for an effective 3-D geometric compression technique that would significantly reduce the time required to transmit 3-D models over digital communication channels, and the amount of memory or disk space required to store the models. Because the prevalent representation of 3-D models for graphics purposes is polyhedral and because polyhedral models are in general triangulated for rendering, this article introduces a new compressed representation for complex triangulated models and simple, yet efficient, compression and decompression algorithms. In this scheme, vertex positions are quantized within the desired accuracy, a vertex spanning tree is used to predict the position of each vertex from 2, 3, or 4 of its ancestors in the tree, and the correction vectors are entropy encoded. Properties, such as normals, colors, and texture coordinates, are compressed in a similar manner. The connectivity is encoded with no loss of information to an average of less than two bits per triangle. The vertex spanning tree and a small-set of jump edges are used to split the model into a simple polygon. A triangle spanning tree and a sequence of marching bits are used to encode the triangulation of the polygon. Our approach improves on Michael Deering's pioneering results by exploiting the geometric coherence of several ancestors in the vertex spanning tree, preserving the connectivity with no loss of information, avoiding vertex repetitions, and using about three times fewer bits for the connectivity. However, since decompression requires random access to all vertices, this method must be modified for hardware rendering with limited onboard memory. Finally, we demonstrate implementation results for a variety of VRML models with up to two orders of magnitude compression.
引用
收藏
页码:84 / 115
页数:32
相关论文
共 24 条
[1]  
[Anonymous], 1973, ART COMPUTER PROGRAM
[2]  
[Anonymous], P ECCV 1996
[3]  
ARKIN EM, 1994, P ALGORITHMS ESA 94, V855, P36
[4]  
BORREL P, 1995, 20302 RC IBM RES
[5]  
CAREY R, 1997, 147721 ISOIEC DIS
[6]  
Deering M., 1995, Computer Graphics Proceedings. SIGGRAPH 95, P13, DOI 10.1145/218380.218391
[7]  
Eck M., 1995, Computer Graphics Proceedings. SIGGRAPH 95, P173, DOI 10.1145/218380.218440
[8]  
Funkhouser T. A., 1993, Computer Graphics Proceedings, P247, DOI 10.1145/166117.166149
[9]  
GUEZIEC A, 1995, 2 ANN INT S MED ROB
[10]  
Hoppe H., 1993, Computer Graphics Proceedings, P19, DOI 10.1145/166117.166119