臺灣博碩士論文加值系統

多邊形網面 (Polygon Mesh) 是一種被廣泛使用來表示三維立體模型 (3D Model) 的原始資料結構。要為一個多邊形網面進行完整編碼，我們分別需要記錄一些它於拓撲學和幾何學上的特點。前者是用來描述點，線和面之間的連接關係 (Connectivity Encoding)。後者則描述一些屬性；例如，每一個面的個別顏色，每一個點的三維座標等。事實上，三維立體模型之壓縮編碼 (3D Model Compression)，其瓶頸主要來自於前者 — 多邊形網面的連接編碼 (Connectivity Encoding of Polygon Meshes)。而在這一篇碩士論文中，我們則是在這一方面提供最佳的壓縮編碼演算法。

Polygon mesh is an important primitive data structure for representing three-dimensional models. Its specification consists of topologic properties and geometric properties. The former describe the connectivity between nodes, edges and faces and the latter describe attributes such as node positions in 3D space, face colors, etc. Our interest is in the efficient encoding of topology, which is the bottleneck for 3D model compression. In the thesis, we provide a linear-time information-theoretically optimal compression algorithm for encoding (decoding) a constant-genus polygon mesh to (from, respectively) a binary bit string.

1 Introduction 4
2 Definitions and Related Work 6
2.1 Definitions . . . . . . . . . . . . . . . . . . 6
2.2 RelatedWork─Lu's Methodology . . . . . . . . . 11
3 The Number of Bits for Encoding a k-Mesh 13
4 Technical Tools 15
5 The Compensation Operation 20
6 The Encoding and Decoding Algorithms 26
7 Time and Space Complexity 30
8 Conclusion 33
Bibliography 34
A Some Technical Proofs 38
A.1 The Number of Bits for Encoding a
Constant-Genus Graph . . . . . . . . . . . . . . . 38
A.2 The Decomposition Operation . . . . . . . . . . . 39
A.3 The Preprocessed Table for (λ, π)-Graphs . . . . . 43

[1] P. Alliez and M. Desbrun. Valence-driven connectivity
encoding of 3D meshes. In Proceedings of
Eurographics '2001 Conference, pages 480—489, 2001.
[2] T. C. Bell, J. G. Cleary, and I. H. Witten.
Text Compression. Prentice-Hall,
Englewood Cliffs, NJ, 1990.
[3] J. A. Bondy and U. S. R. Murty. Graph Theory
with Applications. Macmillan Press LTD, 1976.
[4] A. Brodnik and J. I. Munro. Membership in constant
time and almost minimum space. SIAM Journal on Computing,
28(5):1627—1640, 2000.
[5] D. R. Clark. Compact PAT Trees. PhD thesis,
University of Waterloo, 1996.
[6] S. A. Cook and R. A. Reckhow. Time bounded random
access machines. Journal of Computer and System Sciences,
7:354—375, 1976.
[7] N. Deo and B. Litow. A structural approach to graph
compression. In Proceedings of MFCS '98 Satellite Workshop
on Communications, pages 91—101, 1998.
[8] H. N. Djidjev and S. M. Venkatesan. Planarization of
graphs embedded on surfaces. In Proceedings of 21st
Workshop on Graph-Theoretic Concepts in Computer Science,
pages 62—72. Lecture Notes in Computer Science 1017,
Springer, 1995.
[9] P. Elias. Universal codeword sets and representations of
the integers. IEEE Trans. Inform. Theory, IT-21:194—203,
1975.
[10] J. R. Gilbert, J. P. Hutchinson, and R. E. Tarjan.
A seperator theorem for graphs of bounded genus.
Journal of Algorithms, 5(3):391—407, 1984.
[11] M. T. Goodrich. Planar separators and parallel polygon
triangulation. Journal of Computer and System Sciences,
51(3):374—389, 1995.
[12] X. He, M.-Y. Kao, and H.-I. Lu. A fast general methodology
for information-theoretically optimal encodings of graphs.
SIAM Journal on Computing, 30(3):838—846, 2000.
[13] L. Heath and S. Istrail. The page number of genus g graphs
is o(g). In 19th Symp. on Theory of Computing,
pages 388—397, 1987.
[14] M. Isenburg. Triangle strip compression. In Graphics
Interface '2000, 2000.
[15] M. Isenburg and J. Snoeyink. Face fixer: Compressing
polygon meshes with properties. In Proceedings of
SIGGRAPH '00 Conference, pages 263—270, 2000.
[16] M. Isenburg and J. Snoeyink. Coding polygon meshes as
compressable ASCII. In Web3D '2002, 2002.
[17] A. Khodakovsky, P. Alliez, M. Desbrun, and P. Schroeder.
Near-optimal connectivity encoding of 2-manifold polygon
meshes. Graphical Models, 64:147—168, 2002.
[18] D. King. http://www.3dcompression.com.
[19] D. King, J. Rossignac, and A. Szmczak. Connectivity
compression for irregular quadrilateral meshes. Technical
Report TR-99-36, GVU, Georgia Tech, 1999.
[20] B. Kronrod and C. Gotsman. Efficient encoding of
non-triangular meshes. In Preceedings of Pacific Graphics
2000 Conference.
[21] J. Li and C.-C. Kuo. Mesh connectivity coding by the dual
graph approach. MPEG98 Contribution document No. M3530,
1998.
[22] H.-I. Lu. Linear-time compression of bounded-genus graphs
into information-theoretically optimal number of bits. In
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on
Discrete Algorithms, pages 223—224, 2002.
[23] B. Mohar. A linear time algorithm for embedding graphs in
an arbitrary surface. SIAM Journal on Discrete
Mathematics, 12(1):6—26, 1999.
[24] J. Rossignac. Edgebreak: Connectivity compression for
triangle meshes. IEEE Transactions on Visualization and
Computer Graphics, 5(1):47—61, 1999.
[25] J. Rossignac, A. Safonova, and A. Szymczak. 3D compression
made simple: Edgebreaker on a corner-table. In Shape
Modeling International Conference, 2001.
[26] J. Rossignac and A. Szymczak. Wrap&Zip decompression of
the connectivity of triangle meshes compressed with
Edgebreaker. Computational Geometry: Theory and
Applications, 14(13):119—135, 1999.
[27] P. Sch¨oer. http://www.multires.caltech.edu.
[28] S. Skiena. Graph Isomorphism. §5.2 in Implementing
Discrete Mathematics: Combinatorics and Graph Theory
with Mathematica. Reading, MA: Addison-Wesley,
pp. 181—187, 1990.
[29] A. Szymczak, D. King, and J. Rossignac. An
Edgebreaker-based efficient compression scheme for
regular meshes. In Canadian Conference on
Computational Geometry, 2000.
[30] G. Taubin and J. Rossignac. Geometric compression through
topological surgery. ACM Transactions on Graphics,
17(2):84—115, 1998.
[31] C. Thomassen. The graph genus problem is NP-complete.
Journal of Algorithms, 10(4):568—576, 1989.
[32] M. Thorup. On RAM priority queues. SIAM Journal on
Computing, 30:86—109, 2000.
[33] C. Touma and C. Gotsman. Triangle mesh compression. In
Proceedings of Graphics Interface '98 Conference,
pages 26—34, 1998.
[34] W. T. Tutte. A census of planar triangulations.
Canad. J. Math., 14:21—38, 1962.
[35] R. J. Wilson and J. J. Watkins. Graphs: An Introductory
Approach, pages 261—262. John Wiley & Sons, Inc., 1990.