這次的範例主要示範如何建構以及在 compute shader 中使用 acceleration structure來加速 ray 與幾何場景的碰撞偵測。

Acceleration Structure

在ray tracing中，一般會使用acceleration structure來加速ray與幾何場景的碰撞偵測。acceleration structure其實就是空間分割樹，藉由切割空間以及階層樹的幫助，來快速篩選出可能跟ray碰撞的幾何物件。這次的範例選用最常見的BVH來當作示範，關於BVH的說明可以參考Wiki

Bounding volume hierarchy - Wikipedia

Bounding Volume Hierarchy

• BVH的原理很簡單，但是如何建構一棵好的BVH樹卻是一門大學問，網路上有很多探討這方面的文章。此次範例主要是示範BVH的原理以及用法，因此採用最簡單的二分法來切割空間，由於voxel場景的特性，因此二分法即可達到不錯的效果。
• 二分法作法是尋找目前AABB中最長的一個軸向將AABB切割成兩個子AABB，由於voxel皆是整數大小，只要選擇以整數做為切割長度，就可以確保不會有voxel被切格成多份。BVH在切割時要盡量減少切割到primitive而造成leaf端的primitive重複，因為重複的primitive會造成多餘的計算進而影響效能。
• 在很多平台上compute shader無法支援遞迴，所以範例中利用groupshared memory來當作堆疊使用。利用groupshared memory的好處是他的讀取非常的快速，效能會比使用compute buffer好很多。缺點則是他的大小很有限，而且需分配給所有的group thread使用，因此BVH的深度會受到限制。
• 在範例中我們設定每個group大小為8x8個thread，每個thread分配64個int作為堆疊使用，因此整個group shared memory為 8x8x64x4=16K byte ，正好是groupshared memory的最低標準量。操作thread堆疊時，則可以使用SV_GroupIndex來計算出每個thread的堆疊起始位置。

這次的範例使用了MagicaVoxel ( http://ephtracy.github.io/ )的模型來測試，下圖的場景總共有21129個voxel，每個fragment使用三條ray的情況下(一條是成像，另外兩條是計算陰影)，測試使用BVH以及不使用BVH的效能差異。可以看到使用BVH時可以達到約200fps，而完全不使用時則只有5fps。

With BVH

230 fps (3 Rays per fragment, 1 ray for rendering, 2 rays for shadowing, 21129 voxels)

Without BVH

5 fps (3 Rays per fragment, 1 ray for rendering, 2 rays for shadowing, 21129 voxels)

Github Page

fallingcat/ComputeRayTracingSamples