臺灣博碩士論文加值系統

在大多數的場景瀏覽系統中，幾何資料是存在本地端電腦上的，這種情況下的研究常常注重在如何裁剪物件以達成即時繪圖的效果。但隨著幾何資料的大量增加，需要的容量常常遠大於單機電腦的容量，如何使用一個大型的中央儲存伺服器，讓用戶端從伺服器獲取資料來實現視覺化變得非常必要。而在這種分散式的場景瀏覽系統中，網路頻寬常常是一個效能上的瓶頸，在有限的頻寬及有限的快取記憶體容量之下，即時的選擇有用物件的方法，是件很重要的事情。為了解決前述的問題，我們試著從架構的場景瀏覽系統中打造了一個智慧型的搜尋方式，它可以幫助用戶端即時取得在虛擬場景中有用的模型物件。我們的方法主要是利用具有優先權的搜尋機制，給予每一個包含在搜尋範圍中的物件一個優先權的值。但有好幾個不同範圍及單位的因素會影響優先權值的設定，需要一個方法把這些因素轉換成優先權的參數。在其中我們考慮物件與使用者間的狀態，包含了空間性和時間性的資料，並且用高斯函數來調動這些參數，高斯函數可以調整不同參數的權重值到我們預期的範圍內。用戶因此可以根據物件優先權的順序來正確地取得要顯示的物件。我們的方法同樣可以整合在場景瀏覽系統上作為預先讀取的方法，利用裝置工作的空檔去下載或預先讀取用戶未來可能看到的幾何資料，讓視覺上的接續效果達到最大化。實驗的結果表示我們的方法在提升視覺效果上有很好的表現。

In most walkthrough systems, geometry data are stored on the local device. In such cases, the research usually aims at object culling for real-time rendering. However, with the increasing size of geometry dataset, the storage requirement far exceeds the capacity of a single local machine. It is becoming necessary to employ a large-scale centralized storage server for real-time support of several clients during visualization. Nevertheless, in such a distributed walkthrough system, network transmission is often the performance bottleneck. Therefore, methodology to select most significantly demanded objects under the limited bandwidth and limited cache size constraints is important. For solving the aforementioned problem, we develop an intelligent searching method for a client-server based walkthrough system, which helps clients in time to get the needed geometry objects in the virtual environment. Our work focuses on using a prioritized searching method to assign a priority value to each object within the search range. But there are several factors which have different measurement units that can influence the priority. It needs a scheme to convert those factors into the prioritized parameters. We consider the correlation of user state and object state, including their spatial and temporal information, to dynamically adjust the prioritized parameters of a Gaussian function. Gaussian function can convert the factor values of different parameters to the range we expected. Client therefore can get the display objects according to their prioritized order. Our method can also be integrated into a useful prefetching approach to a walkthrough system, to maximize the effectiveness of visualization, which utilizes device idle time to download or prefetch geometry data that the user might view in the near future. When applied the new developed search method to our walkthrough testbed, experimental results show a good performance increase during the visualization.

CHAPTER 1 INTRODUCTION 1
1.1 RESEARCH MOTIVATION AND OBJECTIVE 1
1.2 RESEARCH CONTRIBUTION 2
CHAPTER 2 RELATED WORK 7
2.1 WALKTHROUGH SYSTEM 7
2.2 CLIENT-SERVER ARCHITECTURE 13
2.3 SPATIAL DATA 13
2.4 GAUSSIAN 15
CHAPTER 3 SYSTEM ARCHITECTURE 16
3.1 SYSTEM OVERVIEW 16
3.2 PREPROCESSING UNIT 17
3.3 SERVER 23
3.4 CLIENT 25
3.4.1 Java3D 27
3.4.2 Scene Graph 28
3.5 CLIENT-SERVER INTERACTION 29
CHAPTER 4 METHODOLOGY 32
4.1 PRIORITIZED RANGE SEARCHING 32
4.1.1 Range Searching 35
4.1.2 Prioritized Parameters 36
4.2 PRIORITIZED FORMULA 38
4.3 PRIORITIZED USING GAUSSIAN 40
4.4 CLIENT CACHING METHOD 45
CHAPTER 5 EXPERIMENTS AND ANALYSIS 48
5.1 PERFORMANCE METRIC 48
5.2 EXPERIMENTAL ENVIRONMENT 51
5.3 EVALUATION OF CLIENT CACHE MANAGEMENT 57
5.3.1 Comparison using Different Cache Policies 57
5.3.2 Comparison using Different Radii and Cache Sizes 59
5.3.3 Comparing Different Object Numbers 62
5.4 EVALUATION OF DIFFERENT PRIORITIZED PARAMETERS ON SERVER 63
5.5 SUMMARY 65
CHAPTER 6 CONCLUSION AND FUTURE WORK 68
REFERENCES 71

[1] D. Cohen-Or, Y.L. Chrysanthou, C.T. Silva, F. Durand, "A survey of visibility for walkthrough applications," IEEE Transactions of Visualization and Computer Graphics, vol. 9, pp. 412-431, 2003.
[2] U. Assarsson and T. Moller, "Optimized view frustum culling algorithms for bounding box," Journal of Graphics Tools, vol. 5, pp. 9–22, 2000.
[3] J. H. Clark, "Hierarchical geometric models for visible surface algorithms," Communications of the ACM, vol. 19, pp. 547–554, 1976.
[4] S. Kumar, D. Manocha, W. Garrett, and M. Lin, "Hierarchical back-face computation," Computers and Graphics, vol. 23, pp. 681–692, 1999.
[5] J. Bittner and V. Havran, "Exploiting coherence in hierarchical visibility algorithms," Journal of Visualization and Computer Animation, vol. 12, pp. 277–286, 2001.
[6] B. Garlick, D. Baum, and J. Winget, "Parallel algorithms and architectures for 3D image generation," ACM SIGGRAPH, 1990.
[7] M. Slater and Y. Chrysanthoum, "View volume culling using a probabilistic caching scheme," In VRST''97: Proceedings of the ACM Symposium on Virtual Reality Software and Technology, ACM Press, 1997.
[8] R. Yagel and W. Ray, "Visibility computations for efficient walkthrough of complex environments," PreJ- ence, vol. 5, pp. 1–16, 1996.
[9] J. Airey, J. Rohlf, and F. Brooks, "Towards image realism with interactive update rates in complex virtual building environments," In Symposium on Interactive 3D Graphics, pp. 41–50, 1990.
[10] S.J. Teller, Visibility Computations in Densely Occluded Polyheral Environments, PhD thesis, CS Division, UC Berkeley, 1992.
[11] S. Coorg and S. Teller, "Real-time occlusion culling for models with large occluders," Proceedings of symposium on Interactive 3D graphics, pp. 83-90, 1997.
[12] T. Hudson, D. Manocha, J. Cohen, M. Lin, K. Hoff, and H. Zhang, "Accelerated occlusion culling using shadow frusta," In Proc. of ACM Symposium on Computational Geometry, pp. 1–10, 1997.
[13] G. Schaufler, J. Dorsey, X. Decoret, and F. Sillion, "Conservative visibility preprocessing using extended projections," Proceedings of Computer Graphics and Interactive Techniques, pp. 229–238, 2000.
[14] P. Wonka, M. Wimmer, and D. Schmalstieg, "Visibility preprocessing with occluder fusion for urban walkthroughs," Technical Report TR-186-2-00-06, Institute of Computer Graphics, pp. 71–82, 2000.
[15] J. Airey, Increasing Update Rates in the Building Walkthrough System with Automatic Model-Space Subdivision and Potentially Visible Set Calculations, PhD thesis, University of North Carolina, Chappel Hill, 1991.
[16] S.J. Teller and C.H. S