方块游戏中的软件遮挡剔除

来源：https://enikofox.com/posts/software-rendered-occlusion-culling-in-block-game/ 我的GPU是AMD Ryzen 7 5700G处理器自带的集成显卡Radeon Vega 8。告诉你这些是想让你知道我的工作站并非图形计算强手。事实上，它性能相当有限。不过值得肯定的是，在UserBenchmark测试中，我的集成显卡比我的低端硬件目标设备——一台2012年购买的笔记本电脑的GPU快48%（https://gpu.userbenchmark.com/Compare/Nvidia-GeForce-GT-650M-vs-AMD-RX-Vega-8-Ryzen-iGPU/m7754vsm441833）。

（旁注：我知道UserBenchmark存在准确性争议，但这并不重要。我只是觉得有趣的是，我最近入手的集成显卡与14年前的笔记本电脑GPU相比，优势竟然并不明显——即便在当时那款GPU也不算出色。）

正是这一点，加上我希望游戏即使在极低配置设备上也能流畅运行，促使我最近决定尝试为我在开发的《方块游戏》（https://enikofox.com/blockgame）（暂定名）编写软件渲染遮挡剔除方案。我对此技术一直很感兴趣。方块和区块是轴对齐的立方体，这使得问题更容易处理，而且方块游戏通常存在大量以地下洞穴形式出现的隐藏几何体。虽然有其他剔除方法（https://tomcc.github.io/2014/08/31/visibility-1.html），但这些算法往往相当复杂，这似乎是个避免复杂性、坚持使用概念简单方法的好机会。

在本文中，我将解释开发过程以及最终采用的解决方案。你也可以阅读我在Mastodon（https://mastodon.gamedev.place/@eniko/115853197106622671）和Bluesky（https://bsky.app/profile/enikofox.com/post/3mbt6yuv3sc2v）上发布的开发日志。

在开始之前，我想说结果相当不错，超出了我的预期。它在60FPS或更低帧率下可在半帧时间内运行完成（当然采用多线程），通常能剔除至少50%通过视锥体剔除保留下来的区块。在地面上，平视地平线时，它能剔除约50-60%的区块，但在室内和地下洞穴中，剔除率可高达95%以上，即使在我较弱的系统上也能实现400+帧率。总体来说非常成功，尽管存在一些失效情况，我会在文末提及。

深度遮挡剔除开/关对比，左侧关闭，右侧开启。## 基于深度的遮挡剔除

其他人比我能更好地解释基于深度的遮挡剔除概念（https://youtu.be/CHYxjpYep_M?t=478），但我还是简要说明一下：获取场景的深度缓冲区，然后为每个待剔除对象检查深度缓冲区，查看其像素是否可见。如果可见，则对象可见；如果不可见，则进行剔除。

这可以有很多应用方式：可以在相对高分辨率下渲染并保守地下采样缓冲区（始终使用最远距离），这称为分层Z缓冲。也可以利用现代技术让GPU协助完成。可以使用运动向量复用前一帧的缓冲区。还可以使用异步回读获取GPU渲染的实际深度缓冲区进行CPU分析，而不会导致GPU停顿。

我将先解释我的最终系统，然后带你了解我实际如何得出该系统的过程。

方块游戏的遮挡剔除

我的做法简单得多，没有上述任何花哨特性。我使用FNA（https://fna-xna.github.io/）创建方块游戏，受限于较旧技术，无法利用GPU能力。虽然可以从GPU回读获取实际深度缓冲区，但无法异步进行，这必然导致某种GPU停顿，效果不佳。因此我选择在CPU上进行渲染。

我以256x128像素分辨率渲染，由于方块游戏中所有物体都是立方体，我将立方体渲染到深度缓冲区（一个简单的浮点数数组），然后对照缓冲区检查更多立方体。

当区块因变更而重建时，我会构建一个“mipmap“链式的遮挡子区块。我的区块大小为16x16x16，因此有5个层级：

1. 这只是整个区块
2. 2x2x2立方体，每个大小为8x8x8方块
3. 4x4x4立方体，每个大小为4x4x4方块
4. 8x8x8立方体，每个大小为2x2x2方块
5. 16x16x16立方体，每个对应单个方块

我首先处理第4层，将具有可见面的完整不透明方块标记为遮挡体。然后逐层下降，将具有可见面且完全由完整不透明方块组成的方块立方体标记为遮挡子区块。

子区块层级1-4的调试渲染，单独渲染。同一区块内的子区块颜色相似。当帧摄像机位置更新后，游戏通知渲染器开始遮挡剔除。这会收集玩家周围的区块，丢弃不含可见面或实体的区块，并在世界空间中对剩余部分进行视锥体剔除。然后将剩余区块发送给遮挡剔除器，后者收集所有遮挡体。最高层级（单个方块遮挡体）包含摄像机半径20格内的遮挡体。接下来的第1至3层根据区块与摄像机所在区块的距离进行收集。

虽然存在大量8x8x8大小的1级遮挡体，但似乎从未出现过16x16x16遮挡体，不过理论上也可以添加。为了避免误剔除，我将每个遮挡体的立方体在水平和垂直方向缩小1像素，使其在足够远距离时消失，而超出合理可视范围的立方体无需渲染。跳过此类遮挡体大幅减轻了遮挡剔除器的工作负载。

遮挡剔除器还会在区块列表中存储每个候选区块的位置、大小和区块索引。一旦所有数据收集完毕，遮挡剔除器无需再接触实际区块数据，这意味着我们实现了线程安全，并唤醒后台线程执行实际工作。

在后台线程中，首先对每个遮挡体进行视锥体剔除，因为之前的视锥体剔除仅针对整个区块，而非子区块，而最多8个顶点的变换比视锥体剔除所需的点积计算开销大得多。

然后将剩余遮挡体的角点变换为深度缓冲区的x/y坐标和深度值。为避免完整4x4投影矩阵乘法的开销，我使用视图矩阵旋转变换，通过加法进行平移，并使用线性视图深度（因为我的缓冲区仅由常规32位浮点数组成）。这减少了运算量，在处理数千顶点时显著更快。遮挡体的深度值取所有计算出的线性深度值的最大值。

如果任何变换后的角点因位于摄像机近裁剪面后方而无效，则完全跳过该遮挡体；否则追踪其“形状“。我没有渲染三角形或面，而是使用一维数组存储深度缓冲区每行的最小和最大x坐标。追踪形状意味着找到8个立方体角点的最小和最大y坐标，然后遍历所有12条立方体边，记录每行的最小和最大x值。

绘制遮挡体变得简单：从最小y（加1）遍历每行到最大y（减1），从一维数组中查找最小和最大x（同样加减1），然后用遮挡体的最远深度值水平填充深度缓冲区。

加减1是因为我以如此低的分辨率渲染深度。通过缩小立方体一个像素，我可以避免在低分辨率下区块完全不可见而在全分辨率下可见的边缘情况。

场景中可见缝隙，但在遮挡剔除器的低分辨率下，没有1像素内缩时该缝隙被完全覆盖，导致误剔除。遮挡剔除器随后对所有待剔除候选对象执行类似操作，只是现在记录的是最近距离而非最远距离，并且不再有1像素内缩。如果深度值小于或等于缓冲区中任何值，则区块可见，无需检查更多像素。如果深度值在任何位置都不满足，则区块可被剔除。这里一个显著变化是：如果候选区块的任何角顶点无效（因位于摄像机近裁剪面后方），则简单视为可见，因为我们无法执行检查。

这种方法在各种情况下效果良好，即使在较慢的CPU上也能良好运行。它真正帮助了老旧系统或像我这样图形性能较弱的设备在大多数正常游戏场景中实现良好帧率，无需洞穴可见性算法的复杂性或开销。

开发过程

当然，我不是一开始就完善了这个优化方案，总得从某个地方开始。我的第一个方法是将每个区块划分为固定数量的子区块。我尝试了每边2和4（分别为每个区块8和16个子区块），简单记录子区块是否完全由不透明方块组成，不管是否有可见面。

然后将所有包含非空气/虚空方块和/或可见实体的区块的子区块发送给遮挡剔除器，使用完整4x4投影矩阵变换其顶点，乘以1/w并记录x/y/z坐标。我将变换后的坐标保存在列表中，先渲染遮挡体，再读取剔除候选对象。如果候选对象的任何区块子区块可见，则整个区块标记为可见。

我当时也没有正确进行视锥体剔除，只排除了已知完全在摄像机后方的区块，因此这个阶段的遮挡剔除器也执行视锥体剔除。

这确实有效，在某种意义上确实剔除了被遮挡的区块。不幸的是，它也非常慢，在渲染距离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) { // 世界空间到视图空间 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);

// 透视除法
var invZ = 1.0f / viewPos.Z;
var xScreen = viewPos.X * invZ * focalLenPixels.X + (bufferWidth / 2);
var yScreen = viewPos.Y * invZ * focalLenPixels.Y + (bufferHeight / 2);

// 视图空间中的距离替代实际深度
var dist = viewPos.Z;

valid = dist > FNARenderer.ZNearPerspective;
return new Vector3F(xScreen, yScreen, dist);

} ``

我进行3x3矩阵乘法并使用加法进行平移。然后进行透视除法并乘以像素焦距。我不关心沿z轴缩放深度，直接使用线性视图空间的深度，因为这仍能满足我的目的。我不需要渲染纹理等，因此这完全适用。

结果是13次乘法和1次除法，对比原来的21次乘法和1次除法。仅乘法运算量就降至62%，处理时间从150毫秒降至99毫秒。效果不错！

优化2：世界空间视锥体剔除

由于我已经将所有内容变换到屏幕空间，也尝试在该空间进行视锥体剔除。很快发现这是个糟糕的主意。虽然可以轻松计算立方体的包围球（sqrt(3) * size * 0.5），但立方体角点在投影到屏幕空间后非线性变化，实际上可能突出得更远。这意味着必须更保守地进行剔除，反而拖慢了整体速度。

幸运的是，有人指出使用视锥体平面与世界空间中立方体包围球进行简单点积会便宜得多且更准确。我找到了从投影矩阵中提取视锥体平面的方法并尝试，发现原始未优化运行时间已降至43%，即61毫秒。

供参考，这是我的平面提取函数，使用FNA的Plane结构体：

`` public static void GetFrustumPlanes(Plane[] planes, Matrix4 viewProjection) { Debug.Assert(planes.Length >= 6);

// 左平面
planes[0] = new Plane(
    viewProjection.M14 + viewProjection.M11,
    viewProjection.M24 + viewProjection.M21,
    viewProjection.M34 + viewProjection.M31,
    viewProjection.M44 + viewProjection.M41
);

// 右平面
planes[1] = new Plane(
    viewProjection.M14 - viewProjection.M11,
    viewProjection.M24 - viewProjection.M21,
    viewProjection.M34 - viewProjection.M31,
    viewProjection.M44 - viewProjection.M41
);

// 下平面
planes[2] = new Plane(
    viewProjection.M14 + viewProjection.M12,
    viewProjection.M24 + viewProjection.M22,
    viewProjection.M34 + viewProjection.M32,
    viewProjection.M44 + viewProjection.M42
);

// 上平面
planes[3] = new Plane(
    viewProjection.M14 - viewProjection.M12,
    viewProjection.M24 - viewProjection.M22,
    viewProjection.M34 - viewProjection.M32,
    viewProjection.M44 - viewProjection.M42
);

// 近平面
planes[4] = new Plane(
    viewProjection.M13,
    viewProjection.M23,
    viewProjection.M33,
    viewProjection.M43
);

// 远平面
planes[5] = new Plane(
    viewProjection.M14 - viewProjection.M13,
    viewProjection.M24 - viewProjection.M23,
    viewProjection.M34 - viewProjection.M33,
    viewProjection.M44 - viewProjection.M43
);

// 归一化平面
for (int i = 0; i < 6; i++) {
    Plane.Normalize(ref planes[i], out planes[i]);
}

} ``

这足够快，最终我将其从后台线程和遮挡剔除器中移出，放入渲染器的常规区块收集流程。

优化3：可见面

然后我意识到我之前关于可见几何体的标准是错误的。我原认为任何包含非空气等非默认不可见方块的区块（或当时的子区块）都可能可见。当然，这很幼稚。只有当区块具有可见面时，它才有可见几何体。