臺灣博碩士論文加值系統

光線追跡是一個在三維繪圖中藉由計算來生成接近真實圖形的演算法。它的好處是能夠模擬出影子以及反射光、折射光等非直射光所造成的效果。然而這個方法因為要算很多次的光線和三角形的相交測試，故運算量極大。雖然有很多加速的方法可以另用特定的資料結構來加速它，要達到即時運算還是很困難。此外互動式的應用在三維繪圖中亦是不可或缺。如果要實現這個應用，場景在畫每一張圖的時候都有可能會變動，而造成事先建好的資料結構要跟著改變。為了解決這個問題，資料結構在每一次場景動作就要重建或更新。尤於重建的時間過長，我們選擇以更新的方式來支援動態場景。為了使畫出來的圖形更真實，我們選用懷式光線的方法來產生反射光和折射光。並把這些光分成很多個光束一次來追跡這些光束。這樣可以減少光源在追跡資料結構的步數。對於資料結構更新的方法，我們則選用重新適合和節點插入這兩種方法。

為了加速上述提到的運算，我們做了一個硬體加速器來加速它，首先此硬體可以來做出畫圖，找出光線和三角形的交點並算出顏色，產生新的光線。另外對於動態場景的支援，這個硬體可以直接來做重新適合這個方法。而在節點插入的這個模式時，此硬體可以幫忙找出最適合的插入點。整個光線追跡系統是由一顆中央處理器，記憶體，我們特製的硬體加速器和一些周邊元件所組成。對於一個352 x 288的圖片，這個系統每秒可以計算出三到十五張圖的速度並支援動態場景的移動。

Ray tracing is an algorithm for synthesizing a realistic image in 3D computer graph-
ics. The advantage of this algorithm is supporting not only the visibility of scene and
shadow but also indirect lighting effects such as reflection and refraction. However,
the computation complexity of ray tracing is very large due to large number of ray-
primitive intersections especially for rendering the indirect lighting effect. Although
there are many accelerating algorithms using data special structures to accelerate the
tracing process, the real time performance is still hard to achieve. Besides, the inter-
active applications with 3D graphics are popular such as 3D gameing, where the scene
may be changed in every frame. This means that the data structure building time is
also an important issue for real time rendering. Aiming to solve these problems, this
thesis proposes a system architecture which uses ASIC to accelerate ray tracing pro-
cess. Instead of considering the primary rays only, secondary rays are also considered
to render more realistic scenes, which is called as Whitted-style ray tracing. By using
packet-based ray traversal algorithm and frustum culling not only in primary rays but
also in shadow rays and secondary rays, the steps of ray traversing are reduced. Be-
sides, aiming to support interactive applications, the data structure should be changed
dynamically. Instead of rebuilding data structure every frames, we use updating based
algorithms such as refit and insertion to update the data structure of the previous frame.
By using updating based algorithm, the building time of new data structure is short and
the traversing result is correct after the scene changes. In the hardware architecture of
this system, multi-threading is used. Moreover, the computation for finding the inser-
tion positions in insertion algorithm and shading are integrated into a specific unit to
enable hardware sharing. This architecture is System-on-a-chip composed of CPU, our
rendering engine, system memory and other peripherals. For an image in resolution of
352 288, the system can achieve 3–15 frames per second and also support dynamic scenes.

Abstract ix
1 Introduction 1
1.1 Computer Graphic . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Why uses Ray Tracing . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 What is Ray Tracing . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3.1 Ray Tracing Overview . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3.2 Ray Generation . . . . . . . . . . . . . . . . . . . . . . . 5
1.3.3 Traversal . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3.4 Intersection . . . . . . .. . . . . . . . . . . . . . . . 6
1.3.5 Shading . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3.6 Ray Tracing Pipeline . . . . . . . . . . . . . . . . . . . . .. . . . 6
1.4 Different Type of Ray Tracing . . . . . . . . . . . . . . . . . .. . . . . . . 8
1.5 Design Challenge . . . . . . . . . . . . . . . . . . . . . . . . 9
1.6 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . 10
2 PreviousWorks 11
2.1 Platform for Ray Tracing . . . . . . . . . . . . . .. . . . . . . . . . . 11
3 Algorithm Development . . . . . . . . . . . . . . . . .13
3.1 Data Structure Overview . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2 Traversal Algorithm . . . . . . . . . . . . . . . . . . . . . . . 15
3.2.1 Coherence of Rays . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2.2 Frustum Culling . . . . . . . . . . . . . . . . . . . . . . . . .16
3.2.3 Grouping and Frustum Culling for Shadow Ray . . . . . . . . . . . . . . . . . . . . . . . . . . .19
3.2.4 Grouping and Frustum Culling for Reflection and Refraction Ray . . . . . . . . . . . . . . . . . . . . . 22
3.3 Algorithm for Dynamic Scenes . . . . . . . . . . . . . . . . .. . . . . . . . 23
3.3.1 Construction . . . . . . . . . . . . . . . . . . . . . . 25
3.3.2 Refit . . . . . . . . . . . . .. . . . . . . . . . . . . 26
3.3.3 Insertion . . . . . . . . . . . . . .. . . . . . . . . . 29
3.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . 29
4 Architecture Design of Ray Tracer . . . . . . . . . . .35
4.1 Architecture Overview . . . . . . . . . . . . . . . . . . . . . . . . 35
4.2 Ray Tracing Unit Overview . . . . . . . . . . . . . . . . . . . . . . . . 36
4.3 Reflection Ray Generation Unit . . . . . . . . . . . . . . . . . . . . .. . . . . 40
4.4 Refraction Ray Generation Unit . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.5 Ray Normalization Unit . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.6 Frustum Generation Unit . . . . . . . . . . . . . . . . . . . . . . . . . .46
4.7 Refit Unit . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.8 Insert Position Determination and Shading Unit . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.9 BVH cache . . . . . . . . . . . . . . . . . . . . . . . . . .60
5 Chip Implementation . . . . . . . . . . . . . . . . . .63
5.1 Design Flow . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.2 Test Consideration . . . . . . . . . . . . . . . . . . . . . .65
5.2.1 Ad-hoc Testing . . . . . . . . . . . . . . . . . . . . . . . . .66
5.2.2 SRAM BIST . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.3 Chip Layout and Specification . . . . . . . . . . . . . . . . . . . . . .67
5.4 Experimental Results and Comparison . . . . . . . . . . . . . . . . . . . . . . . 67
6 Conclusion . . . . . . . . . . . . . . . . . . . . . . 75
Reference . . . . . . . . . . . . . . . . . . . . . . . .77

[1] Solomon Boulos, Dave Edwards, J Dylan Lacewell, Joe Kniss, Jan Kautz, Peter
Shirley, and Ingo Wald, “Packet-based whitted and distribution ray tracing,” in
Proceedings of Graphics Interface 2007, vol. 234, pp. 177–184.
[2] Samuel R. Buss, 3D Computer Graphics: A Mathematical Introduction with
OpenGL, Cambridge University Press, 2003.
[3] http://www.comphist.org/computing history/new page 6.htm.
[4] http://en.wikipedia.org/wiki/Rasterisation.
[5] Andrew S and Glassner, An Introduction to Ray tracing (The Morgan Kaufmann
Series in Computer Graphics), Morgan Kaufmann, 1989.
[6] Peter Shirley R, Keith Morley, and Keith Morley, Realistic Ray Tracing, AK
Peters, Ltd, 2003.
[7] http://en.wikipedia.org/wiki/GeForce 200 Series.
[8] Matt Pharr and Greg Humphreys, Physically Based Rendering: From Theory to
Implementation, Morgan Kaufmann, 2004.
[9] D Jevans and B Wyvill, “Adaptive voxel subdivision for ray tracing,” in Proceed-
ings of Graphics Interface 1989, 1989.
[10] Turner Whitted, “An improved illumination model for shaded display,” in Com-
munications of the ACM, 1980, pp. 343–349.
[11] Robert L. Cook, Thomas Porter, and Loren Carpenter, “Distributed ray tracing,”
in ACM SIGGRAPH Computer Graphics, 1984, vol. 18, pp. 137–145.
[12] Solomon Boulos, Dave Edwards, J Dylan Lacewell, Joe Kniss, Jan Kautz, Peter
Shirley, and Ingo Wald, “Interactive distribution ray tracing,” in SCI Institute
University of Utah Technical Report, 2006.
[13] Ingo Wald, Carsten Benthin, Markus Wagner, and Philipp Slusallek, “Interactive
rendering with coherent ray tracing,” in Computer Graphics Forum Proceedings
of EUROGRAPHICS 2001, Alan Chalmers and Theresa-Marie Rhyne, Eds. 2001,
vol. 20, Blackwell Publishers, Oxford.
[14] Andreas Dietrich, Ingo Wald, Carsten Benthin, and Philipp Slusallek, “The
openRT application programming interface – towards a common API for inter-
active ray tracing,” in Proceedings of the 2003 OpenSG Symposium, Darmstadt,
Germany, 2003, pp. 23–31, Eurographics Association.
[15] John A. Tsakok, “Faster incoherent rays:multi-BVH ray stream tracing,” in Pro-
ceedings of high performance graphics, 2009.
[16] Carsten Benthin, Ingo Wald, Michael Scherbaum, and Heiko Friedrich, “Ray
tracing on the cell processor,” in Proceedings of IEEE Symposium on Interactive
Ray Tracing 2006, September 2006, pp. 7–14.
[17] Timo Aila and Samuli Laine, “Understanding the efficiency of ray traversal on
gpus,” in Proceedings of high performance graphics, 2009.
[18] Lindholm E., Nickolls J., Oberman S., and Montrym J., “A unified graphics and
computing architecture,” in IEEE Micro, 2008, vol. 28, pp. 39–55.
[19] Jorg Schmittler, Ingo Wald, and Philipp Slusallek, “Saarcor – a hardware archi-
tecture for ray tracing,” in Proceedings of the conference on Graphics Hardware
2002. Saarland University, 2002, pp. 27–36, Eurographics Association, available
at http://www.openrt.de.
[20] J¨org Schmittler, Sven Woop, Daniel Wagner, Wolfgang J. Paul, and Philipp
Slusallek, “Realtime ray tracing of dynamic scenes on an FPGA chip,” in Pro-
ceedings of Graphics Hardware, 2004, pp. 95–106.
[21] Sven Woop, J¨org Schmittler, and Philipp Slusallek, “RPU: A programmable ray
processing unit for realtime ray tracing,” in Proceedings of ACM SIGGRAPH 2005
(to appear), July 2005.
[22] Sven Woop, Gerd Marmitt, and Philipp Slusallek, “B-KD trees for hardware ac-
celerated ray tracing of dynamic scenes,” in Proceedings of Graphics Hardware,
2006, pp. 67–77.
[23] Sven Woop, Erik Brunvand, and Philipp Slusallek, “Estimating performance of a
ray-tracing asic design,” in Proceedings of IEEE Symposium on Interactive Ray
Tracing 2006, September 2006, pp. 7–14.
[24] http://www.apptism.com/apps/itracer.
[25] K.R. Subramanian and Donald S. Fussell, “A search structure based on KD-trees
for efficient ray tracing,” in Technical Report Tx 78712-1188, The University of
Texas at Austin, 1992.
[26] V. Havran and J. Bittner, “Onimproving KD-trees for ray shooting.,” in Journal of
WSCG, 2002, pp. 209–216.
[27] Steven M. Rubin and Turner Whitted, “A three-dimensional representation for fast
rendering of complex scenes,” in Computer Graphics, 1980, vol. 14, pp. 110–116.
[28] Goldsmith J. and Salmon J., “Automatic creation of object hierarchies for ray
tracing,” in Computer Graphics and Applications, IEEE, 1987, vol. 7, pp. 14–20.
[29] P. M. Hubbard., “Interactive collision detection.,” 1993.
[30] Gottschalk, M. Lin, and D. Manocha., “OBB-tree: A hierarchical structure for
rapid interference detection.,” in Proceeding of ACM Siggraph, 1996, pp. 171–
180.
[31] J. Klosowski, M. Held, J.S.B. Mitchell, H. Sowizral, and K. Zikan., “Efficient
collision detection using bounding volume hierarchies of kdops,” in IEEE Trans.
on Visualization and Computer Graphics, 1998, vol. 4.
[32] Amy Williams, Steve Barrus, R. Keith Morley, and Peter Shirley, “An efficient
and robust ray-box intersection algorithm,” 2005, vol. 10, pp. 49–54.
[33] Ulf Assarsson and Tomas M¨oller, “Optimized view frustum culling algorithms for
bounding boxes.,” in journals of graphics tools, 2000, vol. 5, pp. 9–22.
[34] Ingo Wald, Solomon Boulos, and Peter Shirley, “Ray tracing deformable scenes
using dynamic bounding volume heiarchies,” in ACM Transactions on Graphics,
2007, vol. 26.
[35] Erik MXansson, Jacob Munkber, and Tomas Akenine-M¨oller, “Deep coherent ray
tracing.,” in symposium on interactive ray tracing, 2006, pp. 79–85.
[36] Ryan Overbeck, Ravi Ramamoorthi, andWilliam R. Mark, “Large ray packets for
real-time whitted ray tracing,” in Proceedings of the 2008 IEEE Symposium on
Interactive Ray Tracing, 2008.
[37] Macdonald, J. D., and K. S. Booth, “Heuristics for ray tracing using space subdi-
vision,” 1989, pp. 153–166.
[38] Christian Lauterbach, Sung-Eui Yoon, David Tuft, and Dinesh Manocha, “Rt-
deform: Interactive ray tracing of dynamic scenes using BVHs,” in Proceedings
of the 2006 IEEE Symposium on Interactive Ray Tracing, 2006, pp. 39–46.
[39] Jason Lawrence, Szymon Rusinkiewicz, and Ravi Ramamoorthi, “Efficient brdf
importance sampling using a factored representation,” in Proceedings of SIGGRAPH 2004, 2004, vol. 23, pp. 496–505.
[40] http://radsite.lbl.gov/mgf/.
[41] Chen-Haur Chang, Chuan-Yiu Lee, and Shao-Yi Chien, “A 2.88mm2 50m intersections/s ray-triangle intersection unit for interactive ray tracing,” in Pro-
ceedings of the 2008 IEEE Asian Solid-State Interactive Circuits Conference,2008.
[42] Paul S.Heckbert, “Derivation of refraction formulas,” 1989.
[43] Behrooz Parhami, Computer Arithmetic Algorithms and hardware Designs, Oxford University Press, 2000.
[44] James D. Foley, Andries van Dam, Steven K. Feiner, John F. Hughes, and
Richard L. Phillips, Introduction to Computer Graphics.
[45] http://en.wikipedia.org/wiki/Phong shading.
[46] http://www.cadence.com/.
[47] http://www.mentor.com/.
[48] http://www.synopsys.com/.
[49] http://www.syntest.com.tw/.