臺灣博碩士論文加值系統

光線追跡是一種簡單卻又極具威力的三維繪圖技術。它利用模擬真實光線行進的方式來描繪出極具真實的畫面，但隨之而來的卻是計算上的高複雜度，也因此無法達到即時的需求。近幾年來，隨著硬體運算能力及演算法的進步，許多軟體實現的光線追跡器以大幅提升其效能到接近即時的程度。但是仍然只有極少數硬體實現的光線追跡器被提出。其原因主要是在於傳統的光線追跡管線的演算法並不利於硬體上的設計。本論文提出一個新的光線追跡演算法。它的特點是相對傳統的演算法而言能夠大量減少晶片內記憶體的使用，卻又能保持相似的效能。
同時，根據此演算法，我們也提出相對應的硬體架構。在此架構裡，我們還使用了多種硬體架構設計的方法來提升其硬體使用率，包括多執行緒、摺疊等，使其能在有限的硬體資源下達到最高的效能。在外部記憶體頻寬方面，運用位元長度分析和頂點分享的技術來減少頻寬。
我們也按照標準單元設計流程實作原形晶片。該晶片利用台積電130 nm技術製程，面積為1。697 X 1。7mm^2。其處理能力為每秒43億浮點數指令運算。

Ray tracing is a simple yet powerful and general algorithm for accurately computing
global light transport and rendering high quality images. While recent algorithmic improvements
and optimized parallel software implementations have increased ray tracing
performance to interactive levels, few efficient hardware solution has been available due
to hardware unfriendly of traditional ray tracing algorithm. This thesis proposes a more
hardware friendly ray tracing algorithm and describes the architecture based on this algorithm.
We also implement a first prototype chip around the world for ray tracing
with standard cell based design flow. By the proposed algorithm, on-chip sram usage of
my design is reduced dramatically compared to previous architectures while it retains
a similar computation amounts. We also use multi-threading and folding technique to
increase the hardware utilization and achieve maximum performance at minimum hardware
resource. The external bandwidth is low enough to duplicate many the same units
to process in parallel, which is achieved by a tiny cache with word length analysis and
vertex sharing technique. The prototype chip is fabricated by TSMC 0.13 μm technology.
The chip size is 1.697×1.7mm2. It is capable of 4.3 giga floating point operations
per-second.
vii

Abstract vii
1 Introduction 1
1.1 Why is Ray Tracing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 What is Ray Tracing . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 Ray Generation . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.2 Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.3 Intersection . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.4 Shading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 PreviousWorks 7
2.1 Algorithm Progress in Interactive Ray Tracing . . . . . . . . . . . . . 7
2.2 Parallel Platform for Ray Tracing . . . . . . . . . . . . . . . . . . . . . 8
3 Algorithm Development 9
3.1 Traversal Algorithm Overview . . . . . . . . . . . . . . . . . . . . . . 9
3.1.1 Uniform Grids . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.1.2 KD-tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.1.3 BVH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Bounding Volume Hierarchy Algorithm In Ray Tracing . . . . . . . . . 12
3.2.1 Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.2.2 AABB Intersection Test . . . . . . . . . . . . . . . . . . . . . 14
3.3 New Traversal Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.3.1 First Hit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
i
ii
3.3.2 Frustum Culling . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.3.3 Change The Ray Order When Both Tests Are Fail . . . . . . . . 19
3.3.4 Node Stack Elimination . . . . . . . . . . . . . . . . . . . . . 19
3.3.5 Record First Active Ray . . . . . . . . . . . . . . . . . . . . . 20
3.3.6 Traversal at Leaf . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.4 Experimental Results and Comparison . . . . . . . . . . . . . . . . . . 22
3.5 Ray-Triangle Intersection . . . . . . . . . . . . . . . . . . . . . . . . 26
3.5.1 Algorithm Adoption . . . . . . . . . . . . . . . . . . . . . . . 26
3.5.2 Fast, Minimum Storage Ray Triangle Intersection . . . . . . . . 27
4 Architecture Design of Ray Tracer 29
4.1 Architecture Overview . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.2 The Ray Casting Unit . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.3 Traversal Unit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.4 Traversal Controller . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.5 Intersection Unit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.6 Ray Buffer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.7 Arbiter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.8 Result Buffer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.9 Cache Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5 Chip Implementation 53
5.1 Design Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.2 Test Consideration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.2.1 Ad-hoc Testing . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.2.2 SRAM BIST . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.3 Chip Layout and Specification . . . . . . . . . . . . . . . . . . . . . . 57
5.4 Experimental Results and Comparison . . . . . . . . . . . . . . . . . . 57
6 Conclusion 63

[1] http://www.nvidia.com/, 2007.
[2] Peter Shirley, Fundamentals of Computer Graphics, 2002.
[3] Vlastimil Havran, “Heuristic ray shooting algorithms.,” PhD thesis, 2000, Department
of Computer Science and Engineering, Czech Technical University in
Prague.
[4] 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, available at http://graphics.cs.unisb.
de/ wald/Publications.
[5] Andreas Dietrich, Ingo Wald, Carsten Benthin, and Philipp Slusallek, “The
OpenRT Application Programming Interface – Towards A Common API for Interactive
Ray Tracing,” in Proceedings of the 2003 OpenSG Symposium, Darmstadt,
Germany, 2003, pp. 23–31, Eurographics Association.
[6] HURLEY J. RESHETOV A., SOUPIKOV A., “Multi-level ray tracing algorithm,”
ACM Transactions on Graphics, pp. 1176–1185, 2005, (Proceedings of ACM
SIGGRAPH 2005).
[7] Ingo Wald, Thiago Ize, Andrew Kensler, Aaron Knoll, and Steven G Parker, “Ray
Tracing Animated Scenes using Coherent Grid Traversal,” ACM Transactions on
Graphics, pp. 485–493, 2006, (Proceedings of ACM SIGGRAPH 2006).
65
66
[8] Ingo Wald, Solomon Boulos, and Peter Shirley, “Ray Tracing Deformable Scenes
using Dynamic Bounding Volume Hierarchies,” ACM Transactions on Graphics,
vol. 26, no. 1, 2007.
[9] Ingo Wald and Vlastimil Havran, “On building fast kd-trees for ray tracing, and
on doing that in O(N log N),” in Proceedings of the 2006 IEEE Symposium on
Interactive Ray Tracing, 2006, pp. 61–69.
[10] Thiago Ize, Ingo Wald, Chelsea Robertson, and Steven G Parker, “An Evaluation
of Parallel Grid Construction for Ray Tracing Dynamic Scenes,” in Proceedings
of the 2006 IEEE Symposium on Interactive Ray Tracing, 2006, pp. 27–55.
[11] David Tuft Dinesh Manocha Christian Lauterbach, Sung-Eui Yoon, “Rt-deform:
Interactive ray tracing of dynamic scenes using bvhs,” in Proceedings of the 2006
IEEE Symposium on Interactive Ray Tracing, 2006.
[12] Stuart A. Green and Derek J. Paddon., “Exploiting coherence for multiprocessor
ray tracing,” IEEE Computer Graphics and Applications, 1989.
[13] Stuart A. Green and Derek J. Paddon., “A highly flexible multiprocessor solution
for ray tracing,” The Visual Computer, 1990.
[14] M. J. Keates and Roger J. Hubbold, “Interactive ray tracing on a virtual sharedmemory
parallel computer,” Computer Graphics Forum, 1995.
[15] N. Jayasena R. Ho W. Dally K. Mai, T. Paaske and M. Horowitz., “Smart memories:
A modular recongurable architecture,” IEEE International Symposium on
Computer Architecture, 2000.
[16] Daniel Reiter Horn, Jeremy Sugerman, Mike Houston, and Pat Hanrahan, “Interactive
k-d tree gpu raytracing,” in Symposium on Interactive 3D Graphics. 2007,
ACM Press New York, NY, USA.
[17] Tim Foley and Jeremy Sugerman, “Kd-tree acceleration structures for a gpu raytracer,”
Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on
Graphics hardware, 2005.
67
[18] Stefan Popov, Johannes G¨unther, Hans-Peter Seidel, and Philipp Slusallek, “Stackless
kd-tree traversal for high performance gpu ray tracing,” Computer Graphics
Forum, vol. 26, no. 3, Sept. 2007, (Proceedings of Eurographics), to appear.
[19] 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.
[20] Jim Knittel Hugh Lauer Hanspeter Pfister, Jan Hardenbergh and Larry Seiler, “The
volumepro real-time ray-casting system,” Computer Graphics, 1999.
[21] MEISSNER M., KANUS U., and STRASSER W., “Vizard ii, a pci-card for realtime
volume rendering,” Proceedings of the ACM SIGGRAPH/EUROGRAPHICS
conference on Graphics hardware, 1998.
[22] D. Hall, “The ar350: Todays ray trace rendering processor,” Proceedings of the
EUROGRAPHICS/SIGGRAPH workshop on Graphics Hardware, 2001, (Hot 3D
Session).
[23] Kentaro Sano Hiroaki Kobayashi, Kenichi Suzuki and Nobuyuki Oba., “Interactive
ray-tracing on the 3dcgiram architecture.,” Proceedings of ACM/IEEE
MICRO-35, 2002.
[24] J. Fender and J. Rose, “A high-speed ray tracing engine built on a fieldprogrammable
system.,” IEEE International Conf. On Field-Programmable Technology,
2003.
[25] Jorg Schmittler, Ingo Wald, and Philipp Slusallek, “Saarcor – a hardware architecture
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.
[26] J¨org Schmittler, Sven Woop, Daniel Wagner, Wolfgang J. Paul, and Philipp
Slusallek, “Realtime Ray Tracing of Dynamic Scenes on an FPGA Chip,” in
Proceedings of Graphics Hardware, 2004, pp. 95–106.
68
[27] J¨org Schmittler Sven Woop and Philipp Slusallek, “Rpu: A programmable ray
processing unit for realtime ray tracing,” in Proceedings of ACM SIGGRAPH
2005 (to appear), July 2005.
[28] SvenWoop, Gerd Marmitt, and Philipp Slusallek, “B-KD Trees for Hardware Accelerated
Ray Tracing of Dynamic Scenes,” in Proceedings of Graphics Hardware,
2006, pp. 67–77.
[29] Erik Brunvand Sven Woop 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.
[30] Amy Williams, Steve Barrus, R. Keith Morley, and Peter Shirley, “An efficient
and robust ray-box intersection algorithm,” journal of graphics tools, vol. 10, no.
1, pp. 49–54, 2005.
[31] P.M. Hubbard., “Interactive collision detection,” Proceedings of IEEE Symposium
on Research Frontiers in Virtual Reality, 1993.
[32] M. Lin Gottschalk and D. Manocha., “Obb-tree: A hierarchical structure for rapid
interference detection.,” Proc. of ACM Siggraph’96, pp. 171–180, 1996.
[33] J.S.B. Mitchell H. Sowizral J. Klosowski, M. Held and K. Zikan., “Efcient collision
detection using bounding volume hierarchies of kdops,” IEEE Trans. on
Visualization and Computer Graphics, vol. 4, no. 1, 1998.
[34] T. KAY and J. KAJIYA, “Ray tracing complex scenes,” Proceedings of SIGGRAPH
1986, 1986.
[35] J. D. MACDONALD and K. S. BOOTH, “Heuristics for ray tracing using space
subdivision,” Proceedingsof Graphics Interface., 1989.
[36] Brian Smits, “Efficiency issues for ray tracing,” Journal of Graphics Tools, 1998.
[37] Ulf Assarsson and Tomas M“oller, “Optimized view frustum culling algorithms
for bounding boxes,” journals of graphics tools, 2000.
[38] J. MAHOVSKY, “Ray tracing with reduced-precision bounding volume hierarchies,”
Ph.D. thesis, University of Calgary, 2005.
69
[39] http://www.daz3d.com/.
[40] http://shape.cs.princeton.edu/search.html.
[41] http://radsite.lbl.gov/mgf/.
[42] Ingo Wald, Realtime Ray Tracing and Interactive Global Illumination, Ph.D.
thesis, Computer Graphics Group, Saarland University, 2004.
[43] TRUMBORE B. MOLLER T., “Fast, minimum storage ray triangle intersection.,”
Journal of Graphics Tools, 1997.
[44] http://www.ati.com/, 2005.
[45] http://www.cadence.com/.
[46] http://www.mentor.com/.
[47] http://www.synopsys.com/.