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

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

地図エンジンでは、地形を表示することができます。地形を表示することで、より現実世界に即したビジュアライゼーションを表現することができます。

地球規模のシーンを描画する地図エンジンでは複雑な地形の全てをレンダリングしてしまうと、メモリやCPU・GPU処理の負荷が高くなってしまいます。

この問題を避けるために動的にLOD処理をして、モデルとの距離に応じて詳細度を変えるアルゴリズムを実装したので紹介します。

LODとは

コンピュータグラフィクスにおいて、複雑な3Dモデルの表示は、一般的に多くのメモリを消費したり、レンダリングに時間がかかります。

このような問題を回避するために、遠くにあるモデルや高速で動いているモデルのような、細部が見えなくても問題ない状況で、簡素化したモデルを表示する方法をLODと呼びます。

詳細は「3DCGにおけるLODアルゴリズム」を参照してください。

地球全体を描画する仕組み

詳細は「カリングとSSEによる地球楕円体上へのタイル描画の最適化」に譲るとして、ここでは大まかに説明します。

地球楕円体上に適切に地図の画像を貼り付けるために、ラスタータイルというデータを使用します。

このデータは、各タイルが一定のサイズになるように分割されており、 Z/X/Y の座標に応じたタイルを取得できるように構造化されています。

これにより、カメラのズームレベルに応じた解像度の画像を取得することができます。

例えば、カメラが地球楕円体よりも遠くにある場合は、Z の値を小さくして、近くにある場合は、Z の値を大きくすることで、より詳細な画像を取得することができます。

Z が 0 の場合は、以下のような全体的な画像が返ってきます。

一方で、Z が 17 の場合は、詳細な画像が返ってきます。

カメラと地球楕円体との距離に応じて適切に計算することで、どのタイルを描画するかを決定します。

地形のデータタイプ

地形を描画する方法として、大きく分けて2つのデータタイプがあります。

1. ラスターデータ
2. ベクターデータ

どちらのタイプでもタイルと同じように Z/X/Y の構造でリクエストできるようになっています。

ラスターデータ

ラスターデータとしては国土地理院から出ている標高タイルやMapboxから出ているTerrain RGB v1があります。

標高タイルデータは以下のような特殊な色をした画像で示されます。画像はPNG形式で、標高をRGBのそれぞれ8bitに分解して格納されます。

標高が格納された画像から地形のモデルを構築します。どのように地形のモデルを構築するかは後述します。

ベクターデータ

ベクターデータしては、CesiumのQuantized-meshというものがあります。Quantized-meshも Z/X/Y の形式でリクエスト可能です。データには事前計算された頂点やインデックス、法線といった地形を描画するために必要な情報が含まれています。

ラスターデータは画像から標高を復元し、地形のメッシュを生成するための計算が必要ですが、Quantized-meshは事前計算されているので、基本的にはリアルタイムに複雑な計算を必要としないため、高速に描画できます。

ラスターデータから地形のモデルを構築する方法

ラスターデータから地形のモデルを構築するには、まず標高が格納された画像から標高値を取り出します。

国土地理院の標高タイルの場合

国土地理院のPNG形式の標高タイルから標高値 x （m）を取り出す場合、仕様に沿って以下のように計算します。

x = 216R + 28G + B
x < 223の場合　h = xu
x = 223の場合　h = NA
x > 223の場合　h = (x-224)u

標高分解能: u = 0.01
無効値（NA）: (R, G, B)=(128, 0, 0)

標高 h が得られたら、タイルの各頂点を h でスケールします。

Mapbox Terrain-RGB v1の場合

国土地理院の標高タイルとは計算式が異なることに注意します。仕様に沿って以下のように計算します。

height = -10000 + ((R * 256 * 256 + G * 256 + B) * 0.1)

分解能は0.1mとなります（国土地理院の標高タイルよりは低い）。

地形メッシュの生成

このときに、タイルの頂点と標高の位置が一致している必要があります。そのため、一枚のタイルを適切な粒度で分割する必要があります。

単純にタイルを分割する場合、標高タイルのピクセル数に合わせて、一律にタイルを細かく分割することになります。

最後に、タイルの各頂点のUVに沿って標高タイルから標高を取り出し、各頂点をスケールします。

しかし、上述したように、単純にタイルを分割する方法だとタイルの粒度が一定になってしまいます。そのため複雑な地形も考慮した粒度でタイルを分割すると全体の分割数が多くなってしまい、平らに近い地形では不要な頂点が生まれてしまいます。

この問題を考慮し、平らな地形では少ない頂点数で分割し、複雑な地形では頂点数を増やして滑らかに見せるようなアルゴリズムがRTINというものです。

Right-Trianguled Irregular Networks (RTIN) とは

このアルゴリズムは地形を効率的に描画するために使用されます。

各タイルとその地形は正方形上に描画されるので、この正方形のタイルを直角部分から斜辺の中央にかけて繰り返し分割して、二等辺三角形になるようにします。このときに斜辺を構成する2つの頂点を保存しておきます。

次に、保存した斜辺を構成する頂点 a、b それぞれの高さ情報を取得し、線形補完した値を計算します。さらに斜辺中央 m の高さと先ほど線形補完した値との誤差 err を計算します。

下の図の通り、斜辺が長くなればなるほど誤差は大きくなります。逆に言うと斜辺を細かくすればするほど誤差が小さくなります。

次に、許容できる最大誤差を指定して、それぞれの斜辺の誤差と比較します。斜辺の誤差が最大誤差を下回るように適切な斜辺を選択します。

このときに分割した情報が階層的に管理されていることで、最大誤差に応じた適切なLODを選択できるようになっています。

下の画像のように誤差を小さくすればするほど、三角形の数は増えてハイポリなモデルになります。一方で誤差を大きくとると三角形は少なくなり、ローポリなモデルになります。

また平坦な地形では誤差は小さいので、誤差を小さくするために斜辺を短くする必要はないため、頂点数を少なくできます。

MARTINIとは

このアルゴリズムを実装したMARTINIというライブラリがあります。これはJavaScriptで実装されており、リアルタイムでも高速に動作するように作られています。

MARTINIのリポジトリの以下のGIFからも最大許容誤差を変えることでLODが変化しているのがわかります。

まとめ

MARTINIを参考に、開発中の地図エンジンにRTINの実装をしました。シンプルなアルゴリズムでありながらかなりの頂点数を減らすことができました。また、標高差に応じて頂点数を減らしているので見た目が綺麗なまま頂点数を減らすことができる点も良いです。

厳密には測っていませんが、アルゴリズム適用前には1万程あった地形の頂点数が、アルゴリズム適用後は最大で6000ほど、平坦な部分では1000程度まで、頂点数を減らすことができました。