3.1 直线图形

在数学上，理想的直线是没有宽度的由无数个点构成的集合。当对直线进行光栅化时，只能在显示器所给定的有限个像素中，确定最佳逼近于该直线的一组像素。用写点方式对像素进行写操作，这就是通常所说的用显示器绘制直线，或直线的扫描转换（见图3-1）。

由于一个图中可以包含成千上万条直线，所以要求绘制算法应尽可能地快。在一些情况下，要绘制1个像素宽的直线；而在另一些情况下，则需要绘制以理想直线为中心线的不同线宽的直线，有时还需要用不同的颜色和线型来画线。

本节将介绍直线的3个常用算法：数值微分法、中点画线法和Bresenham算法，以及直线线宽的处理。

3.1.1 数值微分法

数值微分法（Digital Differental Analyzer，DDA）的本质，是用数值方法解微分方程，即通过同时对x和y各增加一个小增量，计算下一步的x、y值。

1.DDA法的公式推导

为了推导公式方便，将像素间距放大，如图3-2所示。设直线的起点为（xs，ys），终点为（xe，ye），直线的斜率为：

k=Δy/Δx

其中，Δx=xe-xs，Δy=ye-ys。然后，从直线的起点（xs，ys）开始，确定最佳逼近于直线的点坐标（x、y）。设Δx＞Δy＞0，让x从起点到终点变化，每步递增1个像素，计算对应的y坐标。y=kx+b，由于y不一定是整数，用四舍五入方法取整。用这种方法直观可行，然而效率较低。这是因为每步运算都需一个浮点乘法与一个加法运算。可将计算进行简化：

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

这样就可以写出直线扫描转换的数值微分算法：

F(x,y)=y-kx-b=0

当0＜Δx＜Δy时，每步y递增1个像素(yi+1=yi+1)，需计算对应的x坐标：

2.任意方向直线的DDA公式

根据以上公式推导，可将任意方向直线分为以下4类：

3.程序设计

以下为绘制Δx＞Δy＞0方向直线段DDA法的VC程序：

CDC ∗pDC=GetDC（）;        //创建一个屏幕设备环境，GetDC（ ）是CWnd类的成员函数，返回一
                           //个允许用户绘制它的窗口客户区的设备环境
k=（ye-ys）/（xe-xs）;     //（xs，ys）（xe，ye）为直线段的两个端点坐标
y=ys;
for（x=xs;x＜=xe;x++）
{   pDC-＞SetPixel（x，（int）y，RGB（0，0，0））;
    y=y+k;
}

当x0=10，y0=10，x1=150，y1=120时，窗口的坐标原点在左上角，该程序的运行效果如图3-3所示。

在DDA算法中，y与k必须用浮点数表示，这使得它不利于硬件实现。下面将讨论的中点画线法，可以解决这个问题。

3.1.2 中点画线法

1.中点画线法的基本原理

为了讨论方便，假定直线斜率在0～1之间。如图3-4所示，设已确定像素P点与直线最近，坐标为（xp，yp），那么下一个与直线最近的像素只能是正右方的P1（xp+1，yp）或右上方的P2（xp+1，yp+1）两者之一。以M表示P1与P2的中点，即M=（xp+1，yp+0.5）。又设Q是理想直线与垂直线x=xp+1的交点。显然，若M在Q的下方，则P2离直线近，应取P2为下一个像素；若M在Q的上方，应取P1为下一个像素。

2.中点画线法的基本判别式

假设直线的起点和终点分别为（xs，ys）和（xe，ye），则直线方程为

F(x,y)=y-kx-b=0

对于直线上的点，F（x，y）=0；对于直线上方的点，F（x，y）＞0；而对于直线下方的点，F（x，y）＜0。因此，欲判断前述Q在M的上方还是下方，只要把M代入F（x，y），并判断它的符号。构造判别式：

di=F(M)=F(xi+1,yi+0.5)=(yi+0.5)-k(xi+1)-b

当di＜0时，M在直线下方（即在Q的下方），P2更接近理论直线Q，故应取P2作为下一个像素。而当di＞0时，则应取P1。当di=0时，二者一样，可以随便取一个，我们约定取P1。

对每一个像素计算判别式di，根据它的符号确定下一像素。但是计算di有乘法，不利于硬件实现，且运算效率不高。注意到di是xi和yi的线性函数，可采用增量计算，提高运算速度。

3.中点画线法的递推公式

在di≥0的情况下，取正右方像素P1。欲判断下一个像素，如图3-5所示，应计算：

di+1=F(xi+2,yi+0.5)=(yi+0.5)-k(xi+2)-b=di-k

在di＜0的情况下，则取右上方像素P2。要判断下一个像素，如图3-5所示，则要计算：

di+1=F(xi+2,yi+1.5)=(yi+1.5)-k(xi+2)-b=di-k+1

下面计算di的初始值。显然，第1个像素应取（xs，ys），相应的判别式值为：

d0=F(xs+1,ys+0.5)=ys+0.5)-k(xs+1)-b=F(xs，ys)-k+0.5

但由于（xs，ys）在直线上，故F（xs，ys）=0。因此，di的初始值为d0=0.5-k

4.消除小数运算

由于di的计算包含小数，而我们仅需判别di的符号，为了摆脱小数，对上面的判别式两边同时乘2（xe-xs），d0=0.5-k变为：

2(xe -xs) d0=(0.5 -(ye -ys)/ (xe -xs)) 2 (xe -xs) =(xe -xs) -2(ye -ys)

设

D0=2 (xe -xs) d0, d0=xe -xs, d0=xe -xs

则D0=dx-2dy

同理，在di≥0的情况下，di+1=di–k变为：

则

在di＜0的情况下，di+1=di–k+1变为：

则Di+1=Di-2dy+2dx

最后仍将Di用di表示，仅包含整数运算的中点画线算法如下：

x0=y0，ys，dx=xe-xs，dy=ye-ys，d0=dx-2dy

当di≥0时，

xi+1=xi+1，yi+1=yi，di+1=di-2dy

当di＜0时，xi+1=xi+1，yi+1=yi+1，di+1=di-2dy+2dx(i=0,1,2…，dx)

5.程序设计

斜率在0、1之间的第1象限直线的中点法VC主要代码如下：

CDC∗pDC=GetDC（）;
dx=xe-xs; dy=ye-ys; y=ys；
dxx=dx+dx; dyy=dy+dy; d=dx-dyy;
for（x=xs;x＜=xe;x++）
{  pDC-＞SetPixel （x，y，RGB（0，0，0））;
     if（d＜0）
        y=y++，d=d+dxx;
     d=d-dyy;
}

上述算法仅包含整数运算，适合硬件实现。

6.中点画线法绘制直线实例

例3.1 已知直线段的起点为（0，0），终点为（5，2），用中点画线法求出线段各像素坐标值。

解：直线段的起点（第1个像素点）x=0，y=0，dx=5，dy=2，d0=5–2×2=1

d0=1＞0，x=1，y=0，直线段的第2个像素点坐标为（1，0）；

d1=d0-4=-3＜0，x=2，y=1，直线段的第3个像素点坐标为（2，1）；

d2=d1+10-4=3＞0，x=3，y=1，直线段的第4个像素点坐标为（3，1）；

d3=d2-4=-1＜0，x=4，y=2 ，直线段的第5个像素点坐标为（4，2）；

d4=d3+10-4=5＞0，x=5，y=2，直线段的第6个像素点坐标为（5，2）。

该直线的光栅化示意图如图3-6所示。

3.1.3 Bresenham画线算法

Bresenham画线算法是计算机图形学领域中使用最广泛的直线扫描转换算法。该算法最初是为数字绘图仪设计的。由于它也适用于光栅图形显示器，所以后来被广泛用于直线的扫描转换及其他一些应用。为了讨论方便，本节假定直线的斜率在0～1之间，其他情况可类似处理。与中点画线法类似，Bresenham画线算法也是通过在每列像素中确定与理想直线最近的像素来进行直线的扫描转换。

1.算法原理

由于假定直线的斜率在0～1之间，因此在x方向上，每步增加一个单位长度，而y方向是否增加一个单位长根据计算误差项而确定。

如图3-7所示，设（xs，ys）像素已确定，那么下一个像素的x坐标必为xs+1。而y坐标要么不变，要么递增1，是否增1取决于如图3-7所示的误差项d的值。

2.基本判别式

因为直线的起始点在像素点上，所以误差项d的初始值为0。从图3-7中可以看出，x每增加1，d的值相应递增直线的斜率值，即d=d+k(k=dy/dx，dx=xe-xs，dy=ye-ys)。当d≥1时，将d减1，使d始终在0～1之间，因此误差项d的界定为0.5。

当d＞0.5时，直线接近于当前像素（x，y）的右上方像素（x+1，y+1），下一个点取（x+1，y+1），由于y递增1，则相应d要减1，使d始终在0、1之间。

当d＜0.5时，直线接近于像素（x+1，y）；

当d=0.5时，与上述二像素一样接近，约定取（x+1，y+1）。

因此，Bresenham画线算法为：

x0=xs，y0=ys，d0=0，xi+1=xi+1，

当di＜0.5时，di+1=di+k

当di≥0.5时，yi+1di+1=di+k-1 (i=0,1,2…，xe-xs)

3.消除小数运算

先消除判别式di≥0.5的小数。令e=d-0.5，则di≥0.5变为ei≥0，e的初始值为-0.5。Bresenham算法变为：

x0=xs，y0=ys，e0=-0.5，xi+1=xi+1，

当ei＜0时，ei+1=ei+k

当ei≥0时，yi+1ei+1=ei+k-1 (i=0,1,2…，xe-xs)

上述Bresenham画线算法在计算e时，要用到小数与除法，为了便于硬件计算，可以改用整数以避免除法。由于算法中只用到误差项的符号，因此类似中点法，用2 e dx替换e。

e=2edx

整数Bresenham画线算法为：

x0=xs，y0=ys，dx=xe-xs，dy=ye-ys，e0=-dx，xi+1=xi+1，

当ei＜0时，ei+1=ei+2dy

当ei≥0时，

yi+1=yi+1，ei+1=ei+2dy-2dx (i=0,1,2…，dx)

4.程序设计

直线的斜率在0～1之间的Bresenham画线算法的VC主要代码如下：

CDC∗pDC=GetDC（）;
dx=xe-xs; dy=ye-ys;  //（ xs，ys），（xe，ye）为直线段的两个端点坐标
e=-dx; y=ys;
dxx=dx+dx; dyy=dy+dy;
for（x=xs;x＜=xe;x++）
{   pDC-＞SetPixel（x，y，RGB（0，0，0））;
    if（e＞=0）
            y=y++，e=e-dxx;
    e=e+dyy;
}

3.1.4 直线线宽的处理

在实际应用中，除了使用单像素宽的线条，还经常使用指定线宽的直线。欲产生具有宽度的线，可以顺着扫描所生成的单像素线条轨迹，移动一把具有一定宽度的“刷子”来获得。“刷子”的形状可以是一条线段或一个正方形。也可以采用区域填充的办法间接地产生有宽度的线。

（1） 垂直线刷子：假设直线斜率在[-1，1]之间，把刷子放置成垂直方向，刷子中点对准直线一端点，然后让刷子中心往直线的另一端移动，即可“刷出”具有一定宽度的线。如图3-8所示为线宽为5的线段。

实现方法：在直线的扫描转换中，计算出与直线最近的像素点后，在绘制点的同时分别向上和向下多绘制几个点，即可实现垂直刷的宽度线。

（2） 水平线刷子：直线斜率不在[-1，1]之间，可以把刷子放置成水平方向，刷子中点对准直线一端点并往直线的另一端移动，可“刷出”具有一定宽度的线，如图3-9所示。

实现方法：在直线的扫描转换中，计算出与直线最近的像素点后，在绘制点的同时分别向左和向右多绘制几个点，即可实现水平刷的宽度线。

线刷子算法简单、效率高。但有以下几个缺点：

① 线的始末端总是水平或垂直，当线宽较大时，看起来很不自然。

② 两条线的汇合处外角将有缺口，如图3-10所示。

③ 斜线与水平（或垂直）线不一样粗。对于水平线或垂直线，刷子与线条垂直，因而最粗，其粗细与指定线宽相等。而对于45°斜线，刷子与线条成45°角，粗细仅为指定线宽的倍。

④ 当线宽为偶数个像素时，用上述方法绘制的线条要么粗一个像素，要么细一个像素。

（3） 方形刷子：把边宽为指定线宽的正方形的中心沿直线做平行移动，即可获得具有线宽的线条。图3-11所示为用方形刷子绘制的具有宽度的线条。

与线刷子类似，用方形刷子绘制的线条线宽与线条方向有关。与线刷子的情形相反，对于水平线与垂直线，线宽最小；而对于斜率为± 1的线条，线宽最大，为垂直（水平）线宽度的倍。

实现正方形刷子最简单的办法是，把方形中心对准单像素宽的线条上各个像素，并把方形内的像素全部置成线条颜色。这种简单方法将重复地写像素。这是因为对应于相邻两像素的方形一般会重叠许多像素。

生成具有宽度的线条还可以采用区域填充的算法（见3.5.2节“多边形域填充”）。先算出线条边界各顶点，再用直线段把各顶点连接起来，最后调用多边形填充算法把所得的多边形进行填色，即得到具有宽度的线条。用这种方法还可以生成两端粗细不一样的线条。