ブロックゲームにおけるソフトウェアオクルージョンカリング
Software occlusion culling in Block Game (enikofox.com)
要約
統合GPUを持つ低スペックPCでも快適に動作するブロックゲーム開発のため、ソフトウェアレンダリングによるオクルージョンカリング手法を開発しました。CPU側で低解像度のデプスバッファをレンダリングし、チャンク内の可視性を判定することで、特に地下や屋内での描画負荷を大幅に削減することに成功しました。
全文翻訳
Block Gameにおけるソフトウェアオクルージョンカリング
私のGPUは、AMD Ryzen 7 5700G CPUに付属するRadeon Vega 8の統合グラフィックスです。これは、私のワークステーションがグラフィカルなコンピューティングの強力なマシンではないことを知っておいてほしいからです。実際、かなり弱いです。しかし、私の統合GPUは、私がターゲットとしている低スペックハードウェアである2012年に購入したラップトップのGPUよりもUserBenchmarkで48%高速に表示されます。
(余談ですが、UserBenchmarkの不正確さに関する非難は認識していますが、それほど深刻なものではありません。最近手に入れたiGPUが、当時それほど良くないとされていた14年前のラップトップGPUと比較して、より有利にならないのが面白いと思っています。)
それと、私が開発しているBlock Game(仮称)でも、ポテトのようなマシンでもゲームがうまく動作するようにしたいという思いから、以前からそのアイデアに興味があったソフトウェアレンダリングのオクルージョンカリングソリューションを自分で書いてみることにしました。ブロックとチャンクは軸配置のキューブなので、物事は簡単になり、ブロックゲームは地下の洞窟という形で大量の隠れたジオメトリを持つ傾向があります。これらのカリングには他の方法もありますが、アルゴリズムはかなり複雑になる傾向があり、この方法はその複雑さを避け、非常に概念的にシンプルなものに留める良い方法だと思いました。
この記事では、開発プロセスと最終的にたどり着いたソリューションについて説明します。もしよろしければ、MastodonとBlueskyに投稿した開発スレッドを読むこともできます。
始める前に、これが予想以上にうまく機能したと言いたいと思います。60 FPS以下で半フレームで実行され(もちろんスレッド化されています)、通常、フラスタムカリングを通過したチャンクの少なくとも50%をカリングします。地上では、地平線に向かってまっすぐ見ると約50〜60%のチャンクをカリングしますが、屋内や洞窟の地下では95%以上のチャンクをカリングでき、私の弱いシステムでも400 FPS以上のフレームレートを実現します。全体として大成功ですが、最後に触れるいくつかのケースで破綻することがあります。
[画像: Depth occlusion culling on/off の比較、左がoff、右がon。]
Depth occlusion culling on/off の比較、左がoff、右がon。
深度ベースのオクルージョンカリング
他の人々が深度ベースのオクルージョンカリングの概念を私よりも良く説明していますが、ここでは簡単に説明します。シーンの深度バッファを取得し、カリング可能な各オブジェクトについて、そのピクセルが表示されるかどうかを深度バッファで確認します。表示される場合は、表示されます。表示されない場合は、カリングされます。
これには多くのことができます。比較的高い解像度でレンダリングし、バッファを保守的にダウンサンプリング(常に最も遠い距離を使用)することができます。これは階層的Zバッファと呼ばれます。最新のテクノロジーを使用すれば、GPUの助けを借りてこれを行うことができます。モーションベクトルを使用して、前のフレームのバッファを再利用することもできます。非同期リードバックを使用して、GPUをブロックせずにCPUで分析するために実際の深度バッファを取得することもできます。
まず私の最終的なシステムを説明し、次に実際にそのシステムにたどり着いたプロセスを説明します。
Block Game のオクルージョンカリング
私がやったことは、上記で言及した派手なものは何も含まない、はるかにシンプルなものです。私はFNAを使用してBlock Gameを作成しているので、古いテクノロジーに縛られており、GPUの機能を利用できません。GPUから深度バッファを読み取ることはできますが、非同期ではないため、必然的にGPUのストールが発生し、それは良くありません。そのため、CPUでレンダリングしています。
256x128ピクセルの解像度でレンダリングしており、ブロックゲームではすべてがキューブであるため、キューブを深度バッファ(単純なfloatの配列)にレンダリングし、次に他のキューブをバッファに対してチェックします。
チャンクが変更によって再構築されると、オクルーディングサブチャンクの「ミップマップ」チェーンのようなものを構築します。私のチャンクは16x16x16のサイズなので、5つのレベルがあります。
- これは単にチャンク全体です
- 2x2x2のキューブ、各8x8x8ブロックのサイズ
- 4x4x4のキューブ、各4x4x4ブロックのサイズ
- 8x8x8のキューブ、各2x2x2ブロックのサイズ
- 16x16x16のキューブ、各1ブロックに準拠
まずレベル4を処理し、可視面を持つ完全な不透明ブロックをオクルーダーとしてマークします。次にレベルを下げていき、可視面を持ち、完全に不透明なブロックで構成されているブロックのキューブをオクルーディングサブチャンクとしてマークします。
[画像: Subchunk levels 1 through 4 のデバッグレンダリング]
Subchunk levels 1-4 を単独でレンダリングしたもの。同じチャンク内のサブチャンクは似た色をしています。
フレームのカメラ位置が更新されると、ゲームはレンダラーにオクルージョンカリングを開始するように指示します。これは、プレイヤーの周りのチャンクを収集し、可視面やエンティティを含まないチャンクをすべて破棄し、残りをワールド空間でフラスタムカリングします。次に、残りのチャンクをオクルージョンカラーに送信し、すべてのオクルーダーを収集します。最も高いレベル、つまり個々のブロックであるオクルーダーは、カメラから20ブロックの半径内のオクルーダーで構成されます。次に、レベル1から3までの次のレベルは、カメラがいるチャンクからの距離に基づいて収集されます。
8x8x8ブロックサイズのレベル1オクルーダーはたくさんありますが、16x16x16オクルーダーは決して見つからないようですが、理論的にはそれらを追加することもできます。誤ったオクルージョンを防ぐために、各オクルーダーのキューブを水平および垂直方向に1ピクセル縮小します。これにより、十分な距離で消滅し、合理的に見える距離よりも遠くにキューブをレンダリングする意味がなくなります。このようにオクルーダーをスキップすることで、オクルージョンカラーのワークロードが大幅に削減されます。
オクルージョンカラーは、候補となる各チャンクの位置、サイズ、チャンクインデックスをチャンクのリストに格納します。このすべてのデータが収集されると、オクルージョンカラーは実際のチャンクデータに触れる必要がなくなるため、スレッドセーフが達成され、バックグラウンドスレッドにウェイクアップして実際の作業を行うようにシグナルが送られます。
バックグラウンドスレッドでは、すべてのオクルーダーが最初にフラスタムカリングされます。なぜなら、以前のフラスタムカリングはチャンク全体にのみ適用され、サブチャンクには適用されず、最大8つの頂点変換はフラスタムカリングに必要なドット積よりもはるかに高価だからです。
次に、残りのオクルーダーの角が深度バッファのx/y座標と深度に変換されます。完全な4x4射影行列の乗算のオーバーヘッドを回避するために、ビュー行列を使用して回転し、加算で平行移動し、バッファが通常の32ビットfloatで構成されているため線形ビュー深度を使用します。これにより、操作が少なくなり、数千もの頂点を扱う場合に大幅に高速になります。オクルーダーの深度値は、計算されたすべての線形深度値の最大値になります。
変換された角のいずれかがカメラのニアプレーンの後ろにあるため無効な場合、オクルーダーは完全にスキップされますが、そうでない場合は、その「形状」がトレースされます。三角形や面をレンダリングする代わりに、深度バッファの各行の最小および最大x座標を保持する1D配列を使用します。形状のトレースは、8つのキューブコーナーのいずれかの最小および最大y座標を見つけ、次に12のキューブエッジすべてをステップスルーし、各行の最小および最大x値を記録することを意味します。
オクルーダーの描画は、最小y(+1)から最大(-1)までの各行をステップスルーし、1D配列(こちらも+1および-1)から最小および最大xをルックアップし、オクルーダーの最も遠い可能な深度値で深度バッファを水平方向に埋めることで、簡単になります。
+1および-1は、深度を非常に低い解像度でレンダリングしているためです。キューブを1ピクセル縮小することで、この低い解像度ではチャンクがまったく見えなくなるエッジケースを回避できますが、フル解像度では見えるようになります。
[画像: シーンにはギャップが見えますが、オクルージョンカラーの低解像度で1ピクセルのインセットがない場合、ギャップは完全に覆われ、誤ったオクルージョンが発生します。]
シーンにはギャップが見えますが、オクルージョンカラーの低解像度で1ピクセルのインセットがない場合、ギャップは完全に覆われ、誤ったオクルージョンが発生します。
オクルージョンカラーは、候補となるすべてのオクルージョンに対して同様のことを行いますが、ここでは最も近い距離を記録し、1ピクセルのインセットはありません。深度がバッファ内のいずれかの値以下であれば、チャンクは表示されており、それ以上のピクセルをチェックする必要はありません。深度がどこにも通過しない場合、チャンクはカリングできます。ここで注目すべき変更点は、候補チャンクのいずれかのコーナー頂点が無効な場合(カメラのニアプレーンの後ろにあるため)、チェックを実行できないため、単純に表示されていると見なされることです。
このアプローチはさまざまな状況でうまく機能し、遅いCPUでもパフォーマンスを発揮します。特に古いシステムや私のシステムのようなグラフィックスが弱いシステムが、洞窟の可視性アルゴリズムの複雑さやオーバーヘッドなしに、ほとんどの通常のプレイシナリオで良好なフレームレートを達成するのに役立ちます。
プロセス
もちろん、私はこのアプローチを完全に形成され最適化された状態で思いついたわけではありません。どこかから始めなければなりませんでした。最初のアプローチは、各チャンクを固定数のサブチャンクに分割することでした。各エッジで2つと4つ(それぞれチャンクあたり8つと16のサブチャンク)を試しました。そして、可視面があるかどうかに関係なく、サブチャンクが不透明なブロックで満たされているかどうかを単純に記録しました。
次に、非空気/空ブロックや可視エンティティを含むチャンクのすべてのサブチャンクをオクルージョンカラーに送信し、完全な4x4射影行列を使用して頂点を変換し、1/wで乗算してx/y/z座標を記録しました。変換された座標をリストに保存し、オクルーダーを1パスでレンダリングし、別のパスでオクルージョン候補を読み取りました。候補のいずれかのチャンクサブチャンクが表示されていれば、チャンク全体が表示されているとマークされました。
この段階では、カメラの後ろに完全に隠れているチャンクのみを排除していたため、フラスタムカリングも適切に行っていませんでした。そのため、この段階のオクルージョンカラーもフラスタムカリングを行っていました。
これは、カリングされたチャンクをカリングするという「機能する」という言葉のいくつかの定義においては機能しました。残念ながら、それは非常に遅く、レンダリング距離が12チャンクの場合、処理に150〜200ミリ秒かかりました。これは、最適化で埋めるには大きなギャップだと思いました。しかし、試してみることにしました。
最適化1:より安価な変換
最初に、3x3のビュー回転と加算による平行移動、および線形深度の使用というアイデアを思いつきました。通常のやり方では、4x4の射影行列の乗算(16回の乗算)、次にx、y、z座標の1/wによる除算、そしてxとyのバッファサイズによる乗算が必要で、合計21回の乗算と1回の除算になります。
代わりに、次のようにすることにしました。
private static Vector3F Transform(Vector3F position, Matrix4 view, Vector2F focalLenPixels, out bool valid) {
// world to view
Vector3F viewPos;
viewPos.X = view.M11 * position.X + view.M21 * position.Y + view.M31 * position.Z + view.M41;
viewPos.Y = view.M12 * position.X + view.M22 * position.Y + view.M32 * position.Z + view.M42;
viewPos.Z = -view.M13 * position.X + view.M23 * position.Y + view.M33 * position.Z + view.M43);
// perspective divide
var invZ = 1.0f / viewPos.Z;
var xScreen = viewPos.X * invZ * focalLenPixels.X + (bufferWidth / 2);
var yScreen = viewPos.Y * invZ * focalLenPixels.Y + (bufferHeight / 2);
// distance in view space substitute for actual depth
var dist = viewPos.Z;
valid = dist > FNARenderer.ZNearPerspective;
return new Vector3F(xScreen, yScreen, dist);
}
3x3行列の乗算を行い、平行移動には加算を使用します。次に、透視除算を行い、ピクセル単位の焦点距離を乗算します。z軸に沿った深度のスケーリングは気にせず、線形ビュー空間での深度をそのまま使用します。これは私の目的には十分だからです。テクスチャなどをレンダリングしているわけではないので、私の目的にはこれで十分です。
結果は、13回の乗算と1回の除算となり、21回の乗算と1回の除算と比較して、乗算回数が62%少なくなります。これだけでも、必要な処理時間は150msから99msの0.67倍に低下しました。悪くないです!
最適化2:ワールド空間フラスタムカリング
すでにすべてをスクリーン空間に変換していたため、その空間でフラスタムカリングも試していました。それはひどいアイデアであることがすぐにわかりました。キューブのバウンディング球を簡単に計算できますが(sqrt(3) * size * 0.5)、スクリーン空間への投影後、非線形になるため、キューブの角は実際にはるかに突き出ることができます。これは、カリングをより保守的に行う必要があり、すべてが遅くなったことを意味します。
幸いなことに、フラスタム平面とワールド空間のキューブのバウンディング球との単純なドット積が、はるかに安価で正確であることが指摘されました。射影行列からフラスタム平面を抽出する方法を見つけ、それを試したところ、元の最適化されていない実行時間が0.43倍、つまり61msに低下しました。
参考までに、平面を抽出する関数を、FNAのPlane構造体を使用して示します。
public static void GetFrustumPlanes(Plane[] planes, Matrix4 viewProjection) {
Debug.Assert(planes.Length >= 6);
// left
planes[0] = new Plane(
viewProjection.M14 + viewProjection.M11,
viewProjection.M24 + viewProjection.M21,
viewProjection.M34 + viewProjection.M31,
viewProjection.M44 + viewProjection.M41
);
// right
planes[1] = new Plane(
viewProjection.M14 - viewProjection.M11,
viewProjection.M24 - viewProjection.M21,
viewProjection.M34 - viewProjection.M31,
viewProjection.M44 - viewProjection.M41
);
// bottom
planes[2] = new Plane(
viewProjection.M14 + viewProjection.M12,
viewProjection.M24 + viewProjection.M22,
viewProjection.M34 + viewProjection.M32,
viewProjection.M44 + viewProjection.M42
);
// top
planes[3] = new Plane(
viewProjection.M14 - viewProjection.M12,
viewProjection.M24 - viewProjection.M22,
viewProjection.M34 - viewProjection.M32,
viewProjection.M44 - viewProjection.M42
);
// near
planes[4] = new Plane(
viewProjection.M13,
viewProjection.M23,
viewProjection.M33,
viewProjection.M43
);
// far
planes[5] = new Plane(
viewProjection.M14 - viewProjection.M13,
viewProjection.M24 - viewProjection.M23,
viewProjection.M34 - viewProjection.M33,
viewProjection.M44 - viewProjection.M43
);
// normalize planes
for (int i = 0; i < 6; i++) {
Plane.Normalize(ref planes[i], out planes[i]);
}
}
これは十分に高速だったため、最終的にバックグラウンドスレッドとオクルージョンカラー全体から、レンダラーの通常のチャンク収集パスに移動しました。
最適化3:可視面
次に、可視ジオメトリを構成する基準が間違っていたことに気づきました。空気のような定義上見えないブロックを持つチャンク(または当時サブチャンク)はすべて潜在的に表示可能と見なしていました。もちろん、それはナイーブです。チャンクには可視面がある場合にのみ可視ジオメトリがあります。そのため、可視面のないサブチャンクをオクルージョン候補から除外しました。
これにより大幅に改善され、実行時間は元の0.21倍、つまり34msに低下しました。この段階では、SIMDを使用する必要すらなく、はるかに楽観的でした!
最適化4:近いオクルーダー、遠いカリング
この段階で、次の最適化ですべてがうまくいくようになる重要な発見がありました。遠くのサブチャンクは非常に小さくなるため、近くのサブチャンクは大きくなります。
これは、近くのオクルーダーを主に描画したいことを意味します。なぜなら、バッファの大部分を覆う近くのオクルーダーは、数ピクセルしか覆わない遠くのオクルーダーよりも、オクルードする可能性がはるかに高いからです。
また、遠くのサブチャンクを主にテストしたいことを意味します。なぜなら、遠くのサブチャンクは非常に小さくなるため、オクルードされる可能性がはるかに高く、テストするピクセルもはるかに少なくなるからです。
この仮説をテストしたところ、実行時間は0.21倍から0.14倍、つまり37msから29msに低下しました。これは魔法の弾丸ではありませんでしたが、それにつながるのに役立ちました。
最適化5:サブチャンクレベル
近くのものは大きく、遠くのものは小さいという事実(本当に革命的な洞察です、知っています、拍手をお願いします)を認識して、ミップマッピングのようなことをすべきだと気づきました。1つのサイズのサブチャンクを持つのではなく、近くではより小さなサブチャンク、遠くではより大きなサブチャンクを使用すべきです。
これはロードに大いに役立ちます。レンダリング距離が上がると、(サブ)チャンクの数は幾何級数的に増加しますが、遠くではより大きなサブチャンクを使用すると、サブチャンクの数が幾何級数的に減少するため、これら2つの力は互いに相殺されます。
また、オクルーダーはサブチャンクであってほしいと思いましたが、オクルージョン候補をそのように分割する必要性はあまりないことにも気づきました。結局、チャンク全体がオクルードされているかどうかだけを気にするなら、なぜそのテストを8つまたは16の個別のテストに分割する必要があるのでしょうか。各テストには独自の8つの頂点変換があります。そこで、オクルーダーと候補を分割しました。オクルージョン候補はチャンクのままで、オクルーダーは記事の冒頭で説明した複数のサブチャンクレベルを使用しました。
最も高いレベル(各サブチャンクが単一のブロックである場合)では、各サブチャンクまたはブロックについて2ビットの情報を記録します。それは不透明かどうか、そして不透明であればオクルーダーであるかどうか(つまり、可視面があるかどうか)です。サブチャンクがオクルーダーであるかどうかにかかわらず、不透明かどうかを追跡することは、より低いサブチャンクレベルを生成するのに役立ちます。
RAM使用量を最適化するために、実際にはこの情報をzスライスあたり2つの16ビット整数に格納しています。1つは不透明度用、もう1つはオクルージョン用です。
より高いレベル(つまり、より大きなサブチャンク)を生成するときは、前のレベルを見て、2x2x2領域内のすべての前のサブチャンクが完全に不透明であり、少なくとも1つがオクルーダーである場合にのみサブチャンクをオクルーダーとして記録するのと非常によく似たことを行います。言い換えれば、サブチャンクは、それが表す次のレベルのサブチャンクがすべて不透明であり、少なくとも1つに可視面がある場合にオクルーダーとなります。
この最適化を最終的にテストしたとき、私は驚愕しました。レンダリング距離が12チャンクの場合、平均して元の実行時間の0.04倍しかかかりませんでした。前の最適化では37msでしたが、これはわずか4msに低下しました。これは7倍以上のスピードアップです。
他の最適化も5倍高速化していたことを公平に言うと、それらも貢献していました。
この時点で、私は作業は完了したと考え、クリーンアップに移りました。
制限事項
このソフトウェアレンダリング深度オクルージョンカリングアプローチは多くのケースで非常にうまく機能しますが、破綻するインスタンスがいくつかあります。最も注目すべきは、最良のオクルーダーは単一のブロックに対応するサブチャンクであるということです。しかし、処理速度が遅くなりすぎるのを避けるために、限られた数のオクルーダーしか処理できないため、この最も高いレベルのサブチャンクを遠くまでレンダリングすることはできません。
それなしでも、1ピクセルのインセットのため、これらの1³サイズのオクルーダーは比較的早く単一ピクセルや無に縮小する傾向があるため、それらをさらに処理できたとしても、20ブロックよりも遠くに意味はありません。
したがって、プレイヤーが半径20ブロック以内に不透明なブロックがない場所にいる場合、例えば空中に飛んでいる場合や高い崖の上に立っている場合など、最も役立つオクルーダーはまったくレンダリングされません。オクルージョンカリングは依然として役立ちますが、急速に50%を下回り、25%以下になるか、さらに悪化します。
[画像: 最悪のオクルージョンカリングケース。近くのブロックからのオクルーダーが、画面下部中央に数ピクセルサイズの色のついた塊として表示されています。]
最悪のオクルージョンカリングケース。近くのブロックからのオクルーダーが、画面下部中央に数ピクセルサイズの色のついた塊として表示されています。
プレイヤーが上に移動するにつれて、サブチャンクレベルが次々とフェードアウトしていくにつれて、カリングはますます悪化します。また、プレイヤーが作成した構造物は1つ、おそらく2つしか厚くないことが多いため、多くの大きくて遠くのプレイヤーが作成した構造物はオクルーダーとは見なされないでしょう。
しかし、これらのケースはサバイバルモードスタイルのゲームプレイではそれほど一般的ではありません。最悪の場合でも、パフォーマンスはカリングなしの場合と同じパフォーマンスに低下するため、何も損なうことはありません。一方、多くの状況では、特にプレイヤーが屋内にいる場合や洞窟にいる場合、FPSは50%、100%、あるいはそれ以上向上することがあります。したがって、この制限にもかかわらず、この方法は依然として非常に価値があります。
別の問題は、オクルーダーの1ピクセルのインセットがサブチャンク間、特にチャンク間にギャップを引き起こす可能性があることです。オクルーダーは単一のチャンクに限定されているため、複数のチャンクをまたぐことはできません。これにより、そのギャップ沿いのチャンクはカリングされませんが、実際にはこれはオクルージョンカラーのパフォーマンスをほとんど損ないません。
[画像: オクルージョンデバッグビュー。プレイヤーの位置から伸びる3つのチャンクの間に、2つの対角線状のギャップが表示されています。その線に沿って、洞窟チャンクがすべて下まで見えています。]
オクルージョンデバッグビュー。プレイヤーの位置から伸びる3つのチャンクの間に、2つの対角線状のギャップが表示されています。その線に沿って、洞窟チャンクがすべて下まで見えています。
今後の作業
複数のサブチャンクレベルを実装している途中で、サブチャンクが各軸に沿って1ブロック厚のスライスである方が良いかもしれないと気づきました。例えば、サブチャンクが4ブロックのサイズであるレベル2では、4x4x1、4x1x4、1x4x4のサブチャンクになります。これらは、それらのチャンキーな対応物(言葉遊びですみません)よりもはるかに一般的であり、オクルーダーとしてより効果的になります。
また、プレイヤーが作成した構造物のジオメトリにもよりよく適合します。そして、16x16x16のサブチャンクのように実際には発生しないものとは異なり、厚さ1ブロックの16x16スライスは実際に見つかると思います。これらの大きく、より一般的なスライスは、プレイヤーが高い場所にいるときに地面をより良くカバーし、現在この方法の最悪のシナリオである地下の洞窟のカリングを改善する可能性があります。
実際には強力なGPUを持つリグで非常に高いレンダリング距離の場合に役立つかもしれないのは、レンダリング距離が増加するにつれてチェックのボリュームを減らすために、スーパーチャンクに複数のチャンクをグループ化することです。
SIMDを使用してさらに最適化を試みることもできると思いますが、正直なところそれは面倒に思え、わざわざやるかどうかはわかりません。
この記事を楽しんだなら、Block Gameのサイトをご覧ください。スクリーンショット、FAQ、開発フィードがあります。また、Mastodonの@eniko@mastodon.gamedev.placeまたはBlueskyの@enikofox.comで私をフォローすることも検討してください。