3D图形编程指南4续 - 2D图元光栅处理

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


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/3.1/Image316.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图3.7 把凹多边形和凸多边形转换为像素直线</B></FONT></TD></TR></TABLE>
　　图3.7阐明了凹多边形的光栅化的固有复杂性。因此，在许多应用中限制多边形为凸多边形，它的处理要简单的多。当这种简化不可能的时候，我们尝试把凹多边形分割为凸多边形块。比如说，我们利用任意凹多边形都能分解为三角形的事实，进一步处理这些三角形，而三角形总是凸多边形。
　　任意多边形都能被三角化的事实来自Meister定理， 即至少有三个顶点的任意简单多边形至少可分为两个不交叉的耳状体（ear）。一个ear可以由多边形的某个顶点决定，与这个顶点相邻的两个顶点通过对角线相连。比如说，在图3.8中的顶点A确定了一个ear。然而，顶点C没有确定一个ear，因为它的两个相邻顶点的连线经过了多边形的边界，因此不是对角线。


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/3.1/Image317.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图3.8 寻找ear</B></FONT></TD></TR></TABLE>
　　很显然，这个定理对三角形来说是简单的事实（参见图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提出，这种线性算法不适于目前应用的实践。大多数运算时间用于重复那些上面提出的同样类型的简单算法。
　　尽管吸引人，但这种三角分割增加了多边形的数量，既然每次渲染都有某种程度的开销，设计和使用一些更复杂的凹多边形光栅处理算法代替许许多多次廉价的凸多边形光栅处理可能开销更小。在后面的几节中，我们将要讨论绘制凸多边形的简单算法以及适用于任意多边形的更复杂的算法，即使是凹多边形。
<B>
　　3.3.1 光栅化凸多边形</B>
　　必须找出一种光栅化凸多边形的算法，描述所有被多边形边界限制的水平像素直线。让我们考虑一下如何描绘像素直线。任何2D线段可以通过四个参数表示。两个端点的两个坐标。水平线有一个附加的约束，只需要三个参数：共同的高度和两个水平坐标，每个坐标用于每个端点。潜在地，多边形在屏幕上每个可能的高度上都有像素直线。因此，一个适当的数据结构用于保留这些线段，比如说，大小是屏幕高度乘以2的数组。对屏幕上每个可能的垂直坐标来说，其中一个整型数将用于储存像素直线起始点的坐标，另一个用于终点的坐标。


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/3.1/Image318.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图3.9 光栅化的多边形</B></FONT></TD></TR></TABLE>
　　当然，多边形边描绘了像素直线的配置信息。这种算法在每个时刻取出一条边，找出所有的属于当前边的像素，使用这些信息为一些像素直线设置起始和终点值。（参见图3.10）


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/3.1/Image319.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图3.10 存储多边形像素直线的数组</B></FONT></TD></TR></TABLE>
　　当我们在某些边上找到点的时候， 我们不能立刻知道是否它在y高度上指定了像素线段的起点或终点。一种方法与这里用到的排序很类似。我们利用这么一个事实，即像素线段的起始值小于或等于终点值。如果找到的点的x坐标小于已有的扫描线上的起始值，事实上，这个新点是实际的起始点。同样，如果同一个x坐标大于已有的终点，这个新点指定了实际的终点。
　　通过把最大的可能的初始值分配给所有像素线段的起始值，以及把最小的可能值分配给终点值，我们确信每个高度上的第一个点可能放在起点也可能在终点位置（毕竟，任意值可能小于最大的可能值也可能大于最小的可能值）。图3.11阐明了从多边形边寻找像素线段的过程。


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/3.1/Image320.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图 3.11 寻找多边形像素线段的步骤</B></FONT></TD></TR></TABLE>
　　寻找属于多边形边的点的过程，通常称作“边扫描”，它同线段光栅处理中做的非常类似。唯一的不同是，寻找坐标的目的不是标绘像素而是设置像素直线边界。我们也注意到为实现寻找像素直线边界的目的，我们可以彻底避免考虑水平边。水平边与其共享顶点的邻点也带有这些边界所表示的边界信息。观察图3.11，BC边用于设置最后的像素线，但是如果我们忽略了这条边，最后的像素线在AC和AB边处理完后也正确地设置了。
　　一旦每条像素线的配置都被找到了，光栅处理函数在图象位图中必要的位置设上要求的颜色值。这个任务在实践中非常简单， 这是因为内存单元所描述的水平线上的相邻像素占有连续的位置。程序清单3.4给出了实现凸多边形光栅处理的函数。


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

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


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

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


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/3.1/Image323.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>程序清单3.6 像素直线填充循环Intel 80x86汇编</B></FONT></TD></TR></TABLE>
　　这个代码非常容易导入到C程序中，它给出了某种速度上的提升，因为它使用的特别处理器指令非常适合以指定值初始化的数组。更进一步地，我们可以使用C库函数中的 memset来代替汇编，其目的是以某个值填充数组中的每个元素。这个库函数可能已经是用汇编编写的，同我们刚才做的事情非常类似。这个推测很容易用C编译器校验出来。为了这么做，我们可以反汇编memset函数的代码，检查它是如何实现的。在程序清单3.7中就是从libc获得的代码，libc是DJGPP（GNU到MS-DOS的接口）一个库。


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/3.1/Image324.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>程序清单3.7 反汇编memset代码</B></FONT></TD></TR></TABLE>
　　当然，这个代码同我们编写的非常类似，因此调用memset函数也能给我们同样的性能。当然，调用这个函数本身可能要花费一点时间。但是，更可能的是，我们编写的内联汇编代码同memset调用在性能上可能非常地相似。这又是一个用简单的手段来完成，而不是不眠不休的面对着显示器的例子。（不幸的是，只有经过了不眠不休的日子我们才知道如何用简单的方法完成：），但这是另一个故事了，在3D图形应用中需要一点献身精神。）
　　然而，我们要注意到，我们编写的代码以及在程序清单3.8中列出的代码都使用了字节存储指令stosb。Intel 80x86指令也设置了长双字（long　word）存储指令。这个指令完成4字节存储指令并假定了合适的内存队列。使用双字存储指令应该给出了相当客观的收获。因此，无论我们是否不再使用memset，这种内部的探索都是有帮助的。
　　一般地，移动和填充数组在计算机图形应用中是非常普遍的。尝试为这些运算获得更好的性能非常重要。可能，尝试使其易于移植也有好处。一个相当普遍的方法是，设置一个独立的模块（可能同与硬件接口相集成），这个模块为不同的体系架构执行不同的运算，但对其它的模块提供同样的函数原型。
<B></B>
<B>　　3.3.2 光栅化凹多边形
</B>　　正如我们已经看到的，凹多边形光栅处理的主要不同在于每个高度上可能有几个像素跨度要绘制。我们在考虑处理这类多边形的算法时，为了清楚起见做了简化。我们把这种多边形假定为非自交多边形或简单多边形。严格地来说，这种假设并不需要，它有可能对我们考虑的算法产生影响。
　　很显然，如果我们知道在给定扫描线处所有的交叉点，剩下的处理过程就很容易了。我们根据水平x坐标对点进行排序。进一步，假定多边形是简单的，在排序列表中所有的偶数点指定了跨度的起点，紧随其后的是终点。当我们为每个跨度计算填充过程的时候，整个多边形被正确地光栅化了。至于算法的第一部分，如何找出交叉点，最直接的强行解决方案是使用直线方程并检查扫描线和和多边形每个边的交点（在第五章我们将重新回到交叉点计算上来）。但是，这样就导致了许多代价昂贵的计算，我们需要更好的解决方案。
我们可以利用位置属性，它指明了扫描线是否与边交叉，这是一个很好的选择，下一条扫描线也与同一条边相交。从图3.12中能够看出，这个属性只是在极少的情况下不成立，即扫描线通过顶点且不再与以该顶点为端点的边相交。
　　因此，寻找扫描线与边的交叉点的算法可以首先根据其最小的y坐标预排序所有的边（除了无用的水平边）。如果某些边有同样的最小y，则使用较大y值边端点的x值作为辅助排序标准。（跨度起始边这样就出现在跨度终点边的前面。）更进一步地，我们将通过从预排序列表中增加这种边列表来保留当前活动边。当y坐标等于当前扫描线的时候，该边被增加进来。（参见图3.12）


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

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

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


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/3.1/Image326.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图3.13 通过插值进行明暗处理的多边形</B></FONT></TD></TR></TABLE>