黃 欣

(湖北民族學(xué)院 信息工程學(xué)院，湖北 恩施 445000)

在計(jì)算機(jī)圖形系統(tǒng)中，直線是最基本的圖形元素之一.直線的繪制速度，影響了整個圖形系統(tǒng)的效率，一個好的直線算法對于系統(tǒng)性能有重大意義.對于光柵設(shè)備，Bresenham直線算法非常有效.本文以直線A(x1,y1)B(x2,y2)，(x1

定義：

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

規(guī)定:dy≤dx,即0≤k≤1.

Bresenham算法[1]是一個循環(huán)過程.在每一次循環(huán)中，繪圖坐標(biāo)都向X方向移動一步，同時更新Y坐標(biāo)的誤差項(xiàng)并且判斷是否向Y方向移動一步.如果k?1，那么Y方向的位移大大小于X方向的位移(即dy?dx).要提高算法效率，可以設(shè)法減少對Y方向的判斷.有人對此提出過改進(jìn)意見[2].本文從圖形分解的角度給出了一個改進(jìn)方案.光柵圖形是離散的點(diǎn)映射圖形，可以看作是由水平和垂直的線段組成.光柵直線可以看作由一組水平(|斜率|<1)或一組垂直(|斜率|>1)線段組成，直線AB可以看作由一組水平線段相連而成.只要確定了起點(diǎn)和長度，則繪制水平線段不用逐點(diǎn)判斷.本文分析了各水平線段的長度與斜率k之間的關(guān)系，并利用這些規(guī)律設(shè)計(jì)了一個新算法.

1 光柵直線的分段規(guī)律

光柵直線AB由dy+1條水平線段組成，各線段的長度與k的倒數(shù)密切相關(guān).

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

斜率k的倒數(shù)L反映了AB的水平程度，不妨稱之為“平率”.

以下按dy的不同，分三種情況敘述AB的組成規(guī)律.

第一種情況：dy=0.AB僅由一條水平線段(LSo)組成，其長度為:

Lo=dx+1

(1)

第二種情況：dy=1.AB僅由兩條水平線段組成.第一條(LSo)的長度為:

(2)

由此式(2)得證.

第二條(最后一條LSm)的長度為:

Lm=int(L/2)+1.

(3)

證明令x2=y2=0.如果點(diǎn)(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)

證明假設(shè)(xi1,i)、(xi2,i)為LSi的首點(diǎn)和尾點(diǎn),那么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時需要設(shè)法最終確定它們的長度Li,可以先繪制L點(diǎn)，然后利用Bresenham算法中的誤差項(xiàng)判斷下一點(diǎn)是否仍然屬于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; // 初始化誤差項(xiàng)

int de=L*2*dy; // L點(diǎn)誤差和

for(int j=0;j

{ // 首先繪出前L點(diǎn)

for(i=0;i

// 判斷第L+1點(diǎn)

e+=de; // 得到第L+1點(diǎn)的誤差

if(e<0) // 第L+1點(diǎn)也屬于該條水平線段

{ DrawPoint(x,y); // 繪制第L+1點(diǎn)

x++;

e+=2*dy; // 更新誤差項(xiàng)

}

y++; // 指向下一條線段

e-=ue; // 更新誤差項(xiàng)初值

}

// 繪制最后一條水平線段，如果存在(dy>0)

for(i=0;i

}

繪制AB，Bresenham算法需要完成dx+1次誤差項(xiàng)更新和dx+1次誤差項(xiàng)判斷；新算法需要完成dy-1次誤差項(xiàng)判斷，誤差項(xiàng)更新次數(shù)大于等于dy-1小于等于2(dy-1).在2dy

3 測試結(jié)果

以下是對Bresenham算法和分段算法的運(yùn)行時間的測試結(jié)果，測試工具是一臺Pentium/100 PC，測試方法是運(yùn)行1萬次取平均時間[3-5].

表1 Bresenham算法運(yùn)行時間～分段算法運(yùn)行時間 (ms～ms)

從表中可以看出，當(dāng)k<1/2并且dx較大時，新算法運(yùn)行較快.k越小、dx越大，新算法越有效，它適用于直線AB的一個子集.與Bresenham算法一樣，新算法也可以推廣到斜率不屬于[0,1]的情況，它適用于與X軸或Y軸夾角很小(小于arctan(1/2))并且長度較長的直線.

[1] 羅笑南，王若梅．計(jì)算機(jī)圖形學(xué)[M]．廣州：中山大學(xué)出版社，1996：24-28.

[2] 劉勇奎．一個基于直線鏈碼理論的快速直線繪制算法[J]．微計(jì)算機(jī)應(yīng)用，1994，15(6)：29-31.

[3] 鄭莉.C++語言程序設(shè)計(jì)[M].2版.北京：清華大學(xué)出版社，2003.

[4] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語言版)[M].北京：清華大學(xué)出版社，2002：14-17.

[5] 周明德.微型計(jì)算機(jī)原理及應(yīng)用[M].4版.北京：清華大學(xué)出版社，2002.