This explanation is currently available in Japanese.
ひとことで
たくさんの物体を、包囲体（箱や球）を入れ子にした木に入れておく構造です。根の箱がすべての物体を囲み、その子の箱がそれぞれ半分ずつを囲み……と分かれていき、葉には数個の物体が入ります。光線や物体との判定は根から始め、箱に当たらなければ、その中の物体はまとめて調べずに済むので、 個の物体に対して 程度の手間で済みます。レイトレーシングや、静止した地形との当たり判定の定番です。
ゲームでの使いどころ
- レイキャストの高速化：弾・視線・マウスでの選択を、何万ポリゴンの地形やレベルに対して行う。
- レイトレーシング：GPU のハードウェアレイトレーシングは、BVH をたどる処理を専用回路で行う（BLAS/TLAS の 2 段の BVH）。
- 物理エンジンの広域判定：動く物体を入れた動的な AABB 木（Box2D、Bullet の dbvt）で、重なりそうな組を探す。
- メッシュどうしの判定・距離：複雑なメッシュを三角形の BVH にし、2 つの木を同時にたどる。
しくみ
作る（上から分ける）：
- 物体の集まり全体を囲む箱を作ります。
- 箱のいちばん長い軸を選び、物体の中心の並びで 2 つに分けます（中央値で分ける、真ん中の位置で分ける、SAH で最適な位置を探す、など）。
- それぞれの半分について 1〜2 をくり返し、物体が数個になったら葉にします。
SAH（表面積の見積もり）：「光線が子の箱に当たる確率は、箱の表面積に比例する」と考え、分け方の良さを
で見積もり（ は表面積、 は物体数）、これが最小になる位置で分けます。レイトレーシングで最もよく使われる作り方です。
たどる：根から、光線と箱の交差を調べ、当たった箱の子へ進みます。いちばん近い当たりを探すときは、近い方の子から先に調べ、「すでに見つかった当たりより遠い箱」は飛ばします。
実装のポイント
- 配列に平らに並べる：節をポインタでつなぐより、配列に深さ優先の順で並べ、子の番号だけを持つ方が、メモリを連続して読めて速くなります。
- 動く物体：物体が動いたら、葉から根へ向かって箱を作り直すだけ（リフィット）で済ませ、木の形が悪くなったら作り直します。大きく動く物体が多いなら、空間ハッシュやスイープ・アンド・プルーンの方が向くこともあります。
- 速く作る：物体をモートン符号の順に並べ、上位のビットから分けていくと、GPU で一気に BVH を作れます（LBVH）。
- 光線の逆数を前計算：箱との判定では、光線の向きの各成分の逆数を 1 回だけ計算しておき、割り算を掛け算にします。
つまずきやすい点
- 箱どうしの重なり：BVH は空間ではなく物体を分けるので、兄弟の箱が重なることがあります。重なりが大きいと、両方の子を調べることになり遅くなります。SAH で作るとこれが減ります。
- 大きな物体と小さな物体が混ざる：巨大な床と小さな小物を同じ木に入れると、床が根の近くで箱を大きくしてしまいます。静的な地形と動く物体で木を分けます。
- 木の深さ：葉の物体の数を 1 にすると木が深くなり、たどる手間が増えます。2〜8 個程度が目安です。
デモで試すこと
- 260 個の球を、いちばん長い軸で半分ずつに分けて作った BVH です。紫の線は「表示する深さ」の段の箱で、深さを変えると木の各段の分け方がわかります。
- 赤い光線がたどった箱が黄色、調べた球が水色です。左下で、球の判定が総当たりの 260 回に比べてほんの数回で済んでいることを確かめてください。
- 「光線を自動で振る」を切ると、カーソルの方向へ光線を飛ばせます。球の多い所を通ると調べる箱が増え、何もない所を通ると根の近くで打ち切られます。