空間データ構造（BVH ほか）

なぜ空間データ構造が要るのか

レイトレーシングの原理（/graphics/ray-tracing-principles/）は「光線を飛ばして最も近い交点を求める」ことに尽きます。しかし素朴に実装すると、1 本の光線ごとにシーン中の全プリミティブ（三角形など）と交差判定することになり、コストは光線数 × プリミティブ数、つまり O(N) です。数百万〜数十億三角形の現代シーンでは、これは実用になりません。

そこで 空間データ構造（acceleration structure） を使います。狙いは単純で、「この光線がそもそも当たり得ない領域」をまとめて棄却することです。空間や物体を階層的・格子的に区切っておき、光線が通らない区画の中身は交差判定そのものをスキップする。うまく構築すれば、光線あたりの交差判定は O(log N) 近く まで落ちます。この一段の枝刈りが、オフラインからリアルタイムまで全てのレイトレーサを支えています。

三大構造：BVH・kd-tree・uniform grid

代表的な構造は三つです。分類軸は「空間を分割するか（space subdivision）」対「物体を分割するか（object subdivision）」です。

BVH（Bounding Volume Hierarchy） は物体分割の代表で、各ノードが子孫のプリミティブ全体を包む AABB（軸平行境界ボックス、axis-aligned bounding box） を持ちます。光線がノードの AABB と交差しなければ、その部分木は丸ごと棄却できます。プリミティブが必ず 1 葉に入るので参照の重複がなく、後述する動的更新とも相性が良いため、GPU のハードウェアレイトレーシング（RTX など）を含め今日の標準です。

kd-tree は空間そのものを軸平行平面で二分していく空間分割構造です。空間を隙間なく覆えるので密度への適応が高く、静的シーンでのトラバーサル速度は歴史的に強力でした。反面、平面がプリミティブを跨ぐと同じ物体が両側に参照され、メモリと構築が複雑になります。

AABB と光線の交差：slab 法

BVH トラバーサルの最内ループは「光線 対 AABB」の判定です。標準は slab 法 で、ボックスを 3 軸それぞれの平行平面ペア（slab）の共通部分とみなし、各軸で光線がその区間に入る・出るパラメータ t を求めます。

光線: P(t) = O + t·D   （O=原点, D=方向, t≥0）
AABB: 各軸 i で [min_i, max_i]

各軸 i について:
  t1 = (min_i - O_i) / D_i
  t2 = (max_i - O_i) / D_i
  tmin_i = min(t1, t2),  tmax_i = max(t1, t2)

全軸で交差する区間:
  tenter = max(tmin_x, tmin_y, tmin_z)
  texit  = min(tmax_x, tmax_y, tmax_z)

交差の判定:
  tenter <= texit  かつ  texit >= 0  なら光線は AABB を貫く

除算を毎回やらず、光線ごとに 1/D_i を前計算して掛ける（逆数キャッシュ）のが定石です。判定は分岐が少なく SIMD 化しやすいので、4 本・8 本の光線をまとめて処理する レイパケットや、1 本の光線を複数の子ノード（4 分木・8 分木）に一括で当てる wide BVH（BVH4/BVH8） の基礎になります。

SAH ── どこで分割すべきか

BVH の速さは形状（どこで集合を二分するか）でほぼ決まります。その基準が SAH（Surface Area Heuristic、表面積ヒューリスティック） です。発想は確率にあります。凸な親ボックスの内側で一様ランダムに向かう光線が子ボックスに当たる確率は、子の表面積 / 親の表面積 に比例します（幾何確率の結果）。

分割コスト C の推定（ある分割案について）:

  C = Ct
    + (SA(L) / SA(P)) · N(L) · Ci
    + (SA(R) / SA(P)) · N(R) · Ci

  Ct     : ノードをたどる（内部）コスト
  Ci     : プリミティブ1個の交差コスト
  SA(P)  : 親ノードの AABB 表面積
  SA(L),SA(R) : 左右の子の AABB 表面積
  N(L),N(R)   : 左右に入るプリミティブ数

各分割案でこの期待コストを見積もり、最小の案を選びます。「表面積が小さく、かつ中身の少ない子」に分けるほど C は下がる——つまり タイトで空きの少ないボックス が良い木を作ります。全分割位置を厳密評価すると重いので、実務では軸ごとにプリミティブ重心を数十個の ビン（binning） に振り分け、境界候補をビン境界に限定して線形時間で近似します。トップダウンに再帰し、葉のプリミティブ数が閾値以下か、分割してもコストが下がらなくなったら葉として打ち切ります。

トラバーサル ── 木のたどり方

構築した BVH を光線がたどる基本はスタックベースの深さ優先です。ノードの AABB に当たったら子へ降り、葉ならプリミティブと交差判定します。

traverse(root, ray):
  stack.push(root)
  best = ∞
  while stack が空でない:
    node = stack.pop()
    if not intersect_AABB(ray, node.box, best): continue   # best より遠い箱は棄却
    if node が葉:
      for prim in node.prims:
        best = min(best, intersect(ray, prim))
    else:
      # 近い子を後で見るため、遠い子を先に push（近い子を先に処理）
      stack.push(遠い子)
      stack.push(近い子)

高速化の肝は二つです。第一に、既に見つかった最近交点 best より遠い AABB は判定不要（早期棄却）。第二に、近い子を先にたどる と早い段階で best が縮み、遠い部分木をまとめて枝刈りできます。影の有無だけ知りたい シャドウレイ では最近交点は不要で、遮蔽物が一つでも見つかった瞬間に打ち切れる（any-hit）ため、専用のトラバーサルにするとさらに速くなります。GPU では 1 本ずつスタックを持つ代わりに、スタックレス法や wide BVH で分岐と発散（divergence）を抑えます。

動的シーンの更新

物体が動くたびに SAH で作り直すのは高品質ですが高コストです。動的シーンでは作り直しを避ける戦略が要ります。

• リフィット（refit / AABB update）：木の構造は変えず、葉から根へ AABB だけを再計算する。O(N) で速く実装も簡単。ただし物体が大きく動くとボックスの重なりが増え、木の品質（トラバーサル効率）は徐々に劣化する。小さな変形やわずかな移動に向く。
• 部分再構築（partial rebuild）：品質が落ちた部分木だけを SAH で作り直す。全体ビルドとリフィットの中間で、コストと品質のバランスを取る。
• TLAS/BLAS の二段構成：現代のリアルタイム API（DXR/Vulkan RT）が採る方式。物体ごとの詳細な木を BLAS（bottom-level） として一度だけ作り、シーン内の各インスタンスは TLAS（top-level） に「BLAS への参照 + 変換行列」として置く。剛体が動いても BLAS は再利用し、動くのは軽い TLAS だけ——インスタンス化されたシーンで劇的に効く。

まとめ

• 空間データ構造は、光線が当たり得ない領域を階層的・格子的に棄却して交差判定を O(N) から O(log N) 近くへ 落とす仕組みで、あらゆるレイトレーサの土台。
• uniform grid は速いが疎密に弱く、kd-tree は空間分割で密度適応が高く、BVH は物体分割で参照重複がなく動的更新に強い——現在の主流は BVH と AABB。
• SAH は「子の表面積 / 親の表面積」を光線ヒット確率とみなし、トラバーサル + 交差の期待コスト を最小化する分割位置を選ぶ。実務は binning で線形近似する。
• トラバーサルは 近い子優先 + 最近交点による早期棄却 が肝で、シャドウレイは any-hit で打ち切る。
• 動的シーンは refit（AABB のみ）・部分再構築・TLAS/BLAS 二段構成 で全再構築を避けるのが定石。関連する光の計算は /graphics/path-tracing-global-illumination/ を参照。