二分空間分割

コンピュータサイエンスにおいて、バイナリ空間分割（BSP ）は、超平面を分割点として用いてユークリッド空間を再帰的に2つの凸集合に分割する空間分割手法です。この分割プロセスによって、空間内のオブジェクトがBSPツリーと呼ばれるツリーデータ構造の形で表現されます。

バイナリ空間分割は、 1969 年に3D コンピュータグラフィックスの文脈で開発されました。^{[ 1 ] [ 2 ]} BSP ツリーの構造は、シーン内のオブジェクトに関する空間情報を効率的に提供できるため、レンダリングに役立ちます。たとえば、特定の場所のビューアに対してオブジェクトが前から後ろに並んでいるなどです。BSP のその他のアプリケーションには、CADでの形状(構成的ソリッドジオメトリ)に対する幾何学的操作の実行、^{[ 3 ]}ロボット工学および 3D ビデオゲームでの衝突検出、レイ トレーシング、仮想景観シミュレーション、^{[ 4 ]}および複雑な空間シーンの処理を伴うその他のアプリケーションが含まれます。

• 1969年、Schumackerら^{[ 1 ]}は、仮想環境内で慎重に配置された平面を使用してポリゴンの順序付けを高速化する方法を説明するレポートを発表した。この技術は、平面の反対側にあるポリゴンが、より近いポリゴンをいかなる形でも遮ることができないという深度コヒーレンスを利用した。これは、GEやEvans and Sutherlandが作成したフライトシミュレーターで使用された。ただし、ポリゴンデータの編成はシーンデザイナーによって手動で行われた。
• 1980年、Fuchsら^{[ 2 ]}は、Schumackerのアイデアを拡張し、ポリゴンと一致する平面を使用して3D空間を再帰的に分割することで、仮想環境における3Dオブジェクトの表現を実現しました。これにより、バイナリ空間分割ツリー（BSPツリー）として知られる階層的なポリゴンデータ構造の完全自動化されたアルゴリズムによる生成が可能になりました。このプロセスは、環境/オブジェクトごとに1回実行されるオフラインの前処理ステップとして行われました。実行時には、ツリーを走査することで、ビューに依存する可視性の順序が生成されました。
• 1981年のネイラーの博士論文^{[ 5 ]}では、BSPツリーと、可視性を事前計算するための強連結成分を用いたグラフ理論的手法の両方の完全な開発、および2つの手法間の関連性が示されました。次元に依存しない空間探索構造としてのBSPツリーが強調され、可視表面の決定への応用が示されました。この論文には、ツリーのサイズと新しいポリゴンの数が妥当であることを示す最初の実証データも含まれていました（スペースシャトルのモデルを使用）。
• 1983年、Fuchsら^{[ 6 ]}は、Ikonasフレームバッファシステム上でBSPツリーアルゴリズムのマイクロコード実装について説明した。これは、BSPツリーを使用したリアルタイム可視面決定の最初の実証であった。
• 1987年、ThibaultとNaylor ^{[ 3 ]}は、従来のb-rep（境界表現）とは対照的に、BSPツリーを使用して任意の多面体を表現する方法について説明しました。これにより、表面ベースの表現ではなく、ソリッド表現が実現しました。ツールを使用して多面体に対する集合演算が記述され、リアルタイムで構成的ソリッドジオメトリ（CSG）が可能になりました。これは、Quakeエディタで導入され、Unrealエディタにも採用された「ブラシ」を使用したBSPレベルデザインの先駆けとなりました。
• 1990年、Naylor、Amanatides、およびThibault ^{[ 7 ]}は、2つのBSPツリーをマージして、元の2つのツリーから新しいBSPツリーを形成するアルゴリズムを提供しました。これにより、BSPツリーで表現される移動オブジェクトと静的環境（これもBSPツリーで表現される）の組み合わせ、多面体に対する非常に効率的なCSG操作、O(log n * log n)での正確な衝突検出、相互貫入する2つのオブジェクトに含まれる透明な表面の適切な順序付け（X線視覚効果に使用されている）など、多くの利点が得られます。
• 1991年、TellerとSéquin ^{[ 8 ]}は、直交2D環境における可視表面決定を加速するために、潜在的に可視なセットのオフライン生成を提案した。
• 1991年、ゴードンとチェン^{[ 9 ]}は、従来のバック・トゥ・フロント方式ではなく、BSPツリーからフロント・トゥ・バックのレンダリングを実行する効率的な方法を説明した。彼らは、描画済みの画面部分とまだレンダリングされていない画面部分を効率的に記録するために、特別なデータ構造を利用した。このアルゴリズムは、当時の標準的なコンピュータグラフィックスの教科書（Computer Graphics: Principles and Practice ）におけるBSPツリーの説明とともに、ジョン・カーマックがDoomの制作に使用した。
• 1992年のテラーの博士論文^{[ 10 ]}では、任意の3Dポリゴン環境におけるリアルタイムの可視面判定を高速化するための前処理ステップとして、潜在的に可視なセットを効率的に生成する方法が記述されている。これはQuakeで使用され、そのゲームのパフォーマンスに大きく貢献した。
• 1993年、ネイラー^{[ 11 ]}は、優れたBSPツリーの特徴とは何かという問いに答えた。彼は、最悪ケース分析ではなく期待ケースモデルを使用して、ツリーを探索する期待コストを数学的に測定し、この尺度を使用して優れたBSPツリーを構築した。直感的には、ツリーはオブジェクトを多重解像度方式（より正確には、近似ツリーとして）で表現する。ハフマン符号と確率的二分探索木との類似点が指摘されている。
• 1993年にHayder Radhaが発表した博士論文^{[ 12 ]}では、BSPツリーを用いた（自然）画像表現手法が記述されている。これには、任意の入力画像に対する最適なBSPツリー構築フレームワークの開発が含まれる。このフレームワークは、最小二乗誤差（LSE）分割線（LPE）変換として知られる新しい画像変換に基づいている。Radhaの論文では、BSPツリーを用いた最適なレート歪み（RD）画像圧縮フレームワークと画像操作手法も開発されている。

バイナリ空間分割は、ハイパープレーン^{[ 13 ]}を使用してシーンを再帰的に2つに分割し、分割が1つ以上の要件を満たすまで繰り返す一般的なプロセスです。これは、 k -dツリーやクワッドツリーなどの他の空間ツリー構造の一般化と見なすことができ、空間を分割するハイパープレーンは、 k -dツリーやクワッドツリーのように座標軸に沿って配置されるのではなく、任意の方向を持つことができます。コンピュータグラフィックスで平面ポリゴンで構成されるシーンをレンダリングする場合、分割平面は、シーン内のポリゴンによって定義される平面と一致するように選択されることがよくあります。

分割平面の具体的な選択と分割処理の終了基準は、BSPツリーの目的に応じて異なります。たとえば、コンピュータグラフィックスのレンダリングでは、BSPツリーの各ノードに任意の順序でレンダリング可能なポリゴンのみが含まれるまでシーンを分割します。背面カリングを使用する場合、各ノードには凸多角形の集合が含まれますが、両面多角形をレンダリングする場合は、BSPツリーの各ノードには単一平面上の多角形のみが含まれます。衝突検出やレイトレーシングでは、シーンを衝突判定やレイ交差判定が容易なプリミティブに分割することができます。

バイナリ空間分割は、ポリゴンで構成される 3 次元シーンを高速に描画する必要があったコンピュータグラフィックスから生まれました。このようなシーンを描画する簡単な方法は、ペインターアルゴリズムです。これは、ビューアからの距離の順に、奥から手前にポリゴンを生成し、背景と前のポリゴンを、より近いオブジェクトごとに塗りつぶします。このアプローチには 2 つの欠点があります。ポリゴンを奥から手前の順にソートするのに時間がかかることと、ポリゴンが重なり合う場合にエラーが発生する可能性があることです。Fuchs と共著者^{[ 2 ]}は、BSP ツリーを構築することで、指定された視点に関してポリゴンを高速にソートする方法 (シーン内のポリゴンの数に比例) と、重なり合うポリゴンを分割してペインターアルゴリズムで発生する可能性のあるエラーを回避することにより、これらの問題の両方が解決されることを示しました。バイナリ空間分割の欠点は、BSP ツリーの生成に時間がかかることです。そのため、通常は、レンダリングやシーンに対するその他のリアルタイム操作の前に、前処理ステップとして静的ジオメトリに対して 1 回実行されます。 BSPツリーの構築にはコストがかかるため、オブジェクトをツリーに直接移動させる機能を実装するのは困難で非効率的です。

BSP ツリーの標準的な用途は、ペインターのアルゴリズムを使用してポリゴン (両面ポリゴン、つまり背面カリングなし) をレンダリングすることです。各ポリゴンには、前面と背面が指定されますが、これらは任意に選択でき、ツリーの構造にのみ影響し、必要な結果には影響しません。 ^{[ 2 ]}このようなツリーは、シーン内のすべてのポリゴンのソートされていないリストから構築されます。そのポリゴンのリストから BSP ツリーを構築するための再帰アルゴリズムは次のとおりです。 ^{[ 2 ]}

1. リストから多角形Pを選択してください。
2. BSPツリーにノードNを作成し、そのノードのポリゴンリストにPを追加します。
3. リスト内の他の各ポリゴンについて：
   1. その多角形がPを含む平面の手前にある場合、その多角形をPの手前にあるノードのリストに移動します。
   2. その多角形がPを含む平面の背後に完全に位置する場合、その多角形をPの背後にあるノードのリストに移動します。
   3. その多角形が点Pを含む平面と交差する場合、それを 2 つの多角形に分割し、それぞれを点Pの後ろと前の多角形のリストに移動します。
   4. その多角形が点Pを含む平面上にある場合、それをノードNの多角形のリストに追加します。
4. このアルゴリズムをPの前の多角形のリストに適用します。
5. このアルゴリズムをPの後ろにある多角形のリストに適用します。

次の図は、このアルゴリズムを使用して線またはポリゴンのリストをBSPツリーに変換する方法を示しています。8つのステップ（i.～viii.）それぞれにおいて、上記のアルゴリズムが線のリストに適用され、ツリーに新しいノードが1つ追加されます。

分割平面を横切る線や多角形は2つに分割する必要があるため、ツリー内の最終的な多角形または線の数は、元のリストよりも大きくなることがよくあります（場合によってははるか^{に大きくなります[2 ]} ）。この増加を最小限に抑えつつ、最終的なツリーで適切なバランスを維持することが望ましいです。したがって、効率的なBSPツリーを作成するためには、どの多角形または線を分割平面として使用するか（アルゴリズムのステップ1）の選択が重要になります。

BSP ツリーは、ツリーの特定の機能によって決定される順序で、線形時間で走査されます。ペインターのアルゴリズムを使用して両面多角形をレンダリングする例を再び使用すると、多角形P を正しく描画するには、まず平面P の後ろにあるすべての多角形を描画し、次に多角形Pを描画し、最後にPの前の多角形を描画する必要があります。シーン内のすべての多角形に対してこの描画順序が満たされると、シーン全体が正しい順序でレンダリングされます。この手順は、次のアルゴリズムを使用して BSP ツリーを再帰的に走査することによって実装できます。^{[ 2 ]}指定されたビュー位置Vから、BSP ツリーをレンダリングするには、

1. 現在のノードがリーフノードである場合、現在のノードにポリゴンを描画します。
2. それ以外の場合、表示位置Vが現在のノードの手前にある場合：
   1. 現在のノードの背後にポリゴンを含む子BSPツリーをレンダリングする
   2. 現在のノードでポリゴンをレンダリングする
   3. 現在のノードの前にポリゴンを含む子BSPツリーをレンダリングする
3. それ以外の場合、表示位置Vが現在のノードの後ろにある場合：
   1. 現在のノードの前にポリゴンを含む子BSPツリーをレンダリングする
   2. 現在のノードでポリゴンをレンダリングする
   3. 現在のノードの背後にポリゴンを含む子BSPツリーをレンダリングする
4. そうでなければ、視点位置Vは現在のノードに関連付けられた平面上に正確に存在しなければならない。すると：
   1. 現在のノードの前にポリゴンを含む子BSPツリーをレンダリングする
   2. 現在のノードの背後にポリゴンを含む子BSPツリーをレンダリングする

上記で生成されたBSPツリーにこのアルゴリズムを再帰的に適用すると、以下の手順が実行されます。

• このアルゴリズムは、まずツリーのルートノードであるノードAに適用されます。VはノードAの前にあるため、まずAの後ろにあるポリゴンを含む子BSPツリーにアルゴリズムを適用します。
  • このツリーのルートノードはB1です。VはB1の後ろにあるため、まず、 B1の前にポリゴンを含む子BSPツリーにアルゴリズムを適用します。
    • この木は葉ノードD1のみなので、ポリゴンD1がレンダリングされます。
  • 次に、ポリゴンB1をレンダリングします。
  • 次に、 B1の背後にあるポリゴンを含む子BSPツリーにアルゴリズムを適用します。
    • この木は葉ノードC1のみなので、ポリゴンC1がレンダリングされます。
• 次に、 Aの多角形を描きます。
• 次に、 Aの前にポリゴンを含む子BSPツリーにアルゴリズムを適用します。
  • このツリーのルートノードはB2です。VはB2の後ろにあるため、まず、 B2の前にポリゴンを含む子BSPツリーにアルゴリズムを適用します。
    • この木は葉ノードD2のみなので、ポリゴンD2がレンダリングされます。
  • 次に、ポリゴンB2をレンダリングします。
  • 次に、 B2の背後にあるポリゴンを含む子BSPツリーにアルゴリズムを適用します。
    • このツリーのルートノードはC2です。VはC2の前にあるので、まず、 C2の後ろにあるポリゴンを含む子BSPツリーにアルゴリズムを適用します。しかし、そのようなツリーは存在しないので、処理を続行します。
    • ポリゴンC2をレンダリングします。
    • C2の前にポリゴンを含む子BSPツリーにアルゴリズムを適用します。
      • この木は葉ノードD3のみなので、ポリゴンD3がレンダリングされます。

ツリーは線形時間で走査され、ペインターのアルゴリズムに適した遠近順 ( D1、B1、C1、A、D2、B2、C2、D3 ) でポリゴンをレンダリングします。

BSPツリーは、3Dビデオゲーム、特にファーストパーソンシューターや屋内環境のあるゲームでよく使用されます。BSPツリーを使用するゲームエンジンには、 Doom、Quake、GoldSrc、Sourceエンジンなどがあります。これらのエンジンでは、シーンの静的ジオメトリを含むBSPツリーがZバッファと組み合わせて使用​​され、ドアやキャラクターなどの可動オブジェクトを背景シーンに正しくマージします。バイナリ空間分割は、シーン内のポリゴンに関する空間情報を保存および取得する便利な方法を提供しますが、可視表面決定の問題を解決しません。BSPツリーは画像圧縮にも適用されています。^{[ 14 ]}

• シャゼル多面体
• kdツリー
• オクトリー
• クアッドツリー
• 階層的クラスタリングは、効率的なレンダリングのために3Dモデルデータを分割する代替手法です。
• ギロチンによる切断

• Naylor, BF (2005). "バイナリ空間分割木に関するチュートリアル" .
• BSPツリーのプレゼンテーション
• 別のBSPツリーのプレゼンテーション
• ツリー生成のプロセスをデモンストレーションするJavaアプレット
• BSP生成に関する修士論文
• BSPツリー：理論と実装
• 3D空間におけるBSP
• Graphics Gems V: BSPツリーを巡る旅