バイナリ空間分割
コンピュータグラフィックスにおいては、シーンを正しくかつ素早く描画したい。単純な方法として、奥側にあるものから先に描画し、後から手前にあるものを描画するという、Zソートベースの画家のアルゴリズムがある。すなわち、背景から前景へと上に重ねるようにオブジェクトを描画していく方法である。しかし、この方法では後で隠れてしまう部分まで描画するなど、時間を浪費している面があり、また全てのオブジェクトが正しく描画されるわけではない。
Zバッファを使えば、画家のアルゴリズムでの描画順序決定のステップを省略してもシーンを正しく描画できるが、メモリを多く必要とするという問題がある。BSP木はオブジェクトを分割することで画家のアルゴリズムでZバッファなしでも正しく描画できるようにし、オブジェクトをソートする手間を省くことができる。すなわち、簡単な木構造の走査によって正しい描画順序が得られる。また、重ね描きを削減するための visibility list などの他のアルゴリズムの基盤としても機能する。
欠点は、事前処理に時間がかかる点で、そのためBSP木上で移動するオブジェクトを直接実装するのは困難であり、効率が悪い。その場合、BSP木とZバッファを併用し、背景となるシーン上でドアやモンスターといった動くオブジェクトをZバッファで正しくマージする。
BSP木は3Dコンピュータゲームでよく使われ、特にファーストパーソン・シューティングゲームで室内環境を描画する際に使われる。BSPデータ構造を最初に使ったゲームとして『DOOM』 がある。他にもレイトレーシングや当たり判定に使われる。
BSP木は、例えば画家のアルゴリズムにおいてレンダリング性能を改善するのに使われる。木構造は任意の視点から線形時間で走査できる。
画家のアルゴリズムは視点から最も遠いポリゴンを最初に描画するので、以下のコードは木構造を底まで再帰的に走査し、ポリゴンを描画する。再帰から戻る際に視点により近いポリゴンが遠いポリゴンの上に描画される。BSP木がポリゴンを小さな断片に分割済みなので、画家のアルゴリズムの最も難しい部分は既に処理済みである。以下は、背景から前景へと木構造を走査するコード例である。
バイナリ空間分割は、条件を満たすまでシーンを再帰的に2つに分割していく。具体的な分割手法は最終的な目的によって異なる。例えば、当たり判定に使う場合、オブジェクトは容易に当たり判定できる程度にまで分割される。レンダリングにおいては、各部分が凸多角形になれば画家のアルゴリズムを使うのに十分である。
分割面と交差する線や面は2つに分割されるため、最終的なオブジェクト数は必然的に増大する。また、最終的な木構造はそれなりに平衡化されているのが望ましい。したがって、よいBSP木を正しくかつ効率的に生成するためのアルゴリズムは、実装においても最も難しい部分である。3次元空間では平面を使ってオブジェクトの表面を分割する。2次元空間では直線を使ってオブジェクトのセグメント(線分)を分割する。
下図は、複雑な多角形を一連の凸多角形に分割するプロセスを表している。各ステップで多角形をより線分の少ない多角形に分割していき、G と F は凸多角形になっているので、それ以上の分割が不要となっている。