(18.204.227.34) 您好!臺灣時間:2021/05/14 09:58
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

: 
twitterline
研究生:許正佑
研究生(外文):Hsu, Chengyu
論文名稱:使用KD-Tree於光線追蹤法中一個降低交點測試時間的有效方法
論文名稱(外文):An Efficient Algorithm for Reducing Intersection Tests on KD Trees for Ray Tracing
指導教授:鄭進和
指導教授(外文):Cheng, Chinho
口試委員:鍾斌賢林聰武郭文彥
口試日期:2011-07-28
學位類別:碩士
校院名稱:輔仁大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2011
畢業學年度:99
語文別:中文
論文頁數:78
中文關鍵詞:KD-tree光線追蹤法交點測試
外文關鍵詞:KD-treeRay TracingIntersection
相關次數:
  • 被引用被引用:1
  • 點閱點閱:409
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:28
  • 收藏至我的研究室書目清單書目收藏:0
KD-tree近年來被認為是光線追蹤法加速最快的資料結構。但我們實際計算較複雜的場景所做的交點測試次數,發現即使用KD-tree,仍會有98%以上的交點測試,都會是沒有被射線交到的。我們希望能快速排除掉一定不會被射線交到的物體,來避免不必要的物體交點測試,進而提升光線追蹤法的效率。
因為KD-tree是BSP-tree的特例,每次都是根據與軸垂直的切割面,遞迴式的分割左半和右半空間,最後到葉節點也會是一個Axis Aligned Bounding Box(AABB),而場景內的物體也會各自被包成AABB,對應在葉節點內。過去一般射線搜尋到葉節點後,都是直接把葉節點內的所有物體直接做交點測試。但根據我們實驗,發現仍有進步的空間。因此,在本論文中,我們提出了利用射線交到葉節點,一定會有射線的進入位置及離開位置,我們將這兩個位置又形成一個AABB,與這AABB沒有交集的物體則直接排除,不做交點測試。最後,我們實際測試了四個場景,平均可以快速的減少80~90%以上的物體交點測試次數,而我們檢查的時間,平均只有物體交點測試時間的30~40%以下,最後結果顯示光線追蹤法的效率甚至能達到2倍以上。
附表目錄 IV
附圖目錄 VI
第一章 簡介 1
第二章 相關研究 3
2.1 光線追蹤法 3
2.2 KD-tree的建立 5
2.3 KD-tree的搜尋 9
第三章 研究方法 16
3.1 三角面交點測試 16
3.2 AABB交點測試 20
3.3 檢查射線形成的AABB與包圍物體的AABB交集 25
3.4 修正數值誤差 29
第四章 實驗結果與討論 32
4.1 實驗環境 32
4.2 實驗結果 33
4.2.1 場景一 37
4.2.2 場景二 45
4.2.3 場景三 53
4.2.4 場景四 61
4.3 討論與分析 69
第五章 結論與未來展望 75
參考文獻 77
T. Foley and J. Sugerman, "KD-Tree Acceleration Structures for a GPU Raytracer," Proceeding HWWS '05 Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, 2005.
M. Hapala and V. Havran, "Review: Kd-tree Traversal Algorithms for Ray Tracing," Computer Graphics Forum, Vol.30, No. 1, pp.199-213, 2011.
V. Havran, "Heuristic Ray Shooting Algorithms," PhD thesis, Faculty of Electrical Engineering, Czech Technical University in Prague, 2001.
V. Havran and J. Bittner, "On Improving KD-Trees for Ray Shooting," Proceedings of WSCG 2002 Conference, Vol. 5, pp. 209-217, 2002.
V. Havran, T. Kopal, J. Bittner, J. Z ̌a ́ra, "Fast robust BSP tree traversal algorithm for ray tracing," Journal of Graphics Tools, Vol. 2, No. 4, pp. 15-23, 1997.
J. Hurley, A. Kapustin, A. Reshetov and A. Soupikov, "Fast Ray Tracing for Modern General Purpose CPU," Proceedings of Graphicon, 2002.
M. Kaplan, "The Use of Spatial Coherence in Ray Tracing," ACM SIGGRAPH'85 Course Notes 11, pp. 22–26, July 1985.
P. Shirley, M. Ashikhmin, M. Gleicher, S. R. Marschner, E. Reinhard, K. Sung, W. B. Thompson and P. Willemsen, "Miscellaneous Math," Fundamentals of Computer Graphics, 2th ed. Wellesley: A K Perter, pp. 46-47, 2005.

B. Smits, "Efficiency issues for ray tracing," Journal of Graphics Tools, Vol. 3, No. 2, pp. 1-14, 1998.
K. Sung and P. Shirley, "Ray Tracing with BSP Tree," Graphics Gem III, pp. 271-274, 1992.
I. Wald and V. Havran, "On building fast kd-Trees for Ray Tracing, and on doing that in O(N log N)," in 2006 IEEE Symposium Interactive Ray Tracing, pp. 61-69, 2006.
T. Whitted, "An improved illumination model for shaded display," Communication of ACM, Vol. 23, No. 6, pp. 343-349, June 1980.
A. Williams, S. Barrus, R. K. Morley, P. Shirley, "An Efficient and Robust Ray–Box Intersection Algorithm," Journal of Graphics Tools, Vol. 10, pp. 54, 2003.
林正偉, "動態場景中用BVH部分重建來加速光線追蹤法的研究," 天主教輔仁大學資訊工程所碩士論文, 2008.
陳世偉, "動態場景下二維方格建立在光線追蹤法加速的改進," 天主教輔仁大學資訊工程所碩士論文, 2008.
陳彥羽, "利用光束封包對光線追蹤法的研究," 天主教輔仁大學資訊工程所碩士論文, 2007.
楊琬婷, "在動態場景中使用混合型節點之BVH結構於光線追蹤法的研究," 天主教輔仁大學資訊工程所碩士論文, 2008.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔