研究生: |
陳宏光 Hung-Kuang Chen |
---|---|
論文名稱: |
三維物件的高效能大型多邊形網格化簡方法之研究 A Study on the High-Performance Approaches to Large Polygonal Mesh Simplification of 3D Objects |
指導教授: |
林銘波
Ming-Bo Lin 范欽雄 Chin-Shyurng Fahn |
口試委員: |
楊熙年
Shi-Nian Yang 莊榮宏 Rong-Hung Juang 李宗南 Tzun-Nan Lee 李同益 Tony Tung-Yi Lee 鍾國亮 Kuo-Liang Chung |
學位類別: |
博士 Doctor |
系所名稱: |
電資學院 - 電子工程系 Department of Electronic and Computer Engineering |
論文出版年: | 2006 |
畢業學年度: | 94 |
語文別: | 英文 |
論文頁數: | 107 |
中文關鍵詞: | 三維物件 、多邊形網格 、大形多邊形網格 、多邊形網格化簡 |
外文關鍵詞: | 3D object, polygonal mesh, large polygonal mesh, polygonal mesh simplification |
相關次數: | 點閱:223 下載:6 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
由於為許多著色系統支援,多邊形網格已成為多年來三維物件的主流表示法。然而,這類表示法往往需要巨量的多邊形來表示高細節的物件。作為一個防止過度使用多邊形的相當有用的方法,多邊形簡化演算法的研究在近二十年來被密集的研究著.
傳統的內核遞迴邊縮減式簡化演算法通常可產生相當高品質的簡化模型. 但是,這一類的演算卻具有相當低的執行效率及與輸入大小相關的大量記憶體需求。另一方面來說,外核格篩式演算法雖能有效率的處理大型多邊形網格的化簡,卻在使用低解析度網格時往往產生相當低品質的輸出。
在本篇論文中,我將提出三種新的作法:第一種是能產生高品質輸出,低儲存體需求,高效能線性時間的演算法。其次是一個用來處理大量多邊形網格整合快取的外核系統。最後是一個可用來整合多種不同型式簡化演算法,並可同時允許內核、外核、混合型操作、及兩段式簡化的一個與儲體不相依的多邊形網格化簡系統。
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.
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.