バイナリ空間分割 その他の空間分割構造

ウィキペディア

バイナリ空間分割

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

その他の空間分割構造

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

関係表

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

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

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

年表

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