本文档为 CMU 15-473/673 视觉计算系统课程作业 1 的博客/文档。该作业涉及为基于瓦片的渲染器实现 sort-middle 算法。
数据处理
SIMD
在本项目中，我将使用 Intel SIMD（单指令多数据）数据类型传递坐标，具体我们将使用 __m128。它是 Intel SIMD 指令集特有的数据类型，特别用于流式 SIMD 扩展（SSE）系列指令。它表示一个 128 位大小的寄存器，可以同时存储和操作四个 32 位浮点值。
要处理 __m128，我们需要使用特定的 API 进行基本算术运算。在本作业中，我们具体需要以下 API 来完成工作。
Plain Text#include <xmmintrin.h>
int main () {
// 加法
__m128 result_addition = _mm_add_ps(1.0f, 2.0f);
__m128i result_addition_int = _mm_add_epi32(1,2);
// 减法
__m128 result_subtraction = _mm_sub_ps(1.0f, 2.0f);
__m128i result_subtraction_int = _mm_sub_epi32(1,2);
// 乘法
__m128 result_mul = _mm_mul_ps(1.0f, 2.0f);
__m128i result_mul_int = _mm_mullo_epi32(1, 2);
// 除法
__m128 result_div = _mm_div_ps(1.0f, 2.0f);
// 设为零
__m128 zero = _mm_setzero_ps();
// 设为值
__m128 one = _mm_set_ps(1.0f, 2.0f, 3.0f, 4.0f);
}
我们还可以使用 SIMD 指令处理比较和位运算。
Plain Text#include <xmmintrin.h>
int main () {
// 相等比较
__m128 result_equal = _mm_cmpeq_ps(1.0f, 1.0f);
__m128i result_equal_int = _mm_cmpeq_si128(1,1);
// 小于比较
__m128 result_lessThan = _mm_cmplt_ps(1.0f, 2.0f);
__m128i result_lessThan_int = _mm_cmplt_si128(1,2);
// 大于比较
__m128 result_greaterThan = _mm_cmpgt_ps(1.0f, 2.0f);
__m128i result_greaterThan_int = _mm_cmpgt_si128(1,2);
// 按位与
__m128 result_and = _mm_and_ps(1.0f, 2.0f);
__m128i result_and_int = _mm_and_si128(1,2);
// 按位或
__m128 result_or = _mm_or_ps(1.0f, 2.0f);
__m128i result_or_int = _mm_or_si128(1,2);
}
N.4 格式
在本作业中，顶点位置将以定点表示存储，具有 4 位亚像素精度，这称为浮点值的 N.4 格式——n 位用于整数，4 位用于小数。
例如，二进制表达式 1001.0110 可以理解为：
- 整数部分：1001 = 9。
- 小数部分：0110 = 6/16 = 0.375
所以这个数是 9.375。
N.4 格式在 GPU 中广泛用于降低浮点计算成本。此外，N.4 格式最重要的操作之一是舍入。使用该定义，对于 N.4 格式浮点数 a 的二进制表示，我们可以使用位移进行 floor 和 ceil 操作。
光栅化
点在三角形内测试
当我们想要光栅化场景时，我们将调用 RasterizeTriangle() 函数。该函数接受输出图像的一个区域和一个三角形作为输入。然后它识别此屏幕区域内可能至少被此输入三角形部分覆盖的所有 2×2 像素块。
在此过程中，我们需要确定三角形是否实际覆盖此 2×2 像素块中的采样点——这称为三角形覆盖测试。这部分由 TestQuadFragment() 函数完成——它接受四个屏幕点的坐标作为输入，对应于此像素块中的像素。其输出是一个位掩码，指示这些点中哪些位于三角形内，如下图所示。
由于 __m128 寄存器最多可以保存 4 个整数，我们将使用两个寄存器存储 quad 2×2 片段中四个采样点的 x 和 y 坐标（如注释所述，以 N.4 定点格式）。
边方程
要测试像素是否被三角形覆盖，我们使用边方程。将三角形的第 i 个顶点标记为 (xi, yi)。对于查询点 q = (x, y)，我们首先计算
第 i 条边的边方程计算为
点 q 通过三角形内测试的充要条件是
即边方程必须同号。如果点恰好落在边上（即 Ei = 0），我们检查该边是否属于当前三角形。我们可以通过访问 isOwnerEdge[i] 来检查。如果 isOwnerEdge[i] 为 true，表示该边属于三角形，因此我们认为该边上的所有点都在三角形内。
现在，边的掩码应该很清楚了。
现在我们有了 TestQuadFrag() 函数，它返回一个位掩码，指示每个片段的采样是否被覆盖，我们将能够光栅化三角形。我们将在 RasterizeTriangle() 方法中完成此操作。
我们光栅化三角形的方式可以概括为：找到所有候选像素，并使用我们已经编写的 TestQuadFrag() 测试每个像素的覆盖。我们将接收以下输入
- regionX0, regionY0：当前工作瓦片的左上角坐标。
- regionW, regionH：当前工作瓦片的像素宽度和高度。
- tri：设置三角形方程，我们保存三角形顶点的坐标。
- triSIMD：tri 在 SIMD 寄存器中的所有值。
- processQuadFragmentFunc：一个函数值——对于每个可能产生覆盖的 quad 片段，此方法应调用此函数。
查找包围盒
为了加速测试，同时不遗漏任何可能的候选，我们首先找到三角形的包围盒以决定要查看的坐标。通过使用我们在 2.2 节中讨论的 N.4 格式浮点数的位运算，我们将能够轻松完成此操作。
遍历所有 Quad 片段
现在我们可以通过简单地应用 for 循环开始遍历三角形覆盖的所有可能片段。对于我们查看的每个 quad 片段，我们将像素坐标（左下、右下、左上、右上）保存到寄存器中。然后，我们将调用 TestQuadFragment() 方法查看是否接受此三角形。我们将使用简单接受条件，其中所有 quad 都必须通过测试。
Sort-middle 基于瓦片的渲染器
现在我们将开始实现 sort-middle 瓦片并行渲染器。瓦片渲染器将有两个阶段：
- 将三角形放入 bins。它将构建一个数据结构，其中每个屏幕瓦片有一个 bin，每个 bin 包含可能与该 bin 重叠的三角形列表。
- 并行处理 bins，动态地将下一个未处理的 bin 分配给下一个可用的核心。
该过程如图 2 所示。
图 2：Sort-Middle 瓦片并行化方案。图中简要显示了各阶段。
初始化
在基于瓦片的渲染中，我们将屏幕划分为更小的瓦片，我们称之为 bins。每个瓦片将负责处理其内部的三角形。通常，为了提高性能，我们将按三角形覆盖的瓦片对三角形进行分类。此过程称为 binning。
跟踪 bins 的直观方法是使用瓦片向量，其中每个瓦片是投影三角形的向量，我们称之为 bins。然而，当 binning 在多线程上下文中处理时，多个线程可能同时处理三角形，并将它们放入相应的 bins。如果它们直接写入全局 bins，可能会导致：
- 竞态条件。多个线程写入同一数据结构——可能导致数据不一致甚至程序崩溃。
- 性能瓶颈。为了避免竞态条件，我们需要应用锁来确保线程安全——但这几乎肯定会很慢，因为它降低了并行性。
线程本地 Bins
为了解决上述问题，我们引入了线程本地 bins，由我们称为 threadLocalBins 的数据结构维护。现在，每个线程都有自己独立的数据结构来维护 bins。当线程 i 进行 binning 时，它将数据写入自己的 threadLocalBins[i]。通过使用线程本地 bins，我们还避免了使用锁，从而降低了同步成本。一旦每个线程完成自己的 binning，我们需要将每个人的本地 bins 合并到全局 bins 中，并将其交给 ProcessBins() 处理。
步骤
以下步骤描述了我们在 BinTriangles() 中需要完成的工作。
- 初始化。假设屏幕被划分为 gridWidth × gridHeight 个瓦片。全局 bins。它将是 ProjectedTriangles 的向量之向量，大小为 gridWidth × gridHeight。线程本地 bins。它将是 ProjectedTriangles 的向量之向量之向量，因为它将跟踪所有线程的所有本地 bins 结构。即 threadLocalBins[threadId] 返回第 threadId 个线程的本地 bins。
- 线程本地 binning。每个线程将只处理场景中三角形的一部分。它们将根据自己的三角形覆盖范围将三角形放入 threadLocalBins[threadId]。请注意，这也表明 threadLocalBins[threadId] 中的大多数 bins 将是空的，因为一个线程只会处理一个或几个瓦片。对于每个线程，超出其职责范围的瓦片可以被视为空的，如图 3 所示。
- 合并到全局 bin。在所有线程完成 binning 后，我们将 threadLocalBins 中的所有本地 bins 合并到全局 bins 中，其中三角形按瓦片分类。对于每个瓦片，我们合并所有线程的三角形子列表。在这些子列表中，三角形位于此瓦片中。
- 处理全局 bin。最后我们遍历全局 bins，并处理瓦片中的每个三角形。由于每个瓦片独立处理，我们将在多个线程上运行 ProcessBin()。
图 3：线程本地 bins。图中的 4 线程渲染器正在处理 12 个 bins。对于每个线程，它有一个线程本地 bins，只处理场景中三角形的一部分。
Binning 三角形
我们接下来要做的是处理全局 bins 中的 bins。对于每个瓦片，我们将调用 ProcessBin() 来光栅化 bin 中的片段。请注意，在基于瓦片的渲染器中，并行性发生在瓦片之间，而不是片段之间。瓦片内的处理是顺序进行的。因此，我们将一次调用 ShadeFragment() 来着色单个 quad 片段，而不是像非瓦片实现中那样在完整片段缓冲区上调用 ShadeFragments()。
帧缓冲瓦片
我们不是直接写入帧缓冲，而是将颜色和深度更新到帧缓冲。瓦片渲染器的一个优势是整个帧缓冲瓦片将适合缓存。为了获得最佳性能，我们将在处理瓦片时将结果写入瓦片主序帧缓冲结构，然后在最后将结果复制回渲染器的帧缓冲。
适配
由于光栅化以 quad 片段为粒度进行，循环在瓦片中的三角形上运行，并遍历四个片段中的每一个。我们将调用我们在 3.2 节中编写的 RasterizeTriangle()，区域大小指定为当前瓦片的子帧缓冲大小。
以下是我们可能需要解决的一些技术挑战：
- 由于我们直接着色片段（而不是在片段缓冲区中着色片段），我们将调用 ShadeFragment() 而不是 ShadeFragments()。查看 ShadeFragment() 的接口，我们需要知道哪个线程处理正在处理的三角形。否则，我们将使用错误的顶点输出缓冲区或索引输出缓冲区。
- 由于我们写入瓦片化帧缓冲，我们需要小心处理索引。
- 具体来说，ShadeFragment() 的接口中有一个 triId 参数——这不是 ProjectedTriangle 类的成员变量。这是我们在 BinTriangles() 中 binning 此三角形时循环的索引。
为了解决这些问题，我们需要携带和传播这些信息。为了便于处理，我们将维护 BinnedTriangle 结构体的向量，其中结构体保存线程 ID、循环索引和投影三角形。
现在我们将能够处理整个 bins。
完成
处理完成后，我们需要将结果写回帧缓冲。
本文档的 Markdown 格式可通过此处访问：https://hackmd.io/@Lockbrains/vcs1_tilebased_renderer。为获得更好的阅读体验，您可能希望在此链接阅读博客。