三角網格關連性之研究

Connectivity Compression for Triangular Meshes

楊文灝(Wen-Hao Yang)

指導教授 ： 鍾斌賢

中原大學/工學院/電子工程研究所/博士(2005年)

https://doi.org/10.6840/cycu200500446

摘要

中文摘要

三度空間立體模型之單一連接性(single-rate connectivity)壓縮法之研究，可區分成以邊為基礎 (Edge-based) 及以頂點為基礎 (Vertex-based) 兩類；Edgebreaker是以邊為基礎的代表方法，而Valence-driven是以頂點為基礎的代表方法。此兩者均需要使用切割運算元將三度空間立體模型切割成兩個部份，也因為切割的影響將造成額外紀錄距離的負擔或額外的運算位元來辨識切割處，進而降低壓縮的品質。Edgebreaker 演算法的主要缺點有二：第一為多次路徑 (multiple pass traversals) 的壓縮三角片，此方式將造成執行時間的大量浪費。第二為反向的解壓縮程序，此操作程序將使得解壓縮的過程必須在離線 (off-line) 的狀態下進行。Valence-driven 演算法的缺點是在不知道三角網格的分支資訊時，需要額外的演算程序，計算每一個頂點的分支度 (degree) 。為了克服以上的限制，本論文提出了三個針對單一解析度 (single-resolution) 物體之壓縮演算法來解決三角網格連接性的問題。我們的演算法能夠單一路徑的壓縮及解壓縮，並且能在及時 (on-line) 的模式下進行整個程序。
我們提出的三個演算法分別稱為Algorithm I 、Algorithm II及Algorithm III。在Algorithm I 的演算法中，我們提出了J運算元，其主要的功能是跳至作用邊的下一個邊，避免切割的情形發生造成額外的運算元浪費。並且藉由使用Q運算元一次壓縮兩片三角片，達到壓縮率的進一步提升。第二個演算法Algorithm II 主要是利用空間的區域性 (spatial locality) 減少切割所造成的額外浪費，也就是說經由考慮幾何特性提出適當的簡化規則，當切割發生時，省略最後一片三角片，減少分支所造成的浪費。最後一個演算法Algorithm III是將Algorithm I 及 Algorithm II 做進一步的結合，以提升整體的壓縮效率及執行時間。
另一個被利用於本論文的演算技巧是適性算數編碼法(adaptive arithmetic coder)，它可進一步增加壓縮的效率。從大量的實驗數據觀察到，我們所提出的演算法其平均壓縮率均優於Valence-driven 及 Edgebreaker 演算法。從熵/壓縮率(entropy/compression) 相對應的曲線比較也可得知，我們的演算法是較接近entropy的壓縮方式的。此外我們的演算法只需要考慮固定的運算元數目及它們的值的分布情形，即可得到最佳化壓縮率。

關鍵字

geometry compression ； adaptive arithmetic coder ； triangular mesh connectivity

並列摘要

Abstract

Single-rate connectivity compression approaches for 3D models can be divided into edge-based and vertex-based algorithms. Edgebreaker is an edge-based approach, whereas the valence-driven approach is vertex-based. Both approaches use split operation to separate the 3D model into two components, that raise some bottlenecks for spending increased overheads to record the displacement, or an extra operator is needed for identifying the branch. The Edgebreaker is either multiple pass traversals or operate in reverse order. Multiple pass traversals take a long time to execute. Operation in reverse order should work only off line since its decompression order follows the reverse order of the compression. The valence-driven method requires an extra pass to calculate the valence of vertices when the triangular mesh does not have vertex degree information. To eradicate these restrictions, this study presents three edge-based single-resolution compression algorithms for managing triangular mesh connectivity. The proposed algorithms encode and decode 3D models straightforwardly with sequential single traversal.
The proposed Algorithm I provides using the J operator to skip to the next edge of the active boundary; the method need not split overhead. By using Q operator, two triangles are encoded to improve compression ratio. The proposed Algorithm II investigates spatial locality to minimize costs in split operations. Meanwhile, some simplification rules are proposed by considering geometric characteristics which ignore the last triangle when a split occurs. The proposed Algorithm III combines Algorithm I and Algorithm II, the method improves not only the compression ratio but also the execution time.
An adaptive arithmetic coder is applied to the proposed algorithms, to increase the compression ratio. The experimental results indicate that an excellent compression ratio can be obtained, and the average compression ratio associated with the proposed algorithms are better than that associated with the valence-driven and Edgebreaker methods. The curve of compression ratios is near the entropy curve of the proposed algorithms. The proposed algorithms fixed the number of operators and their value distribution by only considering the context between operators in optimizing the compression ratio.

並列關鍵字

三角網格關聯性 ； 幾何壓縮 ； 適性算數編碼法

參考文獻

42. B. S. Jong, T. W. Lin, W. H. Yang, and S. Song. “An Efficient Edge-based Compression Algorithm for 3D Models with Holes and Handles”, Journal of Information Science and Engineering, 2005. (Accepted)

1. P. Alliez and M. Desbrun. “Valence-Driven Connectivity Encoding for 3D Meshes,” Eurographics’01, pp. 480-489, 2001.

2. P. Alliez and M. Desbrun. “Progressive Encoding for Lossless Transmission of 3D Meshes,” Siggraph 2001 Conference Proceedings, pp. 198-205, 2001.

3. C. L Bajaj, V. Pascucci, G. Zhuang, “Single Resolution Compression of Arbitrary Triangular Meshes with Properties”, IEEE Proceedings of the Data Compression Conference, pp.307-316, 1999

4. H. Bruggeser and P. Mani. “ Shellable Decompositions of Cells and Sphere,” Math. Scand., pp. 197-205, 1971.