三种直线段的扫描转换算法

直线段的扫描转换算法

确定最佳逼近于直线的一组象素，且按扫描线顺序，对这些象素进行写操作

三个常用算法：

• 数值微分法（DDA）
• 中点画线法
• Bresenham算法

数值微分法

基本思想

知道了两个端点$P_0(x_0,y_0),P_1(x_1,y_1)$，则可以求出直线段的斜率$k$，根据公式$y=kx+b$来计算响应y点的坐标，取像素点 $(x,(\text{round}(y)))$ 为当前点的坐标

评价：方法直观，效率低

增量算法

在一个迭代算法中，每一步的x，y值使用前一步的值加上一个增量来获得

计算 $y_{i+1}=y_i+k\Delta x$，当$\Delta x=1$时，$y_{i+1}=y_i+k$

即：当x每递增1，y递增k（即直线斜率）

• 由此注意上述分析的算法仅适用于|k| ≤1的情形。在这种情况下，x每增加1，y最多增加1
• 当 |k| >1时，必须把x，y位置互换

void DDALine(int x0,int y0,int x1,int y1,int color)     
{
    int x；							
	float dx, dy, y, k;						
	dx= x1-x0, dy=y1-y0;					   
	k=dy/dx, y=y0;	 					   
	for (x=x0; x<=x1, x++)					   
    {  drawpixel (x, int(y+0.5), color);		   
	   y=y+k;
    }
}
1
2
3
4
5
6
7
8
9
10
11

例子

注意这里额外加了0.5，就可以省掉round运算了

中点画线法

基本思想

设当前像素点为$(x_p,y_p)$，下一个像素点为右侧$P_1$或右上角$P_2$两个点中的一个，设$M=(x_p+1,y_p+0.5)$为$P_1,P_2$的中点，Q为理想直线与$x=x_p+1$垂线的交点。将Q与M的y坐标值进行比较

• 当M在Q点的下方，则右上角的$P_2$为下一个像素点
• 当M在Q点的上方，则右侧的$P_1$为下一个像素点

构造判别式：
d = F ( M ) = F ( x p + 1 , y p + 0.5 ) = a ( x p + 1 ) + b ( y p + 0.5 ) + c

$$\begin{aligned} d=F(M)&=F(x_p+1,y_p+0.5)\\ &=a(x_p+1)+b(y_p+0.5)+c \end{aligned}$$ d=F(M)​=F(xp​+1,yp​+0.5)=a(xp​+1)+b(yp​+0.5)+c​
其中$a=y_0-y_1,b=x_1-x_0,c=x_0{y}_1-x_1{y}_0$

• 当d<0，M在L(Q点)下方，取右上方$P_2$为下一个象素
• 当d>0，M在L(Q点)上方，取右侧$P_1$为下一个象素
• 当d=0，选$P_1$或$P_2$均可，约定取$P_1$为下一个象素

增量算法

d是$x_p,y_p$的线性函数，因此可以采取增量计算，提高运算效率

• 若当前像素处于$d\ge 0$的情况，则去右侧像素$P_1(x_p+1,y_p)$，要判断下一个像素位置，应计算

  $d_1=F(x_p+2,y_p+0.5)=a(x_p+2)+b(y_p+0.5)=d+a$；增量为a

• 若$d<0$时，则要取右上方像素$P_2(x_o+1,y_p+1)$，要判断下一个像素，应计算

  $d_2= F(x_p+2, y_p+1.5)=a(x_p+2)+b(y_p+1.5)+c=d+a+b $；增量为$a+b$

具体算法：

• 画线从$(x_0,y_0)$开始，d的初值

  $d_0=F(x_0+1,y_0+0.5)=F(x_0,y_0)+a+0.5b=a+0.5b$

  $a=y_0-y_1,b=x_1-x_0$

• 可以使用2d代替d来摆脱小数，提高运算效率

• 令$d_0=2a+b,d_1=2a,d_2=2a+2b$，我们有如下算法

void Midpoint Line (int x0,int y0,int x1, int y1,int color)
{   int a, b, d1, d2, d, x, y;
    a=y0-y1, b=x1-x0, d=2*a+b;
    d1=2*a, d2=2* (a+b);
    x=x0, y=y0;
    drawpixel(x, y, color);
    while (x<x1){
     	if (d<0){
            // d<0,应该加增量a+b，这里是d2
            x++, y++, d+=d2;
    	}else {
            // d>=0 应该加增量a，这里是d1
     		x++, d+=d1;
        }
     	drawpixel (x, y, color);
    }  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

例子

先计算$d_0,d_1,d_2$，然后写成左下角的形式

1. 假设从0,0开始，当前d大于0，因此应该加d1得到第二步的d，且y不自增
2. 到第二步，当前d小于0，应该加d2得到第三步的d，且y要加一
3. 到第三步，当前d大于0，应该加d1得到第四步的d，且y不自增，
4. 重复下去直到最后一个点

Bresenham算法

基本思想

设直线方程为$y_{i+1}=y_i+k(x_{i+1}-x_i)=y_i+k$，其中$k=dy/dx$，因为直线的起始点在像素中心，所以误差项d的初值d0=0

X的下标每增加1，d的值相应递增直线的斜率k，即d=d+k。一旦$d\ge 0.5$，就把他减去1

• 当$d\ge 0.5$时，最接近于当前像素的右上方像素$(x_{i+1},y_{p+1})$
• 当$d<0.5$时，更接近于右侧的像素$(x_{i+1},y_i)$

为了方便计算，令$e=d-0.5$，e的初值为-0.5，增量为k（这样比较时候直接与0比较即可）

• 当$e\ge 0$时，最接近于当前像素的右上方像素$(x_{i+1},y_{p+1})$
• 当$e<0$时，更接近于右侧的像素$(x_{i+1},y_i)$

void Bresenhamline (int x0,int y0,int x1, int y1,int color)
{   int x, y, dx, dy;
    float k, e;
    dx = x1-x0, dy = y1- y0, k=dy/dx; 
    e=-0.5, x=x0, y=y0;
    for (i=0; idx; i++){
        drawpixel (x, y, color);
        x=x+1，e=e+k;
        if (e>=0){ 
        	y++, e=e-1;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

例题

首先计算出斜率k，然后写成左下角的形式

1. 第一步从p0出发，当前e小于0，因此y不自增，e+=0.4
2. 第二步：当前e小于0，因此y不自增，e+=0.4
3. 第三步：当前e大于0，因此y自增，e= e + 0.4 - 1
4. 后面一直这样计算下去，注意当e大于0时不止要减1还要再加0.4

总结

• DDA方法：根据直线方程$X\to Y$
• 其他两种的原理：$0<K<1$时，下一个像素只能是当前像素的右侧点或者右上方点
  • 中点画线法：将中点坐标代入方程得到判别式，然后根据判别式的结果确定下一次的y是在右侧还是右上方
  • Bresenham算法：计算误差项，从0开始，每次增加k，然后判断是否大于0.5，后面化成e，只需要判断是否大于0即可