lesson03-直線生成算法市公開課特等獎市賽課微課一等獎?wù)n件

LESSON03基本圖形生成算法第1頁基本圖形生成算法總體目標(biāo)：掌握二維圖形學(xué)基本思想，了解二維圖形生成基本原理掌握直線段生成算法、反走樣算法。掌握圓弧生成及線形處理掌握字符生成基本思想第2頁基本概念光柵顯示器上顯示圖形，稱之為光柵圖形。確定最正確迫近圖形象素集合，并用指定顏色和灰度設(shè)置象素過程稱為圖形掃描轉(zhuǎn)換或光柵化。二維圖形光柵化必須確定區(qū)域?qū)?yīng)象素集，將各個象素設(shè)置成指定顏色和灰度，也稱之為區(qū)域填充。在光柵圖形中，非水平和垂直直線用象素集合表示時，會呈鋸齒狀，這種現(xiàn)象稱之為走樣(aliasing)；用于降低或消除走樣技術(shù)稱為反走樣(antialiasing)。第3頁2.1直線生成算法概述在計算機(jī)產(chǎn)生圖形中，用到大量直線，畫好直線是非常有意義，其普通準(zhǔn)則是：線條應(yīng)該顯得筆直：由連續(xù)點(diǎn)組成直線要顯示在離散網(wǎng)格平面上，一定會有不經(jīng)過網(wǎng)格點(diǎn)，如左下列圖。在這種情況下，必須選擇靠近直線網(wǎng)格點(diǎn)來迫近這條直線。若選擇好，線就顯得較直；不然就會較彎曲，如右下列圖。第4頁2.1直線生成算法概述直線端點(diǎn)位置應(yīng)該準(zhǔn)確：畫出線段假如不準(zhǔn)確，往往會使兩條線之間不能很好鑲接，如右圖。直線濃度應(yīng)該均勻：線段濃度與單位線段中所顯示點(diǎn)數(shù)成正比。要保持線段濃度均勻端點(diǎn)應(yīng)該等距分布。只有嚴(yán)格平行和成45°線才能做到。第5頁2.1直線生成算法概述直線濃度應(yīng)該與線段長度和斜率無關(guān)：

要取得均勻線段濃度，應(yīng)該保持每單位長度點(diǎn)數(shù)是個常數(shù)。普通，采取線段近似長度，以及生成直線算法，使在線段近似長度范圍內(nèi)保持線段濃度均勻。顯示線段速度應(yīng)快：

生成直線可用軟件和硬件來實(shí)現(xiàn)，普通情況下，硬件要比軟件實(shí)現(xiàn)得快。第6頁2.1直線生成算法概述直線慣用生成算法數(shù)值微分(DDA：DigitalDifferentialAnalyzer

)法

中點(diǎn)畫線法Bresenham算法第7頁2.1.1直線DDA算法直線微分方程表示為：

dx/dy=△x/△y

設(shè)直線斜率小于等于1，

起點(diǎn)坐標(biāo)為(xa,ya)，

終點(diǎn)坐標(biāo)為(xb,yb)，

則方程求解步驟分為：

x0=xa

+0.5，xn=xn-1+1

y0=ya

+0.5，yn=yn-1+△y/△x

其中：△x=xb

-xa，△y=yb-ya

上述解表示x方向積分步長為1，y方向增量為△y/△x。yn-1yxynxn-1xn△y/△x第8頁2.1.1直線DDA算法xyn-1yynxn-1xn△y/△x因?yàn)槠聊簧献鴺?biāo)為整數(shù)坐標(biāo)，則真正作為輸出顯示為：

y輸出=trunc(yn)，其中函數(shù)trunc()是指舍尾正數(shù)。

所以y輸出和yn之間量化誤差最大為1。

為了改進(jìn)這方面誤差，

使y0初值增加0.5,

使量化誤差在(-0.5,0.5)范圍之間。

同理，若直線斜率大于1，

則上述方程求解步驟可分為：

x0=xa+0.5，xn=xn-1+△x/△y，

y0=ya+0.5，yn=yn-1+1，

其中△x，△y意義同上。

上述解表示y方向積分步長為1，

x方向增量為△x/△y,其它同上。第9頁DDA直線生成算法描述if|xb-xa|≤|yb-ya|then

計算直線在y方向上增量：length=|yb-ya|else計算直線在x方向上增量：length=|xb-xa|計算x方向單位增量：dx=(xb-xa)/length計算y方向單位增量：dy=(yb-ya)/length置初值：x=xa+0.5，y=ya+0.5fori=1tolengthdo

begin 輸出點(diǎn)(trunc(x),trunc(y)) 計算下一個點(diǎn)坐標(biāo)x=x+dx，y=y+dy

endendofalgorithm第10頁DDA直線生成算法C描述VoidlineDDA(intxa,intya,intxb,intyb){intdx=xb-xa,dy=yb-ya,steps,k;floatxIncrement,yIncrement,x=xa,y=ya;if(abs(dx)>abs(dy))steps=abs(dx);elsesteps=abs(dy);xIncrement=dx/(float)steps;yIncrement=dy/(float)steps;setPixel(round(x),round(y));for(k=0;k<steps;k++){x+=xIncrement;y+=yIncrement;setPixel(round(x),round(y));}}

動畫演示算法第11頁DDA直線生成算法小結(jié)優(yōu)點(diǎn)：在同一坐標(biāo)上,不可能連續(xù)停留兩次。缺點(diǎn)：在本算法中，開始需要執(zhí)行一個除法△y/△x或△x/△y來確定增量，這么用硬件來實(shí)現(xiàn)比較復(fù)雜和昂貴，用軟件實(shí)現(xiàn)相對輕易些，但效率較低。第12頁2.1.2中點(diǎn)畫線法假定直線斜率k在0~1之間，當(dāng)前象素點(diǎn)為（xp,yp），則下一個象素點(diǎn)有兩種可選擇點(diǎn)P1（xp+1,yp）或P2（xp+1,yp+1）。若P1與P2中點(diǎn)（xp+1,yp+0.5）稱為M，Q為理想直線與x=xp+1垂線交點(diǎn)。當(dāng)M在Q下方時，則取P2應(yīng)為下一個象素點(diǎn)；當(dāng)M在Q上方時，則取P1為下一個象素點(diǎn)。這就是中點(diǎn)畫線法基本原理。第13頁2.1.2中點(diǎn)畫線法過點(diǎn)(x0,y0)、(x1,y1)直線段L方程式為F(x,y)=ax+by+c=0，其中，a=y0-y1,b=x1-x0,c=x0y1-x1y0，欲判斷中點(diǎn)M在Q點(diǎn)上方還是下方，只要把M代入F（x，y），并判斷它符號即可。為此，我們結(jié)構(gòu)判別式:d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c;

當(dāng)d<0時，M在L(Q點(diǎn))下方，取P2為下一個象素；

當(dāng)d>0時，M在L(Q點(diǎn))上方，取P1為下一個象素；

當(dāng)d=0時，選P1或P2均可，約定取P1為下一個象素；第14頁2.1.2中點(diǎn)畫線法注意到d是xp,yp線性函數(shù)，可采取增量計算，提升運(yùn)算效率。

若當(dāng)前象素處于d>=0情況，則取正右方象素P1(xp+1,yp),要判下一個象素位置，應(yīng)計算d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c=d+a，增量為a。

若d<0時，則取右上方象素P2(xp+1,yp+1)。要判斷再下一象素，則要計算d2=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b，增量為a＋b。畫線從(x0,y0)開始，d初值d0=F(x0+1,y0+0.5)=F(x0,y0)+a+0.5b，因

F(x0,y0)=0，所以d0=a+0.5b。

因?yàn)槲覀兪褂弥皇莇符號，而且d增量都是整數(shù)，只是初始值包含小數(shù)。所以，我們能夠用2d代替d來擺脫小數(shù)，寫出僅包含整數(shù)運(yùn)算算法程序。第15頁2.1.2中點(diǎn)畫線算法voidMidpointLine(intx0,inty0,intx1,inty1,intcolor){inta,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)

{x++；y++；d+=d2;}

else

{x++；d+=d1;}

drawpixel(x,y,color);

}/*while*/}/*midPointLine*/第16頁2.1.2中點(diǎn)畫線算法演示程序演示第17頁2.1.3Bresenham直線生成算法原理rr+1qq+1tsTiSi設(shè)直線斜率小于1，即△x＞△y,

x方向步長總是1，y方向是否有改變，

取決于直線理論值與假設(shè)點(diǎn)之間誤差值大小。

考慮第i步,即點(diǎn)Pi,它前一點(diǎn)Pi-1

是最靠近直線坐標(biāo)值,其坐標(biāo)為(r,q),

則Pi坐標(biāo)有兩種選擇：

Si

(r+1,q)和Ti

(r+1,q+1)。

取哪一點(diǎn)需判別理論值和

這兩個假設(shè)點(diǎn)之間誤差S,t大小。

若S＞t(或S-t＞0),則取點(diǎn)Ti，反之取點(diǎn)Si。第18頁2.1.3Bresenham直線生成算法原理rr+1qq+1tsTiSi 假設(shè)直線是從(xa,ya)至(xb,yb)，

假如把直線平移使點(diǎn)(xa,ya)

與原點(diǎn)重合，則直線方程可寫成

y=△y/△x·x，

其中：△x=xb-xa，

△y=yb-ya。

則S,t可用下式計算：

S=△y/△x·(r+1)-q

t=(q+1)-△y/△x·(r+1)

S-t=2·△y/△x·(r+1)-2q-1 △x(S-t)=2(r·△y-q·△x)+2△y-△x其中：△x＞0。 令di=△x(S-t)，則di與S-t符號相同

只要判別di符號就可確定下一點(diǎn)坐標(biāo)是Si還是Ti。第19頁2.1.3Bresenham直線生成算法原理

于是

di=2(r·△y-q·△x)+2·△y-△x；

當(dāng)r=xi-1，q=yi-1時，

di=2xi-1·△y-2yi-1△x+2△y-△x

di+1=2xi·△y-2yi·△x+2△y-△x

di+1-di=2△y(xi-xi-1)-2△x(yi-yi-1)

di+1=di+2△y(xi-xi-1)-2△x(yi-yi-1)

所以，di遞推公式為：

d1=2△y-△x di+1=di+2△y

當(dāng)di＜0時，取Si

(xi-1+1,yi-1)

di+1=di+2△y-2△x

當(dāng)di≥0時，取Ti

(xi-1+1,yi-1+1)第20頁Bresenham直線生成算法描述計算x和y方向增量：dx=|xb-xa|，dy=|yb-ya|計算遞推公式初值d1:

d=2dy-dx計算兩個單位增量：incr1=2dy,incr2=2(dy-dx)if(xa＞xb)then

置起點(diǎn)為x=xb，y=yb，置終點(diǎn)為xe=xa,ye=yaelse置起點(diǎn)為x=xa，y=ya，置終點(diǎn)為xe=xb，ye=yb輸出起點(diǎn)(x,y)while(x＜xe)dobegin

x=x+1if(d＜0)thend=d+incr1

elsey=y+1，d=d+incr2

輸出點(diǎn)(x,y)endendofalgorithm 第21頁Bresenham直線生成程序voidInterBresenhamline(intx0,inty0,intx1,inty1,intcolor)