八分木

八分木（Octree）とは

八分木（英: Octree）とは、木構造の一種であり、各ノードが最大8個の子ノードを持つ点が特徴です。特に3次元空間を8つのオクタント（八分空間）に再帰的に分割する際に用いられ、四分木を3次元に拡張したものと捉えることができます。英語では "oct" + "tree" に由来し、"octree" と表記します。

空間表現としての八分木

八分木は、空間を効率的に表現するための強力なツールです。各ノードは空間を8つのオクタントに分割し、この分割を再帰的に繰り返すことで、複雑な3次元空間を階層的に表現できます。

PR（Point Region）八分木

各ノードは、明確な3次元の点を保持し、それが対応する空間領域の中心点となります。この点は、子ノードが表す空間領域の頂点（隅）となり、逆にその点を中心に空間が8分割されます。

MX八分木

各ノードは、対応する空間領域の幾何学的中心点を暗黙的に分割の中心とします。PR八分木とは異なり、MX八分木の根ノードは有限の空間しか表現できません。これは、幾何学的中心を算出する必要があるためです。

空間分割表現としての八分木は、kd木の3次元版と捉えることもできます。

八分木の主な用途

八分木は、その特性から様々な分野で活用されています。以下に主な用途を挙げます。

空間インデックス: 3次元空間内のオブジェクトの位置を効率的に管理します。これにより、オブジェクトの検索や近傍探索が高速化されます。
3次元での効率的な当たり判定: ゲームやシミュレーションにおいて、オブジェクト同士の衝突を高速に検出します。
視野判定: 3Dグラフィックスで、カメラから見える範囲にあるオブジェクトを効率的に判定します。これにより、レンダリングのパフォーマンスが向上します。
高速多重極展開法: 物理シミュレーションにおける計算を高速化する手法です。八分木を用いることで、計算量を大幅に削減できます。
有限要素法: 複雑な形状を持つ物体の解析において、計算を効率化します。
色量子化への応用: 画像の色数を削減する処理に使われます。

八分木による色量子化

1988年にGervautzとPurgathoferによって考案された八分木による色量子化アルゴリズムは、画像の色データを最大9レベルの深さを持つ八分木で符号化します。八分木がこの用途に使われるのは、2^3 = 8であり、RGBモデルの色成分が3つであることによります。

赤(R)、緑(G)、青(B)の最上位ビットの値（例えば、4r + 2g + b）を用いて、根ノードからの分岐を決定します。次の分岐は、最上位から2番目のビットで同様に行います。最下位ビットは、木構造のサイズを削減するために無視されることがあります。

木構造のサイズは制限可能なため、このアルゴリズムはメモリ効率が良いです。八分木の最下位レベルにある葉ノードには、木構造内では表されていない色データが対応しています。レベルが深くなるにつれて、色の差異は微妙になります。パレットの色数と葉ノードの個数を比較しながら標本化を進め、葉ノードの個数がパレットの色数を超える場合は、その部分の木構造を切り捨て、親ノードを葉ノードとして色を対応させます。この際、各葉ノードの色となっている標本数をカウントしておき、切り捨てる部分の決定に利用します。

関連項目

Kd木: 多次元空間を分割する木構造で、八分木の基となる概念です。
Sauerbraten: 八分木をベースとした3Dゲーム。
OGRE: 八分木のシーンマネージャを実装したゲームエンジン。
Sparse Voxel Octree: 大規模な3Dデータを効率的に扱うための技術。

外部リンク

Octree Quantization in Microsoft Systems Journal
Color Quantization using Octrees in Dr. Dobb's
Color Quantization using Octrees in Dr. Dobb's Source Code (zip形式)
Octree Overview
* Parallel Octrees for Finite Element Applications

もう一度検索