DirectX12でFrustumCulling

今更ではありますが、実装してみたので参考にしていただければ幸いです。
最初はCPUによるFrustumCullingを行い、さらにDirectX12ではCompute Shaderによる
FrustumCullingを実装してみました。視錐台カリングとも言われているみたいです。

Frustum Cullingとは

ゲーム開発では、たくさんのメッシュを描画することで
豪華なビジュアルを実現しますが、その為には無駄な描画をなくして
処理速度を上げる必要があります。
Frustum Cullingは描画するカメラ位置の範囲に入っているものだけを
描画するために、カメラの視野内に入っているかどうかを判定する技術です。
そのためには以下の要素が必要となります。

カメラの視野範囲
各メッシュのBoundingBox
上記２つを利用して描画すべきかどうかを判定

事前にですが、自作のライブラリのコードになるので擬似コードとなります。
説明の関係上、Matrixだけ以下のような感じで定義しています。

Matrix.h

	//  matrixは以下のような感じで定義してます。
	  class Matrix{
		  union {
	        float _v[16];
	        float _m[4][4];
	      };
	    //..
	   };

カメラの視野範囲

ではあらためて・・。こちらは、ビュー・プロジェクションマトリックスから算出できます。
ここでも２つの要素が必要で、視野を三角錐みたいな感じで考えると
左・右・上・下・手前・奥の6面(FrustumPlanes)と、
それらの頂点として8点(FrustumCorners)を作成します。

frustum.cpp


void	FrustumCulling::getFrustumPlanes( const Matrix &_vp, Vector4 *planes ) const
{
	Matrix vp = _vp;
	vp.transpose();
	
	Vector4 vright(vp._m[0]);
	Vector4 vup(vp._m[1]);
	Vector4 vforward(vp._m[2]);
	Vector4 vpos(vp._m[3]);

	planes[0] = vpos + vright;		// left
	planes[1] = vpos - vright;		// right
	planes[2] = vpos + vup;			// bottom
	planes[3] = vpos - vup;			// top
	planes[4] = vforward;			// near
	planes[5] = vpos - vforward;	// far
	
}

void	FrustumCulling::getFrustumCorners(const Matrix &vp, Vector4* points) const
{
	const Vector4 corners[] = {
		Vector4(-1, -1, -1, 1),
		Vector4( 1, -1, -1, 1),
		Vector4( 1,  1, -1, 1),
		Vector4(-1,  1, -1, 1),
		Vector4(-1, -1,  1, 1),
		Vector4( 1, -1,  1, 1),
		Vector4( 1,  1,  1, 1),
		Vector4(-1,  1,  1, 1) };
	Matrix invVP = vp;
	invVP.inverse();
	
	for (int i = 0; i != 8; i++)
	{
		Vector4 q = invVP.transform(corners[i]);
		points[i] = q / q.w;
	}
}

BoundingBox

こちらは、モデルの頂点データで一番小さい値と、一番大きい値を
x,y,zの3要素用意します。データの都合上vector4を2つ使って
用意しています。

frustum.cpp

struct stcBoundingBox
{
    Vector4 min;
    Vector4 max;

    stcBoundingBox()
    {
        min.x = min.y = min.z = FLT_MAX;
        min.w = max.w = 1;
        max.x = max.y = max.z = -FLT_MAX;
    }
};

このデータ形式の中に、メッシュ毎の頂点データ読み込み時に判定して
BoundingBoxデータを作成するか、データエクスポート時に作成して
データに埋め込むかのどちらかになると思います。
BoundingBoxデータをもともとのデータ形式として持っている物も
多いかと思います。

範囲内かのチェック処理

ここがメイン処理です。
まずはCPUでの処理を行うので、C++で作成してます。
あとでシェーダーでも行いますが、処理は全く同じです。

frustum.cpp

bool isBoxInFrustum(const Vector4* frPlanes, const Vector4* frCorners, const stcBoundingBox& b)
{

    for (int i = 0; i < 6; i++)
    {
        int r = 0;
        r += (frPlanes[i].dot(Vector4(b.min.x, b.min.y, b.min.z, 1.f)) < 0) ? 1 : 0;
        r += (frPlanes[i].dot(Vector4(b.max.x, b.min.y, b.min.z, 1.f)) < 0) ? 1 : 0;
        r += (frPlanes[i].dot(Vector4(b.min.x, b.max.y, b.min.z, 1.f)) < 0) ? 1 : 0;
        r += (frPlanes[i].dot(Vector4(b.max.x, b.max.y, b.min.z, 1.f)) < 0) ? 1 : 0;
        r += (frPlanes[i].dot(Vector4(b.min.x, b.min.y, b.max.z, 1.f)) < 0) ? 1 : 0;
        r += (frPlanes[i].dot(Vector4(b.max.x, b.min.y, b.max.z, 1.f)) < 0) ? 1 : 0;
        r += (frPlanes[i].dot(Vector4(b.min.x, b.max.y, b.max.z, 1.f)) < 0) ? 1 : 0;
        r += (frPlanes[i].dot(Vector4(b.max.x, b.max.y, b.max.z, 1.f)) < 0) ? 1 : 0;
        if (r == 8) return false;
    }

    int r = 0;
    r = 0; for (int i = 0; i < 8; i++)    r += ((frCorners[i].x > b.max.x) ? 1 : 0);
    if (r == 8) return false;
    r = 0; for (int i = 0; i < 8; i++)    r += ((frCorners[i].x < b.min.x) ? 1 : 0);
    if (r == 8) return false;
    r = 0; for (int i = 0; i < 8; i++)    r += ((frCorners[i].y > b.max.y) ? 1 : 0);
    if (r == 8) return false;
    r = 0; for (int i = 0; i < 8; i++)    r += ((frCorners[i].y < b.min.y) ? 1 : 0);
    if (r == 8) return false;
    r = 0; for (int i = 0; i < 8; i++)    r += ((frCorners[i].z > b.max.z) ? 1 : 0);
    if (r == 8) return false;
    r = 0; for (int i = 0; i < 8; i++)    r += ((frCorners[i].z < b.min.z) ? 1 : 0);
    if (r == 8) return false;

    return true;
}

CPU Culling の結果

これで、基本的なCPUによるFrustumCullingは実装できます。
ただ、CPUでカリングを行うと描画の手前で毎回チェックを行う必要があるので
以下のように非常に細かくCPUを専有します。

（この細かいバーコードみたいなのが、描画チェックにかかった時間になります）
Optikでプロファイルしています。
こちらについて詳細は以下の動画をどうぞ。

GPUでカリング

DirectX12ではComputeShaderを使うことで、GPUを使って計算処理だけを並列で
行うことができます。
GPUではなにかの結果が次の計算に影響を与える場合はには不向きですが
静止モデルを複数配置している場合、それらのBoundingBoxは動かないので
GPUで並列でカメラの範囲内に入っているかのチェックを行っても
不都合がありません。GPU向けの処理ですね。

ComputeShaderに必要なもの

まず、ComputeShaderを実行するには通常の描画とは別の
CommandList,CommandQueue,CommandAllocatorが必要となります。
また、それらの完了待ちにFenceも必要です。
このあたりは、通常のCommand作成時のパラメーターを
D3D12_COMMAND_LIST_TYPE_COMPUTEにするだけでだいたい大丈夫だと思います。

また、RootSignatureやPipelineStateObjectも専用のものが必要となります。

ComputeShaderでFrustumCullingに必要なデータ

3つ必要になります。

FrustumPlanes(Vector4*6)とFrustumCorners(Vector4*8)（ConstantBuffer)
BoundingBoxの配列データ（メッシュの数分）（SRV StructuredBuffer)
結果書き込み用データ(UAV RWStructuredBuffer)

FrustumPlanes,Corners(ConstantBuffer)

こちらは最初に作成したカメラの情報です。
ConstantBufferとして、作成すれば問題ありません。

BoundingBoxの配列データ(SRV StructuredBuffer)

こちらはBoundingBox(Vector4*2)のデータの配列（メッシュの数分）です。
ConstantBufferでは、32bit*4が4096しか割り当てることができません。
1つのBoundingBoxにmaxとminで32bit*4を2個消費するので、2048メッシュしか判定できません。
そこで、StructuredBufferとしてcompute shaderにデータを渡すことで
これを解消できます。

hlsl側には数を指定する必要がなく、どの定数レジスタを使用するかを
設定するだけです。（今回はt0）

constant bufferと同じ様に、CreateCommittedResourceでUPLOADバッファーを作成し、
同じくDescriptorHeapをSRVとして作成。
各種パラメーターをセットしてそれらをCreateShaderResourceView()に渡すことで
準備ができます。

frustum.cpp

	D3D12_SHADER_RESOURCE_VIEW_DESC desc = {};
	desc.Format = DXGI_FORMAT_UNKNOWN;
	// ViewDimensionをBufferにします。
	desc.ViewDimension = D3D12_SRV_DIMENSION_BUFFER;
	desc.Shader4ComponentMapping = D3D12_DEFAULT_SHADER_4_COMPONENT_MAPPING;
	// ここで最大の要素数。4096以上がセットできます。
	desc.Buffer.NumElements = box_num;
	// ここはstcBoundingBoxのsizeofの値です。1要素あたりのサイズ
	desc.Buffer.StructureByteStride = bytestride;
	desc.Buffer.Flags = D3D12_BUFFER_SRV_FLAG_NONE;

	device->CreateShaderResourceView((ID3D12Resource*)resource, &desc, cpu_handle);

結果書き込み用データ( UAV RWStructuredBuffer )

vertex shaderやpixel shaderにない要素ですが、
compute shaderは計算のみを行うのでその結果の出力先を作成、指定する必要が
あります。
CommittedResource作成時のパラメーターを下記のようにセットして
作成します。
今回はintサイズのデータをbox_num分作成してみています。
判定したBoundingBoxが視界範囲内なら1、そうでないなら0をセットします。

frustum.cpp

	auto prop = CD3DX12_HEAP_PROPERTIES(D3D12_HEAP_TYPE_CUSTOM);
	prop.CPUPageProperty = D3D12_CPU_PAGE_PROPERTY_WRITE_BACK;
	prop.MemoryPoolPreference = D3D12_MEMORY_POOL_L0;	

	auto buff = CD3DX12_RESOURCE_DESC::Buffer((sizeof(int) * box_num + 0xff) & ~0xff, D3D12_RESOURCE_FLAG_ALLOW_UNORDERED_ACCESS);
	
	device->CreateCommittedResource(
		&prop,
		D3D12_HEAP_FLAG_NONE,
		&buff,
		D3D12_RESOURCE_STATE_UNORDERED_ACCESS,
		nullptr,
		IID_PPV_ARGS(&resource)
	);

	// 実行後、結果データを読み出すためにマップしておきます。
	void *mapped_data;
	D3D12_RANGE range = { 0, 1 };
	HRESULT result = resource->Map(0, &range, &mapped_data);

Compute Shaderのシェーダー処理

シェーダーに渡すデータの準備と実行準備ができたので、
シェーダーでの計算処理です。
まずは引き取るデータ形式から指定します。

frustum_culling.hlsl

// BBのデータ形式を宣言。
struct stcBoundingBox {
	float4 min;
	float4 max;
};

// 結果書き込み先です。UAVのデータです。
RWStructuredBuffer<int> result : register(u0);

// カメラ視錐台のデータです。ConstantBuffer。
cbuffer cbuff0 : register(b0) {
	float4		frustumPlanes[6];
	float4		frustumCorners[8];
};

// 実際のBoundingBoxの配列データです。
StructuredBuffer<stcBoundingBox> box : register(t0);

ここからはエントリポイントになります。
スレッドの実行数などはまだあまり調べられていません。
gID.xに処理すべきBoundingBoxのindexが入ってくるので
配列データから参照し、判定した結果を出力します。

frustum_culling.hlsl

[numthreads(1, 1, 1)]
void frustum_culling(uint3 gID : SV_GroupID)
{
   result[gID.x] = isBoxInFrustum(box[gID.x]);
}

実際の判定関数はこちらです。基本的にC++で書いた処理と同じです。
特に変更は必要ありません。

frustum_culling.hlsl

int isBoxInFrustum(stcBoundingBox bb)
{
	for( int i = 0; i < 6; i++ )
	{
		int r = 0;
		r += (dot (frustumPlanes[i], float4(bb.min.x, bb.min.y, bb.min.z, 1.0f)) < 0.f) ? 1 : 0;
		r += (dot (frustumPlanes[i], float4(bb.max.x, bb.min.y, bb.min.z, 1.0f)) < 0.f) ? 1 : 0;
		r += (dot (frustumPlanes[i], float4(bb.min.x, bb.max.y, bb.min.z, 1.0f)) < 0.f) ? 1 : 0;
		r += (dot (frustumPlanes[i], float4(bb.max.x, bb.max.y, bb.min.z, 1.0f)) < 0.f) ? 1 : 0;
		r += (dot (frustumPlanes[i], float4(bb.min.x, bb.min.y, bb.max.z, 1.0f)) < 0.f) ? 1 : 0;
		r += (dot (frustumPlanes[i], float4(bb.max.x, bb.min.y, bb.max.z, 1.0f)) < 0.f) ? 1 : 0;
		r += (dot (frustumPlanes[i], float4(bb.min.x, bb.max.y, bb.max.z, 1.0f)) < 0.f) ? 1 : 0;
		r += (dot (frustumPlanes[i], float4(bb.max.x, bb.max.y, bb.max.z, 1.0f)) < 0.f) ? 1 : 0;
		if( r == 8 ) return 0;
	}

	int r = 0;
	r = 0; for ( int a = 0; a < 8; a++ ) r += ( (frustumCorners[a].x > bb.max.x) ? 1 : 0); if ( r == 8 ) return 0;
	r = 0; for ( int b = 0; b < 8; b++ ) r += ( (frustumCorners[b].x < bb.min.x) ? 1 : 0); if ( r == 8 ) return 0;
	r = 0; for ( int c = 0; c < 8; c++ ) r += ( (frustumCorners[c].y > bb.max.y) ? 1 : 0); if ( r == 8 ) return 0;
	r = 0; for ( int d = 0; d < 8; d++ ) r += ( (frustumCorners[d].y < bb.min.y) ? 1 : 0); if ( r == 8 ) return 0;
	r = 0; for ( int e = 0; e < 8; e++ ) r += ( (frustumCorners[e].z > bb.max.z) ? 1 : 0); if ( r == 8 ) return 0;
	r = 0; for ( int f = 0; f < 8; f++ ) r += ( (frustumCorners[f].z < bb.min.z) ? 1 : 0); if ( r == 8 ) return 0;

	return 1;
}

GPU Cullingの結果

CPUと比べると一目瞭然ですね。

実行完了待ちから、CPUへのデータ書き戻しまでも合わせて計測していますが
かなり低コストで実行できています。GPU恐るべし。
GPUからの結果の書き戻し処理は、
作成したUAVのCommittedResourceでmapしたポインタから
データをまるごとコピーするだけでOKです。

frustum_culling.cpp

	// command queueのexecuteとfence待ちを終えてから
	int culling_result[box_num];
	// UAVでmapした領域からメモリにコピー。
	memcpy(&culling_result, mapped_data, sizeof(int) * box_num);

結果を動画でどうぞ

Youtubeチャンネルもやってます。
良ければチャンネル登録してください。

その先は

FrustumCullingはカリングの一番最初の部分かと思います。
この先は、Occlusion Cullingやその他GPU Driven Renderingによる
Meshlet Cullingなどに進んでいくと思います。
今回の件は、カリングの入門として参考になれば幸いです。
カリングは大量の描画の時代に非常に重要な技術ですね。

参考