跳到主要內容

臺灣博碩士論文加值系統

(44.211.117.197) 您好!臺灣時間:2024/05/27 06:18
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:游昇機
研究生(外文):Sheng-Chi Yu
論文名稱:於光跡追蹤法中改良區塊航行演算法之研究
論文名稱(外文):A Study on Improved Grid Traversal Algorithm for Ray Tracing
指導教授:鍾斌賢鍾斌賢引用關係林聰武林聰武引用關係
指導教授(外文):Bin-Shyan JongTwlin
學位類別:碩士
校院名稱:中原大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2001
畢業學年度:89
語文別:中文
論文頁數:72
中文關鍵詞:空間切割3D DDA光跡追蹤法DDA區塊航行階層式架構
外文關鍵詞:DDAhierarchical structuresgrid traversalray tracing3D DDAspatial subdivision
相關次數:
  • 被引用被引用:0
  • 點閱點閱:148
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在加速光跡追蹤法的方式中,以空間切割法的使用最為常見,而空間切割法主要又可區分為兩類:一致性與非一致性的空間切割。在一致性空間切割法中,由於整個場景空間被切割成大小一致的區塊,因此可以使用3D DDA的方式來加速光射線與物體的交點測試。
早期在光跡追蹤法上,用來加速光射線航行的3D DDA方式是延伸自平面上的DDA畫線方法,因此在本論文中將從平面上DDA的畫線方式進行研究探討,接著再從現有的3D DDA方法進行探討,最後結合研究後的結果,提出一個改良型的區塊航行法,並將此方法與現有的3D DDA方式進行比較。
另外由於高密度的一致性空間切割法會佔用相當大的記憶體使用量,因此發展出使用階層式架構的方式來減少記憶體的使用量。針對這方面,本論文也將提出一個簡化型的階層式架構,並配合所提出的改良型區塊航行法,運用在高密度的一致性空間切割環境中,以提升光射線的航行速度,並減少記憶體的使用量。
因此,在本論文中除了提出一個改良型的區塊航行法之外,同時並提出一個搭配此改良型航行法之簡化型階層式架構,以期提升光跡追蹤法的效能與品質。

The spatial subdivision is the most popular method to accelerate ray tracing. The subdivision strategies can separate into two schemes, uniform and non-uniform spatial subdivision. In uniform spatial subdivision, the scenes space divided into many regular grids, so it can use 3D DDA to accelerate ray and object intersection testing.
First, in the ray tracing, the 3D DDA that used to accelerate ray traversing is extended from DDA that draw line in the plane. In this paper, we will study on the vary methods of DDA and 3D DDA, and analysis the result of these studies, then introduce a improved grid traversal method. This method will compare with existing 3D DDA method.
In addition, because the highly resolution uniform spatial subdivision have used large memory consumption. So the hierarchical structures were developed to reduce memory consumption. In this aspect, we will also introduce a simply hierarchical structure and collocate our improved grid traversal method to speed up ray traversing and reduce memory consumption in this highly resolution spatial subdivision environment.
In this paper, besides introducing a improved grid traversal method, we also introduce a simply hierarchical structure that collocate our grid traversal method. We will use these methods to improve the ray tracing quality and efficiency.

第一章 緒論
1.1 簡介
1.2 研究動機
1.3 大綱概述
第二章 DDA演算法之相關研究
2.1 傳統DDA畫線演算法
2.2 雙步式(Double-Step)畫線演算法
2.3 區段重複(Segments repeated)的方法
2.4 N步式(N-Step)畫線演算法
2.5 DDA與其他改進方法之分析與比較
第三章 DDDA演算法之相關研究
3.1 3D DDA演算法之一
3.2 3D DDA演算法之二
3.3 3D DDA演算法之分析與比較
3.4 3D DDA在高密度空間切割上的使用
3.4.1 快速穿越空區域的方式
第四章 改良區塊航行演算法
4.1 改良型區塊航行法
4.2 改良型航行法之推導說明
4.3 改良區塊航行之演算法
4.4 兩層式階層架構(Two-Layer Hierarchies)
第五章 實驗結果與討論
5.1 改良型區塊航行演算法之實驗結果
5.2 兩層式階層架構之實驗結果
5.3 實驗結果的分析與比較
第六章 結論與未來展望
6.1 結論
6.2 未來展望
參考文獻

參考文獻[1]J. Amantides, A. Woo. "A fast voxel traversal alogrithm for ray tracing", Eurographics '87, pp.3-10, 1987.[2]J. Arvo and D. Kirk, "A survey of ray tracing acceleration techniques", An Introduction to Ray Tracing, A.S. Glassner ed., Academic Press, pp.201-262, 1989.[3]E. Angel and D. Morrison, "Short Note : Speeding Up Bresenham’s Algorithm", IEEE Computer Graphics and Application, vol. 11 no. 6, pp. 16-17, 1991.[4]J. G. Cleary and G. Wyvill, "Analysis of an algorithm for fast ray tracing using uniform space subdivision", The Visual Computer, vol. 4, pp. 65-83, 1988.[5]D. Cohen, "Voxel Traversal along a 3D Line", Graphics Gems IV, P. S. Heckbert ed, Morgan Kaufmann published, pp. 366-369, 1994.[6]D. Cohen and Z. Sheffer, "Proximity Clouds — An Acceleration Technique for 3D Grid Traversal", The Visual Computer, vol. 10, no. 1, pp. 27-38, 1994.[7]F. Cazals, C. Puech, "Bucket-like space patitioning data structure with application to ray-tracing", 13th ACM Symopsium on Computational Geometry, pp.11-20, 1997.[8]D. Cohen, A. Kaufman. ŗD line voxelization and connectivity control ", IEEE Computer Graphics and Applications , vol. 17 , no. 6 , pp. 80-87 , Nov.-Dec. 1997[9]J. D. Foley and A. Van Dam, Fundamentals of Interactive Computer Graphics, Chap. 11, pp.431-445, Addison-Wesley, Reading, Mass., 1982.[10]J. D. Foley, A. Van Dam, S. K. Feiner, J. F. Hughes, R. L. Phillips, Introduction to Computer Graphics, Chap. 3, Sect. 2, pp.71-79, Addison-Wesley , Reading, Mass., 1994.[11]A. Fujimoto, T. Tanaka, and K. Iwata, "ARTS: Accelerated ray tracing system", IEEE Computer Graphics and Applications, vol. 6, no. 4, pp. 16-26, 1986.[12]Cindy M. Goral, Kenneth E. Torrance, Donald P. Greenberg and Bennett Battaile, "Modeling the Interaction of Light Between Diffuse Surfaces", ACM Computer Graphics (SIGGRAPH proceedings), 18(3):213-222, 1984[13]A. S. Glassner, "An Overview of Ray Tracing", An Introduction to Ray Tracing, A.S. Glassner ed., Academic Press, pp.1-31, 1989.[14]Graeme W. Gill, "n-step Incremental Straight-Line Algorithms", IEEE Computer Graphics and Applications, vol. 14, no. 3, pp.66-72, 1994[15]D. Jevens and B. Wyvill, "Adaptive voxel subdivision for ray tracing", Proceedings of Graphics Interface '89, pp. 164-172, 1989.[16]P.K. Hsiung and R. Thibadeau, "Accelerating ARTS", The visual computer, vol. 8, pp. 181-190, 1992.[17]K. S. Klimaszewski and T. W. Sederberg, "Faster Ray Tracing Using adaptive Grids", IEEE Computer Graphics and Application, vol. 12, no. 2, pp. 42-51, 1997[18]B. T. Phong, "Illumination for computer generated images", Communication of ACM, vol. 18, no. 6, pp. 311-317, 1975. [19]J. G. Rokne, B. Wyvill, and X. Wu, "Fast Line Scan-Conversion", ACM Trans. Graphics, vol. 9, no. 4, pp. 376-388, 1990[20]F. V. Reeth, P. Monsieurs, P. Bekaert, and E. Flerackers, "Ray tracing Optimization Utilizing Projective Methods", Proceedings of Computer Graphics International 1996, pp. 47-53, 1996.[21]M. Slater, "Tracing a ray through uniformly subdivides n-dimensional space", The Visual Computer, vol. 9, pp. 39-46, 1992.[22]N. Stolte and R. Caubet, "Discrete Ray-Tracing of Huge Voxel Spaces", Eurographics ’95 proceedings, pp. 383-394, 1995.[23]T. Whitted, "An improved illumination model for shaded display", Communication of ACM, vol. 23, no. 6, pp. 343-349, 1980.[24]X. Wu, and J. G. Rokne, "Double-Step Incremental Generation of Lines and Circles", CVGIP, vol. 37, pp. 331-344, 1987.[25]R. Yagel, D. Cohen, and A. Kaufman, "Discrete ray tracing", IEEE Computer Graphics and Application, vol. 12, no. 5, pp. 19-28, 1992.[26]沈維哲, "A Study on Accelerate Ray Tracing by a Tabular Navigation",碩士學位論文,中原大學資訊工程研究所, 1995

電子全文 電子全文(本篇電子全文限研究生所屬學校校內系統及IP範圍內開放)
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top