光栅化算法概述

光栅化渲染技术无疑是渲染 3D 场景图像最常用的技术，然而，这可能是所有技术中理解最少且记录最少的技术（特别是与光线追踪相比）。

为什么会这样，取决于不同的因素。 首先，这是一种过去的技术。 我们并不是说该技术已经过时，恰恰相反，而是大多数用于通过该算法生成图像的技术都是在 20 世纪 60 年代到 20 世纪 80 年代初之间开发的。 在计算机图形学领域，现在已经是中世纪，有关开发这些技术的论文的知识往往会丢失。 光栅化也是 GPU 用于生成 3D 图形的技术。 自 GPU 首次发明以来，硬件技术发生了很大变化，但自 20 世纪 80 年代初以来，它们实现的用于生成图像的基本技术并没有太大变化（硬件发生了变化，但形成图像的底层管道没有变化）。 事实上，这些技术是如此基础，因此如此深入地集成在硬件架构中，以至于没有人再关注它们（只有设计 GPU 的人才能知道它们在做什么，这远非一项微不足道的任务，而是设计一个 GPU 和理解光栅化算法的原理是两件不同的事情；因此解释后者应该不那么难！）。

无论如何，我们认为纠正这种情况是紧迫且重要的。 通过本课程，我们相信它是第一个提供清晰完整的算法图景以及该技术的完整实际实现的资源。

1、光栅化介绍

光栅化（rasterization）和光线追踪（ray tracing）尝试解决可见性或隐藏表面问题，但顺序不同（可见性问题在渲染 3D 场景图像，概述课程中介绍）。 这两种算法的共同点是它们本质上使用几何技术来解决该问题。 在本课中，我们将简要描述光栅化算法的工作原理。 理解原理非常简单，但实现它需要使用一系列技术，尤其是几何领域的技术，你也将在本课程中找到相关解释。

我们将在本课程中开发的用于演示光栅化在实践中如何工作的程序非常重要，因为我们将在下一课程中再次使用它来实现光线跟踪算法。 在同一个程序中实现这两种算法将使我们能够更轻松地比较两种渲染技术产生的输出（至少在应用着色之前它们应该产生相同的结果）和性能。 这将是更好地理解两种算法优缺点的好方法。

2、渲染算法

光栅化算法不是只有一种，而是多种，但为了开门见山，我们可以说所有这些不同的算法都基于相同的总体原理。 换句话说，所有这些算法都只是同一想法的变体。 本课我们在谈论光栅化时将提到这个想法或原则。

那是什么想法？ 在前面的课程中，我们已经讨论了光栅化和光线追踪之间的区别。 我们还建议渲染过程本质上可以分解为两个主要任务：可见性（visibility）和着色（shading）。 光栅化本质上是解决可见性问题的一种方法。 可见性包括能够辨别 3D 对象的哪些部分对相机可见。 这些对象的某些部分可以被剔除，因为它们要么在相机的可见区域之外，要么被其他对象隐藏。

解决这个问题基本上可以通过两种方式来完成：光线追踪和光栅化。

2.1 光线追踪

你可以追踪（tracing）穿过图像中每个像素的光线（ray），以找出相机与该光线相交的任何对象（如果有）之间的距离。 通过该像素可见的对象是具有最小交叉距离（通常表示为 t）的对象。 这是光线追踪中使用的技术。 请注意，在这种特殊情况下，你可以通过循环遍历图像中的所有像素，跟踪每个像素的光线，然后查明这些光线是否与场景中的任何对象相交来创建图像。 换句话说，该算法需要两个主循环。 外循环迭代图像中的像素，内循环迭代场景中的对象：

for (each pixel in the image) { 
    Ray R = computeRayPassingThroughPixel(x,y); 
    float tclosest = INFINITY; 
    Triangle triangleClosest = NULL; 
    for (each triangle in the scene) { 
        float thit; 
        if (intersect(R, object, thit)) { 
             if (thit < closest) { 
                 triangleClosest = triangle; 
             } 
        } 
    } 
    if (triangleClosest) { 
        imageAtPixel(x,y) = triangleColorAtHitPoint(triangle, tclosest); 
    } 
} 

请注意，在此示例中，对象被视为由三角形（且仅是三角形）组成。 我们不迭代其他对象，而是将这些对象视为三角形池并迭代其他三角形。 由于我们在前面的课程中已经解释过的原因，三角形通常在光线追踪和光栅化中用作基本渲染基元（GPU 需要对几何体进行三角测量）。

2.2 光栅化

光线追踪是解决可见性问题的第一个可能的方法。 我们说该技术是以图像为中心的，因为我们将来自相机的光线射入场景（我们从图像开始），而不是相反的我们将在光栅化中使用的方法：

光栅化采用相反的方法。 为了解决可见性问题，它实际上将三角形“投影”到屏幕上，换句话说，我们使用透视投影将该三角形从 3D 表示转换为 2D 表示。 这可以通过将构成三角形的顶点投影到屏幕上（使用我们刚刚解释的透视投影）来轻松完成。 算法的下一步是使用某种技术来填充该 2D 三角形覆盖的图像的所有像素。 这两个步骤如图 2 所示。从技术角度来看，它们执行起来非常简单。 投影步骤只需要透视划分以及将结果坐标从图像空间重新映射到光栅空间，这是我们在前面的课程中已经介绍过的过程。 找出生成的三角形覆盖图像中的哪些像素也非常简单，稍后将进行描述。

与光线追踪方法相比，该算法是什么样的？ 首先，请注意，在光栅化中，在外循环中，我们需要迭代场景中的所有三角形，而不是首先迭代图像中的所有像素。 然后，在内循环中，我们迭代图像中的所有像素，并找出当前像素是否“包含”在当前三角形的“投影图像”内（图 2）。 换句话说，两种算法的内循环和外循环交换了：

// rasterization algorithm
for (each triangle in scene) { 
    // STEP 1: project vertices of the triangle using perspective projection
    Vec2f v0 = perspectiveProject(triangle[i].v0); 
    Vec2f v1 = perspectiveProject(triangle[i].v1); 
    Vec2f v2 = perspectiveProject(triangle[i].v2); 
    for (each pixel in image) { 
        // STEP 2: is this pixel contained in the projected image of the triangle?
        if (pixelContainedIn2DTriangle(v0, v1, v2, x, y)) { 
            image(x,y) = triangle[i].color; 
        } 
    } 
}

该算法是以对象为中心的，因为我们实际上是从几何体开始，然后走回图像，而不是光线追踪中使用的方法，在光线追踪中，我们从图像开始，走回场景。

这两种算法的原理都很简单，但在实现它们和寻找所需解决的不同问题的解决方案时，它们的复杂性略有不同。 在光线追踪中，生成光线很简单，但找到光线与几何体的交集可能会很困难（取决于你处理的几何体的类型），而且计算成本也可能很高。 但现在让我们忽略光线追踪。 在光栅化算法中，我们需要将顶点投影到屏幕上，这既简单又快速，我们将看到需要找出像素是否包含在三角形的二维表示中的第二步具有同样简单的几何解决方案。

换句话说，使用光栅化方法计算图像依赖于两种非常简单且快速的技术（透视过程和确定像素是否位于 2D 三角形内）。 光栅化是“优雅”算法的一个很好的例子。 它所依赖的技术有简单的解决方案； 它们也易于实施并产生可预测的结果。 由于所有这些原因，该算法非常适合 GPU，并且是 GPU 应用来生成 3D 对象图像的渲染技术（也可以轻松并行运行）。

总而言之，光栅化的优点如下：

• 将几何图形转换为三角形使过程更简单。 如果所有基元都转换为三角形基元，我们可以编写快速高效的函数将三角形投影到屏幕上并检查像素是否位于这些 2D 三角形内
• 光栅化是以对象为中心的。 我们将几何图形投影到屏幕上，并通过循环图像中的所有像素来确定它们的可见性。
• 光栅化主要依赖于两种技术：将顶点投影到屏幕上并找出给定像素是否位于 2D 三角形内。
• GPU 上运行的渲染管线基于光栅化算法。

3D Z 缓冲线性插值多边形的快速渲染是最先进工作站的一个基本问题。 一般来说，该问题由两部分组成：1）顶点的 3D 变换、投影和光照计算，2）将多边形光栅化到帧缓冲区中。  — 多边形光栅化的并行算法，Juan Pineda, 1988

术语“光栅化”来自以下事实：多边形（在本例中为三角形）以某种方式分解为像素，并且众所周知，由像素组成的图像称为光栅图像。 从技术上讲，这个过程称为将三角形光栅化为帧缓冲区的图像。

光栅化是确定哪些像素位于三角形内的过程，仅此而已。  —  Larrabee 的光栅化，Michael Abrash

希望本课程到此为止，你已经了解了使用光栅化方法生成 3D 场景图像（由三角形组成）的方式。 当然，到目前为止我们描述的是该算法的最简单形式。 首先，它可以得到很大的优化，但此外，我们还没有解释当投影到屏幕上的两个三角形与图像中的相同像素重叠时会发生什么。 当这种情况发生时，我们如何定义这两个（或更多）三角形中的哪一个对相机可见？ 我们现在就来回答这两个问题。

3、优化：2D 三角形边界框

到目前为止，我们给出的光栅化算法的简单实现的问题是，它需要在内循环中迭代图像中的所有像素，即使三角形中可能包含这些像素中的一小部分（如图所示） 如图 3 所示）。 当然，这取决于屏幕上三角形的大小。 但考虑到我们对渲染一个三角形不感兴趣，而是渲染一个可能由几百到几百万个三角形组成的对象，因此在典型的生产示例中，这些三角形在图像中不太可能非常大。

最小化测试像素数量的方法有多种，但最常见的方法包括计算投影三角形的 2D 边界框并迭代该 2D 边界框中包含的像素而不是整个图像的像素。 虽然其中一些像素可能仍然位于三角形之外，但至少平均而言，它已经可以显着提高算法的性能。 这个想法如图 3 所示。

计算三角形的 2D 边界框非常简单。 我们只需要找到光栅空间中构成三角形的三个顶点的最小和最大 x 坐标和 y 坐标。 下面的伪代码对此进行了说明：

// convert the vertices of the current triangle to raster space
Vec2f bbmin = INFINITY, bbmax = -INFINITY; 
Vec2f vproj[3]; 
for (int i = 0; i < 3; ++i) { 
    vproj[i] = projectAndConvertToNDC(triangle[i].v[i]); 
    // coordinates are in raster space but still floats not integers
    vproj[i].x *= imageWidth; 
    vproj[i].y *= imageHeight; 
    if (vproj[i].x < bbmin.x) bbmin.x = vproj[i].x); 
    if (vproj[i].y < bbmin.y) bbmin.y = vproj[i].y); 
    if (vproj[i].x > bbmax.x) bbmax.x = vproj[i].x); 
    if (vproj[i].y > bbmax.y) bbmax.y = vproj[i].y); 
} 

一旦我们计算了三角形的 2D 边界框（在光栅空间中），只需要循环该框定义的像素即可。 但是你需要非常小心转换光栅坐标的方式，在我们的代码中，光栅坐标被定义为浮点数而不是整数。

首先，请注意，一个或两个顶点可能会投影到画布边界之外。 因此，它们的光栅坐标可能小于 0 或大于图像大小。 我们通过将 x 坐标的像素坐标限制在 [0, Image Width - 1] 范围内，将 y 坐标限制在 [0, Image Height - 1] 范围内来解决此问题。 此外，我们需要将边界框的最小和最大坐标四舍五入为最接近的整数值（请注意，当我们迭代循环中的像素时，这可以正常工作，因为我们将变量初始化为 xmim 或 ymin 并从 当变量 x 或 y 小于或等于 xmax 或 ymax 时循环）。 在循环中使用最终定点（或整数）边界框坐标之前，需要应用所有这些测试。 这是伪代码：

... 
uint xmin = std::max(0, std:min(imageWidth - 1, std::floor(min.x))); 
uint ymin = std::max(0, std:min(imageHeight - 1, std::floor(min.y))); 
uint xmax = std::max(0, std:min(imageWidth - 1, std::floor(max.x))); 
uint ymax = std::max(0, std:min(imageHeight - 1, std::floor(max.y))); 
for (y = ymin; y <= ymin; ++y) { 
    for (x = xmin; x <= xmax; ++x) { 
        // check of if current pixel lies in triangle
        if (pixelContainedIn2DTriangle(v0, v1, v2, x, y)) { 
            image(x,y) = triangle[i].color; 
        } 
    } 
} 

4、图像或帧缓冲区

我们的目标是生成场景图像。 我们有两种方法来可视化程序的结果，要么直接在屏幕上显示渲染的图像，要么将图像保存到磁盘，然后使用 Photoshop 等程序预览图像。 但在这两种情况下，我们都需要在渲染时存储正在渲染的图像，为此，我们使用 CG 中所说的图像或帧缓冲区。 它只不过是具有图像大小的二维颜色数组。 在渲染过程开始之前，创建帧缓冲区并将像素全部设置为黑色。 在渲染时，当三角形被光栅化时，如果给定像素与给定三角形重叠，则我们将该三角形的颜色存储在该像素位置的帧缓冲区中。 当所有三角形都被光栅化后，帧缓冲区将包含场景的图像。 剩下要做的就是在屏幕上显示缓冲区的内容或将其内容保存到文件中。 在本课中，我们将选择后一个选项。

5、深度缓冲区（或 Z 缓冲区）

请记住，光栅化算法的目标是解决可见性问题。 要显示 3D 对象，必须确定哪些表面可见。 在计算机图形学的早期，有两种方法被用来解决“隐藏表面”问题（可见性问题的别称）：Newell 算法和 z 缓冲区。 由于历史原因，我们只提到 Newell 算法，但在本课中我们不会研究它，因为它不再使用。 我们将只研究 GPU 使用的 z 缓冲区方法。

为了让基本的光栅化器正常工作，我们还需要做最后一件事。 我们需要考虑这样一个事实：多个三角形可能与图像中的同一像素重叠（如图 5 所示）。 当这种情况发生时，我们如何决定哪个三角形是可见的？ 这个问题的解决方法非常简单。 我们将使用我们所说的 z 缓冲区（z-buffer），也称为深度缓冲区（depth buffer），你可能已经经常听说或读过这两个术语。

z 缓冲区只不过是另一个与图像具有相同维度的二维数组，但它不是一个颜色数组，而是一个浮点数数组。 在开始渲染图像之前，我们将此数组中的每个像素初始化为一个非常大的数字。 当像素与三角形重叠时，我们还会读取该像素位置的 z 缓冲区中存储的值。 正如你可能猜到的，该数组用于存储从相机到图像中任何像素重叠的最近三角形的距离。 由于该值最初设置为无穷大（或任何非常大的数字），那么，当然，当我们第一次发现给定像素 X 与三角形 T1 重叠时，从相机到该三角形的距离必然低于存储在 z 缓冲区中的值。 然后我们要做的就是用到 T1 的距离替换为该像素存储的值。 接下来，当测试相同的像素 X 时，我们发现它与另一个三角形 T2 重叠，然后我们将相机到这个新三角形的距离与 z 缓冲区中存储的距离进行比较（此时，存储的是到第一个三角形 T1的距离)。 如果到第二个三角形的距离小于到第一个三角形的距离，则 T2 可见，而 T1 被 T2 隐藏。 否则，T1 被 T2 隐藏，而 T2 可见。 在第一种情况下，我们用到 T2 的距离更新 z 缓冲区中的值，在第二种情况下，不需要更新 z 缓冲区，因为第一个三角形 T1 仍然是我们找到的最接近的三角形 到目前为止的像素。 正如你所看到的，z 缓冲区用于存储场景中每个像素到最近对象的距离（我们并没有真正使用该距离，但我们将在课程中进一步提供详细信息）。

在图 5 中，我们可以看到 3D 空间中红色三角形位于绿色三角形后面。 如果我们首先渲染红色三角形，然后渲染绿色三角形，对于与两个三角形重叠的像素，我们必须首先在该像素位置的 z 缓冲区中存储一个非常大的数字（当 z 缓冲区已初始化），然后是到红色三角形的距离，最后是到绿色三角形的距离。

你可能想知道我们如何找到从相机到三角形的距离。 让我们首先看一下该算法的伪代码实现，稍后我们将回到这一点（现在我们假设函数 PixelContainedIn2DTriangle 为我们计算该距离）：

// A z-buffer is just an 2D array of floats
float buffer = new float [imageWidth * imageHeight]; 
// initialize the distance for each pixel to a very large number
for (uint32_t i = 0; i < imageWidth * imageHeight; ++i) 
    buffer[i] = INFINITY; 
 
for (each triangle in scene) { 
    // project vertices
    ... 
    // compute bbox of the projected triangle
    ... 
    for (y = ymin; y <= ymin; ++y) { 
        for (x = xmin; x <= xmax; ++x) { 
            // check of if current pixel lies in triangle
            float z;  //distance from the camera to the triangle 
            if (pixelContainedIn2DTriangle(v0, v1, v2, x, y, z)) { 
                // If the distance to that triangle is lower than the distance stored in the
                // z-buffer, update the z-buffer and update the image at pixel location (x,y)
                // with the color of that triangle
                if (z < zbuffer(x,y)) { 
                    zbuffer(x,y) = z; 
                    image(x,y) = triangle[i].color; 
                } 
            } 
        } 
    } 
} 

6、下一步是什么？

本文只是光栅化算法的非常高级的描述（图 6），但应该已经让你了解我们在程序中需要什么来生成图像。 我们会需要：

• 图像缓冲区（二维颜色数组），
• 深度缓冲区（二维浮点数组），
• 三角形（构成场景的几何体），
• 将三角形的顶点投影到画布上的函数，
• 光栅化投影三角形的函数，
• 一些代码将图像缓冲区的内容保存到磁盘。

在下一章中，我们将看到坐标如何从相机转换到光栅空间。 该方法当然与我们在上一课中学习和介绍的方法相同，但是，我们将在此过程中介绍更多技巧。 在第三章中，我们将学习如何光栅化三角形。 在第四章中，我们将详细研究 z 缓冲区算法的工作原理。

原文链接：An Overview of the Rasterization Algorithm

BimAnt翻译整理，转载请标明出处