前言

前文更新了渲染管线中MVP变换矩阵以及视口变换的算法，今天的内容就是光栅化阶段的算法了。

 

光栅化

在进入具体的光栅化算法之前，首先需要知道光栅化是一个什么样的过程。

简单来说光栅化的目的就是将想要展现的物体给真正显示到屏幕上的过程，因为我们的物体其实都是用一个个顶点数据来表示的，如何将这些蕴含几何信息的数据转化为屏幕上的像素就是光栅化所考虑的东西。

比如说一条直线，究竟该用哪些像素点去逼近它，一个三角形，又用哪些像素集合表示它，这都是光栅化的过程。

本节主要介绍两个直线光栅化和一个三角形光栅化算法。

 

屏幕像素的表示

屏幕中的每一个像素点都用起始为0的整数坐标进行表示，最大值为分辨率-1，考虑到每个像素都有一定的面积，因此定义(x+0.5,y+0.5)为该(x,y)像素的中心，屏幕空间的范围则是[0~Width,0~Height]，如图中黑点所示。

至于如何从MVP变换矩阵后的[-1, 1]的立方体区域投射到整个屏幕的范围，可以查看前文中的视口变换部分。

 

直线光栅化算法之DDA数值微分算法

DDA算法是一个非常简单直观的算法。 首先数学上当任何一条直线知道都可以用y = kx + b来表示，其中k代表斜率。

如果|k| < 1，那么它的主要行进方向就是x轴，即x轴的变化要比y轴快，相反如果如果|k| > 1，那么它的主要行进方向就是y轴，即y轴的变化要比x轴快。如下图所示：

分别就图上两种情况进行考虑(假设起点与终点给定，确定了直线方程，就像图中一样)

1 当|k| < 1时，从起点开始画起每次x = x+1， y = y+k, 并将y四舍五入，得到新的x，y就是像素点应该画的地方

2 当|k| > 1时，从起点开始画起每次y = y+1， x = x+1/k, 并将x四舍五入，得到新的x，y就是像素点应该画的地方

 

直线光栅化算法之中点Bresenham算法

首先规定需要光栅化的线段的起点P0(x0,y0)与终点P1(x1,y1),则该直线方程可以用y = kx + b的形式来表示，定义(x,y) = y – kx – b, 接下来一起看看bresenham算法的具体过程。

中点Bresenham算法的思想其实也比较简单，在这里只给出0 < k < 1 的情况，其它情况可以类推，除却起点与终点，每次的画点只会考虑右边或者右上的点两种情况(由斜率所决定的)，因此只需要在这二者之间做出选择。
那么该依据什么进行判断呢，给出如下两种情况。

我们已经成功画出了前三个蓝色方格之后，所要考虑的便是第三个蓝色方格右边或者右上的橙色方格，此时我们取这两个橙色方格的中点，如图中圆圈符号所对应的那个点，倘若这个点在直线方程的下面，那么很明显我们应该选择右上的方格。

此时中点位于直线方程的上方，此时选择右边的橙色方格。

至此，如何判断两种方格选择的条件已很明显，就是确定中点与直线的位置关系，这里就可以使用到一开始定义的(x,y) = y – kx – b的方程了。

显然，当f(x+1,y+0.5) > 0的时候中点在直线上方，当f(x+1,y+0.5) < 0的时候中点在直线下方 （其中x+1，y+0.5是为了表示两个橙色方格的中点，此时x，y为前一个确定的像素坐标）

伪代码如下：

其中的，some condition也就很明显的是

目前为止，算法整体便已完成，但有一个问题是，每次都要进行一次F（x，y）的计算，倘若直线方程比较复杂，这是很消耗资源的(因为在底层可能是几百万次的重复调用)。因此一种改进方法便是利用增量算法。不难具体算出f(x,y)方程具体如下：

观察可以得出

那么算法只需要算出第一次的 f(x+1,y+0.5) ，之后的每次只需根据上述式子进行相应增量计算即可，如下：

当然中点bresenham算法其实还在这之上进一步做了一步优化，因为第一个d其中存在浮点数0.5,所以将有关d的等式两边都乘以2，消除了该0.5的浮点，增加了计算效率。

 

三角形的光栅化算法

三角形是最基本的多边形，大部分的模型都是用一个个三角形面表示，且任意的其它多边形其实都可以转化成多个三角形的形式，因此三角形的光栅化可以说是图形学中最基础的部分了。

那么该怎么在屏幕上绘制三角形呢？

有一个非常直观的做法，像上图这样，对屏幕中的每一个像素进行计算，如果这个像素点在三角形之中那么这个像素点就应该被采用！

那么该如何去判断一个点在不在三角形内部呢，那么其中一种办法就是利用叉乘的性质了。

如图所示，事先知道需要光栅化的三角形的三个顶点P0，P1，P2，以及检测点Q。 只要分别计算 P0P1 X P0Q，P1P2 X P1Q，P2P0 X P2Q，如果三者同号则代表点P在三条线段的同一边，那么必然处于三角形内部，如果不同号则代表该点一定在三角形外部！

因此自然的，只需要遍历每一个点就可以得出三角形的光栅化结果了。

当然还可以进一步的进行优化，因为显然并没有必要去测试屏幕中的每一个点，一个三角形面可能只占屏幕很小的部分，可以利用一个bouding box 包围住想要测试的三角形，只对该bounding box内的点进行采样测试，如下图：

这样就可以得到很大的效率提升了。

在三角形形状比较极端的情况下，甚至可以让每一行都找其对应的最左和最右，这样一个像素都不会多考虑，相当于每一行都有一个包围盒。

另外，在大量计算时难免会遇到Q点正好位于三角形边上的情况，这时只要自己定义一个标准合理就好，例如用屏幕外一点判断该点是否在公共边某一侧的方法进行判断（在OpenGL和DirextX上，规定左边和上边算三角形内，右边和下边不算）。

 

本文转载自孙晓磊的计算机图形学系列笔记，有所修改，感谢。

我们从小到现在被各种谎言灌满了，
当他成熟起来的第一个标志就是他要呕吐，
重新用理性去认识世界。

——罗曼·罗兰