請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/27850
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 簡韶逸(Shao-Yi Chien) | |
dc.contributor.author | Chuan-Yiu Lee | en |
dc.contributor.author | 李權祐 | zh_TW |
dc.date.accessioned | 2021-06-12T18:24:00Z | - |
dc.date.available | 2008-08-28 | |
dc.date.copyright | 2007-08-28 | |
dc.date.issued | 2007 | |
dc.date.submitted | 2007-08-14 | |
dc.identifier.citation | [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/. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/27850 | - |
dc.description.abstract | 光線追跡是一種簡單卻又極具威力的三維繪圖技術。它利用模擬真實光線行進的方式來描繪出極具真實的畫面,但隨之而來的卻是計算上的高複雜度,也因此無法達到即時的需求。近幾年來,隨著硬體運算能力及演算法的進步,許多軟體實現的光線追跡器以大幅提升其效能到接近即時的程度。但是仍然只有極少數硬體實現的光線追跡器被提出。其原因主要是在於傳統的光線追跡管線的演算法並不利於硬體上的設計。本論文提出一個新的光線追跡演算法。它的特點是相對傳統的演算法而言能夠大量減少晶片內記憶體的使用,卻又能保持相似的效能。
同時,根據此演算法,我們也提出相對應的硬體架構。在此架構裡,我們還使用了多種硬體架構設計的方法來提升其硬體使用率,包括多執行緒、摺疊等,使其能在有限的硬體資源下達到最高的效能。在外部記憶體頻寬方面,運用位元長度分析和頂點分享的技術來減少頻寬。 我們也按照標準單元設計流程實作原形晶片。該晶片利用台積電130 nm技術製程,面積為1。697 X 1。7mm^2。其處理能力為每秒43億浮點數指令運算。 | zh_TW |
dc.description.abstract | 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 | en |
dc.description.provenance | Made available in DSpace on 2021-06-12T18:24:00Z (GMT). No. of bitstreams: 1 ntu-96-R94943110-1.pdf: 989988 bytes, checksum: 656c011ea256435561cd1c517d93db10 (MD5) Previous issue date: 2007 | en |
dc.description.tableofcontents | 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 | |
dc.language.iso | en | |
dc.title | 使用層次包圍盒之光線三角形相交測試之硬體架構設計與實現 | zh_TW |
dc.title | Hardware Architecture Design and
Implementation of Ray-Triangle Intersection with Bounding Volume Hierarchies | en |
dc.type | Thesis | |
dc.date.schoolyear | 95-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 梁柏嵩(Bor-Sung Liang),莊永裕(Yung-Yu Chuang),張雲南(Yun-Nan Chang),陳炳宇(Bing-Yu Chen) | |
dc.subject.keyword | 光線追跡,硬體架構,三維繪圖, | zh_TW |
dc.subject.keyword | Ray Tracing,Hardware Architecture,3D Graphics, | en |
dc.relation.page | 69 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2007-08-15 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電子工程學研究所 | zh_TW |
顯示於系所單位: | 電子工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-96-1.pdf 目前未授權公開取用 | 966.79 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。