バイナリ空間分割

は、（N次元）空間の（(N-1)次元）超平面での分割を再帰的に繰返し、何らかの目的に適したデータ構造を構築する手法である。3次元コンピュータグラフィックスへの応用では、シーンをBSP木（BSP tree）と呼ばれる木構造による表現に変換する。
元々は、画家のアルゴリズムのために、シーンを前処理しておくことで効率を向上させる手段として提案されたものである。つまり、あらかじめシーン中に存在する全てのポリゴンについて、ある1枚のポリゴンを「根」として、残りのポリゴンについて、そのポリゴンより表側にあるか、裏側にあるかという分類を再帰的に適用して、2分木に構成してしまえば（両側にまたがっている場合には分割してしまう）、描画する時には、画家のアルゴリズムであれば、各ポリゴンについてカメラ（視点）が表と裏のどちらにあるかに応じて、そのポリゴンより奥側にあるものをまず先に描き、後から手前にあるものを描けばよい。
他にも、CADにおける図形処理、ロボット工学や3Dコンピュータゲームでの衝突判定、その他の複雑な形状を扱うコンピュータアプリケーションなどといった応用がある。
概要.
コンピュータグラフィックスにおいては、シーンを正しくかつ素早く描画したい。単純な方法として、奥側にあるものから先に描画し、後から手前にあるものを描画するという、Zソートベースの画家のアルゴリズムがある。すなわち、背景から前景へと上に重ねるようにオブジェクトを描画していく方法である。しかし、この方法では後で隠れてしまう部分まで描画するなど、時間を浪費している面があり、また全てのオブジェクトが正しく描画されるわけではない。
Zバッファを使えば、画家のアルゴリズムでの描画順序決定のステップを省略してもシーンを正しく描画できるが、メモリを多く必要とするという問題がある。BSP木はオブジェクトを分割することで画家のアルゴリズムでZバッファなしでも正しく描画できるようにし、オブジェクトをソートする手間を省くことができる。すなわち、簡単な木構造の走査によって正しい描画順序が得られる。また、重ね描きを削減するための visibility list などの他のアルゴリズムの基盤としても機能する。
欠点は、事前処理に時間がかかる点で、そのためBSP木上で移動するオブジェクトを直接実装するのは困難であり、効率が悪い。その場合、BSP木とZバッファを併用し、背景となるシーン上でドアやモンスターといった動くオブジェクトをZバッファで正しくマージする。
BSP木は3Dコンピュータゲームでよく使われ、特にファーストパーソン・シューティングゲームで室内環境を描画する際に使われる。BSPデータ構造を最初に使ったゲームとして『DOOM』 がある。他にもレイトレーシングや当たり判定に使われる。
生成.
バイナリ空間分割は、条件を満たすまでシーンを再帰的に2つに分割していく。具体的な分割手法は最終的な目的によって異なる。例えば、当たり判定に使う場合、オブジェクトは容易に当たり判定できる程度にまで分割される。レンダリングにおいては、各部分が凸多角形になれば画家のアルゴリズムを使うのに十分である。
分割面と交差する線や面は2つに分割されるため、最終的なオブジェクト数は必然的に増大する。また、最終的な木構造はそれなりに平衡化されているのが望ましい。したがって、よいBSP木を正しくかつ効率的に生成するためのアルゴリズムは、実装においても最も難しい部分である。3次元空間では平面を使ってオブジェクトの表面を分割する。2次元空間では直線を使ってオブジェクトのセグメント（線分）を分割する。
下図は、複雑な多角形を一連の凸多角形に分割するプロセスを表している。各ステップで多角形をより線分の少ない多角形に分割していき、G と F は凸多角形になっているので、それ以上の分割が不要となっている。この場合、分割線は多角形の既存の頂点を通るように選ばれており、線分と交差していない。分割線が線分と交差する場合（3次元の場合、面と交差する場合）、その線分（面）は分割線（面）で2つに分けられ、それぞれが別々の独立したオブジェクトの一部となる。
BSP木の有効性はその生成方法に依存するので、よいアルゴリズムが必須である。多くのアルゴリズムは、うまい分割を見つけるまで様々な可能性をテストし、場合によってはバックトラッキングして分割をやり直すこともある。そのため、バイナリ空間分割には一般に時間がかかる。
BSP木は写真画像を表すのにも使われた。BSP木を写真画像に適用すると、数百のノードで数百万ピクセルの画像を表せるため、効率的な表現方法として導入された。コンピュータビジョンや信号処理のアルゴリズムを使ってBSP木を構築する高速アルゴリズムも開発された。それらのアルゴリズムと高度なエントロピー符号と信号近似手法を組み合わせた画像圧縮法も開発された。
BSP木の可視性情報によるシーンのレンダリング.
BSP木は、例えば画家のアルゴリズムにおいてレンダリング性能を改善するのに使われる。木構造は任意の視点から線形時間で走査できる。
画家のアルゴリズムは視点から最も遠いポリゴンを最初に描画するので、以下のコードは木構造を底まで再帰的に走査し、ポリゴンを描画する。再帰から戻る際に視点により近いポリゴンが遠いポリゴンの上に描画される。BSP木がポリゴンを小さな断片に分割済みなので、画家のアルゴリズムの最も難しい部分は既に処理済みである。以下は、背景から前景へと木構造を走査するコード例である。
procedure Tree_traverse (tree:bsp_tree, eye:point) is
begin
 if not Tree_isEmpty (tree) then
 constant location : integer = Tree_getLocation (tree, eye) ;
 -- eye が location の前にある場合
 if 0 < location then
 Tree_traverse (tree.back, eye) ;
 display (tree.polygon_list) ;
 Tree_traverse (tree.front, eye)
 -- eye が location の後ろにある場合
 else if location < 0 then
 Tree_traverse (tree.front, eye) ;
 display (tree.polygon_list) ;
 Tree_traverse (tree.back, eye)
 -- eye が分割超平面上にある場合
 else
 Tree_traverse (tree.front, eye) ;
 Tree_traverse (tree.back, eye)
 end if ;
 end if ;
end
その他の空間分割構造.
BSP木は空間を各ノードで2つの部分領域に分割していく。これに関連して、4つに分割する四分木や8つに分割する八分木がある。
ここで、"p" は使われる分割面の数、"s" は形成される部分領域の数である。
BSP木は任意の次元の空間に使えるが、四分木と八分木はそれぞれ2次元空間と3次元空間の分割に特化している。これらと似ているが、任意の次元で使えるものとして"k"d木がある。