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

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

地図エンジンを開発する際には、さまざまなLODアルゴリズムを使用する必要があります。地図エンジンを開発する中で、多くの手法について学んだので知見をまとめました。

LODとは

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

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

またミップマップのようなシーンに合わせた解像度のテクスチャを使用する方法もあります。

なぜLODが必要か

複雑な3Dモデルになるほど、頂点数が増えて、GPUに頂点を転送するコストが増えます。また頂点数が増えることで計算量も増えてしまいます。

ゲームや地図エンジンのようなリアルタイムレンダリングを扱うソフトウェアでは、大量の処理を行うため、少しでも無駄を省く必要があります。

LODのアルゴリズム

LODを効率的に行うために、アプリケーションや表現の特性に応じた様々なLODの手法が存在します。筆者が今回調べた限りで有用そうなものをピックアップして紹介します。

DLOD (Discrete Levels of Detail)

DLODは詳細度ごとに個別にモデルを用意して、カメラの距離などに応じて詳細度ごとに用意したモデルを適切に表示します。

Three.jsにはLODを実装するためのAPIが提供されています。 LOD.addLevel メソッドに対象のモデルとカメラからの距離を指定することで、距離に応じて適切なモデルを表示することができます。

CLOD (Continuous Levels of Detail)

CLODはカメラの距離などに応じて適切なモデルのポリゴンの詳細度を決めます。DLODが離散的にLODを行うのに対して、CLODは連続的にLODを行います。CLODであることでモデル全体を置き換えることなく、一部のポリゴンのみを詳細化できます。

これにより、大きなモデルを表示するときに、カメラに近い部分は高い詳細度で表示し、反対側は少ないポリゴンで表示するといったことが可能です。

例えば、SSE (Screen Space Error) はCLODの一例といえます。SSEは、主にCesiumで使われるアルゴリズムで、地図タイルやテラインを効率的に描画するために使用されます。「カリングとSSEによる地球楕円体上へのタイル描画の最適化」で紹介した通り、SSEはカメラとタイルの間の距離から計算され、表示するタイルの詳細度を決めます。

HLOD (Hierarchical Levels of Detail)

HLODは、オープンワールドのようなゲームシーンで、遠くに見える複数のモデルを一つの低ポリゴンオブジェクトとしてグループ化し、効率的にレンダリングするためのテクニックです。

複雑なシーンを見せるゲームでは、遠くを見渡した時にレンダリングすべきモデルが多数存在する可能性があります。その時に、たとえモデルごとにローポリモデルを用意したとしても、ドローコールが多くなり、結果としてパフォーマンスが悪化することがあります。

これを避けるために、HLODでは遠くにある複数のモデルをまとめて、さらにローポリモデルにすることで、ドローコールを減らし、パフォーマンスを向上させます。

Unreal Engineでは、固定されているモデルに対して自動でHLODを生成する機能が備わっています。

Virtual Geometry

これまでは、モデルのどの部分をカリングするかの計算を、CPUで行う必要がありました。またLODモデル間の詳細度の差が大きいと、LODを切り替える時に視覚的に不連続に見えてしまうことがあります。

Virtual Geometryという手法を使用することで、1つのモデルをポリゴンごとにクラスター化し、モデルの部分ごとにカリングや詳細度の連続的な切り替えを行うことができます。

Unreal EngineにはNaniteという機能があり、Virtual Geometryの機能を提供しています。

Naniteでは、あるモデルのメッシュの三角形を小さなクラスターにまとめます。さらにこのクラスターをツリー構造にまとめます。

ルートをポリゴン数が少なく近似されたモデルとします。ツリーの枝葉は、モデルのより詳細な部分を表し、それぞれが個別のクラスターに対応します。

これにより、1つのモデルを表示する場合でも部分的にローポリの部分とハイポリの部分を表示することができます。

このツリーを使用することで、Shader側でフラスタムカリングやオクルージョンカリングなどのカリングをインスタンス単位でできるようになります。

Rust製のゲームエンジンであるBevyでも同様の機能の実装を進めており、Naniteを参考に開発しています（参考）。

RTIN

地図エンジンで地形の効率的な表示に使用されるアルゴリズムとして、RTINと呼ばれるものがあります。RTINを使用したライブラリとして有名なのが、MARTINIというMapboxが開発したライブラリがあります。

詳細は別記事に書くので、ここでは簡単に説明します。

このアルゴリズムを使用することで、起伏が激しい部分はハイポリゴンモデルとして描かれ、平坦な部分はローポリモデルとして描かれるように計算することができます。

現在開発中の地図エンジンでも、このアルゴリズムを使用して地形表示を最適化しています。

まとめ

LODには様々な最適化手法があることを学びました。

HLODのような遠方のシーン全体に適用するようなアルゴリズムや、RTINのように地図エンジンに特化したアルゴリズムなど、用途によって適切なアルゴリズムを選ぶのが大切だと感じました。