請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/63380
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 簡韶逸 | |
dc.contributor.author | Wei-Hao Huang | en |
dc.contributor.author | 黃威豪 | zh_TW |
dc.date.accessioned | 2021-06-16T16:38:09Z | - |
dc.date.available | 2017-10-05 | |
dc.date.copyright | 2012-10-05 | |
dc.date.issued | 2012 | |
dc.date.submitted | 2012-10-01 | |
dc.identifier.citation | [1] Samuel R. Buss, Computer Graphics: A Mathematical Introduction with OpenGL, Cambridge University Press, 2003.
[2] http://www.comphist.org/computing history/newpage6.htm. [3] http://en.wikipedia.org/wiki/Rasterisation. [4] Andrew S. Glassner, An Introduction to Ray tracing (The Morgan Kaufmann Series in Computer Graphics), Morgan Kaufmann, 1989. [5] Peter Shirley and R. Keith Morley, Realistic Ray Tracing, AK Peters, Ltd, 2003. [6] Matt Pharr and Greg Humphreys, Physically Based Rendering: From Theory to Implementation, Morgan Kaufmann, 2004. [7] David Jevans and Brian Wyvill, “Adaptive Voxel Subdivision for Ray Tracing,” in Proceedings of Graphics Interface 1989, 1989. [8] Jeffrey Goldsmith and John Salmon, “Automatic Creation of Object Hierarchies for Ray Tracing,” Computer Graphics and Applications, IEEE, vol. 7, no. 5, pp. 14–20, May 1987. [9] Ingo Wald, William R Mark, Johannes G‥unther, Solomon Boulos, Thiago Ize, Warren Hunt, Steven G Parker, and Peter Shirley, “State of the Art in Ray Tracing Animated Scenes,” Computer Graphics Forum, vol. 28, no. 6, pp. 1691–1722, 2009. [10] Jonas Lext, Ulf Assarsson, and Tomas M‥oller, “A Benchmark for Animated Ray Tracing,” IEEE Computer Graphics and Applications, vol. 21, no. 2, pp. 22–31, Mar/Apr 2001. [11] Krzysztof S. Klimaszewski and Thomas W. Sederberg, “Faster Ray Tracing Using Adaptive Grids,” IEEE Computer Graphics and Applications, vol. 17, no. 1, pp. 42–51, Jan/Feb 1997. [12] Javor Kalojanov, Markus Billeter, and Philipp Slusallek, “Two-Level Grids for Ray Tracing on GPUs,” in Eurographics 2011 - Full Papers, 2011, pp. 307–314. [13] Alexander Reshetov, Alexei Soupikov, and Jim Hurley, “Multi-level Ray Tracing Algorithm,” ACM Trans. Graph., vol. 24, no. 3, pp. 1176–1185, July 2005. [14] Daniel Reiter Horn, Jeremy Sugerman, Mike Houston, and Pat Hanrahan, “Interactive k-D Tree GPU Raytracing,” in Proceedings of the 2007 Symposium on Interactive 3D Graphics and Games, New York, NY, USA, 2007, I3D ’07, pp. 167–174, ACM. [15] 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. [16] Sven Woop, 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. [17] CarstenWachter and Alexander Keller, “Instant Ray Tracing: The Bounding Interval Hierarchy,” in Rendering Techniques 2006 - Proceedings of the 17th Eurographics Symposium on Rendering, 2006, pp. 139–149. 51 [18] Jonas Lext and Tomas Akenine-M‥oller, “Towards Rapid Reconstruction for Animated Ray Tracing,” in Eurographics 2001 - Short Presentations, 2001, pp. 311–318. [19] Ingo Wald, Carsten Benthin, and Philipp Slusallek, “Distributed Interactive Ray Tracing of Dynamic Scenes,” in Proceedings of the 2003 IEEE Symposium on Parallel and Large-Data Visualization and Graphics, Washington, DC, USA, 2003, PVG ’03, pp. 77–85, IEEE Computer Society. [20] Johannes Gunther, Heiko Friedrich, IngoWald, and Hans peter Seidel, “Ray Tracing Animated Scenes Using Motion Decomposition,” in Computer Graphics Forum, 2006. [21] Christian Lauterbach, Michael Garland, Shubhabrata Sengupta, David P. Luebke, and Dinesh Manocha, “Fast BVH Construction on GPUs,” Comput. Graph. Forum, vol. 28, no. 2, pp. 375–384, 2009. [22] Kirill Garanzha, Jacopo Pantaleoni, and David McAllister, “Simpler and Faster HLBVH withWork Queues,” in Proceedings of the ACM SIGGRAPH Symposium on High Performance Graphics, New York, NY, USA, 2011, HPG ’11, pp. 59–64, ACM. [23] 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. [24] SvenWoop, J‥org Schmittler, and Philipp Slusallek, “RPU: A Programmable Ray Processing Unit for Realtime Ray Tracing,” in ACM SIGGRAPH 2005 Papers, New York, NY, USA, 2005, SIGGRAPH ’05, pp. 434–444, ACM. [25] http://www.apptism.com/apps/itracer.52 [26] 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. [27] Ingo Wald, Solomon Boulos, and Peter Shirley, “Ray Tracing Deformable Scenes Using Dynamic Bounding Volume Heiarchies,” in ACM Transactions on Graphics, 2007, vol. 26. [28] Chen-Haur Chang, Chuan-Yiu Lee, and Shao-Yi Chien, “A 2.88mm2 50MIntersections/s Ray-Triangle Intersection Unit for Interactive Ray Tracing,” in Proceedings of the 2008 IEEE Asian Solid-State Interactive Circuits Conference, Nov 2008, pp. 181–184. [29] Jae-Ho Nah, Jeong-Soo Park, Chanmin Park, Jin-Woo Kim, Yun-Hye Jung, Woo-Chan Park, and Tack-Don Han, “T&I Engine: Traversal and Intersection Engine for Hardware Accelerated Ray Tracing,” ACM Trans. Graph., pp. 160–160, 2011. [30] SvenWoop, 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. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/63380 | - |
dc.description.abstract | 光線追蹤是一種用於生成在三維電腦圖形環境中的可見影像的渲染演算法。與其他渲染演算法相比,光線追蹤有更好的光學效果,例如對於反射與折射有更準確的類比效果,所以當追求這樣高質量效果時經常使用這種方法。然而一個明顯缺點就是需要龐大的光線與場景中物體交點測試的運算量,特別是在處理反射與折射的時候,因此有許多的加速資料結構演算法被提出以用來減少不必要的運算量。然而每一種資料結構都有其效率不佳的部分,至今為止也沒有一種被廣泛運用的資料結構。
在本篇論文中,我們探究了現今較為流行的資料結構,在不同類型的場景下其性能下降的部分,並且提出了一種混合型資料結構:Bounding Grid Hierarchies (BGH,層次包圍網格),將場景架構以及物體網格分別用BVH(層次包圍盒)和grid(網格)來儲存以及管理。經過實驗數據佐證,在各式場景下BGH皆比BVH和grid節省更多運算量並且在動態場景下有更好的效能。 本篇論文也設計了一個光線追蹤系統並用ASIC(特定應用積體電路)來加速光線追蹤運算,藉由把同質性高的光聚集成光束來一次追蹤,可以減少光在追蹤資料結構的步數。此外,為了支援互動式應用,在動態場景下資料結構必須要被更新。這裡我們不重建整個資料結構,而是使用了部分更新以減少更新的時間,並且維持了資料結構的品質。我們也使用了多執行緒來加速運算。 整個光線追蹤系統是由一顆中央處理器、所設計的硬體加速器、記憶體以及一些周邊元件所組成。對於一張1024x768的圖片,這個系統每秒能有計算出6.67–31.92張圖的速度並能支援動態場景。 | zh_TW |
dc.description.abstract | Ray tracing is an algorithm for synthesizing a realistic image in 3D computer graphics. 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. There are many accelerating algorithms using acceleration data structures to accelerate the tracing process. However, each acceleration structure has its inefficiency part and none of them becomes the main stream. In this master thesis, we investigate the performance degradation of the popular acceleration structures under different types of animated scenes and propose a hybrid
acceleration structure, called Bounding Grid Hierarchies (BGHs), within which the scene structure and object meshes are separately handled by a shallow BVH and many small uniform grids, respectively. The BGH handles both uniformly and non-uniformly distributed scenes more efficiently than the traditional BVH and grid, and the updating scheme for animated scenes is proposed as well. This thesis also proposes a system architecture which uses ASIC to accelerate ray tracing process. By using packet-based ray traversal algorithm and frustum culling, the steps of ray traversing are reduced. Besides, aiming to support interactive applications, the acceleration structure should be changed dynamically. Instead of rebuilding data structure every frames, we use updating based algorithms to update the structure of the previous frame. In the hardware architecture of this system, multi-threading is used. This architecture is System-on-a-chip composed of CPU, our rendering engine, system memory and other peripherals. For an image in resolution of 1024x768, the system outperforms traditional approaches on both rendering and updating phases under different scene configurations and achieves around 6.67–31.92 frame rate per second and also support dynamic scenes. | en |
dc.description.provenance | Made available in DSpace on 2021-06-16T16:38:09Z (GMT). No. of bitstreams: 1 ntu-101-R99943119-1.pdf: 8446644 bytes, checksum: 6ee4167bb8e31a29104ed9be9de55c1c (MD5) Previous issue date: 2012 | en |
dc.description.tableofcontents | Abstract vii
1 Introduction 1 1.1 3D Computer Graphic 1 1.2 Ray Tracing Overview 2 1.2.1 Basic Concept 3 1.2.2 Acceleration Structure Generation 4 1.2.3 Ray Generation 4 1.2.4 Traversal 5 1.2.5 Intersection 5 1.2.6 Shading 6 1.3 Design Challenge 6 1.4 Thesis Organization 7 2 Previous Works 9 2.1 Basic Acceleration Structures 9 2.2 Modifications of Structures 11 2.3 Architecture Design 12 3 Algorithm Development 13 3.1 Proposed Bounding Grid Hierarchies 13 3.1.1 Highly Tessellated Objects 13 3.1.2 Sparse Scenes 18 3.1.3 Bounding Grid Hierarchies 18 3.1.4 Animation and Update 22 3.2 Traversal Algorithm 26 3.2.1 Frustum Culling 27 4 Architecture Design of Ray Tracer 29 4.1 Architecture Overview 29 4.2 Ray Tracing Unit Overview 31 4.3 Unified Traversal Unit 32 4.4 Refit Unit 35 4.5 Cache Architecture 37 4.5.1 BVH Cache 37 4.5.2 Grid Cache 39 4.6 Hardware Implementation 42 4.6.1 Synthesized Results 42 4.6.2 Result Comparisons 44 5 Conclusion 47 | |
dc.language.iso | en | |
dc.title | 支援動態場景之光線追蹤之演算法及硬體架構設計 | zh_TW |
dc.title | Algorithm and Hardware Architecture Design of Ray Tracing for Dynamic Scenes | en |
dc.type | Thesis | |
dc.date.schoolyear | 101-1 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 莊永裕,陳維超,李潤容,張鈞法 | |
dc.subject.keyword | 光線追蹤,資料結構,硬體加速, | zh_TW |
dc.subject.keyword | ray tracing,acceleration structures,hardware, | en |
dc.relation.page | 52 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2012-10-02 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電子工程學研究所 | zh_TW |
顯示於系所單位: | 電子工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-101-1.pdf 目前未授權公開取用 | 8.25 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。