光栅化算法

多数计算机图形图像，是通过光栅显像显示给用户的，这种系统将图像作为像素阵列进行显示，像素（pixel）即图像元素（picture element）的简称。这些像素采用RGB颜色空间。本文讨论光栅显像的基本原理，着重讨论RGB颜色系统和标准图像显示器存在的非线性。

1.光栅显像

台式机和投影显示器的显示技术有多种。这些显示器的分辨率（像素数量）和物理尺寸各不相同，编程人员通常假设像素排成矩形阵列，又称为光栅（raster）。

像素

光栅显示器上的可显示元素称为像素。在显示器上，通常用有序对(i,来表示像素的索引,即表示该像素所在的行与列。如果一台显示器具有n,行、n,列像素，则左下角的元素是像素(0,0)右上角的元素是像素(nx-1,ny-1)

我们需要用实际的二维屏幕坐标来表示像素的位置。随着API的不同，这些系统在细节上会有所不同，但是最常使用的是用整数点阵作为像素的中心，如图,4x3屏幕所示。由于像素占据一定的空间区域，所以距离像素中心具有0.5个单位的过冲(overshoot)。

2.显示器亮度和 $\gamma$ 值

现在所有的显示器都采用数字信号输入方式，接收的是用数字信号表示的像素“值”，然后将其转化为亮度值。断电后显示器的亮度实际上不是零，因为屏幕能够反射环境光线。但我们可以认为此时显示器呈“黑色”，显示器完全打开时呈“白色”。对像素颜色用0到1的数值来表示。黑色为0，白色为1，介于黑白中间的中间灰色为0.5。注意这里“中间”指的是从像素发出光线的强度，而不是指观察到的亮度。人类对光强的感知呈非线性，这不是我们现在讨论的内容。

为了在显示器上产生图像，要先明白两个关键问题。第一，显示器对输入信号的处理是非线性的。例如，如果输入三个像素值0、0.5、1.0，显示的亮度则可能是0、0.25、1.0(也就是0、打开1/4、完全打开)。对于多数显示器，一般利用 $\gamma$ 值来近似表示其非线性，具体数值就是下面公式中的指数:

显示亮度=(最大亮度) $a^{\gamma }$

其中a是介于0到1之间的输入亮度值。例如，如果显示器的y值为2.0，输入值为a=0.5，则显示亮度是最大亮度的1/4，因为0.52=0.25。不管值为多少，a=0对应显示亮度为0，a=1对应最大显示亮度。用y值表示显示器的非线性只是一阶近似,实际中在估计设备的y值时不需要很高的精度。一种度量非线性的直观方法是，找到能产生黑白之间的中间亮度的a值，即下式中的a值:

0.5= $a^{\gamma }$

如果能找到满足上式的a值，则通过两边取对数就可以求出y值:

$\gamma =\frac{ln0.5}{lna}$

标准求a值的方法是，显示黑白相间的像素棋盘模式，如图是具有a值的灰色像素方阵.当从远处观察这幅图像时(或者当你眼睛近视但没带眼镜时)，如果a值正好是黑白的中间值，那么这幅图像的左右两边看起来会大致一样。这是因为，虽然存在很多的黑、白像素，但经棋盘模式混合，整体效果就显示一致的中间色了。为了做好这个实验，必须尝试很多a值，直到53]找到需要的数值为止。可以为用户提供一个滑动条来控制a值，或者将多个不同灰度的方块同时与一个大的棋盘模式比较。值得注意的是，CRT沿水平方向快速改变亮度是有难度的，因此水平的黑白条纹要比棋盘模式效果好。利用人脸识别技术可使亮度匹配结果更加精确(Kindlmann，Reinhard,&Creem，2002)。

一旦知道了 $\gamma$ 值，就可以对输入进行伽马校正，使得输入值a=0.5可以在屏幕上显示出介于黑白中间的灰度效果。变换方法为：

$a = a^{\frac{1}{\gamma }}$

把该式代入显示亮度公式可得：

显示亮度 = (最大亮度) $\left ( a^{^{\frac{1}{\gamma }}} \right ) \gamma$ = a 最大亮度

实际显示器的另一个重要特征是，输入值通常经过了量化处理。因此，我们可以在浮点范围[0,1]内处理亮度值。输入到显示器的信息一般是大小固定的非负整数，取值范围一般是0~255，可采用8位二进制数存储。所以a的取值不是[0,1]中的数字，而是

a的取值 = $\left \{ \frac{0}{255} ,\frac{1}{255},....,\frac{254}{255},\frac{255}{255}\right \}$

则显示的亮度值近似为

$\left \{ M\left ( \frac{0}{255} \right )^{\gamma }, M\left ( \frac{1}{255} \right )^{\gamma }, M\left ( \frac{2}{255} \right )^{\gamma },..., M\left ( \frac{254}{255} \right )^{\gamma } M\left ( \frac{255}{255} \right )^{\gamma } \right \}$

M表示最大亮度。实际应用需要精确控制亮度值，我们要分出256个可能的亮度等级，而且这些亮度在屏幕的不同位置其值也有所不同，尤其是CRT显示器更需要这样做。视角不同也会影响亮度值。幸运的是，实际系统一般不需要做精确标定。

3.RGB颜色

计算机图形学中，多数显示效果都由红绿蓝（RGB）颜色空间确定。RGB颜色空间比较简单，经转换能够直接控制多数计算机屏幕的显示。

对于RGB加性颜色空间，我们有下列混合效果：

红+绿=黄

绿+蓝=青

蓝+红=紫红

红+绿+蓝=白色

青色是一种蓝绿色，紫红色是一种紫色

所以只要让基色光的强度由最小到最大变化，就能在RGB显示器上显示所有颜色。把单色的最亮状态表示为1,则颜色值为0~1之间的分数。这样就产生出一种三维RGB颜色立方体红、绿、蓝为坐标轴，坐标值从0到1变化。颜色立方体如图：

常见的RGB颜色坐标为：

黑色 = (0,0,0)
红色 = (1,0,0)
绿色 = (0,1,0)
蓝色 = (0,0,1)
黄色 = (1,1,0)
紫红色 = (1,0,1)
青色 =(0,1,1)
白色 =(1,1,1)

实际RGB数值以量化形式给出，类似上面显示器亮度和 $\gamma$ 值的灰度级，各成分都用数表示。常用的整数大小占一个字节，所以RGB的各成分是0~255之间的一个整数。三个整数共占用三个字节，也就是24位二进制数。因此，具有“24位颜色”的系统，三基色中的每一种都有256个等级。

4. $\alpha$ 通道

当我们想在背景上面插入一幅前景图片，

对于不透明像素，我们只需要替换相应位置的背景像素即可。

对于完全透明的前景像素，背景像素不在改变。

对于半透明像素，为了将前景与背景混合，就要权衡像素作为前景的分数（fraction）。该分数用 $\alpha$ 表示。如果想把前景色 $c_{f}$ 与背景色 $c_{b}$ 混合，并且被前景覆盖的像素的分数为 $\alpha$ ，那么就可以采用下面的计算公式计算

$c=\alpha c_{f}+(1-\alpha )c_{b}$

如下图，图中的 $\alpha$ 图像可以存储为RGB图像，也可以存储为单通道的灰度图像。尽管使用率很高，但在很多情况下 $\alpha$ 以其他方式得到使用（Porter&Duff,1984）。

在前景图像与背景图像混合之前，先经过 $\alpha$ 通道进行了修剪处理。最下面是组合效果图

5.直线绘制

多数图形软件都包含直线绘制命令，即捕捉屏幕上两个点的坐标，并在它们之间画一条直线。例如，如果发现两个端点是(1,1)和(3,2)，那么就在屏幕上显示这两点，并在它们之间填上一个像素。对一般的屏幕坐标端点 $(x_{0},y_{0})$ 和 $(x_{1},y_{1})$ ，常规作法是在它们之间画出合适的像素点集，这些点近似一条直线。为了简化处理 $x_{0},x_{1},y_{0},y_{1}$ 的值经常规定为整数(像素中心)，因为直线本身就比较粗略，要求子像素精度不合适。在实现API时需要的是实数端点坐标，一般方法是将它们就近取整，这样做比较合理，一般应用编程人员注意不到有什么不同。因为端点坐标是整数，在整数与浮点变量共同参与运算时，就要注意隐式类型转换问题。我们基于直线方程进行直线绘制。有两种类型的方程可供选择:隐式方程和参数方程。下面讲解基于这两种方程的两种算法。

基于隐式方程绘制直线

直线方程 y = ax+b 可以得出斜率

$a = \frac{y_{1} - y_{0}}{x_{1} - x_{0}}$

直线隐式方程

$f(x,y) = (y_{0} - y_{1})x + (x_{0} - x_{1}) + x_{0}y_{1} -x_{1}y_{0} = 0$

在下面的讨论中都假设a∈(0,1]。类似地,可以推出a∈(-∞,-1]、a∈(-1,0]和a∈(1,∞)时的结果这4种情况覆盖了所有的可能情况。
当m∈(0,1]时，直线在x轴上的变化速度大于在y轴上的变化速度。对于y轴方向向下的API,我们可能会想到情况是否变得复杂。实际上我们可以忽略这个细节。可以不考虑几何上的“升”和“降”，因为两种情况下的代数表示是一样的。认真的读者可以证明，得到的算法同样适用于y轴向下的情况。中点算法的重要假设是，我们能绘出没有间隔的最细的直线。两对角像素之间的连接被认为不产生间隔。

绘制直线时，从左端点向右端点进行。只有两种可能:绘制一像素时，和左边所绘像素高度一样，或者高出一个像素。在两端点之间每一列,总是只有一个像素。没有像素就意味着有间隔,有两个像素则直线太粗。就我们正讨论的情况来说，同一行上可以有两个像素;因为直线更接近于水平，因此其走势是向右或者向上。这种认识如图所示，图中显示3条这样的直线，每一条在水平方向的前进速度要比在垂直方向上快。

针对m∈(0,1)情况的中点算法，首先建立最左边的像素，以及最右边像素的列号(x值)，然后沿水平循环建立每个像素的行号(y值)。该算法的基本形式如下:

$y=y_{0}$

for x= $x_{0}$ to $x_{1}$ do

draw(x,y)

if(some condition) then

y=y+1

其中的x和y都是整数。简单地说就是“从左至右不断绘制像素，在该过程中有时需要向y轴正向有所偏移”。关键是如何确定if语句中的条件。

一种有效方法是,参考两候选像点之间的中点位置。更具体地说,对于刚绘制的像素点(x,y),它在屏幕上的坐标为(x,y)，下面要绘制的候选像素为(x+1,y)和(x+1,y+1)。两候选像点之间的中点为(x+1,y+0.5)。如果直线通过中点的下方,就绘制下面的像素:如果直线通过中点的上方,就绘制上面的像素(见图3)。

判断直线是通过点(x+1,y+0.5)的上方还是下方。位于直线上的点(x,y)，满足直线方程f(x,y)=0;位于直线一边的点,满足 f(x,y)>0;位于直线另一边的点，满足f(x,y)<0。由于-f(x,y)=0和 f(x,y)=0都可以作为直线的方程，所以很难利用f(x,y)的正负来快速判断(x,y)究竟位于直线的上、下哪个方向。但是,可以通过分析算出来。y的项(x1-x0)y。要注意(x1-x0)肯定为正数因为x1>x0。这就意味着随着y的增大,(x1-x0)y项的值将变大。因此f(x,+∞)肯定为正，并且位于直线的上方，也就是说直线上方的点都是正的。另一种判断方法是，由于梯度向量中的y分量是正的，因此在直线的上方y可以任意增加，f(x,y)也就肯定是正的。于是，我们可以把if语句中的条件写具体，代码就更明确了:

$y=y_{0}$

for x= $x_{0}$ to $x_{1}$ do

draw(x,y)

if f(x+1,y+0.5) < 0 then

y=y+1

6.三角形光栅化

在屏幕坐标系中，我们经常想绘制一个过二维点p0=(x0,y0)、p1(x1,y1)、p2(x2,y2)的二维三角形。这与直线绘制问题类似，但是它也有自己的特别之处。已经证明端点采用整数坐标没有什么益处，因此允许(x，y)具有浮点值。与直线绘制一样，希望能根据顶点数值插入颜色或其他性质。如果存在重心坐标系，就可以直接计算插入值。例如，假设顶点的颜色为c0、c1、c2，在重心坐标为的三角形内部，某点的颜色值为

$c=ac_{0}+\beta c_{1}+yc_{2}$

这种颜色插值方法在图形学中称为Gouraud插值法，来源于提出该算法的作者(Gouraud，1971)的名字。
光栅化三角形的另一个特别之处是,我们通常对具有公共顶点和公共边的那些三角形进行光栅化。这就意味着要光栅化的是相邻三角形，因此没有空隙。可以使用中点算法画出每个三角形的轮廓，然后填入内部像素，从而实现三角形光栅化。因此，相邻三角形在邻边处都绘制了相同的像素。如果两相邻三角形的颜色不同，则图像将由两个三角形被绘制的顺序来确定。为了避免顺序问题并且消除空隙，最常用的三角形光栅化方法是利用下列约定:当且仅当一个像素的中心位于三角形内部时，才绘制该像素。也就是说，像素中心的重心坐标都在区间(0,1)内。于是又产生了这样的问题:如果像素的中心正好位于三角形的边上，这时怎么办?在后面将讨论到，有好几种方法来处理这种情况。关键结论是:当我们根据顶点插入颜色时，利用重心坐标可以确定是否该绘制一个像素，以及该像素应是什么颜色。于是问题变为如何能快速找到像素中心的重心坐标(Pineda，1988)。蛮力光栅化算法如下:

算法的其余部分把外部循环限制到更小的候选像素集，使重心计算快速有效。寻找三顶点的包围矩形，只对该矩形内的候选像素执行循环，这样就能提高算法的效率。计算重心坐标。于是算法变为:

其中 $f_{ij}$ 是根据适当顶点，可以得出直线：

注意我们用判断条件 a>0代替了 α∈(0,1)。原因是，考虑到 $\alpha$ + $\beta$ + $\gamma$ =1，那么如果 $\alpha$ 、 $\beta$ 、 $\gamma$ 都是正的，它们必然都小于1。同样，我们可以只算出三个重心坐标中的两个，然后利用它们的这种关系计算另一个。和绘制直线的算法类似，这时的算法也可以是增量算法，但不清楚能否降低计算量。每次计算 $\alpha$ 、 $\beta$ 、 $\gamma$ ，也就是计算f(x,y)=Ax+By+C的值。在内部循环中，只有x变化，每次变化1。要注意f(x+1,y)=f(x,y)+4，这是增量算法的基础。在外部循环中，由计算f(x,y)变成计算f(x,y+1)，因此计算效率类似。由于在循环中 $\alpha$ 、 $\beta$ 、 $\gamma$ 的变化增量是固定的，颜色c的变化也一样，因此该算法也可以变为增量算法。例如，像素(x,y)到像素(x+1,y)的红色值改变量，可以设为预先计算出的一个常量。三角形颜色插值的实例见图

处理三角形边上的像素

我们还没有讨论如何处理那些中心位于三角形边上的像素。如果一个像素正好落在三角形的边上,那么它同时还位于相邻三角形的边上。没有明确的方式来确定该像素到底属于哪个三角形。最坏的决定就是不绘制该像素，这时两个三角形之间就会出现一个空隙。如果在两个三角形上都绘制该像素，情况相对会好一点，但仍然不是个好办法。如果三角形是透明的，会造成重复绘制。我们确实想把这样的像素点归于其中的一个三角形，并希望这是个简单过程。只要做好选择，无
论选定哪个三角形都没有关系。应该注意到，屏幕外的任何点肯定位于要绘制的公共边的一侧。对两个互不重看的三角形来说，不在公共边上的顶点位于公共边的相对两侧。这些顶点中正好有一个与屏幕外的点处在同一侧(如下图)。这个常识是做判断的基础。判断p与q是否同号，可以通过判断pq>0是否成立来实现，这种方法在多数情况下都是行之有效的方法。

注意这种判断方法不是完美的，因为通过三角形边的直线也许会正好通过屏幕外的那一点，但至少我们缩小了考虑范围。选用屏幕外的哪一点是任意的，较好的选择是(x,y)=(-1，-1)。需要对那些正好位于边上的点进行核查，但对于完全在内部或者完全在外部的一般情况不应核查。所以有：

当对两个三角形使用同样的直线方程时，我们会希望上面的代码能够消除空隙和重复绘制。实际上，在调用三角形绘制函数时，只有当两个公共顶点的顺序是一样时，直线方程才是一样的。否则直线方程的符号就不同。这个问题取决于编译器是否改变操作的顺序。因此，如果想使算法稳健，应明白编译器以及算术单元的细节。上面伪码的前4行需要认真考虑，用以处理三角形的边正好过像素中心的情况。
除了能把代码改为增量形式外，还存在一些提前退出的可能。例如，如果是负的，那么就不必计算B或者v了。显然这样做能够提高运算速度，对程序进行改进总是值得提倡的。额外的分支对流水操作和并行处理不利，而且会降低代码的运行速度。所以，对于关键部分的代码，应该尝试各种优化方法。

以上代码的另一个细节是，对于退化三角形，即 $f_{y} = 0$ 情况，上面的代码可能会出现除数为0的现象。为了解决这个问题，应采用浮点误差条件，或者增加其他判断方式。

7.简单的反走样技术

前面讲过的直线绘制和三角形绘制算法，普遍存在锯齿现象。如果允许像素值变低或变高些(Crow，1978)，则可以减轻这种视觉上的不足。例如，对于白色背景上的一个黑色三角形如果一个像素的中心几乎位于该三角形的内部，则可以将该像素设为黑白之间的颜色。图1中上面的那条直线就是按这种方法绘出的。在实际应用中，这种模糊化处理可以改进视觉效果，尤
其是在动画制作中。构造“无锯齿”图像的最直接方法就是采用盒式滤波器，将像素设置为盒式区域的平均颜色值。这就意味着，要把所有可绘制的实体都看作已经明确定义的区域。例如，图2中的直线段就是一个矩形。第4章中讨论更复杂的模糊化技术，这些技术可以改善外观质量。像中点算法产生的锯齿状直线这样的现象，是走样(aliasing)造成的结果，该术语来自信号处理。因此，通过认真选择像素值来避免锯齿现象的技术，称为反走样(antialiasing)技术。盒式滤波器可以满足多数情况的需要，适用于对视觉质量要求不是特别高的场合。

实现盒式滤波器反走样的最容易办法是，先建立高分辨率图像，然后进行下采样。例如，我们要处理一幅256x256的图像，其中的直线宽度为1.2个像素。可以在1024x1024的屏幕上，对宽为4.8像素的直线段构成的矩形区域进行光栅化处理，然后对像素进行4x4平均，得到256x256的压缩图像。这是对实际图像的近似盒式滤波，如果目标相对于像素间距不是特别小的话，这种方法的效果还是非常好的。