「バイナリ空間分割」の版間の差分
編集の要約なし |
|||
(6人の利用者による、間の7版が非表示) | |||
1行目: | 1行目: | ||
'''バイナリ空間分割''' |
{{読み仮名_ruby不使用|'''バイナリ空間分割'''|バイナリくうかんぶんかつ|{{lang-en-short|binary space partitioning}}、BSP}}は、︵N次元︶[[ユークリッド空間|空間]]の︵(N-1)次元︶[[超平面]]での分割を再帰的に繰返し、何らかの目的に適したデータ構造を構築する手法である。[[3次元コンピュータグラフィックス]]への応用では、シーンを'''BSP木'''︵BSP tree︶と呼ばれる[[木構造 (データ構造)|木構造]]による表現に変換する。
|
||
<!-- |
<!-- |
||
簡単に言えば、複雑な形状の多角形を凸多角形、すなわち 180°以下の角度の頂点のみで囲まれた小さい多角形に分割する。 |
簡単に言えば、複雑な形状の多角形を凸多角形、すなわち 180°以下の角度の頂点のみで囲まれた小さい多角形に分割する。 |
||
17行目: | 17行目: | ||
欠点は、事前処理に時間がかかる点で、そのためBSP木上で移動するオブジェクトを直接実装するのは困難であり、効率が悪い。その場合、BSP木とZバッファを併用し、背景となるシーン上でドアやモンスターといった動くオブジェクトをZバッファで正しくマージする。 |
欠点は、事前処理に時間がかかる点で、そのためBSP木上で移動するオブジェクトを直接実装するのは困難であり、効率が悪い。その場合、BSP木とZバッファを併用し、背景となるシーン上でドアやモンスターといった動くオブジェクトをZバッファで正しくマージする。 |
||
BSP木は3D[[コンピュータゲーム]]でよく使われ、特に[[ファーストパーソン・シューティングゲーム]]で室内環境を描画する際に使われる。BSPデータ構造を最初に使ったゲームとして |
BSP木は3D[[コンピュータゲーム]]でよく使われ、特に[[ファーストパーソン・シューティングゲーム]]で室内環境を描画する際に使われる。BSPデータ構造を最初に使ったゲームとして『[[DOOM]]』 がある。他にも[[レイトレーシング]]や[[当たり判定]]に使われる。 |
||
== 生成 == |
== 生成 == |
||
37行目: | 37行目: | ||
画家のアルゴリズムは[[視点]]から最も遠い[[ポリゴン]]を最初に描画するので、以下のコードは木構造を底まで再帰的に走査し、ポリゴンを描画する。再帰から戻る際に視点により近いポリゴンが遠いポリゴンの上に描画される。BSP木がポリゴンを小さな断片に分割済みなので、画家のアルゴリズムの最も難しい部分は既に処理済みである。以下は、背景から前景へと木構造を走査するコード例である<ref>[http://web.cs.wpi.edu/~matt/courses/cs563/talks/bsp/document.html Binary Space Partition Trees in 3d worlds]</ref>。
|
画家のアルゴリズムは[[視点]]から最も遠い[[ポリゴン]]を最初に描画するので、以下のコードは木構造を底まで再帰的に走査し、ポリゴンを描画する。再帰から戻る際に視点により近いポリゴンが遠いポリゴンの上に描画される。BSP木がポリゴンを小さな断片に分割済みなので、画家のアルゴリズムの最も難しい部分は既に処理済みである。以下は、背景から前景へと木構造を走査するコード例である<ref>[http://web.cs.wpi.edu/~matt/courses/cs563/talks/bsp/document.html Binary Space Partition Trees in 3d worlds]</ref>。
|
||
< |
<syntaxhighlight lang="ada"> |
||
|
procedure Tree_traverse (tree:bsp_tree, eye:point) is |
||
begin |
|||
if (tree->empty()) |
|||
if not Tree_isEmpty (tree) then |
|||
return; |
|||
constant location : integer = Tree_getLocation (tree, eye) ; |
|||
⚫ | |||
int location = tree->find_location(eye); |
|||
if |
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) ; |
||
⚫ | |||
⚫ | |||
|
Tree_traverse (tree.back, eye) |
||
⚫ | |||
⚫ | |||
|
else |
||
} |
|||
⚫ | |||
</source> |
|||
⚫ | |||
end if ; |
|||
end if ; |
|||
end |
|||
</syntaxhighlight> |
|||
== その他の空間分割構造 == |
== その他の空間分割構造 == |
||
104行目: | 110行目: | ||
{{木構造 (データ構造)}} |
{{木構造 (データ構造)}} |
||
{{Normdaten}} |
|||
{{DEFAULTSORT:はいなりくうかんふんかつ}} |
{{DEFAULTSORT:はいなりくうかんふんかつ}} |
||
[[Category:幾何学的データ構造]] |
[[Category:幾何学的データ構造]] |
2021年9月20日 (月) 07:57時点における最新版
概要[編集]
コンピュータグラフィックスにおいては、シーンを正しくかつ素早く描画したい。単純な方法として、奥側にあるものから先に描画し、後から手前にあるものを描画するという、Zソートベースの画家のアルゴリズムがある。すなわち、背景から前景へと上に重ねるようにオブジェクトを描画していく方法である。しかし、この方法では後で隠れてしまう部分まで描画するなど、時間を浪費している面があり、また全てのオブジェクトが正しく描画されるわけではない。 Zバッファを使えば、画家のアルゴリズムでの描画順序決定のステップを省略してもシーンを正しく描画できるが、メモリを多く必要とするという問題がある。BSP木はオブジェクトを分割することで画家のアルゴリズムでZバッファなしでも正しく描画できるようにし、オブジェクトをソートする手間を省くことができる。すなわち、簡単な木構造の走査によって正しい描画順序が得られる。また、重ね描きを削減するための visibility list などの他のアルゴリズムの基盤としても機能する。 欠点は、事前処理に時間がかかる点で、そのためBSP木上で移動するオブジェクトを直接実装するのは困難であり、効率が悪い。その場合、BSP木とZバッファを併用し、背景となるシーン上でドアやモンスターといった動くオブジェクトをZバッファで正しくマージする。 BSP木は3Dコンピュータゲームでよく使われ、特にファーストパーソン・シューティングゲームで室内環境を描画する際に使われる。BSPデータ構造を最初に使ったゲームとして﹃DOOM﹄ がある。他にもレイトレーシングや当たり判定に使われる。生成[編集]
バイナリ空間分割は、条件を満たすまでシーンを再帰的に2つに分割していく。具体的な分割手法は最終的な目的によって異なる。例えば、当たり判定に使う場合、オブジェクトは容易に当たり判定できる程度にまで分割される。レンダリングにおいては、各部分が凸多角形になれば画家のアルゴリズムを使うのに十分である。 分割面と交差する線や面は2つに分割されるため、最終的なオブジェクト数は必然的に増大する。また、最終的な木構造はそれなりに平衡化されているのが望ましい。したがって、よいBSP木を正しくかつ効率的に生成するためのアルゴリズムは、実装においても最も難しい部分である。3次元空間では平面を使ってオブジェクトの表面を分割する。2次元空間では直線を使ってオブジェクトのセグメント︵線分︶を分割する。 下図は、複雑な多角形を一連の凸多角形に分割するプロセスを表している。各ステップで多角形をより線分の少ない多角形に分割していき、GとFは凸多角形になっているので、それ以上の分割が不要となっている。この場合、分割線は多角形の既存の頂点を通るように選ばれており、線分と交差していない。分割線が線分と交差する場合︵3次元の場合、面と交差する場合︶、その線分︵面︶は分割線︵面︶で2つに分けられ、それぞれが別々の独立したオブジェクトの一部となる。![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/57/Binary_space_partition.svg/460px-Binary_space_partition.svg.png)
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 |
年表[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木を使った画像操作法も開発した。脚注[編集]
- ^ 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.
参考文献[編集]
- 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.