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

Abstract

光線追蹤是一種用於生成在三維電腦圖形環境中的可見影像的渲染演算法。與其他渲染演算法相比，光線追蹤有更好的光學效果，例如對於反射與折射有更準確的類比效果，所以當追求這樣高質量效果時經常使用這種方法。然而一個明顯缺點就是需要龐大的光線與場景中物體交點測試的運算量，特別是在處理反射與折射的時候，因此有許多的加速資料結構演算法被提出以用來減少不必要的運算量。然而每一種資料結構都有其效率不佳的部分，至今為止也沒有一種被廣泛運用的資料結構。 在本篇論文中，我們探究了現今較為流行的資料結構，在不同類型的場景下其性能下降的部分，並且提出了一種混合型資料結構：Bounding Grid Hierarchies (BGH，層次包圍網格)，將場景架構以及物體網格分別用BVH(層次包圍盒)和grid(網格)來儲存以及管理。經過實驗數據佐證，在各式場景下BGH皆比BVH和grid節省更多運算量並且在動態場景下有更好的效能。 本篇論文也設計了一個光線追蹤系統並用ASIC(特定應用積體電路)來加速光線追蹤運算，藉由把同質性高的光聚集成光束來一次追蹤，可以減少光在追蹤資料結構的步數。此外，為了支援互動式應用，在動態場景下資料結構必須要被更新。這裡我們不重建整個資料結構，而是使用了部分更新以減少更新的時間，並且維持了資料結構的品質。我們也使用了多執行緒來加速運算。 整個光線追蹤系統是由一顆中央處理器、所設計的硬體加速器、記憶體以及一些周邊元件所組成。對於一張1024x768的圖片，這個系統每秒能有計算出6.67–31.92張圖的速度並能支援動態場景。

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.