バイナリ空間分割

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

バイナリ空間分割は、 1969年に3Dコンピュータグラフィックスの分野で開発されました。^[1]^[2] BSPツリーの構造は、特定の場所にいる視聴者に対してオブジェクトが前から後ろに順序付けられているなど、シーン内のオブジェクトに関する空間情報を効率的に提供できるため、レンダリングに役立ちます。BSPの他の用途には、 CADでの形状（構成的立体幾何学）の幾何学的操作の実行、^[3]ロボット工学や3Dビデオゲームでの衝突検出、レイトレーシング、仮想風景シミュレーション、^[4]および複雑な空間シーンの処理を伴うその他のアプリケーションがあります。

歴史

1969年、シューマッカーら^[1]は、仮想環境内で慎重に配置された平面を使用してポリゴンの順序付けを高速化する方法について説明したレポートを発表しました。この手法では、平面の反対側にあるポリゴンが、近くのポリゴンを遮ることはできないという深度コヒーレンスを利用しました。これは、GE、エバンス、サザーランドのフライトシミュレータで使用されました。ただし、ポリゴンデータの編成は、シーンデザイナーによって手動で実行されました。

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

概要

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

分割平面の具体的な選択と分割プロセスを終了する基準は、BSP ツリーの目的によって異なります。たとえば、コンピュータグラフィックスのレンダリングでは、BSP ツリーの各ノードに任意の順序でレンダリングできるポリゴンのみが含まれるまでシーンが分割されます。したがって、バックフェースカリングを使用する場合、各ノードにはポリゴンの凸セットが含まれますが、両面ポリゴンをレンダリングする場合は、BSP ツリーの各ノードには単一平面のポリゴンのみが含まれます。衝突検出またはレイトレーシングでは、衝突またはレイ交差テストが簡単なプリミティブにシーンを分割できます。

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

世代

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

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

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

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

トラバーサル

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

現在のノードがリーフノードの場合、現在のノードでポリゴンをレンダリングします。
それ以外の場合、表示位置Vが現在のノードより前にある場合:
1. 現在のノードの背後にあるポリゴンを含む子BSPツリーをレンダリングします。
2. 現在のノードのポリゴンをレンダリングする
3. 現在のノードの前にあるポリゴンを含む子BSPツリーをレンダリングします。
それ以外の場合、表示位置Vが現在のノードより後ろにある場合:
1. 現在のノードの前にあるポリゴンを含む子BSPツリーをレンダリングします。
2. 現在のノードのポリゴンをレンダリングする
3. 現在のノードの背後にあるポリゴンを含む子BSPツリーをレンダリングします。
それ以外の場合、表示位置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 (id Tech 1)、Quake (id Tech 2 の派生)、GoldSrc、Sourceエンジンなどがあります。これらのエンジンでは、シーンの静的ジオメトリを含む BSP ツリーがZ バッファとともに使用されることが多く、ドアやキャラクターなどの可動オブジェクトを背景シーンに正しくマージします。バイナリ空間分割は、シーン内のポリゴンに関する空間情報を保存および取得する便利な方法を提供しますが、可視面の決定の問題は解決しません。BSP ツリーは画像圧縮にも適用されています。^[5]

参照

kdツリー
オクトリー
クワッドツリー
階層的クラスタリングは、効率的なレンダリングのために3D モデルデータを分割する別の方法です。
ギロチン切断

参考文献

^ ab Schumacker, RA; Brand, B.; Gilliland, MG; Sharp, WH (1969). コンピュータ生成画像を視覚シミュレーションに適用するための研究 (レポート)。米国空軍人事研究所。AFHRL-TR-69-14。
^ abcdefg Fuchs, Henry; Kedem, Zvi. M; Naylor, Bruce F. (1980). 「事前ツリー構造による可視表面生成について」(PDF) . SIGGRAPH '80 Proceedings of the 7th annual conference on Computer graphics and interactive technologies . ACM. pp. 124–133. doi :10.1145/965105.807481.
^ ab Thibault, William C.; Naylor, Bruce F. (1987). 「バイナリ空間分割木を使用した多面体に対する集合演算」SIGGRAPH '87 Proceedings of the 14th annual conference on Computer graphics and interactive technologies . ACM. pp. 153–162. doi :10.1145/37402.37421.
^ Etherington, Thomas R.; Morgan, Fraser J.; O'Sullivan, David (2022). 「バイナリ空間分割により、人間が支配する景観に適した階層的かつ直線的な中立景観モデルが生成される」. Landscape Ecology . 37 (7): 1761–1769. Bibcode :2022LaEco..37.1761E. doi : 10.1007/s10980-022-01452-6 .
^ H. Radha、M. Vetterli、R. Leonardi、「バイナリ空間分割ツリーを使用した画像圧縮」、IEEE Transactions on Image Processing、vol. 5、no. 12、pp. 1610-1624、1996 年 12 月、doi: 10.1109/83.544569。

追加参考文献

Naylor, B.; Amanatides, J.; Thibault, W. (1990 年 8 月). 「BSP ツリーのマージにより多面体集合演算が実現」. ACM SIGGRAPH コンピュータグラフィックス. 24 (4): 115–124. CiteSeerX 10.1.1.69.292 . doi :10.1145/97880.97892.
Naylor, B. (1993 年 5 月)。「適切な分割ツリーの構築」。グラフィックスインターフェイス。CiteSeerX 10.1.1.16.4432 。^{[リンク切れ‍ ]}
Chen, S.; Gordon, D. (1991 年 9 月)。「BSP ツリーのフロントツーバック表示」IEEE コンピュータグラフィックスとアプリケーション11 ( 5): 79–85. doi :10.1109/38.90569. S2CID 19056967。
Radha, H.; Leoonardi, R.; Vetterli, M.; Naylor, B. (1991). 「画像のバイナリ空間分割木表現」. Journal of Visual Communications and Image Processing . 2 (3): 201–221. doi : 10.1016/1047-3203(91)90023-9 .
Radha, HMS (1993)。バイナリ空間分割ツリーを使用した効率的な画像表現(PhD)。コロンビア大学。OCLC 30775044 。
Radha, HMS (1994). 「バイナリ空間分割木を使用した効率的な画像表現」.信号処理. 35 (2): 174–181. Bibcode :1994SigPr..35..174R. doi :10.1016/0165-1684(94)90047-7.
Radha, H.; Vetterli, M .; Leoonardi , R. (1996 年 12 月)。「バイナリ空間分割ツリーを使用した画像圧縮」。IEEE Transactions on Image Processing。5 ( 12): 1610–24。Bibcode : 1996ITIP ....5.1610R。doi :10.1109/83.544569。PMID 18290079 。https://ui.adsabs.harvard.edu/abs/1996ITIP....5.1610R/abstract
Winter, AS (1999 年 4 月)。「BSP ツリーを使用したリアルタイム 3D ポリゴンレンダリングの調査」。CiteSeerX 10.1.1.11.9725 。
de Berg, M. ; van Kreveld, M. ; Overmars, M. ; Schwarzkopf, O. (2000). 「§12: バイナリ空間分割」.計算幾何学(第 2 版). Springer-Verlag . pp. 251–265. ISBN 978-3-540-65620-3。ランダム化されたペインターのアルゴリズムについて説明します。
Ericson, Christer (2005)。「8. BSP ツリー階層」。リアルタイム衝突検出。Morgan Kaufmann インタラクティブ 3D テクノロジーシリーズ。Morgan Kaufmann。pp. 349–382。ISBN 1-55860-732-3。

外部リンク

Naylor, BF (2005)。「バイナリ空間分割ツリーのチュートリアル」
BSPツリーのプレゼンテーション
別の BSP ツリーのプレゼンテーション
ツリー生成のプロセスを示すJavaアプレット
BSP生成に関する修士論文
BSP ツリー: 理論と実装
3D空間におけるBSP
グラフィックスの宝石 V: BSP ツリーを歩く

[schumacker69-1] Schumacker, RA; Brand, B.; Gilliland, MG; Sharp, WH (1969). コンピュータ生成画像を視覚シミュレーションに適用するための研究 (レポート)。米国空軍人事研究所。AFHRL-TR-69-14。

[fuchs80-2] Fuchs, Henry; Kedem, Zvi. M; Naylor, Bruce F. (1980). 「事前ツリー構造による可視表面生成について」(PDF) . SIGGRAPH '80 Proceedings of the 7th annual conference on Computer graphics and interactive technologies . ACM. pp. 124–133. doi :10.1145/965105.807481.

[thibault87-3] Thibault, William C.; Naylor, Bruce F. (1987). 「バイナリ空間分割木を使用した多面体に対する集合演算」SIGGRAPH '87 Proceedings of the 14th annual conference on Computer graphics and interactive technologies . ACM. pp. 153–162. doi :10.1145/37402.37421.

[4] Etherington, Thomas R.; Morgan, Fraser J.; O'Sullivan, David (2022). 「バイナリ空間分割により、人間が支配する景観に適した階層的かつ直線的な中立景観モデルが生成される」. Landscape Ecology . 37 (7): 1761–1769. Bibcode :2022LaEco..37.1761E. doi : 10.1007/s10980-022-01452-6 .

[5] H. Radha、M. Vetterli、R. Leonardi、「バイナリ空間分割ツリーを使用した画像圧縮」、IEEE Transactions on Image Processing、vol. 5、no. 12、pp. 1610-1624、1996 年 12 月、doi: 10.1109/83.544569。