三角形光栅化实践

翻译:徐浪(吵吵机器人) 审校:王成林(麦克斯韦的麦斯威尔)

这篇博客是系列博客的一部分

欢迎回来!之前的博客介绍了很多三角形的理论基础知识。这一次，让我们将它应用于三角形光栅化。再次强调，本篇中没有对代码进行详细介绍或优化，但是在下一篇文章中，我们将会讨论实际光栅化渲染器的代码优化。但是在我们开始优化之前，让我们基于上篇博文尽可能地写一个最简单的光栅化渲染器，使用我们在之前博客中介绍的一些基础。

基础光栅化渲染器

正如上篇博文讲到的，我们可以使用一个2阶行列式来计算边函数（该函数会生成重心坐标）。同时我们之前能够通过一个点的三个边函数的符号来判断点是在三角形里面，或者三条边上或者在三角形外面。我们的光栅化渲染器是运行在整型坐标下面的，因此现在让我们的三角形的顶点位置和点坐标也是被以整型的形式给出。方向测试需要计算的二阶行列式代码如下:

现在光栅化我们的三角形所需要做的就是在候选像素中循环判断它们落在三角形的里面或者外面。我们可以直接暴力求解来循环所有的屏幕像素。但是我们试试不要完全这么脑残地做:我们已经知道一个概念就是，落在三角形里面的所有像素一定完全落在该三角形的轴向包围盒里面。同时轴向包围盒也很容易进行计算和遍历。代码如下:

可以看到，这就是一个完整可以运行的三角形光栅化渲染器。尽管在理论上-你还要自己来写min/max和renderPixel函数，我也没有对代码进行测试，但是你可以得到大概的实现思路。代码甚至完成了二维的裁剪。不过不要误解我。我不建议在任何位置直接使用这些代码，后面我会做一些解释。但是我希望你可以看到这些是算法的核心部分。你在实践中看到的任何算法的具体实现都通过介绍一些特征细节和优化来展开美妙的深层简洁。当然这些附加都是值得的。但是它们在某种意义上是实现的细节。当然这里甚至将遍历限制在一个包围盒里面也是一个优化，而且是足够简单和重要的那个。但是我想要指出的一点就是:打心底讲这不是一个需要复杂求解的困难问题。反而，这是一个能够通过应用一些小技巧来实现更有效求解的基础问题，这是一个很重要的区别。

方法存在的问题

正如上面所说，这里列出了一些初始实现需要解决的一些问题:

l  整型溢出。如果计算溢出怎么办？这可能是或者不是一个实际的问题，但是至少值得我们来考虑一下。

l  亚像素精度。这份代码还没有涉及。

l  填充规则。图形API基于一系列权衡的规则来确保当两个未重叠的三角形共享一条边的情况下，每一个被这两个三角形覆盖到的像素或采样点都只被显示一次。GPU和软件光栅化渲染器只要严格地遵守这些规则来避免视觉假象。

l  速度。尽管上面给出的代码足够的短小精悍，但是却不是很有效率。还有很多方法能够让它变得更快，这里我们将涉及到一些，当然整个实现会变得更加复杂。

下面我按顺序处理上面这些问题：

整型溢出

既然所有的计算都在orient2d函数里面，因此我们需要重新观察的计算方程如下:

很幸运的是这个计算式子非常的对称，因此没有特别多不同的子等式需要我们来判断。首先假设我们是p位的有符号整型坐标。这意味着单个坐标值落在之间。通过从下边界减去上边界（反之亦然），我们可以得到两个坐标之间差值的范围

同时将该策略应用于其他三个我们需要计算的坐标差值。然后，我们计算这两个差值的乘积。足够简单

对于其他的乘积采用同样的策略。最终，我们计算两个乘积的差值，导致取值范围扩大到两倍绝对值。

因为P总是非负的。考虑到符号位，这意味着Orient2D落在(2p 2)位的带符号整型范围内。既然我们希望结果落在32位整型范围内，这意味着我们需要来确保不会溢出。换句话说，只要坐标范围落在[-16384,16383]之间就没有问题。超出的部分需要被预先裁剪来确保光栅化过程没有溢出。

顺便说下，这里展示了一个保护带裁剪(guard band clipping)如何运作的:首先光栅化渲染器使用固定的位宽来执行计算，这决定了光栅化渲染器能够接受的坐标范围。X/Y-裁剪只会在一个三角形没有完整落入保护带区域时执行，往往不是和视口大小一样大。注意光栅化渲染器的坐标没有必要完全符合渲染目标的坐标。如果你想要最大化保护带的工作范围，最好的设定就是平移你的光栅化渲染器坐标系统达到中心(既不是左上也不是右下角)和视口中心一致。否则，大的视口需要一个左边比右边更大的保护带(垂轴方向同理)，这不是我们希望的。

不管怎么样。整型溢出不是一个大问题，至少在目前我们的全部都是整型的坐标设定下。我们确实需要检查那些特别大的三角形，但是在实际应用中很少见，因此往往侥幸逃脱了裁剪的需求。

亚像素精度

这一点和下一点，既然对于目标应用我们不会直接去使用它们，因此我会仅仅给出概述而不涉及到细节。

从质量角度考虑，转换顶点坐标到像素是一个非常令人讨厌的过程。对于固定场景和固定视角还好，但是如果相机或者任何一个可视的对象移动缓慢，可以注意到三角形以离散的步长移动，在将顶点坐标约为整型后，每个顶点都从一个像素移动到下一个像素。这会导致三角形看起来不稳定，特别是三角形有贴图的时候。

现在，对于我们的应用考虑这样的流程，我们只是去渲染到深度缓冲中，用户不会直接看到渲染结果。因此我们可以忍受这些视觉上有问题的部分，而不用关心亚像素修正。这意味着我们软件光栅化的三角形不会完整符合硬件光栅化所做的，但是在实践中，如果我们错误处理一个对象的遮挡剔除，仅仅是由于亚像素坐标的差别导致它的某些像素能够被看到，那么这不是一个很大的问题。正如我的一个计算机教授指出过，对于任何事情都会有可以接受错误的边界，而对于遮挡剔除的处理，少量像素的取舍是一个可以接受的错误边界，至少是在它们不是聚集在一处的时候。

但是假设你想精确地渲染用户可见的部分，这样你就一定需要亚像素精度。对于每一个坐标，你至少需要4位额外的位宽(例如坐标是以一个像素的1/16为亚单元)。而DX11兼容的GPU具有8位的亚像素精度(坐标是一个像素的1/256为亚单元)。现在假设亚像素的精度是8位。最通常的方式是直接将所有的坐标乘以256：我们的坐标(仍然是整型)现在就是以一个像素1/256为亚单元，但是我们仍然只对一个像素执行一次采样。代码足够简单:

(这里仅仅展示主循环的框架)

足够简单而且运行良好。至少在理论上是这样的。这份代码和之前的一样没有经过测试，因此小心使用。顺便说下，需要说明的是：果你想要写一个软件光栅化渲染器，这似乎不是你想要的。这个代码以整型坐标的形式来采样三角形覆盖区域。如果你想写一个没有亚像素修正的光栅化渲染器会更加简单(正如我们做的，这就是为什么我们要这样设定坐标)，而且也符合D3D9的设定，但是不同于OpenGL和D3D10 的光栅化规则，因为它们是在成熟的渲染器重所使用的更明智的做法。因此提前警告下你自己。

不管怎么样，正如上面所说，能够运行但是有一个问题:这样计算会耗费我们太多的位宽。在32位整型下我们能够接受的坐标范围仍然是[-16384,16383]，但是到亚像素步骤，下降到大约[-64,63.996]像素。这已经小到即使我们完美地把视口放在中心，我们也不能在一个轴向上处理超过128像素。一个解决方法是降低亚像素精度到4位宽，这样可以满足在我们的坐标空间中适应删除2048X2048像素的渲染目标，虽然不是很舒服但是至少可行。

但是仍然有一个更好的方式。这里我不涉及到过多的细节，因为我们已经涉及到了足够多的细节，虽然不是很困难，但是过于细节。后面我可能会单独拿出来讲。关键的步骤仍然是一次遍历一个像素。我们传入orient2d这个函数的所有p值都是一个像素采样距离的整数。因此和我们接下来将看到的增量估计一起，意味着对于每一个三角形只需要做一次的完整精度的计算。所有的像素迭代代码总是以整型像素为单元进行步进，这意味着亚像素的大小仅仅需要被输入计算一次，而不是平方次。回过头来看，意味着我们可以以8位的亚像素精度来覆盖2048X2048分辨率或者以四位的亚像素精度来达到8192X8192分辨率。还有你可以将三角形转换为2X2的像素块而不是确定的像素，正如我们的三角形光栅化和任何OpenGL/D3D型光栅化渲染器做的，但是在此，我不细说。

填充规则

正如先前解释过的，填充规则的目标是确保两个不重叠的三角形共享同一条边的情况下，当同时渲染它们的时候，每一个像素只被处理一次。现在，如果你在寻找一个确定的描述(这个是对于D3D10 )，可能看起来非常难以去实现，因为需要比较边和边之间的关系，但是幸运的是最终做起来其实非常的简单，尽管我需要一点空间去解释它。

记住我们的核心光栅化渲染器都是以同一顺序来渲染三角形-跟之前一样设定为逆时针方向，正如上次所说的。现在让我们开始看一看我在文章中给你指出的规则。

l  上边缘是一个在其他边之上的精确水平的边。

l  左边缘就是在三角形左部的不精确水平边。

确定是否精确水平很简单(仅仅需要判断y坐标是否不同)。但是第二部分的定义看起来有些难以确定。其实也非常简单。让我们首先考虑上边缘:在其他边之上意味着什么呢？一条边连接两个点。在其他边之上的边连接的应该是最高的两个点。第三个点在它们的下面。在我们的示例三角形中，这样的边就是v1v2。(忽略掉它不是水平的，它仍然是其他边之上的边)。现在我声明符合要求的边一定指向左边。假设它是指向右边，那么v0应该在它的右半空间(负)，这意味着三角形是顺时针绕制，不符合我们之前逆时针的声明。同时这意味着任何水平边如果指向右边一定是底面边，否则我们再次得到一个顺时针的三角形。这里给出我们第一个更新规则。

l  在一个逆时针的三角形上，一个上边缘就是精确水平同时指向左边的边。它的末端点在起始点的左边。

这非常容易判断，仅仅需要对边向量进行一次符号检测。再次使用和之前相同的论据。(考虑边v2v0)，我们可以发现，任何的左边缘都是指向下面的边。任何指向上面的边是确定的右边缘。这给我们第二个更新的规则。

l  在一个逆时针三角形上，左边缘是指向下面的边。它的末端点是严格的在起始点下面。

注意我们可以舍去不水平的要求。任何指向下部的边通过我们定义都不能水平。因此也只需要一次符号检测，甚至比上边缘检测更简单。

现在我们知道怎么去判断哪条边是哪类边，那么我们怎么处理这些信息呢？再次摘抄出D3D10规则:

l  只要像素的中心落入一个三角形里面该像素就需要被绘制;一个像素落在三角形里面当且仅当它通过了上-左规则。而上-左规则就是，该像素的中心被定义在一个三角形里面如果它落在一个三角形的上边缘或者左边缘。

解释来说就是如果我们的采样点完整落入三角形里面，不是一个边界上，不管怎样直接绘制。如果它落在边界上，那么当且仅当它落在上边缘或者左边缘的时候我们进行绘制。

这是我们现在光栅化渲染器的代码:

不管是哪种情况我们都绘制边上的点-因为所有的测试都是满足大于等于0。对于对应于上边缘和左边缘的边函数这是可以的，但是对于其他的边我们需要测试一个更准确的所谓大于等于0。我们可以有多种版本的光栅化渲染器。其中一种是整合判断边0/1/2是或者不是上边缘或者左边缘，但是这种方法太可怕了无法按这个思路进行深入思考。

相反，我们是去使用一个对于整数的事实，那就是x>0和x>=1是等价的。因此我们可以让后面的测试保持原样，通过先计算每条边的偏移量一次，就像这样:

然后稍微改变下边函数的计算

仔细解释下:这稍微改变了我们传递给renderPixel函数的重心坐标(正如我们之前亚像素精度压缩做过的)。如果你没有使用亚像素修正，这可能会有一个大的错误你需要去修正。通过亚像素修正，你可能会决定在差值数量的大小差一不是一个大问题(记住边函数是在区域单元内的，因此1指代的是一个亚像素的平方，这是非常小的值)。无论是哪种方式，每个三角形的偏差值仅仅被计算一次。同时你直接可以对每个三角形只做一次修正，因此这样就没有额外的每个像素的开销。现在，我们也对每个像素应用偏差值，但是一旦我们开始优化它这个偏差会消失。顺便如果你回到整型溢出部分，你将注意到我们在精度要求上有一些缺失;偏差参数不会导致我们需要额外的位宽。最后它终于能够直接运行起来了，在我们光栅化渲染器中可以正确的处理填充规则。

这提醒了我，虽然我们讲的这一部分是一个深度缓存光栅化渲染器，这并不影响我们讨论统一的填充规则。它要做的无非是填充所有的东西在三角形里面或者在边上的行为。这可能是一个疏忽也可能是一个故意的安排来让光栅化渲染器更加传统这样对于应用而言更有意义。我不确定，而且我决定不介入这一点了。但是既然这篇博文是关于光栅化的。如果不去讲解清楚那就没有什么意义。特别是在网上找不到一个好的统一解释的时候。

所有的部分都运行得很好，但是现在我们怎么能够运行得更快呢？

当然这是一个大问题，你可能会讨厌我说，我将在下篇博文里面去给出答案。在软件光栅化概述中我们将解释讨论，然后回到这个系列开始的软件遮挡剔除Demo。

那么这篇博文和上篇博文的重点是什么呢？当然首先，这仍然是我的博客，我只是觉得想去写写它们而已。我决定花费至少两篇博文来讨论光栅化渲染器的重要部分。如果没有这些背景信息也不会对你的理解有什么改变。成熟的果实虽然好吃，但是你仍然需要付出努力，这就是其中的一部分。同时，虽然优化代码很有趣，但是准确性是一定要达到的选择。快速的代码如果没有做好它应该做的这就没有任何意义。因此在让它运行更快之前我要让它足够正确。我可以向你保证花费这个时间是值得的。我将试着尽快完成和上传下一篇博文，敬请期待。

【版权声明】

原文作者未做权利声明，视为共享知识产权进入公共领域，自动获得授权