データ構造入門：圧縮四分木と八分木（Octree）の基礎と活用法

圧縮四分木（Compressed Quadtree）とは

四分木では、分割されたセルごとにノードを保存していくため、データを持たない空のノードが大量に発生しがちです。こうした疎なツリーのサイズを抑えるには、意味のあるデータを保持する葉を持つ部分木、いわゆる「重要な部分木」だけを保存すれば十分です。

さらにサイズを削減することも可能です。重要な部分木だけを扱う場合、枝刈りの過程で、中間ノードの次数が2（親へのリンク1つと子へのリンク1つのみ）であるような長いパスを取り除けます。実際には、そのパスの始点にあるノードUだけを保存し（削除したノード群を表すメタデータをUに関連付けておき）、パスの終点を根とする部分木をUに接続するだけで済みます。ただし、このような圧縮ツリーでも、「悪い」入力点が与えられた場合には高さが線形になり得る点には注意が必要です。

圧縮によってツリーの多くを削減しても、Zオーダー曲線を活用すれば、挿入・削除・探索を対数時間で実行できます。Zオーダー曲線は、完全な四分木の各セル（したがって圧縮四分木のセルも含む）をO(1)時間で1次元の直線へ変換し（逆変換も同様にO(1)時間）、要素全体の全順序を構築します。これにより、四分木のノードを順序付き集合用のデータ構造に格納できるようになります。

ここで、いくつかの妥当な仮定を置きます。まず、2つの実数 α, β ∈ [0, 1] が2進表現で与えられたとき、両者が最初に異なるビットのインデックスをO(1)時間で計算できるものとします。また、四分木における2つの点・セルの最小共通祖先と相対的なZ順序をO(1)時間で求められること、さらに床関数（floor関数）もO(1)時間で計算できることを仮定します。これらの仮定の下では、与えられた点Qのポイントロケーション（Qを含むセルの特定）、削除、挿入の各操作は、すべて基盤となる順序付き集合データ構造での探索にかかる時間（O(log n) 時間）で実行できます。

ポイントロケーションの手順

圧縮ツリー上で点Qの位置を特定する（Qが属するセルを決定する）には、以下の手順を実行します。

• Z順序において点Qより前に来る既存のセルを圧縮ツリー内から探します。このセルをVと呼びます。
• Q ∈ V が成り立てば、Vを返します。
• そうでなければ、非圧縮の四分木において点QとセルVの最小共通祖先となるはずのセルを見つけます。この祖先セルをUと呼びます。
• Z順序においてUより前に来る既存のセルを圧縮ツリー内から探し、それを返します。

具体的な詳細には立ち入りませんが、挿入や削除を行う際は、まず対象となる要素についてポイントロケーションを実行し、その後に挿入・削除を行います。このとき、必要に応じてノードの構築や削除を行い、ツリーの形状を適切に再整形することが重要です。

八分木（Octree）とは

八分木（オクツリー）とは、各内部ノードがちょうど8つの子ノードを持つツリーデータ構造として定義されます。

八分木は、3次元空間を8つのオクタント（八分区）へ再帰的に分割することで空間を区分化する目的で最も広く使われています。

八分木は、四分木の3次元版に相当する構造とみなされています。名称は「oct（八）+ tree」に由来しますが、通常は「t」が1つの「octree」と綴られる点に注意してください。

八分木は、3Dグラフィックスや3Dゲームエンジンで頻繁に採用されています。

空間表現の方式

八分木の各ノードは、自身が表す空間を8つのオクタントへ分割する役割を担います。ポイントリージョン（PR）型の八分木では、ノードは明示的な3次元点を1つ保持します。これはそのノードにおける分割の「中心」であり、8つの子ノードそれぞれに対して1つの角を指定します。一方、行列ベース（MX）型の八分木では、分割点は暗黙的にノードが表す空間の中心となります。PR型のルートノードは無限空間を表現できますが、MX型のルートノードは、暗黙的な中心が一意に定まるよう、有限の有界空間を表現できる必要があります。

主な用途

• 3Dコンピュータグラフィックスにおけるレベル・オブ・ディテール（LOD）レンダリング
• 空間インデックス
• 最近傍探索
• 3次元における効率的な衝突判定
• 有限要素解析
• スパースボクセル八分木
• 状態推定
• 集合推定