臺灣博碩士論文加值系統

在現今虛擬實境與3D電腦圖學的許多應用中，為了呈現出更真實的視覺效果，往往使用了相當大量的polygon，但是如此便使得場景的複雜度越來越高，而造成繪圖系統相當大的負擔。Levels of Detail（LOD）的基本概念是根據實際系統與環境的需求，來適度的改變3D模型的解析度，藉由使用所產生的低複雜度模型，可以有效的降低系統的負擔以增進繪圖的效率。在降低模型的解析度的同時，勢必會對原有的模型外型產生破壞，因此，如何在簡化模型複雜度的同時保持模型的外觀，是一門相當重要的課題。
為了解決上述問題，我們在本論文中提出了以3D skeleton為概念的認知導向LOD系統。模型的skeleton對其而言，是一種與外型相關的簡化描述，可以對我們將模型作簡化時維持模型整體的外觀提供重要的資訊。因此，在對一個模型做簡化的動作前，我們先將其skeleton納入考量，將模型依據skeleton的走向作適度的分割。接下來在各個分隔的區域，根據模型與其相對的3D skeleton關係，找出能代表模型整體外觀特徵的區域和頂點。其後在簡化模型時，就可以藉由保留重要的特徵區域或點來維持模型的基本外型。此外，簡化模型時，我們也考量了模型與形狀辨識有關的模型性質，來增進簡化的結果。

For representing much more realistic visual effects, numerous polygons are often used in many applications of virtual reality and 3D computer graphics today. The number of polygons used in the complicated CG scene becomes more and more. Manipulating and rendering these polygons makes the rendering system a heavy burden. The main purpose of Levels of Detail（LOD）is to reduce the computing cost at the rendering stage by switching among the multi-resolution 3D models according to the actual needs of system and environments. However, the appearance of the model will become coarser certainly while the resolution is reduced. Therefore, simplifying the complexity of models and preserving the appearances of objects at the same time is a very important research issue for LOD.
In this paper, to solve the problem mentioned above, we propose a perception-oriented LOD system by introducing the concept of 3D skeleton. The 3D skeleton is a simplified description to its original model. It provides important information to keep whole appearance while model is simplified. Hence, skeleton is taken into consideration first before we simplify models. Then model is divided appropriately in accordance with the alignment of the skeleton. The regions and vertices which represent the features of whole model could be found according to the relationship between the model and its 3D skeleton. Afterward the basic shape of the model could be preserved by reserving important feature regions and vertices while model is simplified. Furthermore, the properties about shape recognition are also taken into account to improve the result of simplification.

論文摘要 I
Abstract II
致謝 IV
目錄 V
圖片目錄 VI
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 論文編排 4
第二章 相關研究 5
2.1 Level of Detail frameworks 5
2.2 模型簡化演算法 7
2.3 視覺考量的模型簡化 11
第三章 系統架構與演算法 12
3.1 前言 12
3.2 Domain Connected Graph 13
3.3 Quadric Error Metric 16
3.4 模型簡化與DCG和Skeleton的運用 20
第四章 研究結果 27
第五章 結論與未來展望 42
參考文獻 44

[1]P. Heckbert and M. Garland. “Survey of Polygonal Surface Simplification Algorithms”, In SIGGRAPH 97 Course Notes: Multiresolution Surface Modeling.

[2]M. Garland. “Multiresolution Modeling: Survey & Future Opportunities”, Eurographics ’99, State of the Art Reports, September 1999.

[3]Jonathan D. Cohen, “Concepts and Algorithms for Polygonal Simplification”, SIGGRAPH 99 Course Tutorial #20: Interactive Walkthroughs of Large Geometric Datasets. Page(s):C1-C34. 1999. also in SIGGRAPH 2000 Course Tutorial.

[4]Luebke, D.P. “A developer's survey of polygonal simplification algorithms,” Computer Graphics and Applications, IEEE Volume 21, Issue 3, Page(s):24-35, May/Jun 2001.

[5]Tan Kim Heok, Daman, D. “A review on level of detail”, Computer Graphics, Imaging and Visualization, 2004. CGIV 2004, Page(s):70 – 75, July 2004.

[6]W.J. Schroeder, J.A. Zarge, and W.E. Lorensen, “Decimation of Triangle Meshes”, ACM SIGGRAPH Computer Graphics, Volume 26, Issue 2, Page(s):65-70, July 1992.

[7]Jarek Rossignac, Paul Borrel. “Multi-Resolution 3D Approximations for Rendering”, Modeling in Computer Graphics. Springer-Verlag1993. Page(s):455-465.

[8]David Luebke, Carl Erikson. “View-Dependent Simplification of Arbitrary Polygonal Environments”, Proceedings of SIGGRAPH 97. Page(s):199-208.

[9]K.L. Low and T.S. Tan, “Model Simplification Using Vertex-Clustering”, Proc. ACM Symp. Interactive 3D Graphics, Page(s):75-82, 1997.

[10]H. Hoppe, “Progressive Meshes”, SIGGRAPH ’96 Conf. Proc., H. Rushmeier, ed., Page(s):99-108, Aug. 1996.


[11]H. Hoppe, “View-Dependent Refinement of Progressive Meshes”, SIGGRAPH ’97 Conf. Proc., T. Whitted, ed., Page(s):189-198, Aug. 1997.

[12]M. Garland, P.S. Heckbert, “Surface Simplification Using Quadric Error Metrics”, SIGGRAPH ’97 Conf. Proc., T. Whitted, ed., Page(s):209-216, Aug. 1997.

[13]Bernd Hamann, “A data reduction scheme for triangulated surfaces”, Computer Aided Geometric Design, Volume 11 , Issue 2, Page(s):197 – 214, 1994

[14]Fu-Che Wu, Wan-Chun Ma, Rung-Huei Liang, Bing-Yu Chen, Ming Ouhyoung, “Domain Connected Graph: the Essential Skeleton of a 3D Shape”, http://graphics.csie.ntu.edu.tw/DCG/

[15]Nathaniel Williams, David Luebke, Jonathan D. Cohen, Mike Kelly, and Brenden Schubert, “Perceptually Driven Simplification of Lit, Textured Meshes”, Proceedings of 2003 ACM Symposium on Interactive 3D Graphics, Page(s):113-121, 2003.

[16]David Luebke, Martin Reddy, Jonathan Cohen, Amitabh Varshney, Benjamin Watson, Robert Huebner, “Level of Detail for 3-D Graphics”, Morgan Kaufmann, 2002.