臺灣博碩士論文加值系統

光線追蹤法(Ray Tracing)運用在電腦繪圖(Computer Graphic)中可以產生極為逼真的圖片。但是缺點在於，繪圖的速度慢，運算大，尤其是應用在動態場景(Dynamic Scene)中,本論文研究當場景中的物體變動位置時，如何提升程式執行時的效能。
我們使用Bounding Volume Hierarchies,來提升程式執行的效能。在動態場景中，當程式載入新的場景，則必須重新建造新的Bounding Volume Hierarchies Tree。在過去Ingo Wald[14]曾提出，只要更新BVH-Tree中的Bounding Volume範圍，來節省重建時間，如此一來就可以改善程式執行的時間。但是Ingo Wald只有更新物件移動後的範圍，並沒有考慮到當物體移動範圍過度劇烈時，造成Bounding box和Bounding Box過度重複時的情況。
在本論文中我們則改善了Ingo Wald[14]的方法，使用對結點的部份重建，來更新已經重建過的Bounding Box範圍，以避免Bounding Box過度重複的缺點，並且實驗在單一物體變形，或是多個物體移動的情況下，使用我們的方法，效能都會有5%~45%的改善。

第一章 簡介...............................................1
第二章 相關研究...........................................3
2.1動態變形場景.......................................4
2.2 建構Building Bounding volume hierarchies..........5
2.3 BVH-Tree的追蹤....................................6
2.4 Bounding Volume....................................8
2.4.1 Axis-Aligned Bounding Boxes...................9
2.4.2球形的Bounding Box ..........................10
第三章 在動態變形場景中使用BVH...........................11
3.1 建構效能好的BVH-Tree .............................11
3.2在動態場景中建構BVH-Tree..........................17
3.3 動態更新Bounding Volume範圍......................18
3.4 BVH的部份重建.....................................20
3.4.1 Bounding Volume的過度重疊....................21
3.4.2對BVH-Tree的節點做部份重建..................23
3.4.3 對BVH-Tree部分重建所需的時間分析............29
第四章 實驗結果..........................................33
第五章 結論與未來展望....................................44
參考文獻.................................................46

[1]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.
[2]Glassner, A. S., “An Overview of Ray Tracing”, An Introduction to Ray Tracing, A.S. Glassner ed., Academic Press, pp.1-31, 1989.
[3]Goldsmith, J., and J. Salmon, “Automatic creation of object hierarchies for ray tracing”, IEEE CG&A 7, 5, 14.20, 1987
[4]Ottschalk S., Lin M., and Manocha D., “OBB- Tree A Hierarchical Structure for Rapid Interference Detection”, Proc. Of ACM Siggraph’96, 171-180, 2, 1996.
[5]Guibas, L., Nguyen A., and Zhang L., “Collision Detection for Deforming Necklaces”, In Symp. on Computational Geometry, pp. 33-42, 3, 2002.
[6]Humphreys, G., and Rui, W., “Ray Tracing Acceleration Techniques”, University of Virginia, 2003.
[7]Havran, V., Heuristic Ray Shooting Algorithms. PhD thesis, Faculty of Electrical Engineering, Czech Technical University in Prague, 2001.
[8]Herman, J., Haverkort, “Introduction to bounding volume hierarchies.”, Results on Geometric Networks and Data Structures. Ph.D. thesis, Utrecht University, Chapter 1, 2004.
[9]John, A., Andrew, W., “A Fast Voxel Traversal Algorithm for Ray Tracing”, Dept. of Computer Science University of Toronto, Ontario, Canada M5S 1A4, 1987.
[10]Kirill, A., Dmitriev, “Efficiency issues on Ray Tracing Machine”, Keldysh Institute of Applied Mathematics RAS. Moscow, Russia, 2000.
[11]Macdonald, J. D., and Booth, K. S., Heuristics for ray tracing using space subdivision, In Proceedings of Graphics Interface, 152.63, 1989.
[12]Runbin, S., and Whitted, T., “A 3D Representation for Fast Rendering of Comples Scenes”, Proceedings of SIGGRAPH. 110-116, 1980.
[13]Wald, I., Thiago, I., Andrew, K., Aaron, K., Steven, G. Parker, “Ray Tracing Animated Scenes using Coherent Grid Traversal”, SCI Institute, University of Utah, 2006.
[14]Wald, I., Boulos, S., and Shirley, P., “Ray Tracing Deformable Scenes Using Dynamic Bounding Volume Hierarchies”, Technical Report, SCI Institute, University of Utah, No UUSCI-2005-014, ACM Transactions on Graphics, 2006.
[15]Whitted, T., “An improved illumination model for shaded display”, Communication of ACM, vol. 23, no. 6, pp. 343-349, 1980.