ソフトウェアラスタライザー最適化編01 簡単に出来る基本的な最適化

リポジトリ

今回の対応で FPS 4.4 ⇒ 5.9 に上昇しました。

最初に

今回は割と簡単に対応できる以下３つの最適化を行います。
1.メッシュデータの最適化
2.ラスタライズの最適化
3.テクスチャサンプリングの最適化

1.メッシュデータの最適化

レンダリングの中身を変えることなく対応できる最適化です。
現状では単純にトライアングルを全てレンダラーに流し込んでいますが、ハードエッジのみで構成されたモデルでもない限りは同一の頂点が多数含まれています。
今回はこの重複した頂点データをマージして総頂点数を減らすことで頂点変換処理にかかる時間を減らしたいと思います。
メモリも減るので一石二鳥です。

Application.cpp

	// 同一頂点をマージするためのローカル関数
	std::map<VertexData, uint16> VertexMap;
	auto AddVertex = [&](VertexData v, MeshData& Dst)
	{
		// すでに存在する場合はインデックスを返す
		auto it = VertexMap.find(v);
		if (it != VertexMap.end())
		{
			return (*it).second;
		}

		// 新規に追加してそのインデックスを返す
		const uint16 LocalIndex = uint16(Dst._Position.size());

		Dst._Position.push_back(Vector3{ v.Position[0], v.Position[1], v.Position[2] });
		Dst._Normal.push_back(Vector3{ v.Normal[0], v.Normal[1], v.Normal[2] });
		Dst._TexCoord.push_back(Vector2{ v.TexCoord[0], v.TexCoord[1] });

		VertexMap.insert(std::make_pair(v, LocalIndex));
		return LocalIndex;
	};

	// ファイルパスの作成
	std::string FullPath = pFileName;
	size_t path_i = FullPath.find_last_of("\\") + 1;
	size_t ext_i = FullPath.find_last_of(".");
	std::string Dir = FullPath.substr(0, path_i);
	std::string ExtName = FullPath.substr(ext_i, FullPath.size() - ext_i);
	std::string FileName = FullPath.substr(path_i, ext_i - path_i);

	_MeshDatas = std::vector<MeshData>();

	// メッシュファイルを読み込み
	HANDLE hFile = ::CreateFileA(pFileName, GENERIC_READ, FILE_SHARE_READ, nullptr, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, nullptr);
	if (hFile != INVALID_HANDLE_VALUE)
	{
		DWORD ReadedBytes;

		MeshFileBinaryHead Head;
		::ReadFile(hFile, &Head, sizeof(Head), &ReadedBytes, nullptr);

		if (Head.GUID == 'MBIN')
		{
			_MeshDatas.resize(Head.MeshCount);
			for (auto iMesh = 0U; iMesh < Head.MeshCount; ++iMesh)
			{
				auto& Dst = _MeshDatas[iMesh];

				MeshFileBinary MeshBin;
				::ReadFile(hFile, &MeshBin, sizeof(MeshBin), &ReadedBytes, nullptr);

				// テクスチャの読み込み
				Dst._Texture.Load((Dir + MeshBin.TextureName + ".dds").c_str());

				// ジオメトリデータ読み込み
				std::vector<VertexData> VertexDatas(MeshBin.TriangleVertexCount);
				::ReadFile(hFile, &(VertexDatas[0]), sizeof(VertexData) * MeshBin.TriangleVertexCount, &ReadedBytes, nullptr);

				// 頂点データ＆頂点インデックス
				for (auto&& v : VertexDatas)
				{
					Dst._Index.push_back(AddVertex(v, Dst));
				}
			}
		}

		::CloseHandle(hFile);
	}

2.ラスタライズの最適化

三角形のラスタライズ部分を最適化してみたいと思います。
この辺はいろいろなやり方があったりしますが今回はシンプルに一度三角形の外に出たら破棄するという方法をとります。

現状のラスタライザは１ラインずつ処理されており、左端から右端に順番にラスタライズ処理を行っています。
この時内外判定の結果としては以下の３通りしかありません。
1.外 ⇒ 中 ⇒ 外
2.外 ⇒ 中
3.中 ⇒ 外
三角形は凸型の形状をしていますから、一度三角形の中に入った後で外に出た場合は再び三角形の中に入る事はないので、中から外に出た場合はその時点でラインの処理を終わらせることが出来ます。

該当のコードは以下の部分です。

Renderer.cpp

	// 求めたバウンディング内をforで回す
	fp32 py = fp32(y0) + 0.5f;
	for (int32 y = y0; y <= y1; ++y, py += 1.0f)
	{
		bool bRasterized = false;
		bool bFirstSampling = true;
		int32 x_offset = 0;
		fp32 px = fp32(x0) + 0.5f;
		for (auto x = x0; x <= x1; ++x, px += 1.0f, ++x_offset)
		{
			// 辺1-2に対して内外判定
			auto b0 = EdgeFunc(p1.x, p1.y, p2.x, p2.y, px, py);
			if (b0 < 0.0f) if (bRasterized) break; else continue;
			// 辺2-0に対して内外判定
			auto b1 = EdgeFunc(p2.x, p2.y, p0.x, p0.y, px, py);
			if (b1 < 0.0f) if (bRasterized) break; else continue;
			// 辺0-1に対して内外判定
			auto b2 = EdgeFunc(p0.x, p0.y, p1.x, p1.y, px, py);
			if (b2 < 0.0f) if (bRasterized) break; else continue;

			bRasterized = true;

3.テクスチャサンプリングの最適化

テクスチャの最適化は２つになります。
1.サンプリングするピクセルを求める処理の最適化
2.サンプリングした後でブレンドする処理の最適化

1.サンプリングするピクセルを求める処理の最適化

テクスチャのサンプリングに関する最適化から行っていきたいと思います。
まず昔のハードウェアではテクスチャのサイズに2^nという制限がありました、実はこの制限のおかげで可能になる最適化があるからです。

具体的にはピクセル座標を求める際に乗算除算余剰の計算をしている箇所がすべてビット演算だけで処理出来るようになります。

もしテクスチャサイズが256であれば
「value % 256」⇒「value & 255」
「value * 256」⇒「value << 8」
「value / 256」⇒「value >> 8」
という風に置き換えることが出来ます。

元のソースは

	u += 256.0f;
	v += 256.0f;

	const auto& Src = _Surface[0];

	const auto uf = u * fp32(Src.Width);
	const auto vf = v * fp32(Src.Height);
	const auto ui0 = int32(uf);
	const auto vi0 = int32(vf);

	const auto mui0 = ui0 % Src.Width;
	const auto mui1 = (ui0 + 1) % Src.Width;
	const auto mvi0 = vi0 % Src.Height;
	const auto mvi1 = (vi0 + 1) % Src.Height;

	const auto x0y0 = Src.Color[mui0 + (mvi0 * Src.Width)];
	const auto x1y0 = Src.Color[mui1 + (mvi0 * Src.Width)];
	const auto x0y1 = Src.Color[mui0 + (mvi1 * Src.Width)];
	const auto x1y1 = Src.Color[mui1 + (mvi1 * Src.Width)];

	return Color::Lerp(x0y0, x1y0, x0y1, x1y1, uf - fp32(ui0), vf - fp32(vi0));

次のように置き換えられます。

	u += 256.0f;
	v += 256.0f;

	const auto level = 0;
	const auto& Src = _Surface[std::min(level, _SurfaceCount - 1)];

	const auto uf = u * Src.WidthF;
	const auto vf = v * Src.HeightF;
	const auto ui0 = int32(uf);
	const auto vi0 = int32(vf);

	const auto mui0 = ui0 & Src.UMask;
	const auto mui1 = (ui0 + 1) & Src.UMask;
	const auto mvi0 = vi0 & Src.VMask;
	const auto mvi1 = (vi0 + 1) & Src.VMask;

	const auto x0y0 = Src.Color[mui0 + (mvi0 << Src.UBit)];
	const auto x1y0 = Src.Color[mui1 + (mvi0 << Src.UBit)];
	const auto x0y1 = Src.Color[mui0 + (mvi1 << Src.UBit)];
	const auto x1y1 = Src.Color[mui1 + (mvi1 << Src.UBit)];

	return Color::Lerp(x0y0, x1y0, x0y1, x1y1, uf - fp32(ui0), vf - fp32(vi0));

2.サンプリングした後でブレンドする処理の最適化

Color::Lerp()で取得した４点をブレンドしていますがこの部分も最適化していきます。
まずは最適化前のソースですが、こちらは素直にRGBAチャンネルをそれぞれブレンドしています。

	static Color Lerp(Color x0y0, Color x1y0, Color x0y1, Color x1y1, fp32 rateX, fp32 rateY)
	{
		// y0
		Color y0;
		y0.r = uint8(x0y0.r + fp32(x1y0.r - x0y0.r) * rateX);
		y0.g = uint8(x0y0.g + fp32(x1y0.g - x0y0.g) * rateX);
		y0.b = uint8(x0y0.b + fp32(x1y0.b - x0y0.b) * rateX);
		y0.a = uint8(x0y0.a + fp32(x1y0.a - x0y0.a) * rateX);
		// y1
		Color y1;
		y1.r = uint8(x0y1.r + fp32(x1y1.r - x0y1.r) * rateX);
		y1.g = uint8(x0y1.g + fp32(x1y1.g - x0y1.g) * rateX);
		y1.b = uint8(x0y1.b + fp32(x1y1.b - x0y1.b) * rateX);
		y1.a = uint8(x0y1.a + fp32(x1y1.a - x0y1.a) * rateX);
		// result
		Color result;
		result.r = uint8(y0.r + fp32(y1.r - y0.r) * rateY);
		result.g = uint8(y0.g + fp32(y1.g - y0.g) * rateY);
		result.b = uint8(y0.b + fp32(y1.b - y0.b) * rateY);
		result.a = uint8(y0.a + fp32(y1.a - y0.a) * rateY);
		return result;
	}

これを最適化する上でよくある方法はSIMDを利用して並列化するといった手法になります。
Windows98とかの頃は画像処理といえばMMXを使って最適化していました。

今回はSIMD系の命令を使わずに並列化していこうと思います。
まずデータとしては32bitのunsigned intに[A][B][G][R]と8bitずつデータが並んでいます。
当然このままだと計算できないので、これを64bitのunsigned long longに移して[_A][_B][_G][_B]という風に16bitずつのデータに展開します。
この状態でのブレンドの計算をすることで４チャンネル同時にブレンドの計算をすることが出来ます。

以上を踏まえて置き換えたものが以下になります。

	static Color Lerp(Color x0y0, Color x1y0, Color x0y1, Color x1y1, fp32 rateX, fp32 rateY)
	{
		// ＿＿＿＿＿
		// |R|G|B|A|             32bit RGBA
		// ￣￣￣￣￣
		//     ↓
		// ＿＿＿＿＿  ＿＿＿＿＿
		// |R| |B| |  | |G| |A|  32bit R_G_  32bit _G_A
		// ￣￣￣￣￣  ￣￣￣￣￣
		//     ↓
		// ＿＿＿＿＿＿＿＿
		// |R| |B| |G| |A|       64bit packed R_B_G_A
		// ￣￣￣￣￣￣￣￣

		const auto rateX128 = int32(rateX * 128.0f);
		const auto rateX128inv = 0x80 - rateX128;
		const auto rateY128 = int32(rateY * 128.0f);
		const auto rateY128inv = 0x80 - rateY128;

		const auto mask_1010 = 0xFF00FF00;
		const auto mask_0101 = 0x00FF00FF;
		const auto mask = (uint64(mask_1010) << 24) | uint64(mask_0101);

		auto x0y0_packed = (uint64(x0y0.data & mask_1010) << 24) | uint64(x0y0.data & mask_0101);
		auto x1y0_packed = (uint64(x1y0.data & mask_1010) << 24) | uint64(x1y0.data & mask_0101);
		auto x0y1_packed = (uint64(x0y1.data & mask_1010) << 24) | uint64(x0y1.data & mask_0101);
		auto x1y1_packed = (uint64(x1y1.data & mask_1010) << 24) | uint64(x1y1.data & mask_0101);

		x1y0_packed = ((x1y0_packed * rateX128) >> 7) & mask;
		x1y1_packed = ((x1y1_packed * rateX128) >> 7) & mask;
		x0y0_packed = ((x0y0_packed * rateX128inv) >> 7) & mask;
		x0y1_packed = ((x0y1_packed * rateX128inv) >> 7) & mask;

		auto y0_packed = x0y0_packed + x1y0_packed;
		auto y1_packed = x0y1_packed + x1y1_packed;

		y1_packed = ((y1_packed * rateY128) >> 7) & mask;
		y0_packed = ((y0_packed * rateY128inv) >> 7) & mask;

		const auto color = y0_packed + y1_packed;

		Color result;
		result.data = uint32(color >> 24) | uint32(color);
		return result;
	}

最後に

今回は比較的お手軽な最適化をいくつか行いました。
次回以降はあまりお手軽ではない最適化になっていくのでその前の肩慣らしといった感じです。