バイナリ空間分割 バイナリ空間分割の概要

バイナリ空間分割

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/09/20 07:57 UTC 版)

ナビゲーションに移動 検索に移動

元々は、画家のアルゴリズムのために、シーンを前処理しておくことで効率を向上させる手段として提案されたものである。つまり、あらかじめシーン中に存在する全てのポリゴンについて、ある1枚のポリゴンを「根」として、残りのポリゴンについて、そのポリゴンより表側にあるか、裏側にあるかという分類を再帰的に適用して、2分木に構成してしまえば(両側にまたがっている場合には分割してしまう)、描画する時には、画家のアルゴリズムであれば、各ポリゴンについてカメラ(視点)が表と裏のどちらにあるかに応じて、そのポリゴンより奥側にあるものをまず先に描き、後から手前にあるものを描けばよい。

他にも、CADにおける図形処理、ロボット工学や3Dコンピュータゲームでの衝突判定、その他の複雑な形状を扱うコンピュータアプリケーションなどといった応用がある。

概要

コンピュータグラフィックスにおいては、シーンを正しくかつ素早く描画したい。単純な方法として、奥側にあるものから先に描画し、後から手前にあるものを描画するという、Zソートベースの画家のアルゴリズムがある。すなわち、背景から前景へと上に重ねるようにオブジェクトを描画していく方法である。しかし、この方法では後で隠れてしまう部分まで描画するなど、時間を浪費している面があり、また全てのオブジェクトが正しく描画されるわけではない。

Zバッファを使えば、画家のアルゴリズムでの描画順序決定のステップを省略してもシーンを正しく描画できるが、メモリを多く必要とするという問題がある。BSP木はオブジェクトを分割することで画家のアルゴリズムでZバッファなしでも正しく描画できるようにし、オブジェクトをソートする手間を省くことができる。すなわち、簡単な木構造の走査によって正しい描画順序が得られる。また、重ね描きを削減するための visibility list などの他のアルゴリズムの基盤としても機能する。

欠点は、事前処理に時間がかかる点で、そのためBSP木上で移動するオブジェクトを直接実装するのは困難であり、効率が悪い。その場合、BSP木とZバッファを併用し、背景となるシーン上でドアやモンスターといった動くオブジェクトをZバッファで正しくマージする。

BSP木は3Dコンピュータゲームでよく使われ、特にファーストパーソン・シューティングゲームで室内環境を描画する際に使われる。BSPデータ構造を最初に使ったゲームとして『DOOM』 がある。他にもレイトレーシング当たり判定に使われる。

生成

バイナリ空間分割は、条件を満たすまでシーンを再帰的に2つに分割していく。具体的な分割手法は最終的な目的によって異なる。例えば、当たり判定に使う場合、オブジェクトは容易に当たり判定できる程度にまで分割される。レンダリングにおいては、各部分が凸多角形になれば画家のアルゴリズムを使うのに十分である。

分割面と交差する線や面は2つに分割されるため、最終的なオブジェクト数は必然的に増大する。また、最終的な木構造はそれなりに平衡化されているのが望ましい。したがって、よいBSP木を正しくかつ効率的に生成するためのアルゴリズムは、実装においても最も難しい部分である。3次元空間では平面を使ってオブジェクトの表面を分割する。2次元空間では直線を使ってオブジェクトのセグメント(線分)を分割する。

下図は、複雑な多角形を一連の凸多角形に分割するプロセスを表している。各ステップで多角形をより線分の少ない多角形に分割していき、G と F は凸多角形になっているので、それ以上の分割が不要となっている。この場合、分割線は多角形の既存の頂点を通るように選ばれており、線分と交差していない。分割線が線分と交差する場合(3次元の場合、面と交差する場合)、その線分(面)は分割線(面)で2つに分けられ、それぞれが別々の独立したオブジェクトの一部となる。

1. A は木構造の根であり、多角形全体に対応
2. A を B と C に分割
3. B を D と E に分割
4. D を F と G に分割。これらは凸多角形なのでそのまま葉となる。

BSP木の有効性はその生成方法に依存するので、よいアルゴリズムが必須である。多くのアルゴリズムは、うまい分割を見つけるまで様々な可能性をテストし、場合によってはバックトラッキングして分割をやり直すこともある。そのため、バイナリ空間分割には一般に時間がかかる。

BSP木は写真画像を表すのにも使われた。BSP木を写真画像に適用すると、数百のノードで数百万ピクセルの画像を表せるため、効率的な表現方法として導入された。コンピュータビジョン信号処理のアルゴリズムを使ってBSP木を構築する高速アルゴリズムも開発された。それらのアルゴリズムと高度なエントロピー符号と信号近似手法を組み合わせた画像圧縮法も開発された。

BSP木の可視性情報によるシーンのレンダリング

BSP木は、例えば画家のアルゴリズムにおいてレンダリング性能を改善するのに使われる。木構造は任意の視点から線形時間で走査できる。

画家のアルゴリズムは視点から最も遠いポリゴンを最初に描画するので、以下のコードは木構造を底まで再帰的に走査し、ポリゴンを描画する。再帰から戻る際に視点により近いポリゴンが遠いポリゴンの上に描画される。BSP木がポリゴンを小さな断片に分割済みなので、画家のアルゴリズムの最も難しい部分は既に処理済みである。以下は、背景から前景へと木構造を走査するコード例である[1]

procedure Tree_traverse (tree:bsp_tree, eye:point) is
begin
  if not Tree_isEmpty (tree) then
    constant location : integer = Tree_getLocation (tree, eye) ;

    -- eye が location の前にある場合
    if 0 < location then
      Tree_traverse (tree.back, eye) ;
      display       (tree.polygon_list) ;
      Tree_traverse (tree.front, eye)

    -- eye が location の後ろにある場合
    else if location < 0 then
      Tree_traverse (tree.front, eye) ;
      display       (tree.polygon_list) ;
      Tree_traverse (tree.back, eye)

    -- eye が分割超平面上にある場合
    else
      Tree_traverse (tree.front, eye) ;
      Tree_traverse (tree.back, eye)
    end if ;
  end if ;
end

  1. ^ Binary Space Partition Trees in 3d worlds
  2. ^ AN INVESTIGATION INTO REAL-TIME 3D POLYGON RENDERING USING BSP TREES. Andrew Steven Winter. April 1999. available online
  3. ^ 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.
  4. ^ S. Chen and D. Gordon. “Front-to-Back Display of BSP Trees.” IEEE Computer Graphics & Algorithms, pp 79–85. September 1991.


「バイナリ空間分割」の続きの解説一覧



英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「バイナリ空間分割」の関連用語

バイナリ空間分割のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



バイナリ空間分割のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのバイナリ空間分割 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2024 GRAS Group, Inc.RSS