光線追蹤法之平行化加速結構於多核處理器

Abstract

全域照明是現今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.