计算机图形学(一)中点画线法

本文最后更新于:2020年3月4日 晚上

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

中点画线法

基本推导

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

MMP1P_1P2P_2 的中点,易知 MM 的坐标为(xp+1,yp+0.5)(x_p+1,y_p+0.5)

QQ 为理想直线与垂直线 x=xp+1x=x_p+1 的交点。

显然,若 MMQQ的下方,则 P2P_2 离直线更近,应该作为下一个像素;否则就应该取P1P_1

图片 1

假设直线的起点和终点分别是 (x0,y0)(x_0, y_0)(x1,y1)(x_1,y_1)。则直线方程为:

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

其中

a=y0y1a=y_0-y_1
b=x1x0b=x_1-x_0
c=x0y1x1y0c=x_0y_1-x_1y_0

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

图片 2

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

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

此时,我们就有了对 yy 的更新方法

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

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

递推误差项dd

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

d0d\geq0时:

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

d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c=a(xp+1)+b(yp+0.5)+c+a=d+ad_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

此时,dd的增量为aa

d<0d<0 时:

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

d1=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=a(xp+1)+b(yp+0.5)+c+a+b=d+a+bd_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

此时,dd的增量为a+ba+b

至此,我们对 dd 的递推关系便找到了

dn={dn1+a+bd<0dn1+ad0 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|k|<1 时的中点画线算法了

(1) 输入直线的起始和终止端点 P0(x0,y0)P_0 (x_0 ,y_0)P1(x1,y1)P_1 (x_1 ,y_1)

(2) 计算初始值a=y0y1b=x1x0c=x0y1x1y0,d=a+0.5b,x=x0,y=y0a= 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)(x,y)

(4) 判断 dd 的符号。若 d<0d<0,则(x,y)(x,y) 更新为 (x+1,y+1)(x+1,y+1)dd 更新为 d+a+bd+a+b;否则(x,y)(x,y) 更新为(x+1,y)(x+1,y)dd 更新为 d+ad+a

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

优化中点画线算法

对于上面的算法,在步骤(2)中有浮点运算,不利于硬件实现,因此我们需要对之进行改进。由于 dd 只是用来判断正负用的,因此我们用 2d2d 来代替 dd 并不会影响算法的执行结
果。用 2d2d 代替 dd 的新算法如下所示:
(1) 输入直线的起始和终止端点 P0(x0,y0)P_0 (x_0 ,y_0)P1(x1,y1)P_1 (x_1 ,y_1)
(2) 计算初始值a=y0y1b=x1x0c=x0y1x1y0,d=2a+b,x=x0,y=y0,d1=2a,d2=2(a+b)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)(x,y)
(4) 判断 dd 的符号。若 d<0d<0,则(x,y)(x,y) 更新为 (x+1,y+1)(x+1,y+1)dd 更新为 d+d2d+d_2;否则(x,y)(x,y) 更新为(x+1,y)(x+1,y)dd 更新为 d+d1d+d_1
(5) 当直线没有绘制完成时,跳转到步骤(3)执行,否则算法结束。

总结

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


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!