バイナリ空間分割

バイナリ空間分割（バイナリくうかんぶんかつ、英: binary space partitioning、BSP）は、（N次元）空間の（(N-1)次元）超平面での分割を再帰的に繰返し、何らかの目的に適したデータ構造を構築する手法である。3次元コンピュータグラフィックスへの応用では、シーンをBSP木（BSP tree）と呼ばれる木構造による表現に変換する。

元々は、画家のアルゴリズムのために、シーンを前処理しておくことで効率を向上させる手段として提案されたものである。つまり、あらかじめシーン中に存在する全てのポリゴンについて、ある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

その他の空間分割構造

BSP木は空間を各ノードで2つの部分領域に分割していく。これに関連して、4つに分割する四分木や8つに分割する八分木がある。

関係表

名前	p	s
バイナリ空間分割	1	2
四分木	2	4
八分木	3	8

ここで、p は使われる分割面の数、s は形成される部分領域の数である。

BSP木は任意の次元の空間に使えるが、四分木と八分木はそれぞれ2次元空間と3次元空間の分割に特化している。これらと似ているが、任意の次元で使えるものとしてkd木がある。

年表^[2]

• 1969年 Schumacker は、仮想環境内に注意深く置かれた平面によってポリゴンの順序付けを高速化する方法を発表した。この技法は、例えば平面の向こう側にある遠いポリゴンが近いポリゴンを覆い隠すことができないという性質を利用したものである。
• 1980年 Fuchs らは Schumacker のアイデアを洗練させ、ポリゴンと一致した状態にある平面を使って仮想環境を仕切る前処理を定式化した。この前処理によって生成される階層的なポリゴンデータベースをバイナリ空間分割木（BSP木）と呼んだ^[3]。
• 1983年 Fuchs らはBSP木の生成方法と高速レンダリングへの応用を論じた。
• 1987年 Thibault と Naylor はBSP木を使った任意の多面体の表現方法の概略を示した。これにより Constructive Solid Geometry (CSG) への応用が生まれた。
• 1990年 Teller と Séquin は、直交2次元環境での可視面判定を高速化するため、オフラインの Potentially Visible Set (PVS) 生成法を提案した。
• 1991年 Gordon と Chen は、従来からの背景から前景へと描いていく方法（画家のアルゴリズム）ではなく、BSP木を使って前景から背景へと効率的に描く方法を考案した^[4]。彼らはレンダリング済みの部分とレンダリングすべき部分を効率的に記録する特殊なデータ構造を利用した。この研究成果は、John Carmack の DOOM に使われた。
• 1992年 Teller は博士論文で、任意の3Dポリゴン環境でのオフラインの可視面判定のためのPVSの効率的生成と利用を論じた。
• 1993年 Hayder Radha は博士論文で、BSP木を使った写真画像表現を論じた。これには、任意の画像を扱える最適BSP木構築フレームワークの開発が含まれている。このフレームワークはLPL変換 (Least-Square-Error Partitioning Line transform) という画像変換法に基づいている。また、Radha は最適レート歪み(RD)画像圧縮フレームワークとBSP木を使った画像操作法も開発した。

脚注

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.

参考文献

• Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000年). Computational Geometry (2nd revised edition ed.). Springer-Verlag. ISBN 3-540-65620-0  Section 12: Binary Space Partitions: pp.251–265. Describes a randomized Painter's Algorithm.
• H. Radha, "Efficient Image Representation using Binary Space Partitioning Trees.", Ph.D. Thesis, Columbia University, 1993.
• H. Radha, M. Vetterli, and R. Leoonardi, “Image Compression Using Binary Space Partitioning Trees,” IEEE Transactions on Image Processing, vol. 5, No.12, December 1996, pp. 1610-1624.
• H. Radha, M. Vetterli, and R. Leoonardi, “Fast Piecewise Constant Approximation of Images,” SPIE Visual Communications and Image Processing 1991, vol. 1605, pp. 475-486.

外部リンク

• BSP trees presentation
• Another BSP trees presentation (PDF)
• A Java applet which demonstrates the process of tree generation
• A Master Thesis about BSP generating