DirectXの話 第195回

Nanite的仮想化ジオメトリの実装：リソース構築

24/10/13 up

今回から2～3回程度でUE5のNaniteで利用されているような仮想化ジオメトリの実装について書いてみます。
予定しているのは描画までで、ストリーミングについての実装は行いません。
今回は仮想化ジオメトリのリソースを構築する部分について解説します。

仮想化ジオメトリ（Virtual Geometry）とは

通常、アーティストが作成するメッシュはゲームの中ではLOD（Level of Detail）メッシュが作成され、インスタンスの距離や画面に占める面積比によってLODレベルを切り替えるという手法が用いられます。
この手法は描画するにしてもストリーミングするにしても実装が容易いという利点があるのですが、LODレベルの切替時に問題が発生します。
何も考えずに切り替えてしまうとポッピングが発生しますし、ディザによる切り替えを行うと2重にメッシュを描画するフレームが発生してしまいます。
しかもメッシュ単位なので、巨大なメッシュの場合は常にLOD0のベースメッシュが描画されてしまい、LODの意味がなくなったりすることもあります。

このような問題を解決する手段として仮想化ジオメトリ（Virtual Geometry）が注目されています。
仮想化ジオメトリは仮想化テクスチャ（Virtual Texture）のメッシュ版というような存在で、メッシュ全体でLODを生成するのではなく、メッシュの局所ごとにLODを変化させるという手法です。
LODの変化が局所的なのでポッピングはかなり抑止できますし、巨大なメッシュにも対応可能です。
ただし、どの程度それらの恩恵を受けられるかは実装方法によるだろうと思います。
どのような実装方法を用いるかによって実装難易度やパフォーマンス、メリット・デメリットも変わってくるでしょう。

仮想化ジオメトリの実装例

簡単ですが、いくつかの仮想化ジオメトリの実装事例を紹介します。

まず、CEDEC2024で紹介された『ゼルダの伝説 Tears of the Kingdom』の実装事例です。
この作品ではマップの中の洞窟メッシュとして仮想化ジオメトリが使われています。
メッシュをOctreeで分割し、リーフをLOD0としてジオメトリを単純化していく手法のようです。
残念ながらCEDiLには資料が公開されていないので、各種メディアの記事を参考にするしかありません。

同じくCEDEC2024で紹介されたUnityの取り組みについての話もあります。
こちらはモバイルでの使用を考慮したもので、Naniteの仕組みに似ていますが、より簡易的なものになっています。
メッシュの部位ごとにLODを作成していく感じで、部位をまたいだ階層構造は作られないようです。
こちらの資料も公開されていないのであまり詳しいことは言えません。

今回、私が実装したのはNaniteの資料をベースとしています。
基本的な部分はほぼ同じと思っていただければいいかと思いますが、細かい部分はだいぶ違っているはずです。

本実装について

というわけで、本実装についての解説を行います。
実装サンプルは以下となります。

https://github.com/Monsho/VirtualGeometry

本記事ではリソース構築部分のみ解説しますので、ソースコードとしては mesh_grouping.h / .cpp となります。
基本的な処理の流れは以下のようになります。

１．glTFメッシュの読み込み
２．メッシュレットの作成
３．隣接メッシュレットのグループ化
４．グループ化したメッシュレットをマージしてシンプル化
５．リダクションしたポリゴン群からメッシュレットを構築
６．３から繰り返し
７．メッシュレットが1つになったら終了

細かな処理についてはそれぞれで解説します。

さて、本実装では重要なライブラリを利用しています。
まずは meshoptimizer です。
頂点キャッシュを考慮したインデックスの並び替えやメッシュレット作成、シンプル化などを行えるライブラリです。
GitHubのリンクは以下です。

https://github.com/zeux/meshoptimizer

次に METIS です。
このライブラリではグラフ分割を行うことが出来ます。
グラフとはノードとそれをつなぐエッジによって構成されるもので、このライブラリではそれを指定の方法で分割することが出来ます。
こちらもGitHubに存在します。

https://github.com/KarypisLab/METIS

ただ、今回はVisual Studioでのビルドに失敗したので、vcpkg を利用することにしました。

https://vcpkg.link/ports/metis

vcpkgはオープンソースのパッケージマネージャーで、ビルド済みのライブラリをダウンロードしてVSで使用できます。

メッシュレットの作成

まず最初にメッシュ全体からメッシュレットを作成します。
このメッシュレットがLOD0となり、最も詳細なメッシュレットとなります。

メッシュレットの作成は今回2種類を用意しました。
1つは meshoptimizer のメッシュレット生成機能をそのまま利用するもの、もう1つは METIS を利用するものです。
呼び出されている関数は BuildMeshlets 関数ですが、この関数は mesh_grouping.cpp の 197行目で #define定義しています。
実際の関数は BuildMeshletsByMeshopt 関数と BuildMeshletsByMETIS 関数です。
コミットしてあるコードではMETISを利用していますので、meshoptimizer を利用したい場合は切り替えてみてください。

METISによる実装では、ポリゴン1つをグラフ頂点、ポリゴン同士を接続しているエッジをグラフエッジとして登録しています。
1メッシュレットは128ポリゴン以内とするようにしているのですが、meshoptimizer ではポリゴン数と頂点数の最大数を設定できるため特に問題はありません。
しかし、METISによる分割は分割数を指定するもので、分割した1つのグループ中のポリゴン数（グラフ頂点数）を指定することが出来ません。
そのため、ポリゴン数が128以下になるような分割数を指定するのですが、ギリギリを狙うと128を超える場面が散見されました。
結局、124ポリゴンになるような分割数を指定することで、ポリゴン数が128以下になるように調整できました。
どんなメッシュでも124ポリ制限することで対応できるとは限らない点に注意が必要です。

今回両方対応した理由ですが、meshoptimizer のメッシュレット生成があまりうまくないというのが理由です。
飛び地になるようなポリゴンを含めたメッシュレットが結構作成されてしまったので、この問題に強いMETISを利用しました。

実装詳細は各関数を読んでいただければ。特に難しいことはしていないので。

隣接メッシュレットのグループ化

メッシュレットを作成した後、このメッシュレットからグループを作成します。
最大4つのメッシュレットをグループ化します。

この際に用いるのはMETISです。
メッシュレットがグラフ頂点となり、メッシュレットの接続情報がグラフエッジとなります。

ここで考えなければならないのがメッシュレットの接続情報をどのように生成するかという点です。
メッシュレットは複数のポリゴンで構成されていて、接続されるメッシュレットのポリゴンとポリゴンエッジを共有しています。
しかし、同じメッシュレット同士で複数のポリゴンエッジが共有されているため、単純にポリゴンエッジの共有を検索してしまうと同じグラフエッジが複数存在することになります。
METISはそのような状況でも問題なくグラフ分割をしてくれますが、今回はこのポリゴンエッジの共有している数をグラフエッジのウェイト値として扱っています。
つまり共有するポリゴンエッジが多い接続を優先的に保持するように分割することになります。
この理由については後述します。

処理を行っている関数はmesh_grouping.cppの419行目からの GroupMeshlets 関数です。
まず各メッシュレットで境界となるポリゴンエッジを列挙します。エッジには頂点インデックスから生成したハッシュ値を設定します。
次に各エッジハッシュに対して、そのポリゴンエッジを持っているメッシュレットインデックスを登録します。
その後、各メッシュレットが接続する他のメッシュレットのインデックスを生成します。
グラフを分割する前にMETISで利用するグラフデータを生成するのですが、そのときにグラフエッジごとのポリゴンエッジ数を求め、これをウェイト値とします。
最後にグラフを分割します。

これでメッシュレットのグループが作成されます。

グループ化したメッシュレットをマージしてシンプル化

グラフ分割によってグループ化されたメッシュレットはそのグループごとにマージします。
そして、そのマージされたグループごとにシンプル化を行います。
ポリゴン数はおよそ半分まで減らします。

これには meshoptimizer を用います。
meshoptimizer のメッシュシンプル化命令は meshopt_simplify 関数です。
この命令はポリゴンの再構成をするという感じではなく、インデックスを間引くという感じです。
そのため、頂点バッファは以前のものがそのまま利用でき、インデックスバッファのみが変化します。

また、シンプル化の際に重要なのはグループの境界となるエッジについてはシンプル化しないということです。
ここをシンプル化してしまうと隣接するグループとの間でクラックが発生してしまいます。
境界を保持する設定はシンプル化関数の options 引数に meshopt_SimplifyLockBorder を指定します。

シンプル化の際にはシンプル化によるエラーを出力することも必要です。
このシンプル化関数は Surface Simplification Using Quadric Error Metrics というペーパーをベースとしています。
QEMというアルゴリズムはシンプル化した際に頂点が理想的な位置からどの程度離れているかと言うのを示す指標のようです。
関数から出力されるエラー値がこのQEMアルゴリズムで計算された値となります。
このエラー値はどのLODを利用するかの指針となりますので保存しておく必要があります。

シンプル化したポリゴン群からメッシュレットを作成する

4つのメッシュレットをマージして半分のポリゴン数にリダクションしていますので、ここからメッシュレットを作成すると2つのメッシュレットとなります。
このメッシュレットの作成は最初のメッシュレット作成と同様です。

このようにして作成されたメッシュレットはすべてまとめて、そこからさらにグループ化、シンプル化と行っていきます。
最終的にメッシュレットが1つになったら終了です。
もしくはLODレベルの最大値を決めて、そこでストップしてもOKです。

グループ化の注意点

ポリゴンのシンプル化を行う際に境界部分を残すようにしているわけですが、ここには1つの問題点があります。
それは境界部分が長く残ってしまったときにその部分だけ細かく分割されたままLODが生成されてしまうということになります。
これを避けるため、グループ化する際にポリゴンエッジの接続が多いものを優先することにしています。

この問題について以下の図を用いて解説します。

図の左側がメッシュレットをマージした4つのグループと考えてください。
これをシンプル化すると図の真ん中のようになります。
見ての通り、境界部分をそのまま残しつつ内部のポリゴンを削減しています。

図にはしていませんが、この4つのグループそれぞれからメッシュレットを作成します。
グループ1つに対してメッシュレットが2つ作成されるので、4グループで8つのメッシュレットが作成されることになります。

さて、グループ化は4つのメッシュレットで構成されますので、グループが2つ作成されます。
この際、図の右上のようにグループ化されてしまったとしたらどうでしょうか？
真ん中のラインの境界はシンプル化によって省略されますが、それ以外の境界は図の左側と変わっていません。

しかしうまくメッシュレットが作成され、境界エッジが多い部分でグループ化された場合は図の右下のようにシンプル化されます。
境界エッジも確実に減少していきますので、閉じたメッシュであれば最終的にはキレイにポリゴンが削減されるでしょう。
グループ化の際に共有する境界エッジの数をウェイト値として設定している理由がこれです。

ただし、このようにグループ化していくと親子構造が複雑になります。
右上のようにシンプル化したとすると、例えば右上のLODからさらに次のLODを描画する必要がある、という場面でも真ん中の2つのグループを描画すればいいということになります。
しかし右下のようになってしまうと右下から次のLODとなった際に真ん中のグループの親である別のLODについても描画をせず、必ず同じLODを描画しなければならなくなります。
これが地味に難しい問題なのです。
この問題については次回のトラバース編で解説しようと思います。

リソース構築のエントリーポイント

リソース構築のエントリーポイントとなる命令は mesh_grouping.cpp の559行目にある ProcessModel 関数です。

モデル内には複数のメッシュがあるものとし、メッシュごとに処理を行います。
最初にLOD0を生成し（566行目）、メッシュレットのIDを利用して辞書コンテナに登録していきます（571行目）。

各LODの処理は StepLOD というラムダ（577行目）で行います。これが3～5番の処理となります。
実際に各LODレベルのループを行っているのは640行目です。

メッシュレットが1つになるか、最大LODレベルとして設定している128になるかでループが終了します。
実際に128レベルまで行くことはまずないでしょう。
サンプルのスタンフォードバニーの場合は11レベルくらいだったはずです。
ただ、すべてのLODのメッシュレット総数は2000を超えているので、かなり数が多くなります。
より詳細なメッシュの場合は更にメッシュレット総数が増えていくことが予想されます。128レベルでは足りない場合も来るかもしれませんね。

最後に

今回のリソース構築手法はNaniteの手法をベースとしています。
SIGGRAPH 2021 で話されている内容がそれに当たりますので、詳細な解説はそちらをチェックするのがいいのではないかと思います。

https://advances.realtimerendering.com/s2021/Karis_Nanite_SIGGRAPH_Advances_2021_final.pdf

次回はツリーをトラバースして描画する部分について解説します。
最初はCPUでトラバース処理を作成し、それをWork Graphに移植するような流れになります。