こんにちは。Eukaryaの佐々木です。@_keiya01でTwitterをやっているのでよかったらフォローしてください（そんなにつぶやかないですが）。

弊社では新規で3Dの地図エンジンの開発をしています。地図エンジンとは、Google Earthのような3次元空間上に地球儀を表示し、ズームするとより詳細な画像が見れる仕組みで、Google Earthのような地図としての用途はもちろんのこと、位置情報データのビジュアライゼーションにも使用されます。既存の地図エンジンの例としては、CesiumJSやMapbox GL JSなどがあります。

この地球儀の見た目を作るためには、地球楕円体上に巨大な衛星画像を効率よく描画する必要があります。これを実現するために、この後も紹介するQuadtree（四分木）というデータ構造を使用します。このデータ構造を学ぶ過程で、他にも3DCGにおける空間分割のデータ構造があることを知ったので、まとめることにしました。誰かの助けになれば幸いです。

なぜ空間分割が必要か

コンピュータグラフィックスにおいて、大きな空間上で、モデル同士の衝突判定など、モデル同士の関係性に基づいて処理を行う場合、計算量が非常に多くなります。

例えば、あるゲームのシーンに1万個のモデルがあり、それぞれモデルがランダムに動いており、それらの衝突判定をするとします。

一般的に衝突判定のモデル同士の計算には、Bounding boxのような、モデルを一つの単純な面や線で囲ったものを使用します。この場合、単純に線形にそれぞれのモデルのBounding boxを比較する場合、O(n^2) の計算量になってしまいます。

これを解決するために、空間を分割し、ある空間にいるモデル同士のみを比較すれば、計算量はかなり少なくなります。

さらに、空間を構造化することで、親や子の空間をより少ない計算量で探索することができます。

空間分割とは

空間分割とは、3DCGにおいてシーン全体を一定の範囲で分割して、その空間に存在するオブジェクトを容易に参照できるようなデータ構造です。

データ構造は主に、フラットに空間を分割するものと、ツリー構造で分割するものがあります。

フラットなデータ構造の場合は実装が容易ですが、シーンの空間が大きくなると空間の数が多くなってしまい、探索のための計算量が増えてしまいます。

逆に、分割する空間を大きくして分割数を減らすと、分割した空間に配置されるモデルの数が多くなってしまい、計算量が増えてしまいます。

これらを解決する方法の1つに、ツリー構造で空間を分割する方法があります。

次の章で具体的なデータ構造と特徴について紹介します。

空間分割のデータ構造

空間分割のデータ構造には以下のようなものがあります。実際には他にも用途に応じて色々なデータ構造がありますが、今回は代表的なものを取り上げます。

Grid

空間を一定の距離置きにグリッド状にフラットに分割して、それぞれのグリッドごとにその空間に配置されるオブジェクトを管理するデータ構造です。 単純なグリッドなため2D・3D問わずに応用可能なデータ構造です。

以下の画像のように空間を分割し、空間とモデルを紐づけることでモデル間の計算が容易になります。

ただし、先ほども言及したように、フラットなデータ構造のため、空間の数が多くなると探索の時間も長くなります。また空間を大きくとって分割数を減らすと、1空間あたりのモデルの数が増えるのでモデル間の計算に時間がかかります。

Quadtree

日本語では四分木と呼ばれます。2D空間において、あるルートの1つのセルを再帰的に4分割してツリー構造を構築するデータ構造です。各セルにデータを持つ場合もあれば、各葉ノードが1つのデータを保持するような単位まで分割される場合もあります。

例えば、地球全体を写した衛星画像のようなラスターデータを高解像度で3D空間状の楕円体に表示して、地球儀のような表現をする場合、とても処理量が増え、多くのメモリが必要になります。例えば、画像は2Dなので、巨大な画像自体をあらかじめタイル状に分割しておき、これらを四分木のデータ構造として管理することで、カメラの位置に応じて最適な解像度の画像タイルを表示することができます。

Cesiumのような地図エンジンでは「ラスタータイル」と呼ばれる、画像などのラスターデータをズームレベルと楕円体状の座標に応じて4分割した形式のデータに対応しています。これは四分木そのものであるため、各タイルを四分木の対応するセルにタイルの情報を保存することで、カメラの位置に応じた最適なタイルを容易に探索できるようになります。

また同様に2D空間での衝突判定などにも使用できます。

Octree

日本語では8分木と呼ばれます。視覚的には直方体の中心を起点に３次元空間を再帰的に8分割するようなデータ構造です。

Three.jsのexampleにもあるような、3D空間における衝突判定に利用されたり、babylon.jsのOptimizing With Octreeで紹介されているような、アクションに伴うモデルの選択(ピッキング)やレンダリングするメッシュを選定するようなロジックの最適化として使用されます。

Bounding Volume Hierarchie (BVH)

BVHは空間分割というよりも、モデルの各ポリゴンを木構造に落とし込むことで、交差判定を高速化するためのデータ構造と言う方が近い印象です。

仕組みとしては、与えられたモデルを再帰的に「適切な粒度」でBounding boxを2分割して、木構造を作ります。この「適切な粒度」で分割するための計算には様々な方法があります。以下の画像は、Surface Area Heuristic (SAH)を使用して、各葉ノードが最小になるように分割されたBVHの例です。

BVHは、レイトレーシングやパストレーシングのような、あるモデルが光の反射や屈折などにより照らされるような表現を計算するときによく使用されます。SAHはシーン内のレイの分布がランダムであると仮定した時の交差判定にかかるコストを表したもので、各分割点でこのコストを比較し、最小となる点でBounding boxを分割します。

Three.jsにはthree-mesh-bvhというThree.jsのメッシュからBVHを構築するためのライブラリがあります。このライブラリではBounding boxを分割するための方法をいくつか提供しています。SAHも提供されています。

ただしSAHはある程度綺麗なツリーを作れるという点で、消費メモリを少なくしたり、交差判定にかかる時間を短縮できますが、ツリーの構築に時間がかかる点には注意が必要です。

BVHを使用することでThree.js上で高速にパストレーシングが動作する様子が、以下のデモで確認できます。

まとめ

木構造のデータ構造は、一見、銀の弾丸のように見えますが、空間が大きくなり、分割された空間が多くなるほどメモリ占有率も上昇します。これを避けるためにガベージコレクションのような仕組みで不要なノードを削除したり、モデルが空間を移動する際に少ない計算で移動できるような工夫が必要です。

また、最適化されたBVHを構築するためのSAHのコスト計算は、構築後の処理速度は向上しますが、構築に時間がかかるという点でどのような戦略を取るか、表現によって判断が必要です。

とはいえ、仕組みを理解すれば多くのことに応用が効くデータ構造だと思うので、改めてデータ構造を学ぶことは非常に大切だと感じました。

References

• Spatial Partition
• その15 8分木空間分割を最適化する！
• その８ 4分木空間分割を最適化する！（理屈編）
• BVHのはなし
• Bounding Volume Hierarchy (BVH) の実装 - 構築編
• (Task 3) Bounding Volume Hierarchy