引言
　　在前一章我们已经讨论了如何实现不同的坐标变换。这种技术使我们能够描述空间中虚拟对象的各种不同的位置以及通过投影使其对观察者可见。
　　投影变换把对象图元坐标从3D空间映射到视屏的2D空间。这些图元必须在2D空间中绘制，使其对观察者可见。既然我们考虑的是由一系列整齐地镶嵌的小方块组成的光栅图形，因此我们要确定这种几何图元的模拟描述如何能够被正确地转换为一系列离散像素。这个过程被称之为光栅处理（rasterization）。
　　一些图元比另外一些更容易被光栅化。线段和多边形面片首当其冲。在许许多多实际的应用中，绘图模块只支持基本图元的渲染，例如上面提到的这两种。在某些对象的描述需要更复杂的图元光栅处理的情况下，比如说三次曲线或者双三次曲面片，可以通过逼近技术得到。曲线通常以线段逼近，曲面表面则以多边形逼近。不太一般地，有一些例程可以直接光栅化复杂图元，尤其是曲线。
　　在这一章中，我们讨论如何光栅化简单的几何图元：点、线段和多边形。

3.1、光栅化点
　　点的光栅处理比较简单，非常便捷。它只包括把一些指定的位图内存单元设置上颜色数值。但是，不同之处在于，进行光栅处理的图象位图本身就是离散的，而我们要模拟的2D空间中却包含着连续的实数排列。如果我们要在两个整数像素坐标中标绘一个坐标为实数的点，就必须考虑如何处理这种不明确性。可能，把它逼近为最接近它的整数是一个相当合理和非常普通的选择。然而，数字图像的离散本性对光栅图象就来说是固有的误差之源，同时也带来了不完整性。在本章的其它部分还要对此进行讨论。现在，让我们忽略舍入误差，假定点的坐标被作为整数标绘，点的区域等于像素的区域（在这一小节中提到的点实际上是意味着点的附近，数学意义上的点不能被处理）。
　　让我们回忆一下，位图的第一个位置通常是左上角的像素。典型的内存单元排列描述了像素的连续扫描线，也确定了在这种情况下便于使用的参考系。Y轴的方向是从上到下，X轴的方向是从左到右。（参见图3.1）

图3.1 图象位图布局

　　假定每个像素由内存的一个单元代表(字节或双字)， 输出位图的大小是×，像素(x,y)在图象位图中的地址就应该是。在内存中从位图起始位置算起的某个偏移处设定指定的颜色值，最后的结果是，在blit位图后，点出现在屏幕坐标(x,y)上（参见程序清单3.1）

程序清单 3.1 点的光栅处理

3.2、光栅化线段
　　线的光栅处理算法在许多3D应用中是非常重要的。除了渲染线段外，几乎同样的算法也用于其它目的，比如说多边形光栅处理中扫描边的例程等。正因为它很普通，有许多原因要求这个算法要有效率。
　　当然，线段光栅处理的目的在于在给定的线上找到所有内插的像素，或者更一般地，找到非常接近直线轨迹的像素。一条线段通常由两个端点的坐标给定：和（参见图3.2）

图3.2 在线段上寻找点

　　在显示了一条线段的图3.2中，我们可以发现两个相似的三角形。一个由和形成，另一个由x和y形成。后者代表了属于线段上的某个点。仔细观察可以发现，这些三角形是成比例的，如果

　　那么就得到

以及

　　既然我们要沿着线的轨迹找到所有的点，我们就必须获得在区间中的所有的X，并计算相应的Y。然而这里有点问题：我们只有个计算点，但是， 如果Y的范围太大的话，我们找到的点在屏幕上可能不是连续的（参见图3.3）。在退化为垂直线的情况下，可能等于0，使得上面的等式不能成立。在这些情况下，我们必须从一个大区间中取出Y坐标，计算相应的X坐标（参见图3.3）。这样就得到了连续的轨迹并且避免了异常的情况。

图3.3 计算X的Y函数与计算Y的X函数

　　考虑这种方法的性能，我们发现计算单个点时，使用了一个乘法和一个除法。在实践中，这样的开销是非常大的。一个更好的技术是使用前向差分来迭代计算多点坐标。这种技术通常用于光栅化各种多项式曲线，线段可以被认为是在一个常量范围中的这种曲线。这种技术应用了一个简单的事实，在某些点的函数值等于它在点x上的值与函数在区间内前向差分的和。即：

　　尽管通常不是常数，但在直线段的某些特别情况下是常数。让我们看看下面的情况：

　　前向差分描述了函数改变的程度，它简单地被计算为：

　　这就意味着我们能够计算y(x+1)的值，即，对下一个离散的x（假定）来说，其函数值基于前一个离散函数值：

　　这就是计算每个点时要用到小数（浮点或定点）加法，当然，它同原始的方法相比较已经有了相当的改善。前向差分技术同样也可用于复杂曲线。在更复杂的情况中（比如在后面几章中要看到的），函数的前向差分可能不是常数。然而，由于其本身就是多项式函数，所以可以通过求高阶差分得到。
　　要注意到这种算法涉及到了小数（分数），或者是浮点或者是定点。潜在地，它也涉及到整数变换或舍入，因为位图毕竟是离散的。在性能方面，它在只使用整数运算的时候比较完美。我们要考虑的另一种迭代方式不涉及除法或小数。这要归功于J.E. Bresenham。
　　这种方法是在和区间中找到一个较大的范围，沿着这个区间内的点，当在一个较小的范围内增加的时候，变化很显著。让我们考虑一下在线段光栅处理的某个阶段发生了些什么。假定较大（），在给定的线段上和

图3.4 线通过像素栅格

　　图3.4显示了这么一种情况，我们已经在坐标(x,y)处渲染了像素P(x,y)（前一个），现在要确定下一个在哪里，是像素L(x+1,y)（较低的）还是像素H(x+1,y+1)（较高的）。既然实际的线将要通过P和L两个点之间，我们必须标绘中心最接近交叉点I(x+1,y(x))（这里的x=x+1）的那个点。这可以通过比较以交叉点分隔的h段和l段的长度来度量。回想起在原始的线绘制方法，可以得到：

　　以及

　　现在，我们感兴趣的h和l的比较结果，可以通过判断差分的符号得到：

　　如果l-h>0 意味着l>h，交叉点l更接近于H。H点被标绘。否则，如果l£ h，L被标绘。在等式的两端都乘以D X：

　　既然D X 假定为比0大，(l-h)和D X(l-h)的符号就是相同的。我们用d来表示D X(l-h) 并找出在i次和i+1次迭代的的过程中d的符号和数值。

　　我们也能够找出d的初始值。在第一个点上，既然x=0和y=0，我们有：

　　既然d的符号决定了哪一个点移到下一个位置(H or L)，我们要找出在i次迭代中d 的值，假定我们在前面的计算中知道了i-1次迭代中d的值：

　　如果在前一次迭代期间，我们决定在H标绘点，我们有：和，这就意味着

　　另一方面，当较低的点L在前一次迭代中被标绘的时候，我们有和，这就意味着

　　这个导出看起来有点复杂，但是一旦清楚了在循环前和循环中要执行哪一步，实现的算法非常普通。在迭代部分，我们已经找到了d的初值。此外，在循环内，取决于d的符号，我们要么加上2D Y-2D X，要么加上2D Y。既然这两个值在整个循环期间是常量，我们就能够在实际的工作开始之前计算它们。
　　在上面导出过程中，我们假定以及，然而，在实际中我们不必限制这些，一个方法是在不使用上面的假设时把递增改变为递减。对计算内循环来说，在选择了点L的时候我们必须紧记，坐标只有一个有着较大的递增（或递减）范围；当H被标绘的时候，X和Y都改变了， 这时在两个范围都出现同时递进的情况。程序清单3.2给出了一种可能的Bresenham线段绘制算法的实现。

程序清单3.2 直线光栅处理

　　这种算法根本不涉及除法或小数值。它使用了乘2的乘法，但几乎所有的现代编译器都会把它优化为左移一位 — 一种非常廉价的计算。
　　让我们试着分析一下程序清单3.2中出现的例程的性能。首先，我们对内循环中的代码感兴趣，因为大部分线段的这部分函数都要被执行多次。我们能立即看出其中有整数加法函数G_dot。然而，这个函数包含了至少一个乘法，这是我们付出极大努力要避免的运算。
　　让我们回想一下目的图象位图所表达的。如果我们仅仅渲染像素并想标绘另一个挨着它的像素，位图中这两个像素的地址有多大的不同呢？（参见图3.5）

图3.5 图象位图中的相邻像素

　　在图3.5中看得很清楚，如果我们想沿着X轴水平递进，像素B的地址等于像素A的地址加1。另一方面，像素A和C隔开了像素 — 位图的宽度。因此，为了沿着Y轴垂直递进，我们就要在A的地址上增加得到C的地址。使用这种策略，可以修改例程来替换坐标(x,y)，直接计算图象位图中的像素地址。程序清单3.3给出了这种实现方法的迭代部分。

程序清单3.3 优化的直线光栅内循环

　　从程序清单3.3中，我们能够看出在循环体中的代码没有留下任何开销大的运算。
　　基于同样原理的增量算法也用于各种各样的曲线中，特别是圆。这种算法有时侯，特别在2D应用中，有助于给出相当好的性能。然而，曲线也可以用线段逼近，这种方法尽管可能不引人注意，但它在实践中有着广泛的应用。

3.3、光栅化多边形
　　按照定义，多边形是任何边由线段形成的封闭的平面图形。为了表现虚拟对象，我们只对非自交或简单多边形感兴趣，这种多边形只在多边形的顶点处有交点。光栅处理的目的是给封闭区域内的每个像素分配一些指定的颜色。大多数多边形光栅处理方法是使用各类扫描线（scan-line）方法。这种方法是让扫描线沿着多边形垂直移动，在每个不同的高度上与像素直线相交叉。一旦找到了所有的像素线，剩下的是在某个时刻只绘制它们一次。这些直线必须被水平化是因为在大多数普通的图象位图中，像素形成水平线将在内存中占有连续的位置，这样在某些情况下比垂直线渲染的更快。
　　多边形分为凸多边形和凹多边形。按照定义，在多边形内部任意两点的连线不经过多边形的边界，则是凸多边形，反之则为凹多边形。（参见图3.6）

图3.6 凹多边形和凸多边形

　　这种分类与光栅扫描方法学有一定的关联。只有在凸多边形光栅处理中的任意水平扫描线层次上的连续像素跨度（span）才是需要的。很显然，在凹多边形光栅处理中可能需要多跨度。（参见图3.7）

图3.7 把凹多边形和凸多边形转换为像素直线

　　图3.7阐明了凹多边形的光栅化的固有复杂性。因此，在许多应用中限制多边形为凸多边形，它的处理要简单的多。当这种简化不可能的时候，我们尝试把凹多边形分割为凸多边形块。比如说，我们利用任意凹多边形都能分解为三角形的事实，进一步处理这些三角形，而三角形总是凸多边形。
　　任意多边形都能被三角化的事实来自Meister定理， 即至少有三个顶点的任意简单多边形至少可分为两个不交叉的耳状体（ear）。一个ear可以由多边形的某个顶点决定，与这个顶点相邻的两个顶点通过对角线相连。比如说，在图3.8中的顶点A确定了一个ear。然而，顶点C没有确定一个ear，因为它的两个相邻顶点的连线经过了多边形的边界，因此不是对角线。

图3.8 寻找ear

　　很显然，这个定理对三角形来说是简单的事实（参见图3.8 (a)）。对有4个顶点以上的多边形来说，任何顶点要么确定了一个ear，要么没有确定，我们可以找出给定顶点到某些其它顶点的对角线，这样把多边形分割为两个顶点数较少的子多边形。比如说，在图3.8 (b)中的顶点C可以通过对角线连接到顶点F，因为对C的两个邻点D和E来说，F是在直角方向上最接近C的顶点。假定作为结果的两个子多边形有两个不交叉的ear，即便一些ear是使用新导入的对角线构建的，这样的ear不能超过两个，每个ear分别在每个子多边形中，这样原多边形至少有了另外两个剩下的ear。上述内容本质上代表了一个归纳证明的压缩骨架，这里我们第一步说明了在假设的某个小范围内（这里是三角形），对基底来说来说命题是真实的。更进一步证明，如果我们假定假设对问题的某个小于n的小范围正确，并且我们也能证明它对n+1也正确，那么我们就可以得出结论，假设对所有的大于基数范围的n都是正确的。
　　Meister的定理直接推出了下面的三角分割算法：选择一个顶点，检查它是否确定了一个ear。如果是，切割这个三角形，在剩下的多边形中重新应用算法。如果选择的三角形没有确定ear，则把多边形分割为两个子多边形并对这两块重新应用算法。
　　代替了递归的另一种策略是，反复地切割ear，一次一个。换句话说，如果选择的顶点没有确定ear，仅仅检查另一个顶点。通过上面的定理迟早会找出一个ear。
　　必须注意到，测试一个顶点是否确定了一个ear，本质上可以通过测试某些点在三角形内还是在三角形外来简化。如果所有的多边形顶点都在由给定的顶点及其邻点形成的三角形外，这个给定的顶点确定了一个ear。我们将在第五章讨论如何执行多边形包含测试，在这里只需注意到，对确定ear的目的来说，只要对凹顶点（或反射顶点）进行包含测试就足够了。凹顶点（或反射顶点）是内角度超过180度的顶点，比如说图3.8中的F点。
　　一般地，已经知道这么一个问题，即三角化简单多边形需要的时间是顶点数的线性变化量。即，这种算法执行基本运算的数量与顶点数成比例。然而，不久以前，卓越的计算几何学家B. Chazelle提出，这种线性算法不适于目前应用的实践。大多数运算时间用于重复那些上面提出的同样类型的简单算法。
　　尽管吸引人，但这种三角分割增加了多边形的数量，既然每次渲染都有某种程度的开销，设计和使用一些更复杂的凹多边形光栅处理算法代替许许多多次廉价的凸多边形光栅处理可能开销更小。在后面的几节中，我们将要讨论绘制凸多边形的简单算法以及适用于任意多边形的更复杂的算法，即使是凹多边形。

　　3.3.1 光栅化凸多边形
　　必须找出一种光栅化凸多边形的算法，描述所有被多边形边界限制的水平像素直线。让我们考虑一下如何描绘像素直线。任何2D线段可以通过四个参数表示。两个端点的两个坐标。水平线有一个附加的约束，只需要三个参数：共同的高度和两个水平坐标，每个坐标用于每个端点。潜在地，多边形在屏幕上每个可能的高度上都有像素直线。因此，一个适当的数据结构用于保留这些线段，比如说，大小是屏幕高度乘以2的数组。对屏幕上每个可能的垂直坐标来说，其中一个整型数将用于储存像素直线起始点的坐标，另一个用于终点的坐标。

图3.9 光栅化的多边形

　　当然，多边形边描绘了像素直线的配置信息。这种算法在每个时刻取出一条边，找出所有的属于当前边的像素，使用这些信息为一些像素直线设置起始和终点值。（参见图3.10）

图3.10 存储多边形像素直线的数组

　　当我们在某些边上找到点的时候， 我们不能立刻知道是否它在y高度上指定了像素线段的起点或终点。一种方法与这里用到的排序很类似。我们利用这么一个事实，即像素线段的起始值小于或等于终点值。如果找到的点的x坐标小于已有的扫描线上的起始值，事实上，这个新点是实际的起始点。同样，如果同一个x坐标大于已有的终点，这个新点指定了实际的终点。
　　通过把最大的可能的初始值分配给所有像素线段的起始值，以及把最小的可能值分配给终点值，我们确信每个高度上的第一个点可能放在起点也可能在终点位置（毕竟，任意值可能小于最大的可能值也可能大于最小的可能值）。图3.11阐明了从多边形边寻找像素线段的过程。

图 3.11 寻找多边形像素线段的步骤

　　寻找属于多边形边的点的过程，通常称作“边扫描”，它同线段光栅处理中做的非常类似。唯一的不同是，寻找坐标的目的不是标绘像素而是设置像素直线边界。我们也注意到为实现寻找像素直线边界的目的，我们可以彻底避免考虑水平边。水平边与其共享顶点的邻点也带有这些边界所表示的边界信息。观察图3.11，BC边用于设置最后的像素线，但是如果我们忽略了这条边，最后的像素线在AC和AB边处理完后也正确地设置了。
　　一旦每条像素线的配置都被找到了，光栅处理函数在图象位图中必要的位置设上要求的颜色值。这个任务在实践中非常简单， 这是因为内存单元所描述的水平线上的相邻像素占有连续的位置。程序清单3.4给出了实现凸多边形光栅处理的函数。

程序清单 3.4 多边形光栅处理

　　我们已经考虑的算法使我们能够在屏幕上绘制凸多边形。然而，这种算法确实有点不太完美。如果我们检查图3.8，我们能够看到被标绘的像素占有的区域超出了实际的多边形。而且， 如果存在两个共享同一条边的多边形，边上的像素要被标绘两次，每个多边形一次。普通的解决办法是不设置在每个像素线最右端的像素，所有的像素都在最后的线上。
　　为了优化这种光栅处理算法，并不需要做很多。在程序清单3.5中函数的内循环只有简单的内部指令。算法的捷径也不是显而易见的。
　　然而，当性能是最主要的时候，如果所有能得到的书都看过了，所有的朋友都问过了，再没有什么别的主意了，最后的手段是使用汇编语言手工编写代码。在实践中，把一个C程序重新用汇编指令写出来，可能会快10-20%，这已经是一个相当值得考虑的了。当然，其代价是移植性和清晰性的损失。
　　然而，如果用汇编指令重写所有的东西，那就既没有什么特别吸引人的地方也没有实践上的意义。然而，正如我们已经看到的，许多例程的复杂性集中在相对紧密的循环中。大多数以汇编重写代码获得的潜在性能就来自这里。因此，实践中只是在很少一些特别的地方使用汇编指令。
　　就是说，如果有的话，现代编译器功能强大的一个原因就在于汇编内联。它允许直接在C指令中混入低级机器指令代码。不同的C编译器有汇编内联的不同支持。在大多数硬件上都能得到的GNU C编译器对此有着非常详尽的语法设计。

程序清单3.5 GNU C 汇编内联

　　正如在程序清单3.5中看到的，以别名指定的汇编指令允许从C变量中输入参数。别名以百分号（%）开始（双百分号%%表示实际字面意义的百分号，在一些汇编语言中通常是指寄存器以此字符串开始引用）。在许多情形中，机器指令在执行期搞乱了一些寄存器的内容。为了防止C代码从可能不存在的地方继续，我们应该仔细地指定所有被指令搞乱的寄存器。当内联汇编开始执行的时候编译器要确定此时在寄存器中不再使用的信息。看看多边形光栅处理的代码，我们能够看到像素线段渲染循环。这就是一个可能的用汇编重写的地方，因为它十分频繁地被执行，执行了相当可观的内存存取，尤其是在同周围的代码相比较的时候。
　　对Intel 80x86处理器和GNU C编译器来说，用内联汇编代替直线渲染循环的实现方法如程序清单3.6所示。

程序清单3.6 像素直线填充循环Intel 80x86汇编

　　这个代码非常容易导入到C程序中，它给出了某种速度上的提升，因为它使用的特别处理器指令非常适合以指定值初始化的数组。更进一步地，我们可以使用C库函数中的 memset来代替汇编，其目的是以某个值填充数组中的每个元素。这个库函数可能已经是用汇编编写的，同我们刚才做的事情非常类似。这个推测很容易用C编译器校验出来。为了这么做，我们可以反汇编memset函数的代码，检查它是如何实现的。在程序清单3.7中就是从libc获得的代码，libc是DJGPP（GNU到MS-DOS的接口）一个库。

程序清单3.7 反汇编memset代码

　　当然，这个代码同我们编写的非常类似，因此调用memset函数也能给我们同样的性能。当然，调用这个函数本身可能要花费一点时间。但是，更可能的是，我们编写的内联汇编代码同memset调用在性能上可能非常地相似。这又是一个用简单的手段来完成，而不是不眠不休的面对着显示器的例子。（不幸的是，只有经过了不眠不休的日子我们才知道如何用简单的方法完成：），但这是另一个故事了，在3D图形应用中需要一点献身精神。）
　　然而，我们要注意到，我们编写的代码以及在程序清单3.8中列出的代码都使用了字节存储指令stosb。Intel 80x86指令也设置了长双字（long　word）存储指令。这个指令完成4字节存储指令并假定了合适的内存队列。使用双字存储指令应该给出了相当客观的收获。因此，无论我们是否不再使用memset，这种内部的探索都是有帮助的。
　　一般地，移动和填充数组在计算机图形应用中是非常普遍的。尝试为这些运算获得更好的性能非常重要。可能，尝试使其易于移植也有好处。一个相当普遍的方法是，设置一个独立的模块（可能同与硬件接口相集成），这个模块为不同的体系架构执行不同的运算，但对其它的模块提供同样的函数原型。

　　3.3.2 光栅化凹多边形
　　正如我们已经看到的，凹多边形光栅处理的主要不同在于每个高度上可能有几个像素跨度要绘制。我们在考虑处理这类多边形的算法时，为了清楚起见做了简化。我们把这种多边形假定为非自交多边形或简单多边形。严格地来说，这种假设并不需要，它有可能对我们考虑的算法产生影响。
　　很显然，如果我们知道在给定扫描线处所有的交叉点，剩下的处理过程就很容易了。我们根据水平x坐标对点进行排序。进一步，假定多边形是简单的，在排序列表中所有的偶数点指定了跨度的起点，紧随其后的是终点。当我们为每个跨度计算填充过程的时候，整个多边形被正确地光栅化了。至于算法的第一部分，如何找出交叉点，最直接的强行解决方案是使用直线方程并检查扫描线和和多边形每个边的交点（在第五章我们将重新回到交叉点计算上来）。但是，这样就导致了许多代价昂贵的计算，我们需要更好的解决方案。
我们可以利用位置属性，它指明了扫描线是否与边交叉，这是一个很好的选择，下一条扫描线也与同一条边相交。从图3.12中能够看出，这个属性只是在极少的情况下不成立，即扫描线通过顶点且不再与以该顶点为端点的边相交。
　　因此，寻找扫描线与边的交叉点的算法可以首先根据其最小的y坐标预排序所有的边（除了无用的水平边）。如果某些边有同样的最小y，则使用较大y值边端点的x值作为辅助排序标准。（跨度起始边这样就出现在跨度终点边的前面。）更进一步地，我们将通过从预排序列表中增加这种边列表来保留当前活动边。当y坐标等于当前扫描线的时候，该边被增加进来。（参见图3.12）

图3.12 寻找凹多边形像素线中的跨度

　　图3.12显示了一个带有预排序列表的凹多边形，当我们在多边形的顶端开始光栅处理的时候，扫描线的y坐标等于A点的坐标，即AB和AE边的最小y坐标。这两个边都被增加到当前活动边列表中来。
　　对每一个连续扫描线来说，我们使用某种迭代算法计算活动列表中所有边的当前x，并从该表中删除在当前扫描线中已经结束了的。更进一步地，校验在预排序边中一些边的y是否等于当前扫描线的y，如果等于，把它们引入到活动列表中，活动列表每时每刻通过插入来重排序。因为列表几乎已经完整地排序了且只需很小的调整，所以重排序的开销非常小。在这一点上，我们对活动边列表中的边使用当前的x坐标填充跨度和重复插入。
　　为了举例说明这种算法，让我们看看图3.12。一开始对在活动列表中的AB和AE边直到点C水平面进行光栅处理。在这一阶段，两个以上的边被插入，在排序后列表变为：CD,CB,AB,AE。更进一步地，在点B水平面上，在活动列表中的两个边被删除，列表变为：CD,AE。
　　检查这种算法，我们应该注意到，如果我们保留了可能被插入下一位的边的索引，寻找哪些边插入到预排序的列表中是非常廉价的。既然边已经被排序了，我们只需检查当前被索引的边的y，如果它的y大于当前的扫描线，不再检查其它的边。当某些边被插入时，我们推进了索引并且重复检查直到当前边不再适合插入。
　　尽管凹多边形光栅处理很明显比凸多边形麻烦得多，可能许多开发人员选择只处理凸多边形，但这种算法仍然有它的优势。这一点我们将要在隐面消除技术中看到。特别地，我们也把这种算法扩展为同时处理多个多边形。

3.4、插值渲染明暗处理多边形
　　由于光栅处理的开销较小，在前几节讨论的恒定颜色多边形，或者平多边形，可能在很长时间中对许多应用中来说是一个选择。但无论如何，它们表达的是虚拟世界中相当不实际的影像。毕竟，在真实世界中，我们不经常看到严格恒定颜色的多边形面片。即便在单调颜色的表面，光线也导入了明暗不同的图案。表面本身也不是理想光滑的。大多数表面是不完美的，例如存在凹凸或不同材质的突起不平。虽然理想情况下，这些能够以相当大数量的平多边形重现，其中的每个多边形都不相同，但颜色或明暗相同。然而，这种方法不利于用多边形来实现场景建模的目的，因为简单化和组件小尺寸在这种表现手法中是至关紧要的。可以选择的方法是改变多边形光栅处理例程，这样它们就变得更成熟和产生更真实的图像。
　　一种技术是在光栅处理中考虑光线。另一种技术是在多边形上应用纹理。这两种技术都对建模场景给出了能够看到的改善。在后面几章我们在更多的细节上考虑了光线，特别是对在虚拟世界中的不同点如何计算照明度。为了本节的目的，我们假设我们能够计算表示多边形顶点上光线强度的值。既然在照明度上的变化大部分以光滑的途径改变，我们可以在多边形内部通过在顶点数值上插值来为像素计算照明光线。最快也许也是最简单的插值技术要归功于H.Gouraud。

图3.13 通过插值进行明暗处理的多边形

　　其思想是通过保持颜色强度值或多边形每个顶点上的值来集成光栅处理和光线强度计算，并且在计算像素直线的同时线性地插入这些值，以在多边形内部为每个像素找到颜色。（参见图3.14）

图3.14 颜色强度插值

　　换句话说，假定同屏幕空间坐标(x,y)一起，每个顶点有一个I，即颜色强度数值的某个排序，我们可以原始的扫描线方法继续进行处理，在进行的过程中内插照明强度。通过沿着每条边内插颜色强度在多边形左或右边界获得数值（图3.14中的）。然后，当开始渲染任何一条水平线的时候，我们能够进一步地在这条线的起点和端点内插强度，在之间为像素寻找颜色i。
　　这种算法一个很明显的用于为平多边形进行光栅处理的边扫描函数的意义是，顶点现在有更多的信息同它们联系在一起。而且，取决于使用的光线方案，单个的颜色可能用几个值来表达（注意，RGB模式用三个值，分别用于红、绿、蓝三种颜色）。在扫描函数中蕴含了一种可能的设计， 它可能被选择用于构建N维边通用效果扫描器。实际上，我们极为经常地要遇到至少两个其它的情形，即我们要跨越多边形内插其它与光线强度不同的信息。通用的构建方式可以使扫描函数有能力处理多重目的。
　　在程序清单3.10中的函数片段在计算除了x和y的值之外，使用了前向差分，仍然是通过Bresenham迭代来计算

程序清单3.10 边扫描例程（部分）

　　一旦像素直线组成的给定多边形被恢复，光栅处理函数更进一步地跨过每条扫描线内插强度值，举例来说，使用简单的前向差分。与扫描函数相类似，小数可以以定点形式保留下来。在程序清单3.11中的代码片段演示了带有明暗处理的多边形光栅处理的像素直线填充循环

程序清单3.11 渲染带有明暗处理的多边形

　　这里只是一个很简单的说明。它提及到了强度能够同一个冗余维一样被处理得很恰当。实际上，我们在屏幕上考虑明暗处理化的多边形时，用到了两个空间维以及一个颜色维。但是在这个3D空间中所有的顶点都属于同一个平面吗？如果不是，我们要依赖于我们从哪个顶点开始内插来处理不同的明暗值。在实践中，当我们旋转一个带有上面提到的问题的明暗处理多边形的时候，在明暗面上有可见的不连续，根据多边形的方位这个不连续也在变化。一种解决方案是限制多边形仅仅为三角形。在3D空间中，三个不共线点属于同一个平面，因此，对方位不受约束的多边形来说，线性插值将给出光滑的外观。

3.5、渲染纹理多边形
　　在多边形上应用纹理是为了改善合成场景的视觉真实度。实质上，纹理同多边形区域的参数（u,v）的颜色相关联。一种纹理方式是程序纹理，它是由一些函数（程序）为任意(u,v)坐标计算颜色。另外一种，可能是普通一些的方法，把纹理存储为位图。在这种情况下，在2维数组中精确地为每对(u,v) 存储了一个颜色。通过指定多边形每个顶点的纹理坐标把纹理同多边形关联起来。（参见图3.15）

图3.15 多边形和它的纹理

　　我们也可以扩展为插值明暗处理计算颜色强度的插值技术来进行纹理映射。如果我们只是在多边形的每个顶点保持纹理U和V， 可以在边扫描期间顺着边内插这两个值，并且沿着水平线，完成纹理(U,V)输出到屏幕上的像素的过程。(参见图3.16)

图3.16 内插纹理坐标

　　然而，这种方式工作得并不彻底。或者，为了更精确，当使用透视投影寻找多边形在屏幕上的图像的时候，它不能工作。其原因是：透视变换不是线性的，因此在纹理映射期间纹理坐标跨越多边形的改变也不是线性的，不能使用线性插值得到正确的结果。（参见图3.17）
　　或许有人会问，为什么这种方法能为内插明暗处理工作：毕竟，我们一直在使用透视变换？其答案是，它实际上也没有工作，但是用于明暗处理的忽视了透视效果的可视对象在大多数情况下已经非常合适了。然而，对纹理渲染来说忽视它是不行的。它处理了人眼察觉到的可视对象的强度。在横越多边形时，相对较小的可视对象迹象的数量由明暗处理引入。在纹理多边形中，存在着相当大数量的可视对象迹象的数量。在后者情形下，不仅仅是真实性没有直接反映出来，还有可能在形式上彻底地被忽视了。

图3.17 线性纹理映射(注意，有不自然的扭曲)

　　为了在线性纹理映射中确认透视失真的效果，只要考虑下面的情况：一个矩形多边形显示在屏幕上，这样其中一条边比相对的那条更靠近我们，后者几乎消失在无穷远处（参见图3.18）。在纹理图中哪一条线对应屏幕上的像素线？显然，纹理坐标可以沿着AD、AB和DC边插值。然而，在这个例子中，BC边极其地小。因此，没有像素线能够与BC边在纹理图中相对应的贴切地映射。(参见图3.18)

图3.18 用于透视投影多边形的线性纹理映射

　　在某些这类极端的情形下，屏幕上的纹理多边形缺乏与实际的纹理中相对应的部分，其它的部分则不自然地连结进来产生了失真。（参见图3.17）
　　然而，有的时候这种方式的纹理渲染看起来要好一些，当透视变幻的效果微不足道的时候它是很完美的：所有的点与观察者的距离粗略相同，或者距离视平面非常地远。在图3.17中，注意到，前景多边形的纹理看起来不真实，前景多边形的纹理在透视效果比较大的情况下出现了不自然的扭曲失真。实现线性纹理映射有个优点：比起我们后面要讨论的非线性映射，它的花费要小得多。对大多数应用来说，可能需要同时实现这两种方式。在多边形的位置上作简单的分析，如果情形合适，用线性纹理映射进行处理，只是在要紧的位置上使用非线性纹理映射，即，多边形太靠近投影面以及透视失真度比较大。
　　至于非线性纹理映射（参见图3.19），首先，直接的解决方案是在透视投影前分割多边形，这样更多的顶点精确地在屏幕和纹理之间映射，且线性纹理映射限制为较小的多边形，在这些多边形上失真度看起来较小。

图3.19 透视纹理映射

　　然而，这种解决方案增加了多边形的数量，因此不是很吸引人。为了找到一个不同的不需要细分多边形的方法，让我们来试着描述在变换阶段中多边形和它的纹理发生了些什么变化。(参见图3.20)

图3.20 纹理多边形变换阶段

　　考虑一下上面描绘的三个空间：纹理空间、视空间（在投影变换之前，观察者位于坐标起始点的那个空间），最后，是屏幕上的内容 — 屏幕或图象空间。第一个空间是多边形局部。在世界中对象的位置和方位以及观察者的位置和方位决定仿射变换必须把多边形变换到视空间（第五章有这方面所需的详细细节）。屏幕空间包含了依赖于透视变换焦点距离的多边形透视图象。
　　我们已经看到，从世界空间变换到视空间必须进行仿射3D变换。这种变换以4×4矩阵表示。因此，点T(u,v)变换到视空间点可以被表示为：

　　这里的[T]是4×4矩阵。假定我们知道在视空间中向量U和V映射为纹理空间的单位长度向量(1,0)和(0,1)，这些向量描述了纹理的主轴如何经过仿射变换而成为有方向的（oriented）。再假设我们知道纹理空间原点映射为视空间中的点O。知道了这些，我们就可以把三个点的纹理映射表达为以纹理空间中的原点和沿着两个主轴的单位向量表示的形式。

　　知道了这些映射，并且记住纹理只有两个维，我们就可以再次得到变换矩阵[T]，如下：

　　知道了变换，我们就能够表达个别的映射纹理坐标T(u,v)到视坐标V(x,y,z)的公式，如下：

　　更进一步地，视空间中的点V(x,y,z)经过透视变换后，变换为屏幕上的点S(i,j)：

　　为了实现映射，我们需要纹理坐标(u,v)作为屏幕坐标(i,j)的函数。换句话说，我们要知道哪种从纹理中取出的颜色作为屏幕上像素坐标的函数。为了做到这一点，我们从表达视空间坐标为屏幕坐标的函数开始：

　　进一步，通过以纹理空间形式替换x，y和z，我们得到：

　　通过以i，j表达u，v，我们得到：

　　进一步，公式变形之后，可以得到下面的逆映射公式：

　　这两个公式使我们能使用描述纹理方位的两个向量以及描述纹理空间原点映射到视空间的点为任意屏幕坐标计算纹理坐标。这三个附加的参数必须在应用公式前获得。因此，每个多边形处理纹理时，最初都同描述纹理方位的两个向量和描述纹理空间原点的点关联在一起。在我们在多边形顶点上执行变换的同时，也要对这三个参数应用同样的变换。唯一的例外是，我们不必对顶点应用平移变换，因为它们对此不受影响。作为结果，我们也得到了开始纹理计算必须的视屏幕参数。尽管这种方式实现起来相对简单，但是附加到每个多边形上的数据对维护来说也是个大问题。而且，对线性纹理映射来说，我们需要每个顶点上的纹理坐标，因此，如果我们想使用上面的任一种方法渲染多边形，多余的信息会变得很大。在第五章，我们继续回到这个问题上来，提出一种策略，使我们能够在顶点上使用纹理坐标，并重新获得需要的透视纹理映射的信息。
　　如果我们检查公式，我们能够看到一些子表达式对整个多边形来说是常数，一些对每条扫描线来说是常数。因此，正确的计算排列能给出实际的性能。但是，即使考虑到这些，还是得在每个顶点上使用几次昂贵的除法。可能，最简单的优化计算的方式是沿着水平线细分。我们每隔N个点计算真正的纹理映射，然后在其中线性内插计算值，以直接获得点的映射。(参见图3.21)

图3.21 扫描线细分和线性逼近

　　正如我们从图3.21中看到的，我们只是在沿着像素的几个点上作为屏幕坐标(i,j)的函数来计算真正的纹理映射(u,v) 。沿线其它的点从已知精确映射的邻近点纹理坐标的线性插值中得到(u,v)。尽管我们并没有得到精确的结果（仅仅是用如图3.21所示的线段逼近真实的映射路径），但是，我们引人注目地减少了涉及到的昂贵的计算。而且随着精密计算映射的点大量增加，其结果也是十分合理的。
　　在某些环境下可能（比如说以硬件实现）更吸引人的另一个可能的途径是，用多项式曲线逼近纹理映射路径。如图3.21所示，以足够多的线段逼近（这个可以认为是一阶多项式曲线）需要大量的细分。通过应用更高阶的多项式我们能期望得到对实际的纹理映射路径更好的逼近。二次曲线（二阶多项式）就是一个很好的选择，因为真正的映射路径是相对光滑的。因此，我们能够通过求参数曲线的值尝试沿着某些扫描线找到纹理坐标(u,v)：

　　这里的x是描述沿着扫描线位置的参数（参见图3.22）

图3.22 二次曲线逼近

　　显然，为了找到上述表达式的6个系数，我们需要有6个已知左侧值的不同方程。如果我们有三个已知纹理映射精确的点（参见图3.22）就可以做到这一点。我们能够通过使用前面考虑的逆映射的技术找到这样的点。假定我们知道当前扫描线起点、中点和终点的映射。
　　假定参数x沿着扫描线在区间[0,1]变化，这样，在起点，在中点，在终点。这样，我们就进一步构造了6个方程，如下：

　　对 　　　　

　　对 　　　　

　　对 　　　　

　　通过对这些方程和并求解，就得到了系数的表达式：

　　有了这些以后，我们能够通过求二次曲线的值沿着扫描线为任意像素找到逼近的纹理映射。当然，直接求值涉及到了几个代价昂贵的乘法。幸运的是，既然沿着扫描线的像素以迭代的方式处理，我们可以使用在前面的直线光栅处理中考虑到的前向差分的迭代技术，以极为有效的方式求二次曲线的值。正如我们看到的，如果我们知道前一个点的值和前向差分，就能够计算某些点上的函数值，对u纹理坐标来说，就是：

　　我们找出第一个前向差分：

　　因为结果表达式不是常量，但我们可以对多项式函数使用同样的前向差分技术（二次求导）：

　　当然，对和可以同样推理应用。有了这些以后， 我们通过向在前次迭代中已知函数值增加一阶导数能够迭代地找出当前函数值。同时，通过向一阶导数的当前值加入二阶导数计算出用于下次迭代的改正的一阶导数：

　　甚至有可能使用更高阶的多项式（例如三次曲线）用于扫描线纹理映射路径的逼近。系数求导和连续求值与上面一样，只是需要更多的点、更多的等式和更高次的前向差分。在实践上不使用阶数高于三次的多项式，因为它们给出的改善并不值得注意，但附加的开销变得大了起来。
　　我们也可以沿着常数Z直线渲染，来代替沿着扫描线渲染多边形。
　　后面这种方法沿着多边形Z是常数的面上的每条线进行，其优势也正来自此。透视变换是线性的，因此映射路径，比如说对应的直线也是线性的（透视变换是，我们也可以把它看成，这里，如果z是常数，则该式是线性的）。当然，它也有缺点，即，常数Z直线一般不是屏幕上的水平线。这样光栅处理可能出现问题，因为在直接向下的执行方式下，相邻的像素直线间可能有间隔。

3.6、反走样
　　正如我们以前已经注意到的，由于我们或显或隐的简化，存在一些固有的不理想性。举例来说，当绘制多边形的时候，部分地被多边形的解析区覆盖的像素仍然被标绘。这就产生了当我们使用直接向下的光栅处理算法的时候常见的“梯状”锯齿线和锯齿边效果。另一个例子，即，当从纹理图中拾取一个颜色值的时候，我们只考虑一个纹理单元。问题是，在距离观察者较远的距离上，由于透视缩短效果，不是一个单独的颜色而是一个纹理区域对应屏幕上的单个像素。一个关于这个古老问题的流行例子是国际象棋棋盘远离观察者移动。在某些点上，矩形的透视变得比屏幕上的像素小。自然地，举例来说，如果黑和白方块投影到同一个像素上，像素看起来有些灰色的色调。不幸地是，简化的纹理映射没有考虑这个区域，这样取决于周围的情况，要么是黑要么是白被绘制上去。这样，图象看起来非常地不自然，在纹理规则的情况下，比如说棋盘，实际上可能绘制成了不寻常的Moiré样式。
　　所有这些例子演示了由光栅图形离散的本性带来的走样（失真）问题。这样就产生了很奇特的反走样技术来减轻这个问题。这种技术从极其简单的到极度复杂的都有。这些技术可以粗略地分为两类，第一类以绘制例程合并到一起，第二类是在渲染图形的时候进行后期处理来改善品质。
　　举例来说，纹理映射器能够考虑实际的像素区域，在纹理中寻找哪个区域被映射上，进一步地平均颜色得到光滑图象。但这种技术开销比较大。通常用于替换它的方法叫做纹理细化（MIP mapping）。其思路是预先以不同的比例计算纹理，然后对远离观察者的多边形使用较小的纹理。既然它保证了在纹理和屏幕像素间小区域的不同，它也就有较小的走样问题。仅仅有相对较小的关联开销，但结果图象却显示出了相当大的改善。
　　第二类技术在渲染的图象上执行过滤，这样结果图象就更光滑了。原始图象通常是过采样（supersampled）的，换句话说，就是在更高的分辨率下渲染。过滤处理从原始图象中取出一组像素，计算它们强度的加权和。其结果放到过滤过的图象位图中。图3.23显示了过滤过程。在这个例子中，过滤器是赋值过加权的3×3矩阵，用于计算结果像素的强度，然后放到过滤过的位图中。

图3.23 过滤

　　过滤器通常从解析函数的变化中产生，其中最简单和最普通的是门函数（Box）、三角函数和高斯函数（Gaussian）。这些函数关联了跨过几个像素我们想要过滤的区域内点的加权。(参见图3.24)

图3.24 过滤函数

　　代替解析过滤器的另一个途径是，在某个邻域内采样一些随机点。这种方法被称为随机采样。使用这种方法得到的结果看起来更好，因为这种方法趋向于在过滤过的图象中留下可视噪声和不规则图案。人类的视觉系统似乎有能力忽视可视噪声，夸大规则图案。
　　作为过滤结果，多边形的尖锐边和其他由单纯的光栅处理算法导入的失真变得光滑了一些。尽管通常来说彻底地去除采样过疏导致的问题是不可能的，但图象中一般的表现能够使用过滤方法得到相当大的改善。这种技术的限制是它使用了过采样。图象必须在较高分辨率下计算，这个受到可用内存资源和处理大图象的处理时间的限制。
　　另外，在几个例子中看到的空间走样，在运动中显示对象的交互计算机图形应用可能会遇到瞬间走样（temporal aliasing）。在电影中出现的同样的例子是旋转的车轮由于车轮高速旋转在摄像机的采样速度下，看起来反转了旋转方向。在计算机图形应用中尝试解决这个问题的一个方法是导入运动模糊（motion blur）。同减轻空间走样时使用的过滤策略相类似，在这种情况下，我们能在图象位图内计算像素的强度，这个可以通过在几个连续帧中寻找这个像素的加权和，及时在不同的运动中捕捉对象。当然，除了用于减小瞬间走样问题，这种运动模糊效果通常也用于以其自身改善交互图形应用的真实性。
　　这种技术的使用及其依赖于应用程序的目的和可用资源。顶尖的渲染应用可能使用非常复杂的技术用于改善视觉真实性，然而较低的应用，或者受性能约束的时候，可能就要为速度而牺牲真实性。

　　小结
　　总的说来，光栅处理例程用于在光栅显示设备上绘制几何图元。对光栅化复杂几何对象来说是非常昂贵的，我们通常以简单图元（例如线段或多边形）的集合来表达他们，这些简单图元容易光栅化。为了改善多边形的外观，依赖于可用的资源，可以加入明暗处理和纹理映射改善视觉真实性。
　　光栅图形的离散本性经常使走样问题变得各种各样，在绘制算法或后期处理中的反走样技术尝试减轻这些问题。