臺灣博碩士論文加值系統

光線追蹤法(Ray Tracing)[14]最為人詬病的就是顯像的速度太慢，原因在於需要大量計算光線與場景中3D物件的交叉點測試(intersection test)[7]，因此各種光線追蹤的加速架構演算法蓬勃發展，一般使用空間切割法(space subdivision)[5]來對光線與場景中3D物件的交叉點測試做加速，一致性的空間切割法也就是將場景切割成相同大小的立方塊(Grid)[10]，然後再做光線的追蹤，如此可以針對每一個相同區塊與光線做交點測試，因為以相同大小的區塊來做交叉點測試會比多邊形做交叉點測試來的快。
本篇論文以二維一致性的空間切割法與光束封包對光線追蹤法的加速[20]做改進的研究，實驗結果二維方格的封包光束光線追蹤法加入三維立方塊的追蹤(traversal)方式可以加快許多速度，且固定大小的方格也不比變動的方格來的慢，除此之外以PSNR(Peak Signal to Noise Ratio)值[22,23]與MSE(Mean-Square Error)值[22,23]來比較影像的品質也比較好。

第一章 緒論 5
1-1簡介 5
第二章 相關文獻探討 8
2-1光線追蹤演算法 9
2-2光線追蹤加速法 12
2-3空間切割法 13
2-4利用光束封包對光線追蹤法的研究 17
2-5 二維方格加速法 20
第三章 實驗方法 30
3-1 場景 30
3-2光束封包的改進 31
3-3光束封包block大小的影響 35
第四章 實驗結果 38
4-1實驗環境 38
4-2實驗結果 39
第五章 結論與未來工作 48
參考文獻 49

[1]AMANATIDES, J., AND WOO, A., A Fast Voxel Traversal Algorithm for Ray Tracing. In Eurographics ’87. Eurographics Association, 3–10, 1987.
[2]GINO VAN DEN BERGEN. Efficient Collision Detection of Complex Deformable Models using AABB Trees, Journal of Graphics Tools JGT, 1997.
[3]BENTHIN C., WALD I., AND SLUSALLEK P., A Scalable Approach to Interactive Global Illumination. Computer Graphics Forum 22 (3), 621-630, 2003.
[4]FOLEY T., AND SUGERMAN J., KD-tree acceleration sturctures for a GPU raytracer. In Proceeding of HWWS, 15-22, 2005.
[5]GLASSNER A., Space Subdivision for Fast Ray Tracing IEEE Computer Graphics 28, 1984.
[6]GORAL C., TORRANCE K. E., GREENBERG D. P. AND BATTAILE B., Modelling the interaction of light between diffuse surfaces. Computer Graphics, 18 (3), 212-22, 1984.
[7]HUBBARD P. M., Interactive collision detection, Proceedings of IEEE Symposium on Research Forntiers in Virtual Reality (October 1993).
[8]Kajiya J. T., The rendering equation. Proc. SIGGRAPH ’86 Course Notes, San Francisco CA, July. 1986.
[9]Kirill A. Dmitriev, Efficiency issues on Ray Tracing Machine, Keldysh Institute of Applied Mathematics RAS. Moscow, Russia, 2000.
[10]KLIMASZEWSKI, K. S., AND SEDERBERG, T. W, Faster ray tracing using adaptive grids. IEEE CG&A 17 (1) (Jan./Feb.), 42–51. Tech. Rep. 06-010, Department of Computer Science, University of North Carolina at Chapel Hill, 1997.
[11]LAUTERBACH C., YOON S. –E, TUFT D., MANOCHA D RT-DEFORM, Interactive Ray Tracing of Dynamic Scenes using BVHs. Tech. Rep. TR-06-010, Univ. of North Carolina at Chapel Hill, 2006.
[12]A. Reshetov, A. Soupikov, and J. Hurley, Multi-Level Ray Tracing Algorithm. ACM Transaction of Graphics, 24(3):1176-1185, 2005.
[13]Alexander D. Ryer, “The Inverse Square Law”, The Light Measurement Handbook, 1997.
[14]ALAN WATT ,3D Computer Graphics Third Edition, Addison Wesley, ISBN:0-201-39855-9, 2000.
[15]Whitted J. T., A scan line algorithm for the computer display of curved surfaces. Proc. 5th Conf. on Computer Graphics and Interactive Techniques, Atlanta GA, p. 26, 1978.
[16]INGO W., SOLOMON B., AND PETER S., Ray tracing deformable scenes using dynamic bounding volume hierarchies. ACM Transactions on Graphics, 2006.
[17]INGO WALD, Realtime Ray Tracing and Interactive Global Illumination, PhD thesis, Computer Graphics Group, Saarland University, 2004.
[18]INGO W., THIAGO I., ANDREW K., AARON K., AND STEVEN G., Ray Tracing Animated Scenes using Coherent Grid Traversal, 2006.
[19]INGO WALD, SIGGRAPH Course #4, 2006.
[20]洪啟豪，2D Grid Based Acceleration Methods For Ray Tracing in Dynamic Scenes，輔仁大學資訊工程系碩士論文，2006.
[21]陳彥羽，光束封包對光線追蹤的研究，輔仁大學資訊工程系碩士論文，2007.
[22]陳同孝、張真誠、黃國峰著，“電子影像技術，”松崗電腦圖書資料股份有限公司，p251~266，Dec.2000.
[23]陳同孝、張真誠及黃國峰，“數位影像處理技術”，松崗圖書股份有限公司，January 2001.
[24]Jacco Bikker, “Interactive Ray Tracing”, http://www.intel.com/cd/ids/developer/asmo-na/eng/dc/threading/245711.htm?page=1.