八分木

八分木（英: Octree）とは、木構造の一種で、各ノードに最大8個の子ノードがある。3次元空間を8つのオクタント（八分空間）に再帰的に分割する場合によく使われる。四分木を3次元に拡張したものと見ることができる。英語の名称は oct + tree に由来するが "octtree" とは書かず "octree" と書く。

左: 立方体の再帰的な8分割、右: それに対応した八分木

空間表現としての八分木

八分木の各ノードは空間を8つのオクタントに分割する。PR (point region) 八分木の場合、各ノードは明確に1つの3次元の点を格納していて、それがそのノードに対応する空間領域の中心点となる。また、その点は子ノードそれぞれに対応する空間領域の頂点（隅）になり、逆に言えば、その点を中心としてオクタントに分ける。MX八分木では、対応する空間領域の幾何学的中心点を暗黙のうちに分割の中心とする。PR八分木の根ノードは無限の空間を表せるが、MX八分木の根ノードは有限の空間しか表せない（そうでないと幾何学的中心が求められない）。このように空間分割表現として八分木を使う場合、それはkd木の3次元の場合の特殊ケースとなる。

主な用途

• 空間インデックス
• 3次元での効率的な当たり判定
• 視野判定
• 高速多重極展開法
• 有限要素法

色量子化への応用

八分木による色量子化アルゴリズムは、1988年、Gervautz と Purgathofer が考案した。これは、画像の色データを最大9レベルの深さの八分木で符号化するものである。八分木がこの用途に使われるのは、$2^{3}=8$ であり、かつRGBモデルでは色の成分が3つになっているためである。赤 (Red)、緑 (Green)、青 (Blue) の最上位ビットの値を数式（例えば 4r + 2g + b）に入れて、根ノードからの分岐を決定する。次の分岐は最上位から2番目のビットで同様に行う。最下位ビットの方は木構造のサイズを減らすために無視することがある。

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

関連項目

• Kd木
• Sauerbraten - 八分木に基づいた3次元ゲーム
• OGRE - 八分木のシーンマネージャを実装している
• Sparse Voxel Octree

外部リンク

• 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