臺灣博碩士論文加值系統

光跡追蹤法是一項可以產生擬真三維電腦繪圖效果的著色演算法。和目前廣泛地被硬體繪圖管線所採用的傳統掃瞄轉換著色法（rasterized rendering）相比，光跡追蹤法無疑能夠模擬更為真實之全域光影效果，然而龐大的計算複雜度也是其不可避免的代價。在這篇論文裡，我們結合了掃瞄轉換著色法和光跡追蹤法兩者之優點，實作了一個建構於繪圖處理單元（Graphics Processing Unit, GPU）上之光跡追蹤系統。我們首先利用配備深度緩衝區之硬體描畫（rasterization）來快速地決定原光跡追蹤法中「主要光線」所打中之物體並進行著色，接著再尋訪我們所採用的加速結構—邊界體階層樹（Bounding Volume Hierarchy, BVH）來追蹤陰影光及反射光等「次要光線」，藉以產生全域光影效果。此外，我們還使用了一些GPGPU（General-Purpose Computation on GPUs）上的技術，例如：Conditional Counting和Early-Z Culling，來提升繪圖處理單元之使用率。最後我們的實驗結果亦指出，繪圖處理單元在光跡追蹤法這樣的高度平行式應用程式上面，確實是除了CPU之外一個相當具有競爭性的處理平台。

Ray tracing is a rendering technique for producing realistic 3D computer graphics. Compared to traditional rasterized rendering which is generally adopted by graphics pipeline, ray tracing can simulate more realistic global illumination, however, with the cost of expensive computation. In this thesis work, we implement a GPU-based ray tracer that combines advantages of both rendering schemes: efficiency of rasterized rendering and reality of ray tracing. We first use hardware-accelerated rasterization with Z-buffer to quickly determine the first ray-triangle hit of eye rays. Secondary rays such as reflective and shadow rays are then traced to produce global illumination with a bounding volume hierarchy (BVH) which plays the role of our acceleration structure. Furthermore, we employ some GPGPU techniques such as conditional counting and early-z culling to help better utilize the GPU. The experiments show that the GPU is a competitive computational platform for ray tracing.

INTRODUCTION 1
1.1 MOTIVATION 1
1.2 OBJECTIVES 3
1.3 SIGNIFICANCE OF THE WORK 3

BACKGROUND AND RELATED WORK 6
2.1 INTRODUCTION TO RAY TRACING 6
2.2 ACCELERATION STRUCTURE 8
2.2.1 Uniform Grid 9
2.2.2 Bounding Volume Hierarchy 10
2.2.3 KD-Tree 12
2.2.4 Hybrid Structures 14
2.3 PACKET TRACING 15

TECHNIQUES IN GPU PROGRAMMING 17
3.1 PROGRAMMABLE GRAPHICS HARDWARE 17
3.1.1 Programmable Pipeline 17
3.1.2 Vertex Processor 18
3.1.3 Fragment Processor 19
3.2 HIGH-LEVEL SHADING LANGUAGES 20
3.3 GENERAL-PURPOSE COMPUTATION ON GPUS 21
3.3.1 Framebuffer Object 22
3.3.2 Ping-Pong 23
3.3.3 Multiple Rendering Targets 23
3.3.4 Conditional Counting 24
3.3.5 Early-Z Culling 25

APPROACH 28
4.1 SYSTEM OVERVIEW 28
4.2 OFFLINE PRECOMPUTATION 30
4.2.1 Acceleration Structure Creation 31
4.2.2 BVH Encapsulation on Textures 33
4.3 GPU KERNELS 34
4.3.1 Rasterization 34
4.3.2 Shading 36
4.3.3 Shadow 37
4.3.4 Reflection 38
4.3.5 Accumulation 39
4.3.6 Counting 39
4.4 MULTI-PASS REFLECTION 41
4.4.1 Criteria for Termination 41
4.4.2 Ray Update 42

EXPERIMENTS AND ANALYSIS 44
5.1 EXPERIMENTAL SETUP 44
5.2 BVH CONSTRUCTION 46
5.3 EARLY-Z CULLING 48
5.4 MULTI-PASS REFLECTION 50
5.5 CORRECTNESS OF REFLECTION 54
5.6 CPU VS. GPU 55

CONCLUSIONS AND FUTURE WORK 57

BIBLIOGRAPHY 59

[1]Wald, I., Purcell, T. J., Schmittler, J., Benthin, C., and Slusallek, P. Realtime ray tracing and its use for interactive global illumination. In Proceedings of the Eurographics, State of the Art Reports, 2003.
[2]Woop, S., Schmittler, Jörg., and Slusallek, P. RPU: a programmable ray processing unit for realtime ray tracing. ACM Transactions on Graphics, 24, 3, 2005, 434-444.
[3]Benthin, C., Wald, I., Scherbaum, M., and Friedrich, H. Ray tracing on the CELL processor. In Proceedings of the 2006 IEEE Symposium on Interactive Ray Tracing, 2006, 115-124.
[4]Wald, I., Benthin, C., and Slusallek, P. Distributed interactive ray tracing of dynamic scenes. In Proceedings of the IEEE Symposium on Parallel and Large-Data Visualization and Graphics (PVG), 2003.
[5]Cg. http://developer.nvidia.com/page/cg_main.html.
[6]Rost, R. J. OpenGL Shading Language, Second Edition. Addison Wesley, 2006.
[7]OpenGL Shading Language. http://www.opengl.org/documentation/glsl/.
[8]High Level Shading Language. http://en.wikipedia.org/wiki/HLSL.
[9]General-Purpose Computation Using Graphics Hardware. http://www.gpgpu.org/.
[10]Owens, J. D., Luebke, D., Govindaraju, N., Harris, M., Krüger, J., Lefohn A. E., and Purcell, T. J. A survey of general-purpose computation on graphics hardware. In Proceedings of the Eurographics 2005, State of the Art Reports, August 2005, 21-51.
[11]Whitted, T. An improved illumination model for shaded display. Communications of the ACM, 23, 6 (June 1980), 343-349.
[12]Purcell, T. J., Buck, I., Mark, W. R., and Hanrahan, P. Ray tracing on programmable graphics hardware. ACM Transactions on Graphics, 21, 3 (July 2002), 703-712.
[13]Christen, M. Ray Tracing on GPU. Master’s Thesis, University of Applied Sciences Basel (FHBB), 2005.
[14]Thrane, N. and Simonsen, L. O. A Comparison of Acceleration Structures for GPU Assisted Ray Tracing. Master’s Thesis, University of Aarhus, Denmark, 2005.
[15]Carr, N. A., Hoberock, J., Crane, K., and Hart, J. C. Fast GPU ray tracing of dynamic meshes using geometry images. In Proceedings of the Graphics Interface, 2006, 203-209.
[16]Havran, V., Prikryl, J., and Purgathofer, W. Statistical comparison of ray-shooting efficiency schemes. Tech. Rep. TR-186-2-00-14, Institute of Computer Graphics, Vienna University of Technology.
[17]Foley, T. and Sugerman, J. Kd-tree acceleration structures for a GPU raytracer. In Proceedings of the Graphics Hardware, 2005, 15-22.
[18]Horn, D., Sugerman, J., Houston, M., and Hanrahan, P. Interactive k-D tree GPU raytracing. In Proceedings of the ACM Symposium on Interactive 3D Graphics and Games (I3D’07), 2007.
[19]Müller, G. and Fellner, D. W. Hybrid scene structuring with application to ray tracing. In Proceedings of the International Conference on Visual Computing (ICVC’99), Goa, India, February 1999, 19-26.
[20]Wächter, C., and Keller, A. Instant Ray Tracing: The bounding interval hierarchy. In Proceedings of the 17th Eurographics Symposium on Rendering, 2006.
[21]Streaming SIMD Extensions.
http://en.wikipedia.org/wiki/Streaming_SIMD_Extensions.
[22]Wald, I., Ize, T., Kensler, A., Knoll, A., and Parker, S. G. Ray tracing animated scenes using coherent grid Traversal. ACM Transactions on Graphics, 25, 3 (July 2006), 485-493.
[23]Boulos, S., Edwards, D., Lacewell, J. D., Kniss, J., Kautz, J., Wald, I., and Shirley, P. Packet-based Whitted and distribution ray tracing. In Proceedings of Graphics Interface, 2007.
[24]Reshetov, A., Soupikov, A., Hurley, J. Multi-level ray tracing algorithm. ACM Transactions on Graphics, 24, 3 (July 2005), 1176-1185.
[25]The renderman interface specification.
https://renderman.pixar.com/products/rispec/index.htm.
[26]NVIDIA GeForce 8800 product site.
http:// www.nvidia.com/page/geforce_8800.html.
[27]Frame Buffer Object specification. http://oss.sgi.com/projects/ogl-sample/registry/EXT/framebuffer object.txt.
[28]Occlusion Query specification.
http://oss.sgi.com/projects/ogl-sample/registry/ARB/occlusion_query.txt.
[29]Mitchell, J. L. and Sander, P. V. Applications of explicit early-Z culling. In SIGGRAPH 2004 - Real-Time Shading Course Applications of Explicit, 2004.
[30]Goldsmith, J. and Salmon, J. Automatic creation of object hierarchies for ray tracing. IEEE Computer Graphics and Applications, 7, 5, May 1987, 14-20.
[31]Kay, T. L. and Kajiya, J. T. Ray tracing complex scenes. In Proceedings of the SIGGRAPH, 1986, 269-278.
[32]Mahovsky, J. Ray tracing bounding volume hierarchies with the Pluecker-AABB test. Technical report 2004-759-24, University of Calgary, April 2005.
[33]Wald, I., Boulos, S., and Shirley, P. Ray tracing deformable scenes using dynamic bounding volume hierarchies. ACM Transactions on Graphics, 26, 1, 2007.
[34]Weghorst, H., Hooper, G., and Greenberg, D. Improved computational methods for ray tracing. ACM Transactions on Graphics, 3, 1 (January 1984), 52-69.
[35]Carr, N. A., Hall, J. D., and Hart, J. C. The ray engine. In Proceedings of the Graphics Hardware 2002, September 2002, 37-46.
[36]Möller, T. and Trumbore, B. Fast, minimum storage ray-triangle intersection. Journal of Graphics Tools, 2, 1 (1997), 21-28.
[37]ATI Radeon X1950 Technology – GPU Specifications.
http://ati.amd.com/products/RadeonX1950/specs.html.
[38]Blythe, D. The Direct3D 10 system. ACM Transactions on Graphics, 25, 3 (July 2006), 724-734.