八分木
概要
八分木は、3次元空間を再帰的に8つの領域へ分割して表す木構造である。四分木を3次元へ拡張したものとして理解できる。
詳しい説明
八分木では、立方体状の領域を x, y, z の各方向で半分に分け、合計8つの小さな立方体領域を作る。必要な部分だけをさらに8分割することで、3次元空間を階層的に管理できる。物体が存在しない広い空間は大きな領域として扱い、形状の境界や細かい部分だけを分割すると、ボクセル表現のデータ量を抑えられる。3D空間検索、衝突判定、ボリュームデータ管理などに関係する。
CG制作との関係
CG制作では、3D空間やボリュームデータを効率よく扱う考え方として関係する。すべての空間を同じ細かさで扱うのではなく、必要な部分だけを細かくする階層構造である。
ゲーム開発との関係
ゲーム開発では、3D空間内のオブジェクト検索、衝突判定、視界判定、ボクセル地形管理などに利用できる。空間を階層的に分けることで、探索対象を減らしやすい。
検定対策ポイント
八分木は3次元空間を8分割する木構造である。四分木は2次元、八分木は3次元という対応を覚える。
関連用語
タグ
- CGエンジニア検定
- 第2章