二分空間分割
二分空間分割（にぶんくうかんぶんかつ、Binary Space Partitioning, BSP）は、空間を凸集合（convex set）へ再帰的に分割していく手法である。このプロセスにより、BSP木（BSP tree）と呼ばれる木構造データが生成される。元々は3Dコンピュータグラフィックス分野においてレンダリング効率を向上させる目的で1969年に考案されたが、1990年代初頭にid Softwareのジョン・カーマックが『DOOM』や『Quake』のエンジンに採用したことで広く知られるようになった。
BSPは、複雑な3D空間（ゲームのレベルなど）を描画する前に事前計算を行うことで、いかなる視点からでもポリゴンを正しい順序で描画できるようにする強力な技術である。主に、静的（不動）な構造物で構成された空間の処理に極めて効果的である。
概要
二分空間分割の中心的なアイデアは、単一の平面（3Dの場合）または線（2Dの場合）を基準に、空間を「前面（front）」と「背面（back）」という2つの部分空間に分けることにある。そして、分割されたそれぞれの部分空間に対し、さらに別の平面を基準に分割する作業を再帰的に繰り返す。この分割プロセスは、各部分空間がそれ以上分割する必要のない単一の凸空間（葉、leaf）になるまで続けられる。
- ノード（Node）: BSP木の各ノードは、空間の分割に用いられた平面（ポリゴン）を表す。
- 子ノード（Children）: 各ノードは、「前面」部分空間と「背面」部分空間に対応する2つの子ノードを持つ。
- 葉ノード（Leaf Node）: 木の末端に位置し、空（empty）または塗りつぶされた（solid）凸空間を表す。
レンダリングにおける活用
BSPの最も代表的な用途は、Zバッファが存在しなかったり性能が不十分だったりした初期の3Dゲームにおいて、描画順序を決定することであった。BSP木を用いることで、カメラ（視点）の位置に関わらず、常に正しい順序でポリゴンを描画できる。
この方式は画家のアルゴリズムと類似した動作原理を持ち、以下の手順で描画を行う。
- BSP木のルートノードから探索を開始する。
- 現在のノードの分割平面を基準に、カメラ（視点）が「前面」にあるか「背面」にあるかを判断する。
- カメラが「前面」にある場合：
- 「背面」側の子ノードを先に再帰的に描画する。
- 現在のノードのポリゴンを描画する。
- 「前面」側の子ノードを再帰的に描画する。
- カメラが「背面」にある場合は、上記の手順を逆の順序で実行する。
このプロセスにより、カメラから遠いポリゴンから順に描画されるため、近いポリゴンが遠いポリゴンを自然に上書きし、正確なシーンが生成される。
その他の応用分野
- 衝突判定（Collision Detection）: キャラクターやオブジェクトがマップの壁のような固体空間の内部にあるか外部にあるかを、BSP木をたどることで効率的に判定できる。
- 可視性カリング（Visibility Culling）: 現在の視点から見えない領域のポリゴンを描画プロセスから除外することで、パフォーマンスを向上させるためにも利用される。
- レイキャスティング（Ray Casting）: 銃弾や光線がどの物体に最初に衝突するかを判定する計算を高速化できる。
長所と短所
- 長所:
- 描画速度が非常に速い。一度木が構築されれば、描画時には単純な探索だけで正しい描画順序が得られる。
- Zバッファのハードウェアが不要、または補助的に用いるだけで済むため、低スペックのシステムに有利だった。
- 短所:
- BSP木の生成プロセスは非常に複雑で計算コストが高い。そのため、マップの読み込み時に一度だけ実行する必要がある。
- マップの構造が変化しない静的な環境にしか適用できない。ドアやエレベーターのような動的要素は別途処理が必要となる。
- 分割の過程で、元々のポリゴンが複数に分断され、総ポリゴン数が増加することがある。