[[cg:start|CG用語集トップ]] > [[cg:modeling:start|第2章 モデリング]]

====== 四分木 ======

===== 概要 =====

四分木は、2次元領域を再帰的に4つの領域へ分割して表す木構造である。画像や平面領域を効率よく管理するために使われる。

{{:cg:figures:chapter02:fig_2_29_quadtree.png?600|2次元図形の四分木による表現}}

===== 詳しい説明 =====

四分木では、ある正方形領域を必要に応じて4つの小領域に分ける。さらに細かく表したい部分だけを再び4分割することで、均一な格子より少ないデータで領域を表せる場合がある。たとえば、変化の少ない部分は大きな領域のまま保持し、境界や細部がある部分だけを細かく分割できる。画像処理、地図、空間管理、2次元図形の表現などに利用される。

===== CG制作との関係 =====

CG制作では、2次元領域や画像を階層的に管理する考え方として関係する。細部が必要な部分だけを細かくするため、データ量の削減や処理効率の改善につながる。

===== ゲーム開発との関係 =====

ゲーム開発では、2D空間の衝突判定、地形管理、オブジェクト検索などに利用できる。すべてを総当たりで調べるより、空間を分割して管理する方が効率的になることがある。

===== 制作・実装での例 =====

2Dゲームで多数のオブジェクトを管理するとき、画面全体を区画に分けると、近いものだけを調べやすくなる。四分木はその考え方を階層的にしたものと考えられる。

===== 検定対策ポイント =====

四分木は2次元空間を4分割する木構造である。3次元版は[[cg:modeling:octree|八分木]]であり、次元の違いと分割数の違いを押さえる。

===== 関連用語 =====

  * [[cg:modeling:voxel_representation|ボクセル表現]]
  * [[cg:modeling:octree|八分木]]
  * [[cg:fundamentals:pixel|画素]]
  * [[cg:fundamentals:image_resampling|画像の再標本化]]
  * [[cg:modeling:volume_data|ボリュームデータ]]

===== タグ =====

  * CGエンジニア検定
  * 第2章
----
[[cg:modeling:start|← 第2章 モデリング の目次に戻る]]
[[cg:start|← CG用語集トップに戻る]]