直线的分段绘制算法

黄 欣

(湖北民族学院 信息工程学院，湖北 恩施 445000)

在计算机图形系统中，直线是最基本的图形元素之一.直线的绘制速度，影响了整个图形系统的效率，一个好的直线算法对于系统性能有重大意义.对于光栅设备，Bresenham直线算法非常有效.本文以直线A(x1,y1)B(x2,y2)，(x1

定义：

dx=x2-x1，dy=y2-y1，k=dy/dx.

规定:dy≤dx,即0≤k≤1.

Bresenham算法[1]是一个循环过程.在每一次循环中，绘图坐标都向X方向移动一步，同时更新Y坐标的误差项并且判断是否向Y方向移动一步.如果k≪1，那么Y方向的位移大大小于X方向的位移(即dy≪dx).要提高算法效率，可以设法减少对Y方向的判断.有人对此提出过改进意见[2].本文从图形分解的角度给出了一个改进方案.光栅图形是离散的点映射图形，可以看作是由水平和垂直的线段组成.光栅直线可以看作由一组水平(|斜率|<1)或一组垂直(|斜率|>1)线段组成，直线AB可以看作由一组水平线段相连而成.只要确定了起点和长度，则绘制水平线段不用逐点判断.本文分析了各水平线段的长度与斜率k之间的关系，并利用这些规律设计了一个新算法.

1 光栅直线的分段规律

光栅直线AB由dy+1条水平线段组成，各线段的长度与k的倒数密切相关.

定义：L=int(1/k)=int(dx/dy),

斜率k的倒数L反映了AB的水平程度，不妨称之为“平率”.

以下按dy的不同，分三种情况叙述AB的组成规律.

第一种情况：dy=0.AB仅由一条水平线段(LSo)组成，其长度为:

Lo=dx+1

(1)

第二种情况：dy=1.AB仅由两条水平线段组成.第一条(LSo)的长度为:

(2)

由此式(2)得证.

第二条(最后一条LSm)的长度为:

Lm=int(L/2)+1.

(3)

证明令x2=y2=0.如果点(x,0)∈LSm,则y(x)≥-1/2.

而y(x)=y2-k(x2-x)=kx,因此x≥-1/2k=-dx/2dy,那么x≥-int(L/2),由此式(3)得证.

第三种情况：dy=m(m>1).AB由m+1条水平线段组成.第一条和最后一条的长度与dy=1时相同.中间各条线段LSi(i=1,2,…,m-1)的长度为:

Li=L或L+1(i=1,2,…,m-1)

(4)

证明假设(xi1,i)、(xi2,i)为LSi的首点和尾点,那么1-k≤y(xi2)-y(xi1)≤1,而y(x)=y1+k(x-x1),因此1/k-1≤xi2-xi1≤1/k,即dx/dy-1≤xi2-xi1≤dx/dy,那么int(dx/dy)-1≤xi2-xi1≤int(dx/dy),即L-1≤xi2-xi1≤L,由此式(4)得证.

2 光栅直线的分段绘制算法

如果dy>1，在绘制中间各条线段LSi时需要设法最终确定它们的长度Li,可以先绘制L点，然后利用Bresenham算法中的误差项判断下一点是否仍然属于LSi.以下为直线的分段绘制算法(由C++写成).

// 算法：分段绘制直线A(x1,y1)B(x2,y2)

void Line(int x1,int y1,int x2,int y2)

{ int x=x1,y=y1,dx=x2-x1,dy=y2-y1;

// 确定L、Lo、Lm

int L,Lo,Lm;

if(dy==0) // AB仅由一条水平线段组成

{ L=0; Lo=dx+1;Lm=0;}

else

{ L=dx/dy; Lo=L/2; Lm=L/2+1;

if(dx%(2*dy)!=0) Lo=L/2+1;

}

// 绘制第一条水平线段

for(int i=0;i

// 绘制第中间dy-1条水平线段， 如果存在(dy>1)

y++;

int ue=2*dx; // 误差阀值

int e=-dx+ Lo*2*dy -ue; // 初始化误差项

int de=L*2*dy; // L点误差和

for(int j=0;j

{ // 首先绘出前L点

for(i=0;i

// 判断第L+1点

e+=de; // 得到第L+1点的误差

if(e<0) // 第L+1点也属于该条水平线段

{ DrawPoint(x,y); // 绘制第L+1点

x++;

e+=2*dy; // 更新误差项

}

y++; // 指向下一条线段

e-=ue; // 更新误差项初值

}

// 绘制最后一条水平线段，如果存在(dy>0)

for(i=0;i

}

绘制AB，Bresenham算法需要完成dx+1次误差项更新和dx+1次误差项判断；新算法需要完成dy-1次误差项判断，误差项更新次数大于等于dy-1小于等于2(dy-1).在2dy

3 测试结果

以下是对Bresenham算法和分段算法的运行时间的测试结果，测试工具是一台Pentium/100 PC，测试方法是运行1万次取平均时间[3-5].

表1 Bresenham算法运行时间～分段算法运行时间 (ms～ms)

从表中可以看出，当k<1/2并且dx较大时，新算法运行较快.k越小、dx越大，新算法越有效，它适用于直线AB的一个子集.与Bresenham算法一样，新算法也可以推广到斜率不属于[0,1]的情况，它适用于与X轴或Y轴夹角很小(小于arctan(1/2))并且长度较长的直线.

[1] 罗笑南，王若梅．计算机图形学[M]．广州：中山大学出版社，1996：24-28.

[2] 刘勇奎．一个基于直线链码理论的快速直线绘制算法[J]．微计算机应用，1994，15(6)：29-31.

[3] 郑莉.C++语言程序设计[M].2版.北京：清华大学出版社，2003.

[4] 严蔚敏，吴伟民.数据结构(C语言版)[M].北京：清华大学出版社，2002：14-17.

[5] 周明德.微型计算机原理及应用[M].4版.北京：清华大学出版社，2002.