社内勉強会「レンダリング合宿１」 ソフトウェアラスタライザー 最適化編03 マルチスレッドを利用した最適化

#ソフトウェアラスタライザー 最適化編03 マルチスレッドを利用した最適化

##リポジトリ
https://github.com/NoriyukiHiromoto/Rendering01_SoftwareRasterizer/tree/02_03_multi_threading

今回の対応で FPS 5.9 ⇒ 33.6 に上昇しました。
![r.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/358928/76fad328-c697-38c3-0fca-ed67f74cd2fb.gif)


##最初に
今回はいよいよスレッドを用いた最適化を行います。
一番効果的で一番面倒くさい最適化になります。

##まずは準備から
まずはマルチスレッド化するにあたってタスクシステムを作りました。
コア数分のパイプラインを用意してジョブを積んで一気に処理するという簡単な仕組みになっています。
実装は以下のソースになります。
TaskSystem.h / TaskSystem.cpp / TaskPipeline.h / TaskPipeline.cpp

遥か昔にSeleneというゲーム用ライブラリを作ったときのものを流用しています。
10年くらい前でしょうか？

単純に積まれているジョブを各パイプラインが取得して実行していくというだけのものです。
途中で同期をとる必要があるのでバリア同期の機能も入れてあります。

##すぐに並列化できそうなところから
現状の実装でマルチスレッド化できるところを考えてみましょう。

まずは一番簡単に出来そうなのはバッファをクリアしている箇所です。
Framework.cppでは「バッファをクリア⇒描画⇒表示」という流れで行っていますが、これをダブルバッファにすることで
A.「次のフレームの描画」
B.「表示⇒カラーバッファクリア」
C.「深度バッファクリア」
D.「Gバッファクリア」
という形で並列化できます。

というわけで実装した結果が以下になります。

```cpp:Framework.cpp
			// バッファを画面に転送してクリアするジョブ（必要ならBMP出力も
			TaskSystem::Instance().PushQue([&](void* pData) {
				::BitBlt(
					hWindowDC, 0, 0, SCREEN_WIDTH, SCREEN_HEIGHT,
					DIBBuffer[DrawPage].SurfaceDC(), 0, 0, SRCCOPY);
				if (_RequireSaveScene)
				{
					_RequireSaveScene = false;
					SaveToBMP(L"ScreenShot.bmp", BackBuffers[DrawPage]);
				}
				BackBuffers[DrawPage].Clear(0xFF000000);
			}, nullptr);
			// 深度バッファをクリアするジョブ
			TaskSystem::Instance().PushQue([&](void* pData) {
				DepthBuffers[DrawPage].Clear(1.0f);
			}, nullptr);
			// Gバッファをクリアするジョブ
			TaskSystem::Instance().PushQue([&](void* pData) {
				GBuffers[DrawPage].Clear(GBufferData{ 0xFFFF });
			}, nullptr);

			// フレームのdeltaを求める
			static auto PreTime = Timer.GetMicro();
			auto NowTime = Timer.GetMicro();
			auto FrameTime = (fp32)(NowTime - PreTime) / 1000000.0f;
			PreTime = NowTime;

			// フレームの更新処理
			_App.OnUpdate(FrameTime);
			_App.OnRendering(&BackBuffers[RenderPage], &DepthBuffers[RenderPage], &GBuffers[RenderPage]);
```

他にできそうなところは遅延シェーディングの箇所でしょうか。
ポスト処理として全画面を処理しているので、ここは並列化しても特に問題なさそうです。

```cpp:Renderer.cpp
		const int32 w = SCREEN_WIDTH;
		const int32 h = 5;
		const int32 yn = SCREEN_HEIGHT / h;

		for (int32 y = 0; y < yn; ++y)
		{
			union PackedRect {
				struct {
					int16 x, y, w, h;
				};
				int64 packed;
			};
			PackedRect Rect;
			Rect.x = 0;
			Rect.y = y * h;
			Rect.w = w;
			Rect.h = h;

			TaskSystem::Instance().PushQue([this](void* pData) {
				PackedRect Rc;
				Rc.packed = (int64)pData;
				DeferredShading(Rc.x, Rc.y, Rc.w, Rc.h);
			}, (void*)Rect.packed);
		}
```

ここまでは簡単に並列化することが出来ました。

しかし処理負荷を考えたら一番高速化したいのはポリゴンのラスタライズ処理の部分ですが、
そのままメッシュ描画を並列化することはできません。

メッシュ描画の処理を並列化してもポリゴンが重なっている箇所で同一ピクセルに対して複数のスレッドから読み書きを行おうとする可能性があり、深度バッファに対しての操作が正常に行われないため前後関係がおかしくなりちらつきが発生します。

深度バッファへのアクセスにCriticalSectionを使うとかInterlock命令を使うとかで回避できますが、深度バッファにアクセスする旅に同期処理を発生させるのはどう考えても現実的ではありませんし、いちいち同期をするなら並列化する意味がありません。

なので並列化をするためにまずはラスタライズ処理を並列実行しても問題ないような仕組みに書き換えるところからやっていきます。

##タイルベースレンダリング
タイルベースレンダリングとは文字通りタイル単位でレンダリングを行う手法です。

画面をMxN個のタイルに分割し、それぞれのタイル毎にレンダリングを行うようにします。
この方法であればタイル単位では同一ピクセルへの同時アクセスは発生しませんので並列化する事ができます。

これに伴ってメッシュの描画フローが変更されます。
今までの実装では

　1.メッシュのトランスフォーム
　2.ポリゴンのクリッピング
　3.ポリゴンのラスタライズ

という処理でしたが、これを

　1.メッシュのトランスフォーム
　2.ポリゴンのクリッピング
　3.ポリゴンが重なるすべてのタイルのポリゴンリストに登録
　4.タイル毎にポリゴンリストのポリゴンをラスタライズ

このように処理を変更します。
この変更によって
「1.2.3.」をまとめて1つのジョブとして並列化する事が出来、さらに「4.」でタイル毎に並列化することが出来ます。
リストへの登録もCriticalSectionを行わないように先に最大容量の配列を用意しておいてInterlock命令でインデックス操作をしています。

まずはメッシュのレンダリング処理を見てみましょう。

```cpp:Renderer.cpp
	// メッシュ毎にジョブを作って並列処理する
	// ・座標変換
	// ・シザリング
	// ・レンダリングする可能性のあるタイルへのデータの追加
	{
		const int32 MeshCount = int32(_RenderMeshDatas.size());
		for (int32 i = 0; i < MeshCount; ++i)
		{
			TaskSystem::Instance().PushQue([&](void* pData) {
				auto* pMesh = reinterpret_cast<RenderMeshData*>(pData);
				const auto VertexCount = pMesh->pMeshData->GetVertexCount();
				ASSERT(VertexCount <= MAX_VERTEX_CACHE_SIZE);
				thread_local static Vector4 Positions[MAX_VERTEX_CACHE_SIZE];
				thread_local static Vector3 Normals[MAX_VERTEX_CACHE_SIZE];
				const auto mWorld = pMesh->mWorld;
				const auto mViewProj = _mViewProj;
				auto pPosTbl = pMesh->pMeshData->GetPosition();
				for (auto i = 0; i < VertexCount; ++i)
				{
					Matrix_Transform4x4(Positions[i], pPosTbl[i], mViewProj);
				}
				auto pNormalTbl = pMesh->pMeshData->GetNormal();
				for (auto i = 0; i < VertexCount; ++i)
				{
					Matrix_Transform3x3(Normals[i], pNormalTbl[i], mWorld);
				}
				RenderTriangle(
					pMesh->TriangleId,
					pMesh->TextureId,
					pMesh->pMeshData,
					Positions,
					Normals,
					pMesh->pMeshData->GetTexCoord(),
					VertexCount,
					pMesh->pMeshData->GetIndex(),
					pMesh->pMeshData->GetIndexCount());
			}, &_RenderMeshDatas[i]);
		}

		TaskSystem::Instance().PushBarrier();
	}
```

このようにメッシュのレンダリング単位でジョブを作成して並列化を行っています。

座標変換されクリッピングされたあとの各ポリゴンのバウンディングボックスと交差するタイルに対してポリゴンを追加していきます。

```cpp:Renderer.cpp
	const auto x0 = int32(bbMinX);
	const auto x1 = int32(bbMaxX);
	const auto y0 = int32(bbMinY);
	const auto y1 = int32(bbMaxY);

	const auto tx0 = x0 / BUFFER_TILE_SIZE_X;
	const auto tx1 = std::min(x1 / BUFFER_TILE_SIZE_X, MAX_TILE_COUNT_X - 1);
	const auto ty0 = y0 / BUFFER_TILE_SIZE_Y;
	const auto ty1 = std::min(y1 / BUFFER_TILE_SIZE_Y, MAX_TILE_COUNT_Y - 1);

	for (auto ty = ty0; ty <= ty1; ++ty)
	{
		for (auto tx = tx0; tx <= tx1; ++tx)
		{
			PushTriangleToTile(
				tx, ty,
				bbMinX, bbMinY, bbMaxX, bbMaxY,
				InvDenom,
				TriangleId, TextureId,
				v0, v1, v2);
		}
	}
```

タイル毎に保持しているリストに対してポリゴンの情報を追加します。

```cpp:Renderer.cpp
void Renderer::PushTriangleToTile(
	int32 tx, int32 ty,
	fp32 bbMinX, fp32 bbMinY, fp32 bbMaxX, fp32 bbMaxY, fp32 InvDenom,
	uint16 TriangleId, uint16 TextureId, InternalVertex v0, InternalVertex v1, InternalVertex v2)
{
	const auto minTileX = tx * BUFFER_TILE_SIZE_X;
	const auto minTileY = ty * BUFFER_TILE_SIZE_Y;
	const auto maxTileX = minTileX + BUFFER_TILE_SIZE_X - 1;
	const auto maxTileY = minTileY + BUFFER_TILE_SIZE_Y - 1;

	auto& Dst = _RasterizeDatas[ty][tx];
	auto& Tri = Dst.Triangles[Dst.Count.Increment() - 1];
	Tri.bbMinX		= std::max(int16(bbMinX), int16(minTileX));
	Tri.bbMinY		= std::max(int16(bbMinY), int16(minTileY));
	Tri.bbMaxX		= std::min(int16(bbMaxX), int16(maxTileX));
	Tri.bbMaxY		= std::min(int16(bbMaxY), int16(maxTileY));
	Tri.TriangleId	= TriangleId;
	Tri.TextureId	= TextureId;
	Tri.InvDenom	= InvDenom;
	Tri.v0			= v0;
	Tri.v1			= v1;
	Tri.v2			= v2;
}
```

```cpp:Renderer.cpp
	// タイルごとにジョブを作って並列処理する
	// ・三角形のラスタライズをする
	// ・ピクセルごとの深度テストをする
	// ・ピクセルごとの法線とUVをとマテリアル情報をGBufferに書き込む
	{
		const int32 txCount = (SCREEN_WIDTH  + BUFFER_TILE_SIZE_X - 1) / BUFFER_TILE_SIZE_X;
		const int32 tyCount = (SCREEN_HEIGHT + BUFFER_TILE_SIZE_Y - 1) / BUFFER_TILE_SIZE_Y;
		for (int32 y = 0; y < tyCount; ++y)
		{
			for (int32 x = 0; x < txCount; ++x)
			{
				union PackedPosition {
					struct {
						int32 x, y;
					};
					int64 packed;
				};
				PackedPosition Position;
				Position.x = x;
				Position.y = y;

				TaskSystem::Instance().PushQue([this](void* pData) {
					PackedPosition Pos;
					Pos.packed = (int64)pData;
					RasterizeTile(Pos.x, Pos.y);
				}, (void*)Position.packed);
			}
		}

		TaskSystem::Instance().PushBarrier();
	}
```

最後にタイル毎にジョブを発行して全てのタイルのラスタライズを並列に処理します。

#最後に
今回はスレッドを用いた並列化による最適化を行いました。
８コア環境で６倍前後の高速化が行えたので劇的に処理時間が改善しています。

実行してみるとわかりますがタスクマネージャーでCPUをぶん回している感が出ています。
CPUのコア数は増える一方なのでいかに効率的に並列化していくかが大事かと思います。