目次 (12)
BVHとBVTT完全征服
1. なぜ必要なのか? — O(n²)の壁
3Dシーンに物体が1,000個あるとします。フレームごとに「これらのオブジェクトが互いに衝突するのか」を確認するには、単にすべてのペアを調べるだけです。
for A in objects: for B in objects: if A != B: check_collision(A, B)このブルトフォース方式の複雑度はO(n²) 。物体1,000個→約500,000回検査、10,000個で5千万回。 60fpsゲームでは、フレームごとにこの操作を繰り返す必要があります。当然実用的ではありません。
解決の重要なアイデアは、「重なる可能性のないオブジェクトは検査自体をしません」これです。
ここで登場するのがバウンディングボリューム(BB)とBVHです。
2. バウンディングボリューム(BB) — 精度を捨てて速度を得る
複雑なメッシュ型のまま衝突を調べるのは高すぎます。代わりに、衝突を確認するときは、オブジェクトを単純な幾何学的形状に包むバウンディングボリュームを使用します。

上の図はBounding Boxモデルの例です。

最もよく使われるのはAABB(Axis-Aligned Bounding Box)です。世界座標軸に整列した単純な直方体で、2つのAABBの重なり検査は各軸の区間比較6番で終わります。高速ですが回転した物体には無駄が多く発生します。だからOBBのように軸をねじって書くバウンディングボックスを使うことができます。
3. BVH — 空間を階層的に分割する
バウンディングボリュームだけではまだ足りません。衝突を比較しやすくなりましたが、まだすべてのオブジェクトについて調べる必要があります。ゲームでシーンのすべてのオブジェクトをまだ巡回する必要があると思います。 BVH(Bounding Volume Hierarchy)は、これらのオブジェクトをバイナリツリー構造にまとめ、「親ボックスと重ならないと子全体をスキップ」できるようにします。

BVHノード構造
struct BVHNode: aabb: AABB // このノードを包むバウンディングボックス left: BVHNode // 左の子(nullの場合は葉) right: BVHNode // 右の子(nullの場合は葉) object: Object // リーフノードの場合のみ有効BVH構築(トップダウン、再帰分割) - 中間値分割
function buildBVH(objects): node.aabb = computeAABB(objects) // 全体を包むボックス if len(objects) == 1: node.object = objects[0] // リーフノード return node axis = longestAxis(node.aabb) // 最長軸に分割(物体が最も長い方向) sorted = sortByAxis(objects, axis) mid = len(sorted) / 2 node.left = buildBVH(sorted[:mid]) node.right = buildBVH(sorted[mid:]) return nodeレイクロスナビゲーション - SAH分割の活用
function rayIntersect(node, ray): if not intersects(node.aabb, ray): return null // このサブツリー全体をスキップ if isLeaf(node): return preciseIntersect(node.object, ray) hitLeft = rayIntersect(node.left, ray) hitRight = rayIntersect(node.right, ray) return closest(hitLeft, hitRight)> SAH(Surface Area Heuristic) :単純に中間値に分割するのではなく、各分割候補の表面積比で予想探索コストを計算して最も効率的な分割軸を選択します。レイトレーシングエンジンでは必須だそうです。下の図が中間値に分割するのとSAHに分割する違いを示します。

4. BVTT - 2つのBVHを同時に下げる
BVH一つとしては「レイ(光線、光)がどんな物体に合うのか」を見つけることができます。しかし、 「キャラクターAとキャラクターBが衝突するのか?」 2つの複雑なオブジェクト間の競合を見つけるために異なります。
各オブジェクトが独自のBVHを持っているとき、 BVTT(Bounding Volume Traversal Tree)は2つのBVHを同時に再帰巡回して衝突ペアを絞り込みます。

BVTT巡回
function traverseBVTT(nodeA, nodeB, results): // 2 つのノードの AABB が重複しない場合、このペア全体スキップ if not overlaps(nodeA.aabb, nodeB.aabb): return // どちらもリーフなら精密衝突検査 if isLeaf(nodeA) and isLeaf(nodeB): results.add(preciseCheck(nodeA.object, nodeB.object)) return // より大きなノードを最初に分割(コストを最小化) if volume(nodeA) >= volume(nodeB): traverseBVTT(nodeA.left, nodeB, results) traverseBVTT(nodeA.right, nodeB, results) else: traverseBVTT(nodeA, nodeB.left, results) traverseBVTT(nodeA, nodeB.right, results)核心は単純です。両方のノードのAABBが重ならない場合、その下の子ペアは決して衝突できません。だから、サブツリー全体を持っているのです。複雑度はO(log n・log m)になります。
5. BVHとBVTTのまとめ

実務で二人は普通一緒に書いています。シーン全体BVHで「衝突候補ペア」を選び( broad phase )、そのペアに対して各オブジェクトのBVHをBVTTで精密検査します( narrow phase )
6. 実際のエンジンで
- Unity Physics / PhysX : シーンBVH(DBVT)でbroad phase, 各オブジェクト convex hull BVHで narrow phase
- Unreal Engine : `FBVHTree`クラスがBVH管理、`FChaosPhysics`でBVTTベースの衝突ペアを収集
-レイトレーシング(DXR、NVIDIA OptiX) :GPUアクセラレーションBVHナビゲーション、RTX BVHハードウェアユニットで処理
- FCL(Flexible Collision Library):ロボティクス/シミュレーション用オープンソース、BVTTベースの衝突クエリを提供
仕上げ
BVHとBVTTは結局同じコアアイデアの2つのアプリケーションです。 「重ならない空間は早く捨てる」 BVHがシーンとレイの間の問題を解決した場合、BVTTはそのアイデアを2つの複雑なオブジェクト間の問題に拡張しました。

上の写真は低価格VTKで複数の物体間のIntersectionされる部分を強調してレンダリングする写真です。 vtkを活用して、データが変わっても素早くリレンダリングできるようにしました。最初はVertexが重なり合うだろうという単純な考えをしましたが、考えてみると面が交差しなければ互いに衝突するので複雑になりました。それで、衝突地点をすばやく見つける方法を探し、BVHとBVTTまで勉強するようになりました。
