OptiX/DXRとシェーダーテーブル

![instancing.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/150193/11c66977-b9f8-f6be-2b66-b56806c10d9e.jpeg)
モデルデータ: [The Stanford 3D Scanning Repository](http://graphics.stanford.edu/data/3Dscanrep/)

# はじめに
この記事は[レイトレアドベントカレンダー2020](https://qiita.com/advent-calendar/2020/raytracing)の記事として作成されました。
こんにちは、[@shocker_0x15](https://twitter.com/Shocker_0x15)と申します。2018年末よりDirectX Raytracing (DXR)が登場し、リアルタイムレンダリングにおけるレイトレーシングに注目している方も多いでしょう。DXRを使うにあたって面倒に感じるであろう要素のひとつがシェーダーテーブルだと思います。当記事ではシェーダーテーブルの概念と使い方について紹介・解説します。

# GPU用レイトレーシングAPI
シェーダーテーブルの解説に移る前に2020年時点でのGPU用レイトレーシングAPIについて軽くおさらいしておきます。

## OptiX
https://developer.nvidia.com/optix
NVIDIAによって2009年頃から提供されている、NVIDIA GPU専用のレイトレーシングAPIです。三段階以上のAcceleration Structureやモーションブラー、カーブプリミティブのサポートなど基本的にDXRよりも高機能です。当初はホスト側(CPU側)のAPIは結構抽象化されていたのですが2019年に登場したOptiX 7.0以降DXRと同等のローレベルAPIに変化しました。基本的にCUDAと組み合わせて使用します。GPUカーネル(シェーダー)の言語はCUDA C++ (2020年時点ではほぼC++17)で記述します。

## DirectX Raytracing (DXR)
https://microsoft.github.io/DirectX-Specs/d3d/Raytracing.html
DirectXと統合されたGPU用レイトレーシングAPIです。シェーダー構成はOptiXと同じで、DXRはOptiXをベースにリアルタイムレンダリング向けに機能を単純化・調整することで作られたと予想できます。OptiXも前述の通り7.0以降DXRに逆に合わせるようなかたちでローレベルなAPIに変化、シェーダーテーブルなどがユーザーに見えるようになり、OptiXとDXRはますますそっくりになりました。DXR用のシェーダーはHLSLで記述します(言語機能が化石すぎて辛い)。

## Vulkan Raytracing
https://www.khronos.org/blog/vulkan-ray-tracing-final-specification-release
筆者はVulkan Raytracingは触ったことはないのですが、スペックを見る限り基本的にはDXRと~~ほぼ同等と考えてよいのではないでしょうか~~(2021年時点でRoot Signature周り等結構違うみたいですが、シェーダテーブルの考え方は多分そんなに変わらないはず)。ただ気になる点としては必ずしもRay Tracing Pipelinesのサポート(つまりシェーダーテーブルを使う実装)が必須とされていないので、プラットフォームによっては使い勝手が大きく異なるかもしれません。

## 関連用語
| 用語 | 意味・解説 |
|:--|:--|
| AS | Acceleration Structure<br/>レイとシーンとの交差判定を高速化するためのデータ構造。 |
| BLAS / GAS | Bottom-Level AS / Geometry AS<br/>三角形やユーザー定義プリミティブなどを要素に持つAS。BLASはDXR、GASはOptiX用語。典型的には**相対的に**位置や大きさが不変なジオメトリの集まりをひとつのBLAS/GASにグループとしてまとめます。 |
| Instance | ひとつのBLAS/GASは異なるトランスフォーム(移動や回転・スケール)を使ってシーン中に複数コピー存在することができます。BLAS/GASへの参照とトランスフォーム(とその他の付随情報)をまとめたものをインスタンス(Instance)と呼びます。OptiXの場合はMotion Transformや後述のIASへの参照とすることもできます。 |
| Instancing | ひとつのBLAS/GASから複数のインスタンスによって複数コピーをシーン中に表現することをインスタンシングと呼びます。従来からのリアルタイムレンダリング(ラスタライゼーション)におけるインスタンシングと意味は似ていますが実現方法は異なっています。 |
| Multi-level Instancing | インスタンシングを使用したシーンをさらにインスタンシングすることをMulti-levelインスタンシングと呼びます。DXRは2020年時点では対応していません。 |
| TLAS / IAS | Top-Level AS / Instance AS<br/>インスタンスを要素に持つAS。TLASはDXR、IASはOptiX用語。Multi-level Instancingに対応しているためかOptiXではGAS/IASともに呼称が違います。 |
| Shader Table / Shader Binding Table | ジオメトリごと・レイタイプごとなどに起動すべきシェーダーのIDとデータの組を格納したテーブル。OptiX documentationではShader Binding Table (SBT)という呼称が使われています。 |
| Shader Record / SBT Record | シェーダーテーブル中の要素でシェーダーIDとデータの組。DXRではデータ部分をLocal Root Argumentsと呼んだりもするみたいです。 |
| Shader / Program | GPU上で実行するプログラム。OptiXの場合はShaderではなくProgramと呼びます(の割にはShader Binding Tableという呼称が使われる)。CUDAの場合はGPUカーネルと呼んだりもします。 |
| Ray Generation Shader / Program | ホスト側から直接起動するシェーダー。ここからレイをトレースすることによりシェーダーテーブルの設定に応じて様々なシェーダーが起動されることになる。 |
| Miss Shader / Program | レイが何にもヒットしなかったときに起動されるシェーダー。レイのタイプごとに異なるシェーダーが起動するようにシェーダーテーブルを設定できる。 |
| Any-Hit Shader / Program | レイの探索範囲で見つかったレイとジオメトリの交点で起動されるシェーダー。<br/>Closest-Hit Shaderが起動される交点の候補を決定する。 |
| Closest-Hit Shader / Program | レイの探索範囲で見つかった最も近い交点で起動されるシェーダー。 |
| Intersection Shader / Program | レイとプリミティブの交差判定を記述するシェーダー。三角形に関してはユーザーが自分で書く必要はない。 |
| Hit Group | Any-Hit, Closest-Hit, Intersection Shader/Programをまとめたシェーダー。 |
| Callable Shader / Program | 他のシェーダーからユーザーが任意で呼び出すことできるシェーダー。<br/>関数ポインターのようなイメージ。 |

# シェーダーテーブル
従来のリアルタイムレンダリング(ラスタライゼーション、正確にはZバッファー法)ではメッシュごと、マテリアルごとといったシーン中の局所的なレンダリングに関してシェーダーやテクスチャーをバインドしドローコマンドを積んでいました。そういったレンダリングで正確に扱われるのは視点から見える一次の可視性のみで、シャドウやAO、グローバルイルミネーションを扱うために必要な二次以降の可視性を正確に求めるのは容易ではありません。レイトレーシングの場合、予めシーン全体を含むASを構築しておけば二次以降の任意の可視性評価が容易に行えます。一方で二次反射などを扱う場合シーン中のあらゆる場所でマテリアルの評価を行う必要がありますが、この場合に読むべきマテリアルのデータや実行すべきシェーダーをひとつに予め決定するのは困難です。OptiXやDXRといったGPU用のレイトレーシングAPIにはそういった状況を柔軟に扱うためにシェーダーテーブル、またはシェーダーバインディングテーブルと呼ぶ仕組みが用意されています。

シェーダーテーブルはGPUメモリ上のシェーダーレコード(SBTレコード)の配列です。

```
| Shader Record 0 | Shader Record 1 | ... 
```

各シェーダーレコードは関連するシェーダーIDとマテリアル評価などに必要なデータ部からなります。

```
| Shader ID | User Data |
 <- Shader Record ----->
```

シェーダーIDのサイズはAPIによって決まっています。シェーダーID部に書き込む内容もユーザーには不透明な部分になっているため、APIから提供される値をそのままコピーする必要があります。一方でデータ部は完全に任意となっており、サイズもユーザーが決める(アラインメントの制約はAPIによって決まっている)ことになりますが、シェーダーテーブル全体でそれぞれのシェーダーレコードは同じサイズである必要があります。

## 4種類のシェーダーテーブル
OptiX/DXRには次に示す4(5)種類のシェーダーテーブルがあります。

- Ray Generation Shader/Program用
- Miss Shader/Program用
- Hit Group用
- Callable Shader/Program用
- (Exception Program用, OptiXのみ)

Hit Group用のシェーダーテーブル以外は難しいところがないので当記事で解説はしません。Hit Group用のシェーダーテーブルはBLAS/GAS中のジオメトリ(やマテリアル区別)やインスタンスが持つオフセットに関して適切な順番で配置する必要があるので少し複雑になっています。

## BLAS/GASとシェーダーレコード
あるBLAS/GAS中に含まれる複数のジオメトリに対応するシェーダーレコードはメモリ上で連続している必要があります。さらにOptiXの場合、ひとつのジオメトリが複数のマテリアル"枠"(マテリアルの区別に相当、DXRの場合は1ジオメトリ1マテリアル枠)を持てますが、ひとつのジオメトリに属するマテリアル枠もまたメモリ上で連続している必要があります。少々ややこしいことに、それぞれのマテリアル枠には複数のシェーダーレコードが含まれます。このマテリアル枠あたりのシェーダーレコード数は典型的にはレイタイプ数に相当し、基本的な使い方をする上ではHit Group用シェーダーテーブル全体で共通です。少なくともBLAS/GAS中で変化することはありません(できません)。このマテリアル枠中のシェーダーレコードを使い分けることでレイタイプごとに異なるシェーダーの起動やデータの読み込みが可能になります。

例として3つのジオメトリA, B, CからなるBLAS/GAS Aを考えてみます。
ここで
- ジオメトリAはマテリアル枠数1
- ジオメトリBはマテリアル枠数3
- ジオメトリCはマテリアル枠数2
であるとします。そしてマテリアル枠あたりのレコード数(典型的にはレイタイプ数)は2であるとします。BLAS/GAS Aに対応するシェーダーレコードのレイアウトは次に示すようになります。(下のような図、iOSで見ると謎の改行入って見づらくなったのでそのうち直します。)

```
    (相対的な)index | 0  | 1  | 2  | 3  | 4  | 5  | 6  | 7  | 8  | 9  | 10 | 11 | 0 ...
    geometry-offset | 0       | 1       | 2       | 3       | 4       | 5       | 0 ...
      Material Slot | A-0     | B-0     | B-1     | B-2     | C-0     | C-1     | D-0 ...
ジオメトリの参照範囲 <- A ---> <- B -----------------------> <- C -------------> <- D -- ...
  BLAS/GASの参照範囲 <- BLAS/GAS A --------------------------------------------> <- BLAS/GAS B -- ...
```

合計で6つのマテリアル枠になります。実際のシェーダーレコード数はこの場合6x2=12になります。レイトレース実行時にはユーザーが渡した値とシステムが内部的に計算した値を組み合わせることでアクセスされるシェーダーレコードが決定されますが、上に示す`geometry-offset`が内部的に使われる値になります。あるBLAS/GASに対応するシェーダーレコードの並び順はBLAS/GASビルド時に渡すジオメトリ情報の配列の順番に沿っておく必要があります。つまり、ここではBLAS/GAS Aのビルド時に`{A, B, C}`の順番でジオメトリ配列を渡したので(渡す予定なので)シェーダーレコードの順番もメモリ上でジオメトリA, B, Cとしています。

### シェーダーやマテリアルも変えたインスタンシング
OptiX/DXRのインスタンスはBLAS/GASへの参照を持ちます。同じ参照を持った複数のインスタンスそれぞれで異なる移動・変形を用いることでシーン中に同じBLAS/GASを複数表示することができます。インスタンスには参照しているBLAS/GASに対応したシェーダーテーブル中のオフセットも設定する必要があります。ここで面白いのが、**ひとつのBLAS/GASに対して上に示したような対応するシェーダーテーブル領域が1つである必要はありません。** 同じレイアウトを使って異なるレコード内容にした領域を用意、そこへのオフセットをインスタンスに設定すればシェーダーやマテリアルを変えたインスタンシングが実現できます。

## Hit Group用シェーダーテーブルのインデックス計算
実行時にアクセスされるHit Group用のシェーダーテーブルのインデックスは、

- ヒットしたBLAS/GAS中のジオメトリに対応するオフセット(`geometry-offset`/`geometry-index`, システムが自動で計算)
- あらかじめ各インスタンスに設定されたオフセット(`instance-offset`)
- トレースコールに渡した値

から決定されます。ホスト側でHitGroup用シェーダーテーブルのベースアドレスやストライドも設定しているため該当領域にアクセスするために必要な値は全て揃います。
以下にOptiXとDXRのトレースコールとパラメターの対応表を示します。

```cpp
// OptiX
void optixTrace(OptixTraversableHandle handle,
                float3 rayOrigin, float3 rayDirection,
                float tmin, float tmax, float rayTime,
                OptixVisibilityMask visibilityMask,
                unsigned int rayFlags,
                unsigned int SBToffset,
                unsigned int SBTstride,
                unsigned int missSBTIndex,
                unsigned int& p0,
                ...
                unsigned int& p7);

// DXR
Template <payload_t>
void TraceRay(RaytracingAccelerationStructure AccelerationStructure,
              uint RayFlags,
              uint InstanceInclusionMask,
              uint RayContributionToHitGroupIndex,
              uint MultiplierForGeometryContributionToHitGroupIndex,
              uint MissShaderIndex,
              RayDesc Ray,
              inout payload_t payload);
```
| OptiX | DXR | 備考 |
|:--|:--|:--|
| `handle` | `AccelerationStructure` | Acceleration Structureのハンドル |
| `rayOrigin`<br/>`rayDirection`<br/>`tmin`<br/>`tmax`<br/> | `Ray` | レイとその範囲 |
| `rayTime` | N/A | レイの時間<br/>モーションブラー用でOptiXのみ。 |
| `visibilityMask` | `InstanceInclusionMask` | インスタンスマスク |
| `rayFlags` | `RayFlags` | レイフラグ |
| `SBToffset` | `RayContributionTo`-`HitGroupIndex` | レイごとのシェーダーテーブル中のオフセット<br/>典型的にはレイタイプ(enumの数値)。 |
| `SBTstride` | `MultiplierFor`-`GeometryContributionTo`-`HitGroupIndex` | BLAS/GAS中のあるジオメトリに対応する、シェーダーテーブル中のオフセットにかかる係数<br/>典型的にはレイタイプ数。 |
| `missSBTIndex` | `MissShaderIndex` | Missシェーダーのインデックス<br/>典型的にはレイタイプ(enumの数値)。 |
| `p0`...`p7` | `payload` | ペイロード<br/>OptiXはデータもしくはそのポインターをuint32_tの参照としてパックする。 |

両APIともにトレースコールに同様の値を渡していることがわかります。
インデックスの計算式は次のようになっています。

```
// OptiX
hitgroup-index = instance-offset +
                 geometry-offset * SBTstride +
                 SBToffset

// DXR
hitgroup-index = instance-offset +
                 geometry-index * MultiplierForGeometryContributionToHitGroupIndex +
                 RayContributionToHitGroupIndex
```

対応表と合わせてみるとわかりますが、ほぼ同じであることがわかります。OptiXは各ジオメトリが複数のマテリアル枠を持てるので`geometry-index`ではなく`geometry-offset`として区別していますが、1ジオメトリ1マテリアル枠という運用にすれば完全に同じになります。逆に言えばDXRの場合は異なるシェーダーやマテリアルを使い分けたい場合はジオメトリを分割する必要があります。**注意点として`instance-offset`には`SBTstride` / `MultiplierForGeometryContributionToHitGroupIndex`がかかりません。** つまりインスタンスに設定するオフセットはレイタイプ数に関係なく絶対的なものになります。複数のASのハンドルそれぞれで異なるレイタイプの集合を扱うような少し高度な使い方をする場合、Hit Group用シェーダーテーブル全体でレイタイプ数が共通という制約があると、すべてのマテリアル枠に関してシェーダーレコードを全レイタイプ数分確保しないといけなくなるため、このような形になっていると予想しています。

## 実装に関して
**Hit Group用のシェーダーテーブルのレイアウトはTLAS/IASには一切依存しません。また、BLAS/GASのビルドが終わっている必要もありません。** 各BLAS/GASに所属するジオメトリの数(とOptiXの場合はそれぞれのジオメトリが持つマテリアル枠数)が決定すればレイアウトを計算することができるので、インスタンスに設定するオフセットを計算することができます。何かOptiXやDXRのラッパーを作る場合にはシェーダーテーブルのレイアウト計算と実際にレコード内容を書き込むフェーズ、そしてAS自体のビルドを分けて考えるとすっきりするかもしれません。

## 実例
記事の先頭に載せている画像のシーンでは、コーネルボックス風の部屋の中にStanford Bunny(と土台)を3つ配置しています。Stanford Bunny(と土台)のBLASは1つしか作っていませんが、インスタンシングによって異なるマテリアルが実現できています。参考までにこのシーンのシェーダーテーブル全体を以下に載せておきます。レイタイプ数は2種類です。

- GAS Room & Light
    - Geometry Room (マテリアル枠3つ)
    - Geometry Light  (マテリアル枠1つ)
- GAS Bunny & Base
    - Geometry Bunny  (マテリアル枠1つ)
    - Geometry Base  (マテリアル枠1つ)
- Instance Room & Light
    - 参照するAS: GAS Room & Light
    - instance-offset: 0
- Instance Bunny & Base (R)
    - 参照するAS: GAS Bunny & Base
    - instance-offset: 8
- Instance Bunny & Base (G)
    - 参照するAS: GAS Bunny & Base
    - instance-offset: 12
- Instance Bunny & Base (B)
    - 参照するAS: GAS Bunny & Base
    - instance-offset: 16

それぞれのマテリアル枠ごとに2つのシェーダーレコード、1つ目がBRDF評価などのライティング計算、2つ目がシャドウレイ処理用のシェーダーです。それぞれにはシェーダーIDと関連するユーザーデータ(頂点や三角形バッファー、テクスチャーなど)が含まれます。

```
       hitgroup-index | 0    | 1    | 2    | 3    | 4    | 5    | 6    | 7    | 8    | 9    | 10   | 11   | ...
      geometry-offset | 0           | 1           | 2           | 3           | 0           | 1           |
        Material Slot | Gray Wall   | Red Wall    | Blue Wall   | Light       | Bunny       | Base        |
  ジオメトリの参照範囲 <- Room --------------------------------> <- Light ---> <- Bunny ---> <- Base ---->
インスタンスの参照範囲 <- Inst Room & Light ---------------------------------> <- Inst Bunny & Base (R) ->

       hitgroup-index | 12   | 13   | 14   | 15   | 16   | 17   | 18   | 19   |
      geometry-offset | 0           | 1           | 0           | 1           |
        Material Slot | Bunny       | Base        | Bunny       | Base        |
  ジオメトリの参照範囲 <- Bunny ---> <- Base ----> <- Bunny ---> <- Base ---->
インスタンスの参照範囲 <- Inst Bunny & Base (G) -> <- Inst Bunny & Base (B) ->
```

- `optixTrace(..., SBToffset = 0, SBTstride = 2, ...)`を実行、青色の壁にレイがヒットした場合：<br/>GASのヒット情報から内部的に`instance-offset = 0`, `geometry-offset = 2`と決定され、`hitgroup-index = 0 + 2 * 2 + 0 = 4`のシェーダーが実行される。
- `optixTrace(..., SBToffset = 1, SBTstride = 2, ...)`を実行、緑色のうさぎにレイがヒットした場合：<br/>GASのヒット情報から内部的に`instance-offset = 12`, `geometry-offset = 0`と決定され、`hitgroup-index = 12 + 0 * 2 + 1 = 13`のシェーダーが実行される。

DXRの場合は1ジオメトリ1マテリアル枠なので上のようなシーンを構成する場合のシェーダーテーブルは次のようになるでしょう(Material Slot = ジオメトリごとの参照範囲となります)。

```
       hitgroup-index | 0    | 1    | 2    | 3    | 4    | 5    | 6    | 7    | 8    | 9    | 10   | 11   | ...
       geometry-index | 0           | 1           | 2           | 3           | 0           | 1           |
        Material Slot | Gray Wall   | Red Wall    | Blue Wall   | Light       | Bunny       | Base        |
インスタンスの参照範囲 <- Inst Room & Light ---------------------------------> <- Inst Bunny & Base (R) ->

       hitgroup-index | 12   | 13   | 14   | 15   | 16   | 17   | 18   | 19   |
       geometry-index | 0           | 1           | 0           | 1           |
        Material Slot | Bunny       | Base        | Bunny       | Base        |
インスタンスの参照範囲 <- Inst Bunny & Base (G) -> <- Inst Bunny & Base (B) ->
```

※実際にはシーン全体がstaticなのであればひとつのBLAS/GASにまとめたほうが良いとか、マテリアルも別にせず統一したほうが良いとか考えられますが、ここではシェーダーテーブル説明のために敢えて分解しています。

# 番外編
## OptiXを楽に使う
この記事ではシェーダーテーブルの解説を書いておきながらアレなんですが、サクッとレイトレAPIを使ってみるにあたってはシェーダーテーブル周辺の理解とセットアップは面倒なのでOptiX用のライブラリを作りました。

OptiX Utility: OptiX Lightweight Wrapper Library
https://github.com/shocker-0x15/OptiX_Utility

このライブラリはシェーダーバインディングテーブルのセットアップや、Acceleration Structureの構築の前準備などを自動化します。シェーダーテーブルの自動生成にあたっては、ユーザーが任意の形で与えたマテリアルごと、ジオメトリごと、GASごとのユーザーデータを内部的に収集しSBTレコードを適切なレイアウトで配置します。OptiXは7.0以降良くも悪くもメモリ確保やASのビルドを始めとして、様々な細かい制御がすべてユーザー責任になった一方面倒なコードの記述も非常に増えました。このライブラリは自由度は可能な限り残しつつ面倒な部分だけを隠すことを意識しています。CUDAのメモリを扱うライブラリも同時に提供していますが、同等のコードをすでに持っている場合は3ファイル(.h/.cppのみ, libやdllは無し)の追加だけで使えます。

## Acceleration Structure
OptiXやDXRなどのGPU用レイトレーシングAPIを使えば比較的簡単に高速なレイトレーシングアプリケーションを作成することができて幸せなのですが、一方でいくら最近のGPUが速いといってもこれらのAPIによって実現される速さは異常では？一体何がどうなっているんだ？と気になって悶々とする方もいるかもしれません(特に自分でレイトレのコードを書いたことがある人)。
もちろん速さの大きな要因としては昨今のGPUの並列計算能力(加えて2018年半ばごろからレイトレをハードウェア的に高速化する仕組みも徐々に導入)がひとつ挙げられるのですが、もうひとつの大きな要因としてはAcceleration Structureと呼ばれる交差判定を高速化するためのデータ構造が挙げられます。むしろこっちのほうがGPUよりも寄与が大きいでしょう。ASには様々なものがありますが、レイトレの文脈ではBounding Volume Hierarchy (BVH)が最もよく使われます。このあたりの技術的詳細が気になる方は次に紹介する記事や論文を参考にされると良いかもしれません。

- Bounding Volume Hierarchy (BVH) の実装 - 構築編/交差判定編
  https://qiita.com/omochi64/items/9336f57118ba918f82ec
  https://qiita.com/omochi64/items/c2bbe92d707b280896fd
  Surface-Area Heuristicというコスト関数を考慮したBVHのビルドと交差判定の実装に関して解説されています。
- BVHのはなし
  https://shinjiogaki.github.io/bvh/
  BVHの様々な構築・最適化手法について幅広く概要がまとめられています。この記事を読めばBVHに関してどんな世界がひろがっているのか簡単に把握できると思います。
- Spatial Splits in Bounding Volume Hierarchies
  BVH中の三角形の形状・姿勢によってはAABBがスカスカになって交差判定の効率低下を招きます。この論文ではSpatial Splittingによって三角形を分割し必要に応じて複数のAABBを割り当てることによって効率化を図ります。Split BVH (SBVH)と呼びます。
- Shallow Bounding Volume Hierarchies for Fast SIMD Ray Tracing of Incoherent Rays
昨今のCPUにはSSEやAVXといったSIMD演算器が搭載されており、それらを活用してBVHとの交差判定を高速化する手法が提案されています。二分木ではなく四分木のBVHを構築するためQuad BVH (QBVH)と呼ばれます。
- Fast BVH Construction on GPUs
  GPU上で高速にBVHを構築するLinear BVH (LBVH)という手法が提案されています。三次元空間に散らばった各プリミティブにモートンコードという数値を割り当て、1次元のソートによって空間的に近いプリミティブたちを木構造中の近傍に集めます。
- Maximizing Parallelism in the Construction of BVHs, Octrees, and k-d Trees
  LBVHではモートンコードのソート後に木構造を生成する処理があるのですが、この論文では元論文よりも高速な手法が提案されています。
- Fast Parallel Construction of High-Quality Bounding Volume Hierarchies
  LBVHは構築は非常に速いのですが生成される木の品質が良くありません。この論文ではTreelet Restructuringと呼ぶGPU上で行う木構造の最適化が提案されています。またSBVHのような三角形分割をGPUで行う方法についても提案されています。
- Embree
  https://www.embree.org/
  Intelによって提供されているASのビルド・交差判定ライブラリです。SIMDを最大限活用しているためCPU上で非常に高速にBVHのビルドや交差判定を行うことができます。オープンソースなのでコードも読むことができ、BVHビルダーの部分などが参考になります。ユーザー定義のBVHデータ構造にあてはめてカスタムビルドする機能もあるので、BVHの構築だけはEmbreeに任せるといったことも可能です。

ところでAcceleration Structureって(一応)日本語訳が欲しくないですか？直訳すると「加速構造」になるのですが微妙だと感じています。色々考えた結果個人的には「加速機構」とか「高速化機構」のほうが意味が通るかなーと思っていますがいかがでしょう(「機構」は辞書にも載ってるstructureの訳にもなるし、データ構造というだけでなく、アルゴリズム的なニュアンスも含んでいそう)。そもそも訳さないほうが幸せ、とかは一旦ナシで。