臺灣博碩士論文加值系統

這幾年來，虛擬實境與網路多媒體技術的搭配應用相當地普遍，最常見的莫過於建築物的導覽。對於這類的3D幾何圖形，檔案容量相當地龐大，在現今有限的網路頻寬之下，對傳輸品質是相當不利的。若要即時地將這些大量的3D模型描繪出來，目前面臨最大的瓶頸，乃是在繪圖顯像硬體中的記憶體匯流排頻寬的不足。基於上述的兩個原因，如果將3D幾何圖形先行壓縮，那麼傳輸的時間將大大地降低。若要描繪的3D模型，也事先予以壓縮而儲存在主記憶體中；當繪圖管線要進行描繪時，先透過即時的解壓縮處理器，就可以迅速地描繪出正確的模型。
雖然壓縮與解壓縮技術可以解決頻寬不足的瓶頸，但在即時的要求之下，速度更是一大考驗。我們演算法單純的觀念就是由一個邊可以找到對應的兩個頂點，也就是相鄰的兩片三角片，加上同心圓的構想，將這些幾何模型的三角片表示成二元樹的架構，針對此二元樹適度地編碼，一方面可以完整又清楚地紀錄下三角片之間的關係，而且不會浪費太多記憶體空間；另一方面只需要利用一個佇列即可以完成壓縮與解壓縮的動作，處理過程相當簡單快速。
我們將此方法與現有的局部網格化演算法作實例比較，不論在壓縮比或是執行速度方面均比該方法優異，同時我們針對各種不同的三度空間幾何模型進行壓縮，平均的壓縮率大約為12至13倍左右，若加上差分編碼之後，可以提高到15倍左右，有些模型甚至可以達到18倍。至於速度方面，壓縮與解壓縮的部分所花費的時間不相上下，而且速度相當地快，這是因為壓縮與解壓縮的演算法十分簡單，也不會浪費太多的記憶體空間，非常適合實現在硬體架構上，形成一個即時壓縮與解壓縮的處理器。

Recently, the applications for the combination of virtual reality and multimedia technique are popular, such as the architectural walkthroughs. For these 3D (three dimension) geometry objects, they almost are large datasets. However, the performance of transmission is not satisfactory due to the limitation of bandwidth of current networks. In addition, the real-time graphics hardware is facing a large memory bus bandwidth bottleneck in which the amount of 3D geometry objects cannot be sent fast enough to the graphics pipeline interface. Base on the above reasons, if these geometry objects can be transmitted on networks in compressed format, the transmission time will be reduced greatly. Similarly, the geometry object can be stored in main memory in compressed format. Upon rendering in graphics pipeline interface, the compressed geometry data is sent to the rendering hardware for real-time decompression using an efficient hardware decompressor.
Although the geometry compression/decompression technique can solve the memory bus bandwidth bottleneck, the proof of run time is important in real-time qualification. The idea of our algorithm is that one edge can connect to two new vertices to form two contiguous triangles. Furthermore, the idea of homocentric circle is added and these triangles of geometry objects can be represented by the binary tree structure. We can encode the binary tree to linear structure moderately. Such solutions can record the triangle information completely, and less storage space is needed on main memory. We only need a queue to perform the compression and decompression operations. The processes are fast enough for real-time applications.
We present the geometry compression/decompression algorithm that has better compression ratios and run time than local meshify algorithm. We have tried our optimized geometry compressor on several datasets. It achieves compression ratios of 12 to 15 times over binary encoded triangle strips. Some geometry objects can achieve up to 18. The Run time of compression operation likes decompression operation, and is fast. Because the compression/decompression algorithm is very simple and less storage space is needed on main memory. These benefits allow a real-time hardware realization of compression/decompression algorithm.

摘要.........................................................I
Abstract...................................................III
致謝.........................................................V
目錄........................................................VI
圖片目錄..................................................VIII
表格目錄....................................................IX
第1章 緒論...................................................1
1.1背景與動機..............................................1
1.2內容簡介................................................3
第2章 相關研究討論............................................4
2.1帶狀三角片（Triangle Strip）的介紹.......................5
2.2一般化帶狀三角片（Generalized Triangle Strip）...........6
2.3一般化三角網格（Generalized Triangle Mesh）..............8
2.4產生一般化三角網格的相關研究.............................10
第3章 壓縮與解壓縮的方法論....................................16
3.1三角片頂點座標之壓縮方法.................................17
3.2三角片材質屬性或顏色之壓縮方法...........................19
3.3三角片頂點法向量之壓縮方法...............................20
3.4一般化三角網格的尋找.....................................22
3.5壓縮與解壓縮演算法處理核心介紹...........................27
3.5.1相關資料結構........................................28
3.5.2壓縮與解壓縮演算法...................................33
3.6網格暫存器的容量探討.....................................43
第4章 實驗結果與討論..........................................44
4.1實驗結果與比較...........................................45
4.2座標量化限度測試.........................................54
4.3網格暫存器容量測試.......................................56
第5章 結論與未來展望..........................................61
參考文獻.....................................................63

[1] Deering M. Geometry Compression. Computer Graphics
（Proceeding of SIGGRAPH）, PP.13-20, August, 1995
[2] Francine Evans, Steven Skiena, and Amitabh Varshney.
Optimizing Triangle Strips for Fast Rendering（Proceeding
of the IEEE Visualization）, PP.319-326, October, 1996
[3] Gabriel Taubin, and Jarek Rossignac. Geometric Compression
Through Topological Surgery. IBM RC-20340
（http://www.research.ibm.com/vrml/binary）, 1996
[4] Mike M. Chow. Optimized Geometry Compression for Real-time
Rendering（Proceeding of the IEEE Visualization）, PP.347-
354, 1997
[5] Richard S. Wright, Jr. and Michael Sweet. OPENGL
SUPERBIBLE. Waite Group PressTM. 1996
[6] Stefan Gumhold, and Wolfgang StraBer. Real Time Compression
of Triangle Mesh Connectivity（Proceeding of SIGGRAPH）,
PP.133-140, July, 1998
[7] Sum Microsystems, Inc. Java 3DTM API Specification, Version
1.1（http://java.sun.com/products/java-media/3D/）,
December, 1998
[8] 杜家玫. 網際網路上幾何壓縮技術之研究. 國立清華大學 碩士論文.
1998
[9] Jean-loup Gailly and Mark Adler, zlib Version1.1.3
（http://www.cdrom.com/pub/infozip/zlib/）