臺灣博碩士論文加值系統

虛擬場景的瀏覽可讓使用者未親自置於真實環境中，也能對該環境有所了解。但隨著場景複雜度與相關應用的增加，如何能在有限的網路頻寬與受限的硬體資源下，讓使用者在大型虛擬環境中仍擁有一定的瀏覽品質，就成為相當重要的課題。本論文為了解決瀏覽大型環境的問題，提出了一個有效的解決方案。本論文所提議的系統採用了即時的場景管理機制，其作用在於減少網路傳輸之幾何資料量，並有效管理使用者端計算資源。另外，我們還採用了具優先權概念的MLM(Most Likelihood Movement)預取模型，經由預測使用者未來可能動向來進行場景的預取。為了提高預取的準確率，此模型將滑鼠的操控特性和障礙物對瀏覽行為的影響納入考量。本系統的快取機制，則是依據瀏覽行為在空間與時間的相關性而設計的混合式相關(Hybrid Coherence)快取模型。我們已實做了整個瀏覽大型場景的前後端系統，並以實驗的方式驗証所採用的機制能有助於瀏覽效率的提昇。

Walkthrough in a virtual environment enables a user to have realistic experiences in an unreachable scene. However, as the complexity and applications of virtual environments increase, it becomes an emerging issue to maintain the quality of a walkthrough experience. In this thesis, we propose an effective data management scheme to address this issue. First, we propose to use real-time scene management to reduce the amount of geometry data transmission and to manage the computing resources on the client side. Second, we propose a prioritized MLM(Most Likelihood Movement) model to prefetch possible future objects, based on users’ current motion intentions. In addition, this prefetching model has accounted for mouse control and influence of obstacles in walkthrough to increase prefetching accuracy. Lastly, a hybrid coherence cache model is proposed to take advantages of both the temporal and spatial localities of walkthrough. We have implemented the front-end and back-end systems for the proposed scheme and done extensive experiments to demonstrate how these techniques can improve the effectiveness of walkthrough in a large virtual environment.

第一 章 緒論 1
1.1 研究動機與目的 1
1.2 本論文的貢獻 3
1.3 本論文的章節架構 4
第二 章 相關研究 5
2.1 幾何複製的相關研究 5
2.2 資料管理的相關研究 7
2.3 與本論文相近的研究 8
第三章 問題定義 11
3.1 基本問題定義 11
3.2 虛擬環境瀏覽的類型 13
3.2.1伺服器端與使用者端資料管理 13
3.2.2單人與多人虛擬環境 14
3.2.3 特殊假設與無特殊假設的瀏覽行為 15
3.3 本論文的範疇 15
第四 章 系統架構 17
4.1 系統架構概述 17
4.2 即時場景管理 19
4.3 混合式相關快取模型 21
4.3.1 空間相關性的判斷 23
4.3.2 實例說明 24
第五章 MLM 預取模型 27
5.1 瀏覽過程中資料存取的觀察 28
5.2 優先權的觀念 31
5.3 滑鼠操控對瀏覽行為的影響 32
5.3.1 滑鼠空間 32
5.3.2 滑鼠的導正行為 36
5.4 障礙物對瀏覽行為的影響 39
5.5 結合滑鼠操控與障礙物影響的模型 41
第六章 實作與實驗 42
6.1 實作成果 42
6.1.1 瀏覽系統運作 42
6.1.2 後端場景的建立與管理 46
6.2 實驗 49
6.2.1 實驗結果 51
6.2.2實驗討論 53
第七章 結論 58
7.1 結論 58
7.2 未來發展方向 59
參考文獻 60

[1] J. Airey, J. Rohlf, and F. Brooks, “Towards Image Realism with Interactive Update Rates in Complex Virtual Building Environments,” in ACM 1990 Symposium on Interactive 3D Graphics, pp. 41-50, 1990.
[2] M. Berg, M. Kreveld, M. Overmars, and O. Schwarzkopf, Computational Geometry-Algorithms and Applications, pp. 20-29, 1997.
[3] blaxxun3D, URL: http://www.blaxxun.com/products/blaxxun3d/.
[4] Blizzard: DIABLO, Computer game, URL: http://www.blizzard.com/worlds-diablo.shtml.
[5] M. Carey, M. Franklin, Livny, and E. Shekita, “Data Caching Tradeoffs in Client-Server DBMS Architectures,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 357-366, 1991.
[6] A. Chan, R. W. H. Lau, and A. Si, “A Motion Prediction Method for Mouse-Based Navigation,” in Proceedings Of CGI’2001, IEEE Computer Society Press, pp. 139-146, July 2001
[7] B. Y. L. Chan, A. Si, and H. V. Leong, ”Cache Management for Mobile Databases: Design and Evaluation,” in Proceedings of the IEEE International Conference on Data Engineering, pp. 54-63, Feb. 1998.
[8] J. Chim, R. Lau, H. Leong, and A. Si, “Multi-Resolution Cache Management in Digital Virtual Library,” in Proceedings of IEEE Advances in Digital Library, pp. 66-75, 1998.
[9] S. Coorg and S. Teller, ”Temporally coherent conservative visibility,” in Proceedings of the twelfth annual symposium on Computational geometry, pp. 78-87, 1996.
[10] M. DeHaemer and M. Zyda, “Simplification of Objects Rendered by Polygonal Approximations,” in Computers and Graphics, 15(2):175-184, 1991.
[11] DIS Steering Committee, “IEEE Standard For Distributed Interactive Simulation-Application Protocols,” IEEE Standard 1278, 1998.
[12] C. Faisstnauer, D. Schmalstieg, and W. Purgathofer, “Priority Scheduling for Networked Virtual Environments,” in IEEE Computer Graphics and Applications, 20(6), pp. 66-75, November 2000.
[13] M. Franklin, M. Carey, and M. Livny, “Global Memory Management in Client-Server DBMS Architectures,” in Proceedings of the International Conference on Very Large Database, pp. 596-609, 1992.
[14] A. Funkhouser, H. Seqin and J. Teller, “Management of Large Amounts of Data in Interactive Building Walkthroughs,” in Proceedings of the 1992 symposium on Interactive 3D graphics, pp. 11-20, 1992.
[15] Z. Gigus, J. Canny, and R. Seidel, “Efficiently Computing and Representing Aspect Graphs of Polyhedral Objects,” in IEEE Transactions on Pattern Analysis and Machine Intelligence, 13(6), 542— 551, 1991.
[16] Z. Gigus and J. Malik, “Computing the Aspect Graph for Line Drawings of Polyhedral Objects,” in IEEE Transactions on Pattern Analysis and Machine Intelligence, 12(2), pp. 113— 122, 1990.
[17] H. Hoppe, “Progressive Meshes,” in Proceedings of ACM SIGGRAPH’96, pp. 99-108, August 1996.
[18] H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, and W. Stuetzle, “Mesh Optimization,” in ACM Computer Graphics (SIGGRAPH’93), volume 27, pp. 19-26, August 1993.
[19] J.Y. Huang, C.T. Fang-Tsou, and J.L. Chang, “A Multiuser 3D Web Browsing System”, IEEE Internet Computing, 2,5, 70-79, 1998.
[20] ID Software: DOOM, Computer game, URL: http://www.idsoftware.com/games/doom/doom-final/.
[21] A. Katz and K. Graham, “Dead Reckoning for Airplanes in Coordinated Flight,” in Proceedings of Workshop on Standards for Interoperability of Defense Simulations, pp. 5-13, 1994.
[22] G. Liu and G. Maguire, “A Class of Mobile Motion Prediction Algorithms for Wireless Mobilecomputing and Communications,” in Mobile Networks and Applications, 1(2), pp. 113-121, 1996.
[23] M. R. Macedonia, M. J. Zyda, D. R. Pratt, P. T. Barham, and S. Zeswitz, “NPSNET: A Network Software Architecture for Large-Scale VEs,” Presence 3(4), pp. 265-287, 1994.
[24] S. Park, D. Lee, M. Lim, and C.Yu, ”Scalable Data Management Using User-Based Caching and Prefetching in Distributed Virtual Environments,” in Symposium on Virtual Reality Software and Technology, 2001.
[25] G. Taubin and J. Rossignac, “Geometric Compression through Topological Surgery,” in ACM Transactions On Graphics, 1998.
[26] S. Teller and C. Sequin, “Visibility Preprocessing for Interactive Walkthroughs,” in Proceedings of ACM Computer Graphics Conference (SIGGRAPH91), pp. 61-69, 1991.
[27] G. Turk, “R-tiling Polygonal Surfaces,” in ACM Computer Graphics (SIGGRAPH’92), volume 26, pp. 55-64, July 1992.
[28] VRML97 International Standard, URL: http://www.web3d.org/technicalinfo/specifications/vrml97/index.html.