支援動態場景之懷氏光線追跡之演算法及硬體架構設計

光線追跡是一個在三維繪圖中藉由計算來生成接近真實圖形的演算法。它的好處是能夠模擬出影子以及反射光、折射光等非直射光所造成的效果。然而這個方法因為要算很多次的光線和三角形的相交測試，故運算量極大。雖然有很多加速的方法可以另用特定的資料結構來加速它，要達到即時運算還是很困難。此外互動式的應用在三維繪圖中亦是不可或缺。如果要實現這個應用，場景在畫每一張圖的時候都有可能會變動，而造成事先建好的資料結構要跟著改變。為了解決這個問題，資料結構在每一次場景動作就要重建或更新。尤於重建的時間過長，我們選擇以更新的方式來支援動態場景。為了使畫出來的圖形更真實，我們選用懷式光線的方法來產生反射光和折射光。並把這些光分成很多個光束一次來追跡這些光束。這樣可以減少光源在追跡資料結構的步數。對於資料結構更新的方法，我們則選用重新適合和節點插入這兩種方法。為了加速上述提到的運算，我們做了一個硬體加速器來加速它，首先此硬體可以來做出畫圖，找出光線和三角形的交點並算出顏色，產生新的光線。另外對於動態場景的支援，這個硬體可以直接來做重新適合這個方法。而在節點插入的這個模式時，此硬體可以幫忙找出最適合的插入點。整個光線追跡系統是由一顆中央處理器，記憶體，我們特製的硬體加速器和一些周邊元件所組成。對於一個352 x 288的圖片，這個系統每秒可以計算出三到十五張圖的速度並支援動態場景的移動。

關鍵字

三維繪圖；光線追跡；懷氏光確追跡；層次包圍盒；系統單晶片

並列摘要

Ray tracing is an algorithm for synthesizing a realistic image in 3D computer graph- ics. 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. Although there are many accelerating algorithms using data special structures to accelerate the tracing process, the real time performance is still hard to achieve. Besides, the inter- active applications with 3D graphics are popular such as 3D gameing, where the scene may be changed in every frame. This means that the data structure building time is also an important issue for real time rendering. Aiming to solve these problems, this thesis proposes a system architecture which uses ASIC to accelerate ray tracing pro- cess. Instead of considering the primary rays only, secondary rays are also considered to render more realistic scenes, which is called as Whitted-style ray tracing. By using packet-based ray traversal algorithm and frustum culling not only in primary rays but also in shadow rays and secondary rays, the steps of ray traversing are reduced. Be- sides, aiming to support interactive applications, the data structure should be changed dynamically. Instead of rebuilding data structure every frames, we use updating based algorithms such as refit and insertion to update the data structure of the previous frame. By using updating based algorithm, the building time of new data structure is short and the traversing result is correct after the scene changes. In the hardware architecture of this system, multi-threading is used. Moreover, the computation for finding the inser- tion positions in insertion algorithm and shading are integrated into a specific unit to enable hardware sharing. This architecture is System-on-a-chip composed of CPU, our rendering engine, system memory and other peripherals. For an image in resolution of 352 288, the system can achieve 3–15 frames per second and also support dynamic scenes.

並列關鍵字

3D computer graphic ； ray tracing ； Whitted style ray tracing ； BVH ； SOC

參考文獻

[13] Ingo Wald, Carsten Benthin, Markus Wagner, and Philipp Slusallek, “Interactive

[25] K.R. Subramanian and Donald S. Fussell, “A search structure based on KD-trees

[1] Solomon Boulos, Dave Edwards, J Dylan Lacewell, Joe Kniss, Jan Kautz, Peter

[12] Solomon Boulos, Dave Edwards, J Dylan Lacewell, Joe Kniss, Jan Kautz, Peter

[14] Andreas Dietrich, Ingo Wald, Carsten Benthin, and Philipp Slusallek, “The

國際替代計量

支援動態場景之懷氏光線追跡之演算法及硬體架構設計

全文下載

主題瀏覽