バイナリ空間分割
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/09/20 07:57 UTC 版)
（バイナリくうかんぶんかつ、英: binary space partitioning、BSP）は、（N次元）空間の（(N-1)次元）超平面での分割を再帰的に繰返し、何らかの目的に適したデータ構造を構築する手法である。3次元コンピュータグラフィックスへの応用では、シーンをBSP木（BSP tree）と呼ばれる木構造による表現に変換する。
- ^ Binary Space Partition Trees in 3d worlds
- ^ AN INVESTIGATION INTO REAL-TIME 3D POLYGON RENDERING USING BSP TREES. Andrew Steven Winter. April 1999. available online
- ^ H. Fuchs, Z. M. Kedem and B. F. Naylor. “On Visible Surface Generation by A Priori Tree Structures.” ACM Computer Graphics, pp 124–133. July 1980.
- ^ S. Chen and D. Gordon. “Front-to-Back Display of BSP Trees.” IEEE Computer Graphics & Algorithms, pp 79–85. September 1991.
- 1 バイナリ空間分割とは
- 2 バイナリ空間分割の概要
- 3 その他の空間分割構造
- 4 参考文献
- 5 外部リンク
バイナリ空間分割
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/02 01:09 UTC 版)
「Doom engine」の記事における「バイナリ空間分割」の解説
Doomは、バイナリ空間分割（BSP）と呼ばれるシステムを利用している。ツールを使用して、事前にステージのBSPデータを生成する。このプロセスは大きなステージではかなり時間がかかる場合があるため、Doomでは壁を移動することはできない。ドアとリフトは上下に動くが、どれも横には動かない。 レベルはバイナリツリーに分割される。ツリー内の各位置はステージの特定の領域を表す「ノード」である（ルートノードはステージ全体を表す）。ツリーの各分岐には、ノードの領域を2つのサブノードに分割する分割線がある。同時に、この分割線はlinedefを「seg」と呼ばれるラインセグメントに分割する。 ツリーの葉には凸多角形があり、ステージをさらに分割する必要はない。これらの凸多角形はサブセクター（または「Sセクター」）と呼ばれ、特定のセクターにバインドされる。各サブセクターには、関連するsegのリストがある。 BSPシステムは、サブセクターをレンダリングに適した順序に並べ替える。アルゴリズムはかなり単純である： ルートノードから開始する。 このノードの子ノードを再帰的に描画する。カメラに最も近い子ノードは、スキャンラインアルゴリズムを使用して最初に描画される。これは、カメラがノードの分割線のどちら側にあるかを見ることで分かる。 サブセクターに達したら、そのサブセクターを描画する。 ピクセルの列全体が満たされる（つまり、これ以上隙間が残らなくなる）と、プロセスは完了する。この順序付けにより、表示されていないオブジェクトの描画に時間を費やすことがなくなり、その結果、速度のペナルティなしにマップを非常に大きくすることができる。
※この「バイナリ空間分割」の解説は、「Doom engine」の解説の一部です。
「バイナリ空間分割」を含む「Doom engine」の記事については、「Doom engine」の概要を参照ください。
- バイナリ空間分割のページへのリンク
