不規則三角網格之視域計算與應用

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：139

、訪客IP：18.224.37.68

姓名

鄭松賓(Sung-Pin Cheng) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

不規則三角網格之視域計算與應用
(Visibility Computation and Applications on Triangulated Irregular Networks)

相關論文

★ 適用於大面積及場景轉換的視訊錯誤隱藏法	★ 虛擬觸覺系統中的力回饋修正與展現
★ 多頻譜衛星影像融合與紅外線影像合成	★ 腹腔鏡膽囊切除手術模擬系統
★ 飛行模擬系統中的動態載入式多重解析度地形模塑	★ 以凌波為基礎的多重解析度地形模塑與貼圖
★ 多重解析度光流分析與深度計算	★ 體積守恆的變形模塑應用於腹腔鏡手術模擬
★ 互動式多重解析度模型編輯技術	★ 以小波轉換為基礎的多重解析度邊線追蹤技術(Wavelet-based multiresolution edge tracking for edge detection)
★ 基於二次式誤差及屬性準則的多重解析度模塑	★ 以整數小波轉換及灰色理論為基礎的漸進式影像壓縮
★ 建立在動態載入多重解析度地形模塑的戰術模擬	★ 以多階分割的空間關係做人臉偵測與特徵擷取
★ 以小波轉換為基礎的影像浮水印與壓縮	★ 外觀守恆及視點相關的多重解析度模塑

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

由於地理資訊系統的廣泛與普及化運用，各種不同的計算與分析需求亦不斷地產生。對於地理資訊系統使用者而言，可以依照本身的需求，選擇適合的計算與分析方法以取得所需資訊是很重要的；例如，許多地理資訊系統相關的應用需要視域計算，諸如手機基地台之最大涵蓋範圍地點分析、瞭望台之最佳視野範圍地點分析、軍隊行軍撤退之最隱蔽路線等。
本研究是針對視域計算技術進行研究與實作。我們提出一個以不規格三角網格地形為基礎的視域計算演算法；這個演算法使用了特定的範圍角度來縮小處理範圍並使用射線測試函式減少投影計算量以提高執行效率。此演算法讓使用者可以更方便、更有效率的對地形執行視域計算；並提供視域計算做地理資訊系統的相關應用。

摘要(英)

Several important applications of geographic information systems (GIS) require visibility computation, such as, the line-of-sight communication, the optimal placement of a radial tower or a watchtower, finding the path with certain visibility properties (scenic or hidden paths) and so on. Thus, a better visibility computation algorithm makes the applications more efficient. The goal of our research is to study the visibility computation technique and implement the algorithm for several related applications.
In this study, we proposed an improved visibility computation algorithm which is based on the triangulated irregular networks. We use intersection test module instead of the general projection method to achieve the same results; moreover, we use specific angles to narrow the test range to improve performance. By the proposed methods, we can reduce the computation of the algorithm to obtain better performance.
The proposed algorithm is roughly divided into three parts: the spatial analyst, radial sort, and visibility computation. First, the spatial analyst performs the neighborhood and zone analysis for visibility computation. Second, the radial sort step decides the processing sequence. Finally, the visibility computation step calculates the visibility information.
The visibility information obtained form our visibility computation algorithm can conform to the properties of line-of-sight. Therefore, the visibility information can solve the line-of-sight computation problems on TINs for lots of applications.

關鍵字(中)

★ 視域分析
★ 視域計算

關鍵字(英)

★ visibility computation
★ viewshed

論文目次

Abstract ii
Contents iii
List of Figures vi
Chapter 1 Introduction 1
1.1 Motivation 1
1.2 Overview of this study 1
1.2.1 Visibility concepts and definitions 2
1.2.2 Classification of visibility problems 2
1.2.3 Visibility algorithm 2
1.2.4 Applications for visibility computation 3
1.3 Thesis organization 3
Chapter 2 Related Works 4
2.1 Visibility computation on terrain 4
2.1.1 Visibility computation on RSG 4
2.1.2 Visibility computation on hierarchical terrain models 5
2.2 Watershed 6
2.3 Hidden surface removal 7
2.4 Visibility preserving terrain simplification 10
Chapter 3 Preliminary 12
3.1 Terrain models 12
3.1.1 Digital elevation models 12
3.1.2 Digital terrain models 12
3.1.3 RSGs and TINs 13
3.2 Visibility on terrain 14
3.3 Visibility problems 20
3.3.1 Point visibility problem 20
3.3.2 Line visibility problem 21
3.3.3 Region visibility problem 21
Chapter 4 Visibility Algorithm on Triangulated Irregular Networks 22
4.1 Visibility algorithm on RSG 22
4.2 Visibility algorithm on TIN 23
4.3 Radial sort 24
4.4 Visibility computation 31
4.4.1 Determine the projected relevant horizons of triangle t 34
4.4.2 Update the horizons list and determine the visible portion of t 40
4.4.3 Pseudocode of the visibility algorithm on TIN 47
4.5 Intersection test between linear components and triangle 48
Chapter 5 Experiments and Applications 53
5.1 Experiments 53
5.1.1 Radial sort 53
5.1.2 Visibility computation 55
5.2 Applications 60
5.2.1 Single-viewpoint application 60
5.2.2 Multi-viewpoint application 61
5.2.3 Path-finding application 63
Chapter 6 Conclusion 67
References 68

參考文獻

[1]Berg, M., D. Halperin, M. Overmars, J. Snoeyink, and M. van Kreveld, "Efficient ray shooting and hidden surface removal," in Proc. 7th Ann. ACM Symposium on Computational Geometry, New York, 1991, pp.21-30.
[2]Bertrand, G., "On topological watersheds," Journal of Mathematical Imaging and Vision, vol.22, issue.2-3, pp.217-230, 2005.
[3]Cazzanti M., L. D. Floriani, G. Nagy, E. Puppo, "Visibility computation on a triangulated terrain," in Progress in Image Analysis and Processing II, Singapore, 1992, pp.721-728.
[4]Chazelle, B. and L. J. Guibas, "Fractional cascading: I. A data structuring technique, " Algorithmica, vol.1, pp.133-162, 1986.
[5]Cole, R. and M. Sharir, "Visibility problems for polyhedral terrains," Journal of Symbolic Computation, vol.7, no.1, pp.11-30, 1989.
[6]Couprie, M., L. Najman, and G. Bertrand, "Quasi-linear algorithms for the topological watershed," Journal of Mathematical Imaging and Vision, vol.22, issue.2-3, pp.231-249, May 2005.
[7]D'evai, F., "Quadratic bounds for hidden-line elimination," in Proc. 2nd ACM Symposium on Computational Geometry, New York, 1986, pp.269-275.
[8]Eberly, H. D., 3D Game Engine Architecture: Engineering Real-Time Applications with Wild Magic, Morgan Kaufmann, Jan. 2005.
[9]Edelsbrunner, H., L. J. Guibas, and M. Sharir, "The upper envelope of piecewise linear functions: algorithms and applications," Discrete and Computational Geometry, vol.4, pp.311-336, 1989.
[10]Fisher, P. F., "Algorithm and implementation uncertainty in viewshed analysis," Int. Journal of Geographical Information Systems, vol.7, pp.331-347, 1993.
[11]Fisher, P. F., "An exploration of probable viewsheds in landscape planning," Environment and Planning B: Planning and Design, vol.22, no.4, pp.527-546, 1995.
[12]Fisher, P. F., "Extending the applicability of viewsheds in landscape planning," Photogrametric Engineering & Remote Sensing, vol.62, no.11, pp.1297-1302, 1996.
[13]Fisher, P. F., "Reconsideration of the viewshed function in terrain modeling," Geographical Systems, vol.3, no.1, pp.33-58, 1996.
[14]Floriani, L. D., "A pyramidal data structure for triangle-based surface description," IEEE Computer Graphics and Applications, vol.9, pp.67-78, 1989.
[15]Floriani, L. D., D. M. Jung, and G. Nagy, Efficient Hidden Surface Computation on Triangulated Terrains, R. P. I. Computational Geometry Laboratory, TR# 89-1103, Nov. 1989.
[16]Floriani, L. D., B. Falcidieno, G. Nagy, and C. Pienovi, "On sorting triangles in a Delaunay tessellation," Algorithmica, vol.6, pp.522-532, 1991.
[17]Floriani, L. D., E. Puppo, and G. Nagy, "Computing a line-of-sight network on a terrain model," in Proc. 5th Int. Symp. Spatial Data Handling," Charleston, 1992, pp.672-681.
[18]Floriani, D. L., and E. Puppo, "A hierarchical triangle-based model for terrain description, " in Proc. of the Int. Conf. GIS - From Space to Territory: Theories and Methods of Spatio-Temporal Reasoning on Theories and Methods of Spatio-Temporal Reasoning in Geographic Space, London UK, 1992, pp.236-251.
[19]Floriani, D. L., C. Montani, and R. Scopigno, "Parallelizing visibility computations on triangulated terrains," International Journal of Geographical Information Systems, vol.8, pp.515-531, 1994.
[20]Floriani, D. L. and P. Magillo, "Visibility algorithm on triangulated digital terrain models," International Journal of Geographic Information Systems, vol.8, no.1, pp.13-41, 1994.
[21]Floriani, D. L. and P. Magillo, "Computing the visibility map on a hierarchical triangle-based terrain Model," in Proc. ACM Symp. on Applied Computing, Phoenix, 1994, pp.279-296.
[22]Floriani, D. L. and P. Magillo, "Horizon computation on a hierarchical triangulated terrain model," The Visual Computer, vol.11, no.3, pp.134-149, 1995.
[23]Floriani, D. L. and P. Magillo, "Algorithms for visibility computation on terrains: a survey," Environment and Planning B - Planning and Design, vol.30, no.5, pp.709-728, 2003.
[24]Foley J. D., A. van Dam, S. K. Feiner and J. F. Hughes, Computer Graphics: Principles and Practice. Second Edition in C, Addison Wesley, 1997.
[25]Franklin, W. R. and M. S. Kankanhalli, "Parallel object-space hidden surface removal," ACM Computer Graphics, vol.24, no.4, pp.87-94, 1990.
[26]Guting, R. H. and T. Ottmann, "New algorithms for special cases of the hidden line elimination problem," in Proc. on STACS 85 2nd Annual Symp. on Theoretical Aspects of Computer Science, New York, 1987, pp.188-204.
[27]James, A. and A. M. Day, "The hidden face determination tree," Computers and Graphics, vol.23, no.3, pp.377-387, 1999.
[28]Jung, D.M., Comparison of Algorithms for Terrain Visibility, Master Thesis, Rensselaer Polytechnic Institute, Troy, New York, Aug. 1989.
[29]Ketan, M., "Hidden surface removal with respect to a moving view point," in Proc. of the Twenty Third Annual ACM Symp. on Theory of Computing, New Orleans, May 1991, pp.512-522.
[30]Lee, J., "Analysis of visibility sites on topographic surfaces," International Journal of Geographic Information Systems, vol.5, no.4, pp.413-425, 1991.
[31]Lee, J., and D. Stucky, "On applying viewshed analysis for determining least-cost paths on digital elevation models," Int. Journal of Geographic Information Systems, vol.12, pp.891-905, 1998.
[32]McKenna, M., "Worst-case optimal hidden-surface removal," ACM Trans. on Graphics, vol.6, issue 1, pp.19-28, 1987.
[33]Michael, M., "A watershed algorithm for triangulated terrains," in Proc. of the 11th Canadian Conf. on Computational Geometry, Aug. 16, 1999, pp.24-35.
[34]Moshe, B. B., J. Mitchell, M. Katz, Y. Nir, "Visibility preserving terrain simplification: an experimental study," in Proc. Annual Symp. on Computational Geometry, Barcelona, Spain, June, 2002, pp.303-311.
[35]Mulmuley, K., "An efficient algorithm for hidden surface removal," in Proc. of the 16th annual conf. on Computer graphics and interactive techniques, New York, 1989, pp.379-388.
[36]Nagy, G., "Terrain visibility", Computers & Graphics, vol.18, no.6, pp.763-773, Nov.-Dec., 1994.
[37]Overmars, M. H. and M. Sharir, "Output-sensitive hidden surface removal," in Proc. of 30th Annual Symp. on Foundations of Computer Science, Oct. 1989, pp.598-603.
[38]Preparata, F.P., and M.I. Shamos, Computational Geometry: An Introduction, Springer-Verlag, New York, 1985.
[39]Reif, J. and S. Sen, "An efficient output-sensitive hidden surface removal algorithm and its parallelization," in Proc. of The Fourth Annual Symp. on Computational Geometry, Illinois, United States, 1988, pp.193-200.
[40]Schmitt, A., "Time and space bounds for hidden line and hidden surface algorithms," in Proc. Eurographics’8, North Holland, 1981, pp.43-56.
[41]Shapira, A., Visibility and Terrain Labeling, Master's Thesis, ECSE Department, Rensselaer Polytechnic Institute, Troy, New York 1990.
[42]Sutherland, I E., R F. Sproul, and Schumaker, "A characterization of ten hidden-surface algorithms," ACM Computing Surveys, vol.6, issue 1, pp.1-55, March 1974.
[43]Weiler, K. and P. Atherton, "Hidden surface removal using polygon area sorting," in Proc. of the 4th Annual Conf. on Computer Graphics and Interactive Techniques, San Jose, CA, 1977, pp.214-222.

指導教授

曾定章(Din-Chang Tseng)

審核日期

2006-7-19

推文