八分木のソースを表示

[[画像:Octree2.png|thumb|right|400px|左: 立方体の再帰的な8分割、右: それに対応した八分木]]
'''八分木'''（[[英語|英]]: '''Octree'''）とは、[[木構造 (データ構造)|木構造]]の一種で、各ノードに最大8個の子ノードがある。3次元空間を8つのオクタント（八分空間）に再帰的に分割する場合によく使われる。[[四分木]]を3次元に拡張したものと見ることができる。英語の名称は ''oct'' + ''tree'' に由来するが "''octtree''" とは書かず "''octree''" と書く。

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

== 主な用途 ==

* [[空間インデックス]]
* 3次元での効率的な[[当たり判定]]
* [[陰面処理|視野判定]]
* {{仮リンク|高速多重極展開法|en|Fast multipole method}}
* [[有限要素法]]

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

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

== 関連項目 ==
* [[Kd木]]
* [[Sauerbraten]] - 八分木に基づいた3次元ゲーム
* [[OGRE]] - 八分木のシーンマネージャを実装している
* [[Sparse Voxel Octree]]

== 外部リンク ==
*[https://web.archive.org/web/20140605161956/http://www.microsoft.com/msj/archive/S3F1.aspx Octree Quantization in Microsoft Systems Journal]
*[http://www.ddj.com/184409805 Color Quantization using Octrees in Dr. Dobb's]
*[ftp://66.77.27.238/sourcecode/ddj/1996/9601.zip Color Quantization using Octrees in Dr. Dobb's Source Code] (zip形式）
*[http://web.cs.wpi.edu/~matt/courses/cs563/talks/color_quant/CQoctree.html Octree Overview]
*[http://sc07.supercomputing.org/schedule/pdf/pap117.pdf Parallel Octrees for Finite Element Applications]

{{データ構造}}

{{DEFAULTSORT:はちふんき}}

[[Category:ツリー (データ構造)]]
[[Category:コンピュータ・グラフィックス・データ構造]]
[[Category:データベース・インデックス技術]]
{{Software-stub}}