计算机图形学笔记------直线的扫描转换
目的
在数字设备上绘制一条直线，其过程为给定直线的起点和终点，在光栅显示器的二维点阵中确定一组点最佳逼近所给直线。
绘制直线的本质是确定点序列。
数值微分法（DDA）
算法原理
直线的一阶导数连续，对应微分增量成比例，可以使用当前位置
(
x
i
,
y
i
)
(x_i,y_i)
(xi,yi)分别加上两个小增量
ε
∗
Δ
x
varepsilon*Delta x
ε∗Δx与
ε
∗
Δ
y
varepsilon*Delta y
ε∗Δy即可求出相应的
(
x
i
+
1
,
y
i
+
1
)
(x_{i+1},y_{i+1})
(xi+1,yi+1)（
ε
varepsilon
ε取值极小），即：
y
i
+
1
=
y
i
+
ε
∗
Δ
y
y_{i+1}=y_i+varepsilon*Delta y
yi+1=yi+ε∗Δy
x
i
+
1
=
x
i
+
ε
∗
Δ
x
x_{i+1}=x_i+varepsilon*Delta x
xi+1=xi+ε∗Δx
相应的直线的斜率为：
d
y
d
x
=
Δ
y
Δ
x
=
Y
1
−
Y
0
X
1
−
X
0
=
k
frac{dy}{dx}=frac{Delta y}{Delta x}=frac{Y_1-Y_0}{X_1-X_0}=k
dxdy=ΔxΔy=X1−X0Y1−Y0=k
近似拟合
由于在实际的机器中我们无法实现那么高的精度，所以我们选择
ε
=
1
m
a
x
(
∣
Δ
x
∣
,
∣
Δ
y
∣
)
varepsilon=frac{1}{max(|Delta x|,|Delta y|)}
ε=max(∣Δx∣,∣Δy∣)1，将对应的
ε
∗
Δ
x
varepsilon*Delta x
ε∗Δx或
ε
∗
Δ
y
varepsilon*Delta y
ε∗Δy变为单位步长，对应有不同斜率有两种情况：
一种情况为：
m
a
x
(
∣
Δ
x
∣
,
∣
Δ
y
∣
)
=
∣
Δ
x
∣
max(|Delta x|,|Delta y|)=|Delta x|
max(∣Δx∣,∣Δy∣)=∣Δx∣，即
∣
k
∣
<
=
1
|k|<=1
∣k∣<=1。
y
i
+
1
=
y
i
+
ε
∗
Δ
y
=
y
i
+
1
∣
Δ
x
∣
∗
Δ
y
=
y
i
±
k
y_{i+1}=y_i+varepsilon*Delta y=y_i+frac{1}{|Delta x|}*Delta y=y_ipm k
yi+1=yi+ε∗Δy=yi+∣Δx∣1∗Δy=yi±k
x
i
+
1
=
x
i
+
ε
∗
Δ
x
=
x
i
+
1
∣
Δ
x
∣
∗
Δ
x
=
x
i
±
1
x_{i+1}=x_i+varepsilon*Delta x=x_i+frac{1}{|Delta x|}*Delta x=x_ipm 1
xi+1=xi+ε∗Δx=xi+∣Δx∣1∗Δx=xi±1
另一种情况为：
m
a
x
(
∣
Δ
x
∣
,
∣
Δ
y
∣
)
=
∣
Δ
y
∣
max(|Delta x|,|Delta y|)=|Delta y|
max(∣Δx∣,∣Δy∣)=∣Δy∣，即
∣
k
∣
>
=
1
|k|>=1
∣k∣>=1。
y
i
+
1
=
y
i
+
ε
∗
Δ
y
=
y
i
+
1
∣
Δ
y
∣
∗
Δ
y
=
y
i
±
1
y_{i+1}=y_i+varepsilon*Delta y=y_i+frac{1}{|Delta y|}*Delta y=y_ipm 1
yi+1=yi+ε∗Δy=yi+∣Δy∣1∗Δy=yi±1
x
i
+
1
=
x
i
+
ε
∗
Δ
x
=
x
i
+
1
∣
Δ
y
∣
∗
Δ
x
=
x
i
±
1
k
x_{i+1}=x_i+varepsilon*Delta x=x_i+frac{1}{|Delta y|}*Delta x=x_ipm frac{1}{k}
xi+1=xi+ε∗Δx=xi+∣Δy∣1∗Δx=xi±k1
由于在绘制时设备无法绘制半个像素，所以需要对x，y进行四舍五入取整，实现为：
x
i
=
(
i
n
t
)
(
x
i
+
0.5
)
x_i=(int)(x_i+0.5)
xi=(int)(xi+0.5)，
y
i
=
(
i
n
t
)
(
y
i
+
0.5
)
y_i=(int)(y_i+0.5)
yi=(int)(yi+0.5)
代码实现
void DDA(int x0,int x1,int y0,int y1)
{
int dx.dy,epsl,k;
float x,y,xIncre,yIncre;
dx=x1-x0;
dy=y1-y0;
x=x0;
y=y0;
if(abs(dx)>abs(dy)){//对应|k|与1比较
epsl=abs(dx);
}else{
epsl=abs(dy);
}
xIncre=(float)dx/(float)epsl;
yIncre=(float)dy/(float)epsl;
for(k=0;k<=epsl;k++){
drawPixel((int)(x+0.5),(int)(y+0.5));
x+=xIncre;
y+=yIncre;
}
}
在迭代中，对应新的x，y的值都是以前一步的值加上一个增量获得的，对应代码中的x+=xIncre与y+=yIncre，这种表示的算法为一个增量算法。算法简单，易于实现。
评价
优点：算法直观，易于实现。
缺点：涉及浮点数运算，不利于硬件实现。
中点Bresenham算法
算法原理
对于相应直线的斜率有：
Δ
y
Δ
x
=
Y
1
−
Y
0
X
1
−
X
0
=
k
frac{Delta y}{Delta x}=frac{Y_1-Y_0}{X_1-X_0}=k
ΔxΔy=X1−X0Y1−Y0=k
直线方程有
f
(
x
,
y
)
=
y
−
k
x
−
b
f(x,y)=y-kx-b
f(x,y)=y−kx−b
相应的在图像上可以将平面划分为三个部分，分别为
f
(
x
,
y
)
=
0
,
f
(
x
,
y
)
>
0
,
f
(
x
,
y
)
<
0
f(x,y)=0,f(x,y)>0,f(x,y)<0
f(x,y)=0,f(x,y)>0,f(x,y)<0
这里我们仅考虑
0
<
k
<
1
0<k<1
0<k<1的情况，所以对于x方向的增量(增量取1)，产生的y只有两个可能的点(x+1，y)，或者(x+1,y+1)，我们以两点之间的中点来进行评判，即(x+1,y+0.5)。对于实际的直线f(x,y),我们将中点带入有：d=f(x+1,y+0.5)，如果其值大于0，说明对应直线在中点下方，所以应该取(x+1，y)，若值小于0，说明对应直线在中点上方，所以应该取(x+1，y+1)，即：
y
=
y
+
1
(
d
<
0
)
y=y+1 (d<0)
y=y+1(d<0)
y
=
y
(
d
≥
0
)
y=y (d geq 0)
y=y(d≥0)
误差迭代
对于相应产生误差d，根据之前产生的误差的取值有两种取值方式：
当d小于0时，上次对应取的点为f(x+1,y+1)，所以这次我们判断的中点为f(x+2,y+1.5)。
对应的结果为
d
i
+
1
=
f
(
x
+
2
,
y
+
1.5
)
=
y
+
1.5
−
k
(
x
+
2
)
−
b
=
y
+
0.5
−
k
(
x
+
1
)
−
b
−
k
=
d
i
−
k
+
1
d_{i+1}=f(x+2,y+1.5)=y+1.5-k(x+2)-b=y+0.5-k(x+1)-b-k=d_i-k+1
di+1=f(x+2,y+1.5)=y+1.5−k(x+2)−b=y+0.5−k(x+1)−b−k=di−k+1
对应误差的增量为
1
−
k
1-k
1−k
当d大于0时，上次对应取的点为f(x+1,y)，所以这次我们判断的中点为f(x+2,y+0.5)。
对应的结果为
d
i
+
1
=
f
(
x
+
2
,
y
+
0.5
)
=
y
+
0.5
−
k
(
x
+
2
)
−
b
=
y
+
0.5
−
k
(
x
+
1
)
−
b
−
k
=
d
i
−
k
d_{i+1}=f(x+2,y+0.5)=y+0.5-k(x+2)-b=y+0.5-k(x+1)-b-k=d_i-k
di+1=f(x+2,y+0.5)=y+0.5−k(x+2)−b=y+0.5−k(x+1)−b−k=di−k
对应误差的增量为
−
k
-k
−k
误差的初值为对应(x,y)取
(
x
0
,
y
0
)
(x_0,y_0)
(x0,y0),中点为
(
x
0
+
1
,
y
0
+
0.5
)
(x_0+1,y_0+0.5)
(x0+1,y0+0.5)，
d
0
=
f
(
x
0
+
1
,
y
0
+
0.5
)
d_{0}=f(x_0+1,y_0+0.5)
d0=f(x0+1,y0+0.5)
对应
f
(
x
0
,
y
0
)
=
0
=
y
0
−
k
x
0
−
b
f(x_0,y_0)=0=y_0-kx_0-b
f(x0,y0)=0=y0−kx0−b，所以有
d
0
=
0.5
−
k
d_0=0.5-k
d0=0.5−k
展开一下有
d
0
=
0.5
−
Δ
y
Δ
x
d_0=0.5-frac{Delta y}{Delta x}
d0=0.5−ΔxΔy，即为
2
Δ
x
d
0
=
Δ
x
−
2
Δ
y
2Delta xd_0=Delta x-2Delta y
2Δxd0=Δx−2Δy
将相应的
d
0
=
2
Δ
x
d
0
d_0=2Delta xd_0
d0=2Δxd0，对应的增量也对应乘以
2
Δ
x
2Delta x
2Δx为
−
k
∗
2
Δ
x
=
−
2
Δ
y
-k*2Delta x=-2Delta y
−k∗2Δx=−2Δy与
(
1
−
k
)
∗
2
Δ
x
=
2
Δ
x
−
2
Δ
y
(1-k)*2Delta x=2Delta x-2Delta y
(1−k)∗2Δx=2Δx−2Δy
代码实现
void MidBresenham(int x0,int x1,int y0,int y1){
int dx,dy,d,UpIncre,DownIncre,x,y;
if(x0>x1){
x=x1;
x1=x0;
x0=x;
y=y1;
y1=y0;
y0=y;
}
x=x0;
y=y0;
dx=x1-x0;
dy=y1-y0;
d=dx-2*dy;
UpIncre=2*dx-2*dy;
DownIncre=(-2)*dy;
while(x<=x1){
drawPixel(x,y);
x++;
if(d<0){
y++;
d+=UpIncre;
}else{
d+=DownIncre;
}
}
}
对应 k > 1 k>1 k>1时将对应的x与y互换即可，如果斜率为负值，将对应其中一个坐标改增量为减即可，其余的操作均是相同的。同时避免了除法运算的问题。