データ構造のBSPツリー

コンピュータサイエンスでは、超平面をパーティションとして実装することにより、空間を2つの凸集合に再帰的に分割するために、バイナリ空間分割（BSP）と呼ばれる方法が実装されています。この細分化のプロセスにより、BSPツリーと呼ばれるツリーデータ構造の形式で領域内のオブジェクトが表現されます。

バイナリ空間分割は、1969年に3Dコンピュータグラフィックスのコンテキストで発明されました。BSPツリーの構造により、レンダリングに役立つシーン内のオブジェクトに関する空間情報が可能になります。たとえば、オブジェクトは前から後ろに並べられます。すばやくアクセスできるように、特定の場所にいる視聴者を尊重します。 BSPの他のアプリケーションには、CADでの形状（構成的ソリッドジオメトリ）による幾何学的操作の実現、3Dビデオゲームとロボット工学での衝突検出、レイトレーシング、および複雑な空間シーンの処理を伴うその他のアプリケーションが含まれます。

概要

バイナリ空間分割は、分割が1つ以上の要件を満たすまで、シーンを2つに再帰的に分割する一般的なプロセスとして扱われます。これは、k-dツリーやクアッドツリーのように座標軸に揃えるのではなく、空間を分割する超平面が任意の方向を向いている、k-dツリーやクアッドツリーなどの他の空間ツリー構造の一般化と見なすことができます。平面ポリゴンで構成されるシーンをレンダリングするためにコンピュータグラフィックスに実装される場合、分割平面は、シーン内のポリゴンによって定義された平面と一致するように選択されることがよくあります。分割平面の具体的な選択と分割プロセスを完了するための基準は、BSPツリーの目的によって異なります。たとえば、コンピュータグラフィックスのレンダリングでは、BSPツリーの各ノードが任意の順序でレンダリングできるポリゴンのみで構成されている場合を除いて、シーンは分割されます。したがって、裏面カリングが実装されている場合、各ノードは凸状のポリゴンセットで構成されますが、両面ポリゴンをレンダリングする場合、BSPツリーの各ノードは単一平面内のポリゴンのみで構成されます。衝突検出またはレイトレーシングでは、シーンをいくつかのプリミティブに分割して、衝突または光線の交差テストを簡単に行うことができます。

生成

BSPツリーの標準的な実装は、画家のアルゴリズムを使用してポリゴン（両面、つまり裏面カリングなし）をレンダリングするためのものです。各ポリゴンは、表側と裏側で指定されます。これらは任意に選択でき、ツリーの構造にのみ影響し、必要な結果には影響しません。このようなツリーは、シーン内のすべてのポリゴンのソートされていないリストから構築されます。そのポリゴンのリストからBSPツリーを構築するための再帰的アルゴリズムは

• リストからポリゴンAを選択します。
• BSPツリーにノードNを構築し、そのノードのポリゴンのリストにAを追加します。
• リストの相互ポリゴンについて
• そのポリゴンがAを含む平面の完全に前にある場合は、そのポリゴンをAの前のノードのリストに移動します。
• そのポリゴンがAを含む平面の完全に後ろにある場合は、そのポリゴンをPの後ろのノードのリストに移動します。
• そのポリゴンがAで構成される平面と交差している場合は、それを2つのポリゴンに分割し、Pの前後にあるそれぞれのポリゴンのリストに移動します。
• そのポリゴンがAを含む平面内にある場合は、ノードNのポリゴンのリストに追加します。
• このアルゴリズムをAの前にあるポリゴンのリストに適用します。
• このアルゴリズムをAの後ろにあるポリゴンのリストに適用します。