Creator_Chen's Dream Island

给定一条直线，如何在光栅上将这条直线画出来？解决这个问题最直接的想法就是将光栅上离该直线最近的像素标记出来，这样会得到一个像素集合，这个像素集合就是这条直线的光栅化结果。但是，如何确定离直线最近的像素呢？考虑这样一条直线AB，其斜率在区间(0, 1)内，宽度为1（如下图所示）。

网格代表显示器光栅，为了方便说明，假设横线与竖线的交点为光栅上的像素（实际上像素位于每个小方格的中心，不过这应该不影响算法的推导），红色的实心圆就是直线AB的光栅化结果。对于这样的直线，我们不难发现一个事实，即光栅上每一列只有一个像素被选定。假设我们现在正处于直线的光栅化算法过程中，并假设算法的当前步选中了像素P，那么算法的下一步将从像素E和像素NE中选择一个作为该步的光栅化结果。如何决定选择E还是NE其实很简单，只须判断E与NE连线的中点M跟直线AB的关系即可。如果M位于直线AB的上方，那么显然像素E离直线AB更近，这时就选择E作为这一步的光栅化结果。反之如果M位于直线的下方，则选择NE.如果M恰好位于直线AB上，那么E与NE只须任选一个。如何判断M与直线AB的关系？设直线AB的一般式方程为a * x + b * y + c = 0，令F(x, y) = a * x + b * y + c，则2D直角坐标系中任意一点P(x_p, y_p)与直线AB有如下三种关系：

• 当F(x_p, y_p) > 0时，如果b < 0，则P位于直线AB下方。如果b > 0，则P位于直线AB上方。
• 当F(x_p, y_p) < 0时，如果b < 0，则P位于直线AB上方。如果b > 0，则P位于直线AB下方。
• 当F(x_p, y_p) = 0时，P刚好位于直线AB上。

可以通过将直线AB的斜截式方程y = (Δy/Δx) * x + b简单的变形来得到上面的a和b（a = Δy，b = -Δx）。

好了，假设E与NE连线的中点M的坐标为(x_m, y_m)，令d = F(x_m, y_m)，现在我们来看看如何根据d的值来选择E或NE，以及选择E或NE时M的坐标以及d的值有何变化。

• 如果d > 0，由于b < 0，所以M在直线AB下方，选择NE。那么算法下一步将从NE右边的像素和NE右上的像素中选择一个，此时M的坐标将由(x_m, y_m)变成(x_m + 1, y_m + 1).则d_new = F(x_m + 1, y_m + 1)，Δd = d_new - d = Δy - Δx.
• 如果d < 0，由于b < 0，所以M在直线AB上方，选择E。那么算法下一步将从E右边的像素和E右上的像素中选择一个，此时M的坐标将由(x_m, y_m)变成(x_m + 1, y_m).则d_new = F(x_m + 1, y_m)，Δd = d_new - d = Δy.
• 如果d = 0，则M刚好位于直线AB上，这时处理过程同d < 0的情况。

通过上面的讨论，可以看到这样一种规律，d的值决定了算法当前步应该选择的像素，选择的像素又决定了算法下一步的d值。稍微整理一下，就得到了直线的中点扫描转换算法：

几个需要注意的问题：

1. 上面算法假设待光栅化的直线斜率在区间(0, 1)内，起始点坐标为(x0, y0)，结束点坐标为(x1, y1)，这些坐标都是整数，且x0 < x1.
2. 对于其他斜率直线的光栅化，可以根据斜率分情况讨论（分析过程和上面类似），也可以利用对称性将其变换成斜率在(0, 1)内的直线进行光栅化。
3. 要小心处理起始点和结束点的顺序。以上面的图为例，从A到B光栅化和从B到A光栅化会得到不同的结果。因为对于直线AB上刚好穿过M的点，我们会选择E作为该点的光栅化结果。然而，对于直线BA上刚好穿过M的点，我们很自然会选择W.显然，要想跟AB光栅化结果一样，这种情况下必须选择SW，而非W.解决这个问题的最简单的办法就是，不管传给光栅化函数的断点顺序如何，我们始终以AB为顺序进行光栅化。
4. 上面算法仅支持整数端点坐标，要想支持浮点数端点坐标，只须在求出DeltaX和DeltaY后将浮点坐标四舍五入成整数坐标，再执行光栅化即可。注意，四舍五入后的坐标所对应的像素，其实是原直线的延长线上某点的光栅化结果。
5. 理论上光栅化直线时像素亮度应该取I/cosθ.其中，I为用户期望的像素亮度值（即传入光栅化函数的亮度值），θ为直线与x轴或y轴的夹角（直线斜率在区间[-1, 1]内时为直线与x轴夹角，否则为直线与y轴夹角）。这样才能使不同直线上单位长度线段的亮度相同。假设上图中的紫色实心圆是直线AB在x轴上投影直线的光栅化结果，显然，直线AB的光栅化结果和它在x轴上投影直线的光栅化结果具有相同的亮度，因为两者具有相同的像素数量。但是，由于直线AB的长度是其投影长度的1/cosθ，所以直线AB单位长度的亮度是其投影直线单位长度亮度的cosθ倍.所以，如果用强度为I的像素对直线AB的投影直线进行光栅化，那么只有用强度为I/cosθ的像素对直线AB进行光栅化，两者才能得到相同的单位长度亮度。但实际实验发现，即使用相同亮度的像素对二者进行光栅化，人眼也几乎观察不到差别。
6. 对于平行于x轴或平行于y轴，以及斜率的绝对值为1的直线，应该作为特殊情况进行特殊处理。