臺灣博碩士論文加值系統

由於為許多著色系統支援，多邊形網格已成為多年來三維物件的主流表示法。然而，這類表示法往往需要巨量的多邊形來表示高細節的物件。作為一個防止過度使用多邊形的相當有用的方法，多邊形簡化演算法的研究在近二十年來被密集的研究著.
傳統的內核遞迴邊縮減式簡化演算法通常可產生相當高品質的簡化模型. 但是，這一類的演算卻具有相當低的執行效率及與輸入大小相關的大量記憶體需求。另一方面來說，外核格篩式演算法雖能有效率的處理大型多邊形網格的化簡，卻在使用低解析度網格時往往產生相當低品質的輸出。
在本篇論文中，我將提出三種新的作法：第一種是能產生高品質輸出，低儲存體需求，高效能線性時間的演算法。其次是一個用來處理大量多邊形網格整合快取的外核系統。最後是一個可用來整合多種不同型式簡化演算法，並可同時允許內核、外核、混合型操作、及兩段式簡化的一個與儲體不相依的多邊形網格化簡系統。

Owing to the support by most rendering systems, the polygonal mesh representation has been the dominant representation scheme of 3D objects for many years. However, to represent an object in high resolution, it usually requires enormous amount of polygons. Consequently, the polygonal mesh simplification as a very useful scheme to prevent from overly use of polygons was intensively studied.
Traditional iterative-edge-collapse-based in-core simplification algorithms usually create very good quality approximations. Somehow, this class of algorithms has relatively low runtime efficiency and large main memory cost that is sensitive to its input mesh size. On the other hand, the out-of-core grid-based algorithms capable of dealing with very large meshes often create very low quality approximations at low resolution grids.
In this dissertation, we will propose a linear-time high efficiency and low main memory cost simplification algorithm for high quality discrete LOD generations, a novel cache-based approach to dealing with large meshes, and a storage independent simplification system allowing in-core, out-of-core, hybrid operations, and multistage integration of simplification algorithms of various types.

Chapter 1 Introduction 1
1.1 The Background 1
1.2 The Problem Statement 3
1.3 Motivations and Contributions 4
1.4 Dissertation Outline 6
Chapter 2 Terminology 7
2.1 Topological Notations 7
2.2 The Ring of a Vertex 7
2.3 The Quadric Error Metrics 8
2.4 The Replacement Selection Heap 9
2.5 The Cache Algorithms 11
Chapter 3 Related Work 13
3.1 The Simplification Schemes 13
3.1.1 Iterative contraction 13
3.1.2 Grid-based re-sampling 16
3.2 Related Algorithms 17
3.2.1 The in-core simplification algorithms 17
3.2.2 The simplification algorithms for large meshes 18
3.2.3 The multiphase approach 20
3.3 The Level-of-Detail Representations 20
3.3.1 Discrete LOD 21
3.3.2 Dynamic LOD 21
3.3.3 View-Dependent LOD 21
Chapter 4 A Linear Time Polygonal Mesh Simplification Algorithm 23
4.1 The Simplification Algorithm 24
4.1.1 The vertex ring construction stage 26
4.1.2 The simplification stage 27
4.1.3 The output stage 32
4.1.4 Time complexity analysis 32
4.2 Experimental Results 34
4.2.1 Memory costs 35
4.2.2 Runtime efficiency 36
4.2.3 Output quality 37
4.3 Discussions and Conclusions 38
Chapter 5 A Novel Cache-Based Approach to Large Mesh Simplification 46
5.1 Overview 46
5.2 The Simplification Layer 47
5.2.1 The input mesh and associated data structures 48
5.2.2 The construction of vertex rings 49
5.2.3 The computation stage 50
5.2.4 The contraction stage and the dependency control strategies 54
5.2.5 The output stage 58
5.3 The Cache Layer 59
5.4 Experimental Results 61
5.4.1 The memory costs and running times 62
5.4.2 The evaluation of output quality 64
5.5 Discussions and Conclusions 70
Chapter 6 The Storage Independent Simplification System 72
6.1 The System Overview 72
6.2 The Algorithm Layer 73
6.2.1 Algorithm I – a linear-time iterative edge collapse algorithm 74
6.2.2 Algorithm II – a uniform-grid vertex clustering algorithm 75
6.3 The Data Management Layer 76
6.3.1 The device independent primitives 77
6.3.2 The operation modes 77
6.3.3 The initialization flows 80
6.4 Experimental Results 81
6.4.1 Running times 81
6.4.2 The comparisons 82
6.5 Discussions and Conclusions 89
Chapter 7 Conclusion and Future Work 90
7.1 Conclusion 90
7.2 Future Work 91

1.A. Watt, 3D Computer Graphics, 3rd Ed., Addison-Wesley, Reading, MA, 2000.
2.D. Lubke, et al., Level-of-Detail for 3D Graphics, Morgan Kaufman, San Francisco, CA, USA, 2003.
3.M. J. Ackerman, “The visible human project,” in Proceedings of IEEE, Vol. 86, pp. 504-511, 1998.
4.M. Levoy et al., “The Digital Michelangelo Project: 3D scanning of large statues,” in Proceedings of the SIGGRAPH ‘00, pp. 131-144, 2000.
5.J. Trimble and M. Levoy, “Stanford Digital Forma Urbis Romae Project,” http://formaurbis.stanford.edu/docs/FURproject.html, 2002.
6.O. Deussen et al., “Realistic modeling and rendering of plant ecosystems,” in Proceedings of the 25th annual conference on Computer graphics and interactive techniques, ACM Press, New York, NY, USA, pp. 275-286, 1998.
7.M. R. Mine, J. Shochet, and R. Hughston, “Building a massively multiplayer game for the million: Disney's Toontown Online,” ACM Computers in Entertainment, Vol. 1, No. 1, Article 06, 2003.
8.T. A. Funkhouser and C. H. Sequin, “Adaptive display algorithm for interactive frame rates during visualization of complex virtual environments,” in Proceedings of the SIGGRAPH ‘93, pp. 247-254, 1993.
9.H. Hoppe et al., “Mesh optimization,” in Proceedings of the SIGGRAPH ‘93, Vol. 27, pp. 19-26, 1993.
10.J. H. Clark, “Hierarchical geometric models for visible surface algorithms,” Communications of the ACM, Vol. 19, No. 10, pp. 547-554, 1976.
11.H. Hoppe, “Progressive meshes,” in Proceedings of the SIGGRAPH ‘96, Vol. 30, pp. 99-108, 1996.
12.M. Garland and P.S. Heckbert, “Surface simplification using quadric error metrics,” in Proceedings of the SIGGRAPH ‘96, Vol. 30, pp. 209-216, 1996.
13.P. Lindstrom and Greg Turk, “Evaluation of memoryless simplification,” IEEE Transactions on Visualization and Computer Graphics, Vol. 5, No. 2, pp. 98-115, 1999.
14.L. Kobbelt, S. Campagna, and H. P. Seidel, “A general framework for mesh decimation,” in Proceedings of the Graphics Interface ‘98, pp.43-50, 1998.
15.W. J. Schroeder, J. A. Zarge, and W. E. Lorensen, “Decimation of triangle meshes,” in Proceedings of the SIGGRAPH ‘92, Vol. 26, pp. 65-70, 1992.
16.J. Rossignac and P. Borrel, “Multi-resolution 3D approximation for rendering complex scenes,” in Proceedings of the Geometric Modeling in Computer Graphics ‘93, pp. 455-465, 1993.
17.K. L. Low and T. S. Tan, “Model simplification using vertex clustering,” in Proceedings of the Symposium on Interactive 3D Graphics ‘97, pp. 75-82, 1997.
18.A. D. Kalvin, and R. H. Taylor, “Superfaces: Polygonal Mesh Simplification with Bounded Error,” IEEE Computer Graphics and Applications, Vol. 16, No. 3, pp. 64-77, 1996.
19.R. Ronfard and J. Rossignac, “Full-range approximation of triangulated polyhedra,” in Proceedings of the Eurographics ‘96, Vol. 15, No. 3, pp. 67-76, 1996.
20.S. Campagna, L. Kobbelt, and H. P. Seidel, “Efficient decimation of complex meshes,” Technical Report, Computer Graphics Group, University of Erlangen-Nürnberg, Germany, 1998.
21.J. Wu and L. Kobbelt, "Fast mesh decimation by multiple-choice techniques," in Proceedings of the International Fall Workshop on Vision, Modeling, and Visualization ‘02, pp. 241-248, 2002.
22.D. Brodsky and B. Watson, “Model simplification through refinement,” in Proceedings of the Graphics Interface ‘00, pp. 221-228, 2000.
23.P. Lindstrom, “Out-of-core simplification of large polygonal models,” in Proceedings of the SIGGRAPH ‘00, Vol. 34, pp. 259-270, 2000.
24.P. Lindstrom and C. T. Silva, “A memory insensitive technique for large model simplification,” in Proceedings of the IEEE Visualization ‘01, pp. 121-126, 2001.
25.P. Lindstrom, “Out-of-core construction and visualization of multiresolution surfaces,” in Proceedings of the Symposium on Interactive 3D Graphics ‘03, pp. 93-102, 2003.
26.E. Shaffer and M. Garland, “Efficient adaptive simplification of massive meshes,” in Proceedings of the IEEE Visualization ‘01, pp. 127-134, 2001.
27.P. Choudhury and B. Watson, “Completely adaptive simplification of massive meshes,” Technical Report CS-02-09, Northwestern University, Evanston, Illinois, 2002.
28.H. Hoppe, “Smooth view-dependent level-of-detail control and its application to terrain rendering,” in Proceedings of the IEEE Visualization ‘98, pp. 35-42, 1998.
29.J. El-Sana and Y. J. Chiang, “External memory view-dependent simplification,” Computer Graphics Forum, Vol. 19, No. 3, pp. 139-150, 2000.
30.C. Prince, Progressive Meshes for Large Models of Arbitrary Topology, Master Thesis, Department of Computer Science and Engineering, University of Washington, Seattle, 2000.
31.P. Cignoni et al., “External memory management and simplification of huge meshes,” IEEE Transactions on Visualization and Computer Graphics, Vol. 9, No. 4, pp. 525-537, 2003.
32.J. Wu and L. Kobbelt, “A stream algorithm for the decimation of massive meshes,” in Proceedings of the Graphics Interface ‘03, pp. 185-192, 2003.
33.M. Isenburg, P. Lindstrom, S. Gumhold, and J. Snoeyink, “Large mesh simplification using processing sequences,” in Proceedings of the IEEE Visualization ‘03, pp. 465-472, 2003.
34.E. Shafer and M. Garland, “A multiresolution representation for massive meshes,” IEEE Transactions on Visualization and Computer Graphics, Vol. 11, No. 2, pp.139-148, 2005.
35.M. Garland and E. Shaffer, “A Multiphase Approach to Efficient Surface Simplification,” in Proceedings of the IEEE Visualization ‘02, pp. 117-124, 2002.
36.H. K. Chen et al., “A linear time algorithm for high quality mesh simplification,” in Proceedings of the IEEE International Symposium on Multimedia Software Engineering ‘04, pp. 169-176, 2004.
37.H. K. Chen et al., “A novel cache-based approach to large mesh simplification,” Journal of Information Science and Engineering, to appear.
38.D. E. Knuth, The Art of Computer Programming, Vol. 3, Addison-Wesley, Reading, New Jersey, 1973.
39.J. Hennessy and D. A. Patterson, Computer Architecture– A Quantitative Approach, Morgan Kaufman, San Francisco, California, 1990.
40.P. Cignoni, C. Montani, C. Rocchini, and R. Scopigno, “A general method for preserving attribute values on simplified meshes,” in Proceedings of the IEEE Visualization ‘98, pp. 59-66, 1998.
41.J. Cohen, M. Olano, and D. Manocha, “Appearance preserving simplification,” in Proceedings of the SIGGRAPH '98, pp.115-122, 1998.
42.H. Hoppe, “New quadric metric for simplifying meshes with appearance attributes,” in Proceedings of the IEEE Visualization ‘99, pp. 59-66, 1999.
43.P. Sander, J. Snyder, S. Gortler, H. Hoppe, "Texture mapping progressive meshes," in Proceedings of the SIGGRAPH ‘01, pp. 409-416, 2001.
44.M. Garland and Y. Zhou. “Quadric-based simplification in any dimension,” ACM Transactions on Graphics, Vol. 24, No. 2, pp. 209-239, 2005.
45.M. Isenburg, S. Gumhold, and J. Snoeyink, “Processing sequences: a new paradigm for out-of-core processing on large meshes,” preprint available at http://www.cs.unc.edu/~isenburg/papers/igs-ps-03.pdf, 2003.
46.M. Garland and P. S. Heckbert, QSlim v.2.0 Simplification Software, Dept. of Computer Science, Univ. of Illinois, http://graphics.cs.uiuc.edu/~garland/software/QSlim.html, 1999.
47.T. A. Funkhouser, Database and display algorithms for interactive visualization of architectural models, Ph.D. Dissertation, the University of California at Berkeley, 1993.
48.M. Giegl and M. Wimmer, “Unpopping: solving the image-space blend problem,” available at www.cg.tuwien.ac.at/research/vr/unpopping/unpopping.pdf, submitted to Journal of Graphics Tools, Special Issue on Hardware-Accelerated Rendering Techniques, 2005.
49.D. Luebke and C. Erikson, “View-dependent simplification of arbitrary polygonal environments,” in Proceedings of the SIGGRAPH '97, Vol. 31, pp. 199-208, 1997.
50.J. C. Xia, J. El-Sana, and A. Varshney, “Adaptive real-time level-of-detail-based rendering for polygonal models,” IEEE Transactions on Visualization and Computer Graphics, Vol. 3, No. 2, pp. 171-183, 1997.
51.D. Dobkin and D. Kirkpatrick, “A linear algorithm for determining the seperation of convex polyhedra,” Journal of Algorithms, Vol. 6, pp. 381-392, 1985.
52.P. Cignoni, C. Rocchini, and R. Scopigno, “Metro: measuring error on simplified surfaces,” in Proceedings of the Eurographics ‘98, Vol. 17, No. 2, pp. 167-174, 1998.
53.F. J. Corbat´o, “A paging experiment with the multics system,” in In Honor of P. M. Morse, MIT Press, pp. 217-228, 1969.
54.R. W. Carr and J. L. Hennessy, “WSClock– A simple and effective algorithm for virtual memory management,” in Proceedings of the Symposium on Operating Systems Principles ‘81, pp. 87-95, 1981.
55.J. Houle and P. Poulin, “Simplification and real-time smooth transitions of articulated meshes,” in Proceedings of the Graphics Interface ‘01, pp. 55-60, 2001.
56.C. H. Lin and T. Y. Lee, “Metamorphosis of 3D polyhedral models using progressive connectivity transformations,” IEEE Transactions on Visualization and Computer Graphics, Vol. 11, No. 1, pp. 2-12, 2005.