こんにちは。Eukaryaの佐々木です。

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

3D空間上に地球儀のような見た目を作るためには、地球楕円体上に巨大な画像を貼り付ける必要があります。ズームした時にも綺麗な解像度で見せるために、ラスタータイルと呼ばれるタイル状に4分割された画像をアプリケーション側で取得して表示する必要があります。

今回、この機能を地図エンジンに実装したので簡単に仕組みを紹介します。

地球楕円体上へタイルを描画する仕組み

先ほども述べた通り、地球楕円体状にカメラのズームレベルに応じた解像度の画像を描画するために、ラスタータイルと呼ばれるデータがあります。これは各タイルが一定のサイズになるように分割されており、 Z/X/Y の座標に応じたタイルを取得できるように構造化されて作られています。ラスタータイルの慣例として Z が先頭に来る点に注意してください。

例えば、地理院地図の標準地図を見てみます。

座標が 0/0/0 の場合は以下のように、地球全体の画像を返す画像が返ってきます。

今度はズームレベル17のデータを見てみましょう。皇居が写っており、かなり詳細度の高い画像であることがわかります。この画像は 17/116418/51611 であり、数値の大きさから詳細度の高い画像であることがわかります。

これらの座標は 0/0/0 をルートとして、それぞれのタイルを再帰的に4分割した構造になっています。

例えばズームレベルが 1 の場合は 1/0/0, 1/0/1, 1/1/0, 1/1/1 の4つのタイルが存在します。同様にズームレベルが 2 の場合はズームレベル 1 のそれぞれのタイルを4分割した数のタイルが存在することになります。

これを繰り返していくと、ズームレベルが20の時には4の20乗個のタイルを描画する必要があります。しかし、この膨大な数のタイルを一度にリアルタイムに描画するのは困難です。そのため、本当に必要なタイルのみを選択して描画する必要があり、それにはどのタイルを描画するのかを効率的に選択する必要があります。

四分木 (Quadtree)

先ほど説明したタイルがルートから4分割されるような構造は、四分木（Quadtree）というデータ構造に似ています。そのため、このデータ構造はタイルを効率よく管理する方法としてよく使用されます。このツリー構造を利用することで、カメラから見えている範囲のタイルのみを効率的に辿ることができます。

ツリー構造であるため、親要素が不可視であれば、子要素も常に不可視であるという前提が成り立つため、不要な探索を避けることができます。

より詳細な説明は別記事の「3DCGにおける空間分割のデータ構造と仕組み」に譲ります。

Frustum Culling

Frustum cullingは、カメラのフラスタム（視錐台）の範囲外にあるオブジェクトをカリングするための仕組みです。3DCGにおいて一般的なテクニックです。フラスタムとはカメラの可視範囲を以下の画像のようなピラミッド状の形で表したものです。

Frustum cullingをするには、オブジェクトのバウンディングボックスとフラスタムを構成する各平面との距離を計算して、バウンディングボックスがフラスタムの内側にあれば描画し、外側にある場合は描画しないという判定をします。これにより、カメラのフラスタム外に存在するタイルの描画を避けることができます。

Horizon Culling

しかし、地図エンジンにおいては、これだけでは問題があります。

地球楕円体を遠くから見た時には、地球全体が見えて欲しいです。そのためには、このフラスタムはかなり大きなオブジェクトにする必要があり、水平線の向こう側にあるタイルが不必要に描画されてしまいます。

そこで、この問題を解決するために、Horizon cullingと呼ばれるアルゴリズムを併用します。

詳細な説明はCesiumの「Horizon Culling」という記事に譲りますが、これらのロジックを使用することでFrustum cullingでは不十分だったタイルの描画を避けることができます。

Horizon cullingの仕組みを以下の図に沿って簡単に説明します。なお、この図では点Tが対象となる点です。

1. 点Tが三角形VCHの内側にあるかをチェックします。これを計算するためにVTとVCのドット積から投影点である点Qを求めます。
2. 同様に点Pを求め、VQ間とVP間の距離を比較し、楕円体の正面にあるかを確認し、正面にない場合は描画をスキップします。
3. ベクトルの内積と余弦定理の関係により、下図のαとβのコサインを求めそれぞれを比較し、βが大きい場合に、点Tは範囲外とみなし、描画をスキップします。

上図の点Tをどのように求めるかについても考慮が必要です。

遮蔽したいオブジェクトの中心などを点Tとして固定してしまうと、地形などを表示する際に意図せずカリングされてしまう可能性があります。

そのため「Computing the horizon occlusion point」にあるように適切なポイントを計算する必要がある点には注意が必要です。

Screen Space Error (SSE)

Screen Space Error（SSE）は、カメラとモデルとの位置に応じて詳細度（LOD: Level of Detail）を適切に表示するための手法の1つです。LODはモデルのポリゴンの数を表し、LODが上がるほど解像度が高く、ポリゴン数の多いモデルが表示されます。

地図エンジンでは、地球全体のタイルや地形を描画するために、数十万のポリゴンを適切に描画する必要があります。例えば、ラスタータイルを描画する場合、カメラとタイルとの距離に応じて適切なLODのタイルを表示したいです。これを実現するためにSSEを使用します。

私たちの地図エンジンでは、CesiumのSSEのロジックをベースに実装を進めています。ここでは簡単に、タイルのレンダリングに使用しているSSEの仕組みを、Cesiumのコードをベースに解説します。詳細は「Massive-Terrain Rendering - 3D Engine Design for Virtual Globes」を参照してください。

正確なSSEの計算はモデルごとに必要になりますが、今回実装したCesiumベースのSSEは、地形を単純なモデルとみなして計算します。

1. 高解像度モデルと低解像度モデルのポイント間の誤差を表す、Geometric error を計算します（参考）。ズームレベルが0の時のタイルのGeometric Errorを事前に計算し（参考）、その値を使用してズームレベルごとの誤差を計算します（参考）。

   const levelZeroGeometricError = (ellipsoid.maximumRadius * 2 *
     Math.PI *
     TerrainProvider.heightmapTerrainQuality) /
     (tileImageWidth * numberOfTilesAtLevelZero);
   const maxGeometricError = levelZeroGeometricError / (1 << level);
   

2. Geometric errorをスクリーンの高さでスケールし、表示するピクセル数を求めます（参考）。

   const x = maxGeometricError * screenHeight;
   

3. アスペクト比に応じて垂直方向の視野角を計算します。fovは水平方向の角度であるため、画面が縦長の場合はそのまま近似できますが、横長の場合は正確な角度を計算する必要があります（参考）。また、垂直方向の視野角の半分のタンジェントからフラスタム前面の幅と距離の比率を計算します（参考）。

   const fovy = aspectRatio <= 1 ? fov
     : Math.atan(Math.tan(fov * 0.5) / aspectRatio) * 2.0;
   const sseDenominator = 2.0 * Math.tan(0.5 * fovy);
   

4. タイルとカメラの距離にカメラの視野角から求めたsseDenominatorをかけて、このタイルのスクリーン上の表示幅を求めます（参考）。

   const w = distance * sseDenominator;
   

5. 求めたピクセル数を表示幅で割り、さらにピクセルの解像度で割ると、SSEを求めることができます。

   const sse = x / w / window.devicePixelRatio;
   

6. このエラーを許容できる最大のSSEと比較して、最大値より小さければ、対象のタイルをレンダリングします（参考）。

以下の図のρがSSEを表します。ε がGeometric Error、x がピクセル数、d がモデルとの距離、θ が視野角、w が表示幅です。

まとめ

これらのアルゴリズムを使用することである程度の速度でタイルを描画することができます。

ただ、これはあくまでもレンダリングするタイルを適切に選択するためのロジックです。そのため、選択されたタイルに複雑な地形を描画したり、タイル間の隙間を埋めて綺麗に描画したりといった、さらに発展的な処理をする必要があります。

地図エンジン開発は学ぶべきことが無限にありますね…！