社内勉強会「レンダリング合宿１」 ソフトウェアラスタライザー 最適化編04 重心座標計算の最適化

#ソフトウェアラスタライザー 最適化編04 重心座標計算の最適化

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

今回の対応で FPS 76.7 ⇒ 92.2 に上昇しました。

##最初に
今回は息抜きの最適化です。
大した事はしないですが処理回数の多い箇所なので効果はかなり高いです。

##重心座標系の計算処理
まずは重心座標系の計算をしている箇所を確認してみましょう。

```cpp:Renderer.cpp
				auto b0 = EdgeFunc(p1.x, p1.y, p2.x, p2.y, px, py);
				if (b0 < 0.0f) if (bRasterized) break; else continue;
				auto b1 = EdgeFunc(p2.x, p2.y, p0.x, p0.y, px, py);
				if (b1 < 0.0f) if (bRasterized) break; else continue;
				auto b2 = EdgeFunc(p0.x, p0.y, p1.x, p1.y, px, py);
				if (b2 < 0.0f) if (bRasterized) break; else continue;
```

見ての通りEdgeFunc()で計算を行っています。
中身を確認してみます。

```cpp:Renderer.cpp
fp32 Renderer::EdgeFunc(const fp32 ax, const fp32 ay, const fp32 bx, const fp32 by, const fp32 cx, const fp32 cy)
{
	return ((bx - ax) * (cy - ay)) - ((by - ay) * (cx - ax));
}
```

掛け算２回に引き算４回ですね。
それほど重い計算でもなさそうです。
分かりやすくするために展開してみましょう。

```cpp
auto b0 = EdgeFunc(p1.x, p1.y, p2.x, p2.y, px, py);
auto b0 = ((p2.x - p1.x) * (py - p1.y)) - ((p2.y - p1.y) * (px - p1.x));
```

まずここで「(p2.x - p1.x)」「(p2.y - p1.y)」この二つはループ中に値が変化しないのでループの外で事前計算しておくことができます。
さらに「x+1」した際のb0の値が変化するのは式後半の「(p2.y - p1.y) * (px - p1.x)」の部分だけですので、xが+1する際にb0の変化量は「(p2.y - p1.y)」ということになります。
同じ要領で「y+1」した場合の変化量は「(p2.x - p1.x)」ということになりますので、これは単純な加減算で処理ができることになります。

これらを踏まえて書き直したソースが以下のものになります。

```cpp:Renderer.cpp
	for (int32 i = 0; i < Count; ++i)
	{
		const auto& Tri = Src.Triangles[i];

		const auto p0 = Tri.v0.Position;
		const auto p1 = Tri.v1.Position;
		const auto p2 = Tri.v2.Position;
		const auto n0 = Tri.v0.Normal;
		const auto n1 = Tri.v1.Normal;
		const auto n2 = Tri.v2.Normal;
		const auto t0 = Tri.v0.TexCoord;
		const auto t1 = Tri.v1.TexCoord;
		const auto t2 = Tri.v2.TexCoord;

		const auto InvDenom		= Tri.InvDenom;
		const auto TextureId	= Tri.TextureId;
		const auto TriangleId	= Tri.TriangleId;

		const auto x0 = Tri.bbMinX;
		const auto x1 = Tri.bbMaxX;
		const auto y0 = Tri.bbMinY;
		const auto y1 = Tri.bbMaxY;

		const auto beign_x = fp32(x0) + 0.5f;
		const auto beign_y = fp32(y0) + 0.5f;

		const auto p2_p1_x = p2.x - p1.x;
		const auto p2_p1_y = p2.y - p1.y;
		const auto p0_p2_x = p0.x - p2.x;
		const auto p0_p2_y = p0.y - p2.y;
		const auto p1_p0_x = p1.x - p0.x;
		const auto p1_p0_y = p1.y - p0.y;

		auto b0_row = (p2_p1_x * (beign_y - p1.y)) - (p2_p1_y * (beign_x - p1.x));
		auto b1_row = (p0_p2_x * (beign_y - p2.y)) - (p0_p2_y * (beign_x - p2.x));
		auto b2_row = (p1_p0_x * (beign_y - p0.y)) - (p1_p0_y * (beign_x - p0.x));

		auto pDepthBuffer = _pDepthBuffer->GetPixelPointer(0, y0);
		auto pGBuffer = _pGBuffer->GetPixelPointer(0, y0);

		for (auto y = y0; y <= y1; ++y)
		{
			auto bRasterized = false;

			auto b0_col = b0_row;
			auto b1_col = b1_row;
			auto b2_col = b2_row;

			for (auto x = x0; x <= x1; ++x, b0_col -= p2_p1_y, b1_col -= p0_p2_y, b2_col -= p1_p0_y)
			{
				if (b0_col < 0.0f) if (bRasterized) break; else continue;
				if (b1_col < 0.0f) if (bRasterized) break; else continue;
				if (b2_col < 0.0f) if (bRasterized) break; else continue;

				bRasterized = true;

				auto b0 = b0_col;
				auto b1 = b1_col;
				auto b2 = b2_col;

				const auto Depth = (b0 * p0.z) + (b1 * p1.z) + (b2 * p2.z);
				auto& DepthBuf = pDepthBuffer[x];
				if (Depth >= DepthBuf) continue;
				DepthBuf = Depth;

				b0 *= InvDenom;
				b1 *= InvDenom;
				b2 *= InvDenom;

				const auto w = 1.0f / ((b0 * p0.w) + (b1 * p1.w) + (b2 * p2.w));
				auto& GBuff = pGBuffer[x];
				GBuff.TextureId = TextureId;
				GBuff.TriangleId = TriangleId;
				GBuff.Normal.x = (b0 * n0.x) + (b1 * n1.x) + (b2 * n2.x);
				GBuff.Normal.y = (b0 * n0.y) + (b1 * n1.y) + (b2 * n2.y);
				GBuff.Normal.z = (b0 * n0.z) + (b1 * n1.z) + (b2 * n2.z);
				GBuff.TexCoord.x = ((b0 * t0.x) + (b1 * t1.x) + (b2 * t2.x)) * w;
				GBuff.TexCoord.y = ((b0 * t0.y) + (b1 * t1.y) + (b2 * t2.y)) * w;
			}

			b0_row += p2_p1_x;
			b1_row += p0_p2_x;
			b2_row += p1_p0_x;

			pDepthBuffer += SCREEN_WIDTH;
			pGBuffer += SCREEN_WIDTH;
		}
	}
```

ループ処理１回につきEdgeFunc()を３回呼び出していましたが、こうすることで加算３回で済みます。
これだけでもかなり効果があるのですがもう１か所簡単にいじれる箇所があります。

```cpp
				b0 *= InvDenom;
				b1 *= InvDenom;
				b2 *= InvDenom;
```

この部分です。
ループごとにDenomで割っている処理なのですが、これもループ中に値が変わらないのでループ外で事前に計算しておくことができます。

```cpp
	// 外積から面の向きを求めて、裏向きなら破棄する（backface-culling)
	const auto Denom = ((p1.x - p0.x) * (p2.y - p0.y)) - ((p1.y - p0.y) * (p2.x - p0.x));
	if (Denom <= 0.0f) return;

	// 補間処理の事前計算
	auto& t0 = v0.TexCoord;
	auto& t1 = v1.TexCoord;
	auto& t2 = v2.TexCoord;

	const auto InvDenom = 1.0f / Denom;
	p0.z *= InvDenom;
	p1.z *= InvDenom;
	p2.z *= InvDenom;
	p0.w *= InvDenom;
	p1.w *= InvDenom;
	p2.w *= InvDenom;
	t0.x *= InvDenom;
	t0.y *= InvDenom;
	t1.x *= InvDenom;
	t1.y *= InvDenom;
	t2.x *= InvDenom;
	t2.y *= InvDenom;
```

このような感じです。
これでひとまずループ外に出せそうな計算を全て消すことができました。

#最後に
今回は重心座標系の計算の最適化を行いました。
可能な限り計算をループの外に追い出すという基本通りの最適化でしたが、ループの回数がとにかく多い箇所なのでかなりの効果がありました。