计算机图形学（一）中点画线法

中点画线是比较基础的画线法，重点是确定递推公式。

中点画线法

基本推导

假设直线的斜率在0、1之间,假设x坐标为 $x_p$ 的各像素点中，与直线最近者已经确定为 $P(x_p,y_p)$ 。那么，下一个与直线最近的像素只能是正右方的 $P_1(x_p+1,y_p)$，或者右上方的 $P_2(x_p+1,y_p+1)$ 两者其中之一。

令 $M$ 为 $P_1$ 和 $P_2$ 的中点，易知 $M$ 的坐标为 $(x_p+1,y_p+0.5)$ 。

设 $Q$ 为理想直线与垂直线 $x=x_p+1$ 的交点。

显然，若 $M$ 在 $Q$ 的下方，则 $P_2$ 离直线更近，应该作为下一个像素；否则就应该取 $P_1$ 。

假设直线的起点和终点分别是 $(x_0, y_0)$ 和 $(x_1,y_1)$ 。则直线方程为：

$F(x,y)=ax+by+c=0$

其中

$a=y_0-y_1$ $b=x_1-x_0$ $c=x_0y_1-x_1y_0$

该直线方程将平面分为三个区域：
对于直线上的点，$F(x,y)=0$ ；
对于直线上方的点，$F(x,y)>0$；
对于直线下方的点，$F(x,y)<0$。

此时我们将 $M$ 点带进直线方程，通过判断代入方程的结果的正负，即可判断 $M$ 点是在直线方程上方还是下方。

即判别式 $d=F(M)=F(x_p+1,y_p+0.5)=a(x_p+1)+b(y_p+0.5)+c$

此时，我们就有了对 $y$ 的更新方法

$y=\left\{\begin{array}{lcl} y+1 &{d<0}\\ y &{d \geq 0} \end{array} \right.$

当 $d<0$ 时，说明 $M$ 点在直线的下方，那么直线离 $P_2(x_p+1,y_p+1)$ 点更近，所以下一个逼近于直线的点应该取 $P_2(x_p+1,y_p+1)$，即 $y=y+1$ ，反之，当 $d>0$ 时，说明 $M$ 点在直线的上方，那么直线离 $P_1(x_p+1,y_p)$ 点更近，所以下一个逼近于直线的点应该取 $P_1$ ，即 $y$ 不变。当 $d=0$ 时说明 M 点在直线上，那么取 $P_1(x_p+1,y_p)$ 或 $P_2(x_p+1,y_p+1)$ 皆可。由于假设 $|k|<1$ ，所以 $x$ 每次都增加 1。

递推误差项$d$

因为我们求$d$的时候用了乘法以及浮点数，所以对于计算机而言，硬件开销大，为此我们要想办法找到递归的方法来求$d$。

当 $d\geq0$时：

由上面的结论我们知道，此时我们取的点是$P_1(x_p+1,y_p)$，而我们要画的下一个点为$P_3(x_p+2,y_p)$，或者$P_4(x_p+2,y_p+1)$。将$P_3(x_p+2,y_p)$与$P_4(x_p+2,y_p+1)$的中点$M(x_p+2,y_p+0.5)$带入直线方程$(x,y)=ax+by+c=0$中可以得到

$d_1=F(x_p+2,y_p+0.5)=a(x_p+2)+b(y_p+0.5)+c=a(x_p+1)+b(y_p+0.5)+c+a=d+a$

此时，$d$的增量为$a$。

当$d<0$时：

由上面的结论我们知道，此时我们取的点是$P_2(x_p+1,y_p+1)$，而我们要画的下一个点为$P_4(x_p+2,y_p+1)$，或者$P_5(x_p+2,y_p+2)$。将$P_4(x_p+2,y_p+1)$与$P_5(x_p+2,y_p+2)$的中点$M(x_p+2,y_p+1.5)$带入直线方程$(x,y)=ax+by+c=0$中可以得到

$d_1=F(x_p+2,y_p+1.5)=a(x_p+2)+b(y_p+1.5)+c=a(x_p+1)+b(y_p+0.5)+c+a+b=d+a+b$

此时，$d$的增量为$a+b$。

至此，我们对$d$的递推关系便找到了

$d_n=\left\{\begin{array}{lcl} d_{n-1}+a+b &{d<0}\\ d_{n-1}+a &{d \geq 0} \end{array} \right.$

中点画线算法公式

现在我们可以找到当$|k|<1$时的中点画线算法了

（1） 输入直线的起始和终止端点 $P_0 (x_0 ,y_0)$和 $P_1 (x_1 ,y_1)$；

（2） 计算初始值$a= y_0 - y_1 ,b= x_1 - x_0 ,c= x_0 y_1 - x_1 y_0 ,d=a+0.5*b,x=x_0 ,y=y_0$

（3） 绘制点$(x,y)$；

（4） 判断 $d$ 的符号。若$d<0$，则$(x,y)$更新为$(x+1,y+1)$，$d$ 更新为 $d+a+b$；否则$(x,y)$更新为$(x+1,y)$，$d$ 更新为 $d+a$；

（5） 当直线没有绘制完成时，跳转到步骤（3）执行，否则算法结束。

优化中点画线算法

对于上面的算法，在步骤（2）中有浮点运算，不利于硬件实现，因此我们需要对之进行改进。由于 $d$ 只是用来判断正负用的，因此我们用 $2d$ 来代替 $d$ 并不会影响算法的执行结
果。用 $2d$ 代替 $d$ 的新算法如下所示：
（1） 输入直线的起始和终止端点 $P_0 (x_0 ,y_0 )$和 $P_1 (x_1 ,y_1)$；
（2） 计算初始值$a= y_0 - y_1 ,b= x_1 - x_0 ,c= x_0 y_1 - x_1 y_0 ,d=2*a+b,x=x_0 ,y=y_0 ,d_1=2*a, d_2=2*(a+b)$；
（3） 绘制点$(x,y)$；
（4） 判断 $d$ 的符号。若$d<0$，则$(x,y)$更新为$(x+1,y+1)$，$d$ 更新为 $d+d_2$；否则$(x,y)$更新为$(x+1,y)$，$d$ 更新为 $d+d_1$；
（5） 当直线没有绘制完成时，跳转到步骤（3）执行，否则算法结束。

总结

通过上面的分析可知，中点画线算法的基本思想就是借助一个决策变量 $d$ 的正负符号，
来确定下一个该点亮的像素点。中点画线算法有很多优点，如下所示。
（1） 不必计算直线的斜率，因此不必除法运算；
（2） 不用浮点数，只用整数；
（3） 只有加法和乘 2 运算，在计算机内部用位移操作实现即可，因此效率很高。
正因为中点画线算法有上述优点，因此其运算速度很快，利于硬件实现。