請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/8861
標題: | 光線追蹤法之平行化加速結構於多核處理器 Parallel KD Tree Acceleration Structures for Ray Tracing on Multi-Core Processor |
作者: | Chih-Cheng Tseng 曾至正 |
指導教授: | 鄭士康(Shyh-Kang Jeng) |
關鍵字: | 全域照明,光線追蹤,電腦動畫,互動,遊戲,空間分割,二元樹, KD tree,global illumination,ray tracing,animation,interactive,game, |
出版年 : | 2009 |
學位: | 碩士 |
摘要: | 全域照明是現今3D電腦動畫所必備,其原理在於應用光線追蹤法模擬真實光線,但其計算量極大,故遲遲未能應用在即時性的互動遊戲。在後摩爾定律的年代,桌上處理器核心數量不斷提高,八核及十六核CPU不久後將釋出,可以預見全域照明法即將出現在電腦遊戲當中。
在各種加速結構中, KD tree能夠最有效率的分割場景。特別在沒有關聯性組織的場景中,快速移動的物體,局部性的結構更新很快就失去效力,在這種狀況下通常需要全域性的快速結構重建。 本論文將略過ray tracing其他部分,而專注於KD tree多核平行化的深入探討,這是加速ray tracing的關鍵。將場景分割成許多子空間,再使用多核心CPU分別處理分割過的子空間,最後再將子樹合併。我們得到了一個接近完全平行化的建造方法,同時仍然維持著樹的高品質。 Global illumination is vital in nowadays computer animation, where ray tracing is used to simulate the lighting in real world. Due to the massive computation requirement, the algorithm cannot be applied in real time interactive application. In the era of post Moore’s law, desktop CPU has more and more cores, 8-core and 16-core CPU are going to appear, one can see the prospect of ray traced games. KD tree is able to fast cull out the empty spaces in the scene, while other structures lack this feature. Especially for unstructured scenes with fast changing geometry where local updates of the structure degrade immediately and a fast reconstruction is preferred. In the thesis we will skip other parts of ray tracing, but focus on the parallel implementation of the KD tree on multi-core CPU, that is the key to speed up. At beginning we decompose the scene space into sub regions. These sub regions are going to be processed by different cores of CPU. Finally we merge the subtrees into one. We achieve a near fully parallel construction and still preserve a high quality tree. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/8861 |
全文授權: | 同意授權(全球公開) |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-98-1.pdf | 3.56 MB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。