BSPツリー（空間分割木）とは？データ構造の基本原理と生成アルゴリズムを徹底解説

BSPツリーの概要

コンピュータサイエンスの分野では、バイナリ空間分割（Binary Space Partitioning：BSP）と呼ばれる手法が用いられています。これは、超平面（ハイパープレーン）を分割面として使用し、空間を再帰的に2つの凸集合へと分割していく方法です。この分割処理を繰り返すことで、領域内のオブジェクトを木構造（ツリー構造）として表現できるようになります。このデータ構造がBSPツリーです。

バイナリ空間分割は、1969年に3Dコンピュータグラフィックスの文脈で考案されました。BSPツリーの構造により、シーン内のオブジェクトに関する空間情報を高速に参照することが可能になります。例えば、特定の視点位置から見て「手前から奥へ」という順序でオブジェクトを並べ替えるといった処理は、レンダリングにおいて非常に有用です。

BSPツリーの主な応用分野には、以下のようなものがあります。

• CADにおけるソリッドモデリング（CSG：構成的ソリッドジオメトリ）など、形状に対する幾何演算
• 3Dゲームやロボティクスにおける衝突判定
• レイトレーシング（光線追跡法）
• 複雑な空間シーンを扱うその他 various 応用

BSPツリーの特徴とk-d木・クアッドツリーとの関係

バイナリ空間分割は、シーンを要求条件を満たすまで2つずつ再帰的に分割していく汎用的なプロセスと捉えられます。k-d木やクアッドツリーといった他の空間木構造の一般化と見ることもできます。

両者の大きな違いは、分割面（超平面）の向きにあります。k-d木やクアッドツリーでは分割面が座標軸に平行に制限されますが、BSPツリーでは任意の向きの超平面を採用できるため、より柔軟な空間分割が可能です。

コンピュータグラフィックスで平面ポリゴンから構成されるシーンを描画する場合、分割面はシーン内のポリゴンが定義する平面と一致するように選ばれることが一般的です。どの分割面を選び、いつ分割処理を完了させるかという基準は、BSPツリーの目的によって異なります。

用途別の分割基準

• グラフィックスレンダリングの場合： BSPツリーの各ノードに含まれるポリゴンが任意の順序で描画できる状態になるまで分割を続けます。バックフェイスカリング（裏面カリング）を行う場合は各ノードが凸多角形の集合となり、両面ポリゴンを描画する場合は各ノードが同一平面上のポリゴンのみを持つようになります。
• 衝突判定やレイトレーシングの場合： 衝突テストや交差判定を簡単に行えるプリミティブ単位になるようシーンを分割します。

BSPツリーの生成アルゴリズム

BSPツリーの代表的な実装例は、ペインターズアルゴリズム（画家のアルゴリズム）を用いた両面ポリゴンのレンダリングです。

まず、各ポリゴンに表側と裏側を割り当てます。この表裏の選択は任意であり、結果には影響せず、ツリーの構造だけが変化します。このようなBSPツリーは、シーン内の全ポリゴンを含む未整列のリストから構築されます。ポリゴンのリストからBSPツリーを構築する再帰的アルゴリズムは以下の通りです。

構築手順

1. リストの中から1つのポリゴンAを選択します。
2. BSPツリーにノードNを構築し、そのノードのポリゴンリストにAを追加します。
3. リスト内の残りの各ポリゴンについて以下を判定します。
4. ポリゴン全体がAを含む平面より完全に前方にある場合 → Aの前方ノードリストへ移動します。
5. ポリゴン全体がAを含む平面より完全に後方にある場合 → 後方ノードリストへ移動します。
6. Aを含む平面がポリゴンと交差している場合 → ポリゴンを2つに分割し、それぞれ前方リストと後方リストへ移動します。
7. ポリゴンがAを含む平面上にある場合 → ノードNのポリゴンリストに追加します。
8. Aの前方にあるポリゴンのリストに対して同じアルゴリズムを再帰的に適用します。
9. Aの後方にあるポリゴンのリストに対しても同様に再帰的に適用します。

この処理を再帰的に繰り返すことで、シーン全体を階層的に分割したBSPツリーが完成します。完成したツリーをトラバースすることで、視点からの奥行き順序を効率的に求めることができ、隠面消去や正しい描画順序の決定が高速に行えます。