臺灣博碩士論文加值系統

光線追蹤法是一種經由觀察人眼物理成像方法所衍生出來的一種繪圖技巧，也因為基於物理原理，每一個像素的顏色都是經過物體本身的顏色累加光源、反射及折射而來，最後所得到的成像也就極為逼真。但由於每一條光線都需要跟場景中的物體做交點測試，造成描繪整個場景中全部的像素時，需要龐大的時間來運算，尤其是當遇到大型場景時所需要的執行時間更是令人不敢恭維，這也是光線追蹤法讓人詬病之處，為了解決上述所帶來的問題，衍生出了各種的空間分割法，目前KD-tree被公認為在靜態場景中可對光線追蹤法有著最佳的加速效率。

本論文中我們利用鄰近射線的相關性，也就是鄰近射線在找到交點時可能會落在樹中同個葉節點當中或是相隔不遠的葉節點。所以我們利用光束封包中的測試射線先執行完整光線追蹤法，並利用其鄰近射線的相關性找出新的樹根節點，之後再將光束封包中的所有光線從此新的根節點往下搜尋物體，即可以節省射線搜尋整顆KD-tree所需花費的時間，提升光線追蹤法整體執行效率，最後在四個測試場景實驗中得知利用光束封包可減少大量射線需搜尋KD-tree節點的數量，並對整體執行時間有50~64%的加速比率，且對於影像品質保有一定的水準。

第一章 簡介………………………………………………………………………1
第二章 相關研究…………………………………………………………………3
2.1 光線追蹤法 …………………………………………………………3
2.2 KD-Tree …………………………………………………………………………………………………………5
2.3 光束封包……………………………………………………………7
2.4 二維方格加速法……………………………………………………10
第三章 我們的方法 ……………………………………………………………12
3.1 最大包圍節點………………………………………………………13
3.2 紀錄路徑……………………………………………………………15
3.3 預先排除……………………………………………………………16
3.4 相同節點……………………………………………………………19
3.5 搜尋最大包圍節點…………………………………………………23
3.6 背景成像加速………………………………………………………25
3.7 加速陰影射線………………………………………………………28
第四章 實驗結果與討論………………………………………………………30
4.1 實驗環境……………………………………………………………30
4.2 實驗場景……………………………………………………………31
4.2.1 場景一…………………………………………33
4.2.2 場景二…………………………………………37
4.2.3 場景三…………………………………………41
4.2.4 場景四…………………………………………45
4.3 實驗結果……………………………………………………………32
4.4 錯誤評估……………………………………………………………49
4.5 討論…………………………………………………………………53
第五章 結論與未來展望………………………………………………………75
參考文獻…………………………………………………………………………77

[1]C. Benthin, “Realtime Ray Tracing on Current CPU Architectures,” PhD thesis, Computer Graphics Group, Saarland University, 2006.
[2]J. Bentley, “Multidimensional Binary Search Trees Used for Associative Searching,” Communications of the ACM 18, pp. 509–517, 1975.
[3]G. Bergen, “Efficient Collision Detection of Complex Deformable Models Using aabb Trees,” Journal of Graphics Tools, 2(4):1–14, 1997.
[4]R. L. Cook, T. Porter and L. Carpenter, “Distributed Ray Tracing,” Computer Graphics (SIGGRAPH ’84 Proceedings), vol. 18, pp. 137–45, 1984.
[5]K. Dmitriev, V. Havran and H. P. Seidel, “Faster Ray Tracing with SIMD Shaft Culling,” Research Report, Max-Planck Institut Für Informatik, MPI–I–2004–4–006, 2004.
[6]C. Fowler, S. Collins and M. Manzke, “Accelerated Entry Point Search Algorithm for Real Time Ray Tracing,” ACM Spring Conference on Computer Graphics, 2009.
[7]H. Fuchs, Z. M. Kedem and B. F. Naylor, “On Visible Surface Generation by A Priori Tree Structures,” SIGGRAPH Computer Graphics 14, pp. 124–133, 1980.
[8]A. S. Glassner, “Space Subdivision for Fast Ray Tracing,” IEEE Computer Graphics and Applications 28, vol. 4, no. 10, pp 15-22, 1984
[9]A. S. Glassner, “ An Introduction to Ray Tracing,” Academic Press Ltd., London, UK, 1989.
[10]M. Hapala and V. Havran, “ Review:Kd-tree Traversal Algorithms for Ray Tracing,” Computer Grapgics Forum Volume 30, no. 1, pp. 199–213, 2011.
[11]V. Havran, “Heuristic Ray Shooting Algorithms,” PhD thesis, Faculty of Electrical Engineering, Czech Technical University in Prague, 2001.
[12]V. Havran and J. Bittner, “LCTS:Ray Shooting Using Longest Common Traversal Sequences,” Computer Graphics Forum 19, pp. 59–70, 2000.
[13]M. Kaplan, "The Use of Spatial Coherence in Ray Tracing," ACM SIGGRAPH’85 Course Notes 11, pp. 22–26, July 1985.
[14]J. D. Macdonald and K. S. Booth, “Heuristics for Ray Tracing Using Space Subdivision,” Visual Computer 6, pp. 153–165, 1990.
[15]R. Overbeck, R. Ramamoorthi and W. R. Mark, “Large Ray Packets for Real-time Whitted Ray Tracing,” IEEE Symposium on Interactive Ray Tracing, 2008.
[16]A. Reshetov, “Omnidirectional Ray Tracing Traversal Algorithm for KD-trees,” Proceedings of the IEEE Symposium on Interactive Ray Tracing, pp. 57–60, 2006.
[17]A. Reshetov, “Faster Ray Packets Triangle Intersection Through Vertex Culling,” ACM SIGGRAPH 2007 posters, USA, 2007.
[18]A. Reshetov, A. Soupikov and J. Hurley, “Multi Level Ray Tracing Algorithm,” ACM SIGGRAPH 2005 Papers, USA, pp. 1176–1185, 2005.
[19]S. T. Thakkar and T. Huff, “Internet Streaming SIMD Extensions,” Computer 32, pp. 26–34, 1999.
[20]I. Wald, C. Benthin, M. Wagner and P. Slusallek, “Interactive Rendering with Coherent Ray Tracing,” Computer Graphics Forum, pp. 153–164, 2001.
[21]I. Wald, C. P. Gribble, S. Boulos and A. Kensler, “SIMD Ray Stream Tracing SIMD Ray Traversal with Generalized Ray Packets and On-the-fly Re-Ordering,” Technical Report UUSCI-2007-012, 2007.
[22]I. Wald, T. Ize, A. Kensler, A. Knoll and S. G. Parker, “Ray Tracing Animated Scenes Using Coherent Grid Traversal,” ACM SIGGRAPH 2006 Papers, New York, USA, pp. 485–493, 2006.
[23]T. Whitted, “An Improved Illumination Model for Shaded Display,” Communication of ACM, vol. 23, no. 6, pp. 343-349, 1980.
[24]M. Zwaan, E. Reinhard and F. W. Jansen, “Pyramid Clipping for Efficient Ray Traversal,” University of Bristol, Bristol, UK, 1995.
[25]洪啟豪, “動態場景下用二維方格建立在光線追蹤法加速的研究,” 天主教輔仁大學資訊工程所碩士論文, 2007.
[26]連國珍, “數位圖像處理,” 儒林書局,台北,2001.
[27]楊琬婷, “在動態場景中使用混合型節點之BVH結構於光線追蹤法的研究,” 天主教輔仁大學資訊工程所碩士論文, 2008.