臺灣博碩士論文加值系統

KD-tree常使用在靜態繪圖中，因為靜態的場景中資料結構變動不大，效能堪稱最佳，我們簡化測試光線的運算數量，使用光束封包來進行光線追蹤，以光強度取代顏色作為判斷的依據，使用陰影最大包圍節點來減少尋訪的路徑與運算，在部分運算中使用SSE來改寫，整體的效能比原始的光線追蹤方式有顯著的提升。

第一章 簡介 1
第二章 相關研究 3
2.1 用光束封包進行光線追蹤法 3
2.1.1 光線追蹤 3
2.1.2 光束封包 6
2.2 使用SSE 做部分運算加速 7
2.3 AABB包圍體 9
2.4 KD-TREE 使用最大包圍節點尋訪 16
第三章 我們的方法 20
3.1 以光強度作為最終判斷 20
3.2 陰影的最大包圍節點選用 23
3.3 使用SSE運算 24
3.3.1 以SSE執行正規化 26
3.3.2 以SSE執行Color中的加法、減法與乘法 29
3.3.3 以SSE取得光線/三角形交點的法向量 30
3.3.4 以SSE取得光線在在物體上的交點 31
3.3.5 以SSE尋找最大包圍節點 31
3.3.6 以SSE檢查光線/ AABB交點 32
3.3.7 以SSE計算進入點與離開點 34
第四章 實驗結果與討論 35
4.1 實驗環境 35
4.2 實驗場景 36
4.2.1 場景一：Chess＋Box 38
4.2.2 場景二：Teapot＋Box 40
4.2.3 場景三：Bunny＋Box 42
4.2.4 場景四：Dragon＋Box 44
4.3 討論 46
第五章 結論與未來展望 48
參考文獻 50

[1]A. Appel, “Some techniques for shading machine renderings of solids.” AFIPS Conference Proc. 32, pp.37-45, 1968.
[2]T. Whitted, “An improved illumination model for shaded display.” Proceedings of the 6th annual conference on Computer graphics and interactive techniques, 1979.
[3]B.T. Phong, "Illumination for computer generated pictures." Communications of ACM, No. 6, 311–317.1975.
[4]邱弘偉，「改進KD-tree搜尋法以加速光束封包光線追蹤法」，天主教輔仁大學資訊工程所碩士論文，2011。
[5]B. Tóth, “Speed optimized Recursive Ray-tracer with KD-tree and SSE vector mathematics.“ Budapest University of Technology and Economics, 2004.
[6]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.
[7]S. Boulos, D. Edwards, J. D. Lacewell, J. Kniss, J. Kautz, P. Shirley, and I. Wald, "Packet-based Whitted and Distribution Ray Tracing." In Proc. Graphics Interface, May 2007.
[8]I. Wald, S. Woop, C. Benthin, G. S. Johnson, and M. Ernst, ”Embree： A Kernel Framework for Efficient CPU Ray Tracing.” Journal ACM Transactions on Graphics（TOG） TOG Homepage, Volume 33, Issue 4, July 2014.
[9]Attila T. Áfra, "Improving BVH Ray Tracing Speed Using the AVX Instruction Set." Eurographics（Posters）, 2011.
[10]Hotball, Available：https：//www.csie.ntu.edu.tw/~r89004/hive/index.html
[11]JA. Tsakok, ”Fast Ray Tracing Techniques.” MS thesis. University of Waterloo, 2008.
[12]B. Smits, "Efficiency issues for ray tracing." Journal of Graphics Tools, Vol. 3, No. 2, pp. 1-14, 1998.
[13]T. L. Kay and J. T. Kajiya. "Ray tracing complex scenes." In SIGGRAPH’86: Proceedings of the 13th annual conference on Computer graphics and interactive techniques, pages 269–278, New York, NY, USA, 1986, ACM Press.
[14]A. Williams, S. Barrus, R. K. Morley, and P. Shirley: "An Efficient and Robust Ray-Box Intersection Algorithm." Journal of graphics tools, 10（1）:49-54, 2005.
[15]許正佑，「使用KD-tree於光線追蹤法中一個降低交點測試時間的有效方法」，天主教輔仁大學資訊工程所碩士論文，2011。
[16]ANN: A Library for Approximate Nearest Neighbor Searching, Available：http://www.cs.umd.edu/~mount/ANN/
[17]C. Benthin, “Realtime Ray Tracing on Current CPU Architectures.” PhD thesis, Computer Graphics Group, Saarland University, 2006.
[18]J. Bentley, “Multidimensional Binary Search Trees Used for Associative Searching.” Communications of the ACM, 18, pp. 509–517, 1975.
[19]R. Overbeck, R. Ramamoorthi, and W. R. Mark, “Large Ray Packets for Real-time Whitted Ray Tracing.” IEEE Symposium on Interactive Ray Tracing, 2008.
[20]S. T. Thakkar and T. Huff, “Internet Streaming SIMD Extensions.” Computer 32, pp. 26–34, 1999.
[21]I. Wald, C. Benthin, M. Wagner and P. Slusallek, “Interactive Rendering with Coherent Ray Tracing.” Computer Graphics Forum, pp. 153–164, 2001.
[22]Kevin Suffern, “Ray Tracing from the Ground Up.” A K Peters, Ltd, 2007.
[23]S. Omohundro. “Efficient algorithms with neural network behavior.” Complex Systems, 1：273, 1987.
[24]詹曜駿，「動態光束封包的成像加速法」，天主教輔仁大學資訊工程所碩士論文，2015。
[25]H. Dammertz1, J. Hanika1, and A. Keller.”Shallow Bounding Volume Hierarchies for Fast SIMD Ray Tracing of Incoherent Rays.”In Proceedings of the 19th Eurographics Conference on Rendering, 1225–1234. 2008.
[26]I. Wald, P. Slusallek, C. Benthin, and M.Wagner,” Interactive rendering with coherent ray tracing.” Computer Graphics Forum 20, 3, 153--164. 2001.
[27]I. Wald, S. Boulos, and P. Shirley,“Ray tracing deformable scenes using dynamic bounding volume hierarchies.”ACM Transactions on Graphics （TOG）, v.26 n.1, p.6-es, January.2007.
[28]G. Chatzianastasiou, and G.A. Constantinides, "An Efficient FPGA-based Axis-Aligned Box Tool for Embedded Computer Graphics." International Conference on Field Programmable Logic and Applications (FPL). IEEE, 2018.
[29]G.E. Moore, "Cramming more components onto integrated circuits.",1965.