基本圖形生成算法

如何在指定的輸出設(shè)備上根據(jù)坐標(biāo)描述構(gòu)造基本幾何圖形（點(diǎn)、直線、圓、橢圓、多邊形域、字符串及其相關(guān)屬性等）?第3章基本圖形生成算法2圖形生成的概念直線段的掃描轉(zhuǎn)換圓的掃描轉(zhuǎn)換多邊形的掃描轉(zhuǎn)換與區(qū)域填充屬性處理反走樣技術(shù)第3章基本圖形生成算法點(diǎn)的生成

點(diǎn)是圖形中最基本的圖元，直線、曲線以及其它的圖元都是點(diǎn)的集合。在幾何學(xué)中，一個點(diǎn)既沒有大小，也沒有維數(shù)，點(diǎn)只是表示坐標(biāo)系統(tǒng)中一個位置。在計算機(jī)圖形學(xué)中，點(diǎn)是用數(shù)值坐標(biāo)來表示的。在直角坐標(biāo)系中點(diǎn)由（x,y)兩個數(shù)值組成的坐標(biāo)表示，在三維坐標(biāo)系中點(diǎn)是由（x,y,z)三個數(shù)值組成的坐標(biāo)表示。在輸出設(shè)備上輸出一個點(diǎn)，就要把應(yīng)用程序中的坐標(biāo)信息轉(zhuǎn)換成所用輸出設(shè)備的相應(yīng)位置。對于一個CRT監(jiān)視器來說，輸出一個點(diǎn)就是要在指定的屏幕位置上打上電子束，使該位置上的熒光點(diǎn)亮。在PC機(jī)中，點(diǎn)亮屏幕上一個點(diǎn)是由BIOS控制完成的，各種程序語言中都有描點(diǎn)語句。例如C語言為putpixel(x,y,color),putpixel(放,擺-像素)。3.1圖形生成的概念3圖形的生成：是在指定的輸出設(shè)備上，根據(jù)坐標(biāo)描述構(gòu)造二維幾何圖形。圖形的掃描轉(zhuǎn)換：在光柵顯示器等數(shù)字設(shè)備上確定一個最佳逼近于圖形的像素集的過程。

用像素點(diǎn)集逼近直線3.1圖形生成的概念3.1圖形生成的概念

在數(shù)學(xué)上，理想的直線是沒有寬度的、由無數(shù)個點(diǎn)構(gòu)成的集合。當(dāng)我們對直線進(jìn)行光柵化時，只能在顯示器所給定的有限個像素組成的矩陣中，確定最佳逼近該直線的一組像素，并且按掃描線順序?qū)@些像素進(jìn)行寫操作，這就是通常所說的直線的掃描轉(zhuǎn)換。

通常用于直線光柵化的算法有數(shù)值微分法（DDA）、中點(diǎn)畫線法和Bresenham畫線算法。3.2直線的掃描轉(zhuǎn)換直線光柵化算法直線段生成求與直線段充分接近的像素集直線的繪制要求（1）直線要直；（2）直線的端點(diǎn)要準(zhǔn)確，無定向性無斷裂；（3）直線的亮度、色澤要均勻；（4）畫線的速度要快；（5）具有不同的色澤、亮度、線型等。3.2直線的掃描轉(zhuǎn)換解決的問題：給定直線兩端點(diǎn)P0(x0,y0)和P1(x1,y1)，畫出該直線。數(shù)值微分法(DDA算法)中點(diǎn)畫線算法Bresenhan算法3.2直線的掃描轉(zhuǎn)換已知一條直線段L（P0,P1）,其端點(diǎn)坐標(biāo)為：P0(x0,y0),P1(x1,y1)?？捎嬎愠鲋本€的斜率k為：DDA（DigitalDifferentialAnalyzer）畫線算法也稱數(shù)值微分法，是一種增量算法。它的算法實(shí)質(zhì)是用數(shù)值方法解微分方程，通過同時對x和y各增加一個小增量，計算下一步的x、y值。3.2.1數(shù)值微分法(DDA法)假定端點(diǎn)坐標(biāo)均為整數(shù)，取直線起點(diǎn)P0(x0,y0)作為初始坐標(biāo)。畫線過程從x的左端點(diǎn)x0開始，向x右端點(diǎn)步進(jìn)，每步x遞增1，計算相應(yīng)的y坐標(biāo)，y=kx+b，取像素點(diǎn)（x，round（y））作為當(dāng)前點(diǎn)的坐標(biāo)。問題:每步需要用到浮點(diǎn)數(shù)的乘法、加法和取整運(yùn)算，效率不高。怎么辦??3.2.1數(shù)值微分法(DDA法)11增量算法因?yàn)?

y=kx+b,所以:yi+1=kxi+1+b=k(xi+1)+b=kxi+b+k=yi+k(xi,yi)→(xi+1,yi+k)3.2.1數(shù)值微分法(DDA法)

r例圖中

k<1△X=1

△Y=kr將算得的直線上每個點(diǎn)的當(dāng)前坐標(biāo)，按四舍五入得到光柵點(diǎn)的位置

r浮點(diǎn)數(shù)取整:yi=round(yi)=(int)(yi+0.5)12

有：

yi+1=yi+k?△Xr若0<k<1，即x>y

q因光柵單位為1，

q可以采用每次x方向增加1，

q而y方向增加k的辦法得到下一個直線點(diǎn)。因:3.2.1數(shù)值微分法(DDA法)演示說明13例：畫直線段P0(0,0)--P1(5,2)解：斜率K=2/5=0.4，所以X方向每次步長為1，Y方向遞增K。初始點(diǎn)為（0，0）。xint(y+0.5)y0 0 01 0 0.42 1 0.8

3 1 1.24 2 1.65 2 2.0當(dāng)k

1時，必須把x，y地位互換yi+1=yi+k14程序?qū)崿F(xiàn)：voidDDALine(intx0,inty0,intx1,inty1,intcolor){intx;floatdx,dy,k,y;dx=x1-x0;dy=y1-y0;k=dy/dx;y=y0;for(x=x0;x<=x1;){

drawpixel(x,int(y+0.5),Color);x++;y=y+k;}}15通常情況下，直線的方向分為8個不同的區(qū)域，每個區(qū)域的處理方法有所不同。K=△y/△x區(qū)域dxdy1a(1)1k1b(2)1/k12a(4)-1k2b(3)-1/k13a(5)-1-k3b(6)-1/k-14a(8)1-k4b(7)1/k-13.2.1數(shù)值微分法(DDA法)163.2.1數(shù)值微分法(DDA法)18增量算法直觀、易實(shí)現(xiàn)不利于用硬件實(shí)現(xiàn)數(shù)值微分法(DDA法)——特點(diǎn)3.2.2中點(diǎn)畫線算法中點(diǎn)畫線算法的基本思想為了討論方便，假設(shè)直線的斜率在0到1之間，若直線在x方向上增加一個光柵單位，則在y方向上的增量只能在0到1之間。設(shè)P（xp,yp）是直線上的一點(diǎn)，與P點(diǎn)最近的網(wǎng)格點(diǎn)為（xi,yi）,那么，下一個與直線最近的像素只能是正右方的網(wǎng)格點(diǎn)P1（xi+1,yi）或右上方的網(wǎng)格點(diǎn)P2（xi+1,yi+1）兩者之一。再以點(diǎn)M（xi+1,yi+0.5）表示P1和P2的中點(diǎn)，設(shè)Q是直線與垂直線x=xi+1的交點(diǎn)。顯然，若M在Q的下方，則P2離直線較近，應(yīng)取P2為下一個像素點(diǎn)，否則應(yīng)取P1做為下一個像素點(diǎn)，這就是中點(diǎn)畫線算法的基本思想。

問題：如何判斷M與Q點(diǎn)的關(guān)系？19圖

直線將平面分為三個區(qū)域3.2.2中點(diǎn)畫線算法假設(shè)直線的起點(diǎn)、終點(diǎn)分別為：（X0,Y0),(X1,Y1)

則直線方程可表示為：

F(x,y)=a*x+b*y+c（1）

其中：

a=Y0-Y1,b=X1-X0,c=X0*Y1-X1*Y0

空間某點(diǎn)（x,y）與直線的關(guān)系：

當(dāng)：20

設(shè)直線的起點(diǎn)和終點(diǎn)分別為（x0,y0)和(x1,y1)則直線方程為F(x,y)=ax+by+c=0（1）∴欲判斷中點(diǎn)M點(diǎn)是在Q點(diǎn)上方還是在Q點(diǎn)下方，只需:將中點(diǎn)M坐標(biāo)代入（1）式，并判斷其符號即可確定像素點(diǎn)的選取。構(gòu)造如下判別式：采用增量計算

d=F(M)=F(x+1,y+0.5)=a(x+1)+b(y+0.5)+c在d≥0的情況下(M在直線上(Q點(diǎn))或上方)，取正右方像素P1在d<0的情況下(M在直線(Q點(diǎn))下方)，取右上方像素P23.2.2中點(diǎn)畫線算法能否采用增量算法呢？3.2.2中點(diǎn)畫線算法若d0->M在直線上方->取P1;此時再下一個像素的判別式為

d1=F(x+2,y+0.5)(F(x,y)=ax+by+c=0)=a(x+2)+b(y+0.5)+c=a(x+1)+b(y+0.5)+c+a=d+a；增量為ad=F(M)=F(x+1,y+0.5)=a(x+1)+b(y+0.5)+c若d<0->M在直線下方->取P2;此時再下一個象素的判別式為

d2=F(x+2,y+1.5)=a(x+2)+b(y+1.5)+c=a(x+1)+b(y+0.5)+c

+a+b=d+a+b

；增量為a＋b3.2.2中點(diǎn)畫線算法d=F(M)=F(x+1,y+0.5)=a(x+1)+b(y+0.5)+c畫線從(x0,y0)開始，d的初值（F(x,y)=a*x+b*y+c）

d0=F(x0+1,y0+0.5)=a(x0+1)+b(y0+0.5)+c=ax0+a+by0+0.5b+c=ax0+by0+c+a+0.5b=F(x0,y0)+a+0.5b=a+0.5b注：由于（x0,y0）在直線上，故F(x0,y0)=0所以，d的初始值d0=a+0.5b

3.2.2中點(diǎn)畫線算法由于只用d的符號作判斷，為了只包含整數(shù)運(yùn)算,可以用2d代替d來擺脫小數(shù)，提高效率。用2d代替d后，d0=2a+bd的增量都是整數(shù)(d1:2a,d2:2(a+b))如果進(jìn)一步把算法中2*a改為a+a等等，那么這個算法不僅只包含整數(shù)變量，而且不包含乘除法，適合硬件實(shí)現(xiàn)。3.2.2中點(diǎn)畫線算法演示說明d的初始值d0=a+0.5b

解:

K=dy/dx=2/5=0.4<1,故x方向增1,y方向根據(jù)d的符號判斷.

a=y0-y1=-2;b=x1-x0=5;d0=2a+b=1;d1=2a=-4;d2=2(a+b)=6;xyd00110-321331-1425521例:按照中點(diǎn)畫線算法，確定直線（0，0）（5，2）的點(diǎn)亮像素。列出計算過程，并列出所選像素坐標(biāo)。在d≥0的情況下，取正右方像素P1，判斷再下一像素應(yīng)計算

d1=a(x+2)+b(y+0.5)+c=d+a,故d的增量為a.在d<0的情況下，取右上方像素P2，判斷再下一像素應(yīng)計算

d2=a(x+2)+b(y+1.5)=d+a+b,故d的增量為a+b.d的初始值d0=a+0.5b用2d代替d后，d0=2a+bd的增量都是整數(shù)d1：2ad2：2(a+b)程序?qū)崿F(xià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);}}在d<0的情況下(M在直線(Q點(diǎn))下方)，取右上方像素P2,再下一個像素的判別式為d2.在d>=0的情況下(M在直線(Q點(diǎn))上方)，取正右方像素P1,再下一個像素的判別式為d1.3.2.3Bresenham畫線算法

Bresenham算法是計算機(jī)圖形學(xué)領(lǐng)域使用最廣泛的直線生成算法。假設(shè)直線斜率k?[0,1]。Bresenham畫線算法的基本原理是：按直線從起點(diǎn)到終點(diǎn)的順序計算直線與各垂直網(wǎng)格線的交點(diǎn)，然后確定該列像素中與此交點(diǎn)最近的像素。

這是計算機(jī)科學(xué)教授JackEltonBresenham最知名的一項(xiàng)創(chuàng)新，開發(fā)于1962年。

因?yàn)樾甭瘦^小，所以每條垂直線上最多選取一個像素。如果像素點(diǎn)Pi-1(xi-1，yi-1)是已經(jīng)選定的離直線最近的像素點(diǎn)，現(xiàn)在要決定下一個像素點(diǎn)Pi是Ti

還是Si。如圖3-5所示。由圖3-5不難看出：若s<t，則Si比較靠近理想直線，應(yīng)選Si;若s≥t，則Ti比較靠近理想直線，應(yīng)選Ti。3.2.3Bresenham畫線算法令dx=x2-x1，dy=y2-y1遞推公式：di的初值：當(dāng)di≥0時，選Ti，當(dāng)di<0時，選Si，由于只包含加、減法和左移（乘2）的運(yùn)算，而且下一個像素點(diǎn)的選擇只需檢查di的符號，因此Bresenham畫線算法很簡單，速度也相當(dāng)快。3.2.3Bresenham畫線算法請看下面的推導(dǎo)過程結(jié)論已知，Pi(xi,yi)，xi

＝xi－1＋1，當(dāng)Pi＝Ti時，yi

＝y(tǒng)i-1+1；當(dāng)Pi＝Si時，yi

＝y(tǒng)i-1顯然，無論下一個像素點(diǎn)是Ti還是Si

，x方向都增1，即xi

＝xi－1＋1，要決定的是y方向是否增1。由圖3-5不難看出

:若s<t,則Si比較靠近理想直線，應(yīng)選Si

；若s≥t，則Ti比較靠近理想直線，應(yīng)選Ti

。設(shè)一直線段由(x1，y1)到(x2,y2)，則直線方程可表示為：(yi+1=yi+k?△X)式中，dx=x2-x1,dy=y2-y1。經(jīng)變換后可表示為從(0,0)到(dx，dy)的直線，此時方程為:3.2.3Bresenham畫線算法f(x)=kx因此有：因?yàn)閐x>0，所以可將dx(s-t)的正負(fù)作為選擇Ti

或Si的依據(jù)。若記其為di，則：(1)

3.2.3Bresenham畫線算法注:Si的坐標(biāo)(xi-1+1,yi-1),Ti的坐標(biāo)(xi-1+1,yi-1+1)f(x)=kx(di≥0時，選Ti,否則選Si)將每一個下標(biāo)加1，則有：兩式相減得(2-1)因?yàn)閤i-xi-1=1，所以得到遞推公式：因此，當(dāng)di≥0時，選Ti

。這時y方向增1，即yi-yi-1=1，則(2)3.2.3Bresenham畫線算法注:當(dāng)di≥0時,說明:s>=t,反之t>s問:當(dāng)di≥0時，為什么選Ti?當(dāng)di<0時，選Si。這時yi-yi-1=0，則：di的初值可由(1)式得出，當(dāng)i=1時(x0,y0)=(0,0)即d1d1=2(x0dy-y0dx)+2dy-dx。由我們的假設(shè)，x0=0,y0=0。即3.2.3Bresenham畫線算法

例:請指出用Bresenham算法掃描轉(zhuǎn)換

從像素點(diǎn)p1（0，0）到p2（5，2）的線段時的像素位置。

解:K=dy/dx=2/5=0.4<1,故x方向增1,y方向根據(jù)d的符號判斷.dx=x2-x1=5-0=5dy=y2-y1=2-0=2

d1=2*dy-dx=4-5=-1

td1=2(dy-dx)=2(2-5)=-6

td2=2*dy=2*2=4xyd00-110321-331142-552-1d1=2dy-dxd>=0,x=x+1,y=y+1di+1=d+2(dy-dx)td1=2(dy-dx)d<0,x=x+1,y=ydi+1=d+2dytd2=2*dy在上述關(guān)于斜率和起點(diǎn)的假設(shè)下，bresenham算法程序?yàn)?3.2.3Bresenham畫線算法

bresenham算法簡單，只包括加減和移位運(yùn)算,并且全部為整數(shù)運(yùn)算，因此效率很高，對硬件要求低。對該算法執(zhí)行過程的跟蹤模擬演示。1．線型2．線寬3．線色

線型一般可用16位二進(jìn)制的掩膜表示，其中為0的位對應(yīng)位置像素不顯示。如虛線表示為：0011001100110011

線寬處理起來比想像到的可能要復(fù)雜一點(diǎn)，一般只能近似。

線色一般光柵掃描系統(tǒng)可以提供多種顏色，通常用0，1，2…等整數(shù)值表示不同顏色。詳見P49--503.2.4直線屬性

圓弧是圖形圖像中經(jīng)常使用的元素。3.3.1圓的特性圓心位于原點(diǎn)的圓有四條對稱軸：x=0，y=0，x=y和x=-y直線。若已知圓弧上一點(diǎn)（x,y），可以得到其關(guān)于四條對稱軸的其它7個點(diǎn)，這種性質(zhì)稱為八對稱性，如下圖所示。本節(jié)討論的圓的生成算法均只計算從x=0到x=y分段內(nèi)（1b區(qū)域）的像素點(diǎn)，其余的像素位置利用八對稱性即可得出。

3.3生成圓弧的常用算法38顯示圓弧上的八個對稱點(diǎn)算法voidCircle_Points(intx,inty,intcolor){Putpixel(x,y,color);Putpixel(x,-y,color);Putpixel(-x,y,color);Putpixel(-x,-y,color);Putpixel(y,x,color);Putpixel(y,-x,color);Putpixel(-y,x,color);Putpixel(-y,-x,color);}圓的掃描轉(zhuǎn)換簡單方程生成圓弧中點(diǎn)畫圓算法簡單方程產(chǎn)生圓弧(1)給定圓心在原點(diǎn)，利用其函數(shù)方程，直接離散計算為:X2+Y2=R2Y=Sqrt(R2-X2)在一定范圍內(nèi)，每給定一X值，可得一Y值。當(dāng)X取整數(shù)時，Y須取整。缺點(diǎn)：浮點(diǎn)運(yùn)算，開方，取整，不均勻。yx演示簡單方程產(chǎn)生圓弧(2)

顯然，確定x,y的初值及d值后，即可以增量方式獲得圓周上的坐標(biāo)，然后取整可得像素坐標(biāo)。但要采用浮點(diǎn)運(yùn)算、乘法運(yùn)算、取整運(yùn)算。圓的極坐標(biāo)方程為：42假設(shè)中心在原點(diǎn)，半徑為整數(shù)R的圓的lb區(qū)域的1／8圓部分，現(xiàn)討論如何從x＝０到x＝y(tǒng)順時針確定離理想圓弧最近的像素集合。假設(shè)x坐標(biāo)為xp的各像素點(diǎn)中與該圓弧最近者已確定，為P（xp,yp），那么，下一個與圓弧最近的像素只能是正右方的P1(xp+1,yp)，或右下方的P2（xp+1,yp-1）兩者之一。令M為P1和P2的中點(diǎn)，易知M的坐標(biāo)為（xp+1,yp-0.5）。顯然，若M在圓內(nèi)，則P1離圓弧近，應(yīng)取為下一個像素；否則應(yīng)取P2。3.3.2中點(diǎn)畫圓算法43將M點(diǎn)的坐標(biāo)代入圓方程F(x,y)=x2+y2-R2=0，得到判別式d：可知:d>0點(diǎn)M在圓外,應(yīng)取p2作為下一個像素d=0點(diǎn)M在圓上,約定取p2作為下一個像素d<0點(diǎn)M在圓內(nèi),應(yīng)取p1作為下一個像素即根據(jù)每一個像素計算判別式d,根據(jù)它的符號確定下一個像素.與中點(diǎn)畫線一樣,d也可以采用增量計算:3.3.2中點(diǎn)畫圓算法在d≥0的情況下，取右下方像素P2，再下一個像素取哪個應(yīng)計算:

故d的增量為2(xp-yp)+5在d<0的情況下，取正右方像素P1，再下一個像素取哪個應(yīng)計算:

故d的增量為2xp+33.3.2中點(diǎn)畫圓算法這樣得到了dp的遞推公式，從中可以導(dǎo)出圓的中點(diǎn)算法。當(dāng)然，還需要一個初始條件。在1b區(qū)域，假定x0=0,y0=R。則3.3.2中點(diǎn)畫圓算法如果半徑是整數(shù),則可以對d0簡單取整:d0=1-R(R是整數(shù))46voidmidpointcircle(intr,intcolor){intx,y;floatd;x=0;y=r;d=1.25-r;Circle_Points(x,y,color);while(x<=y){if(d<0)d=d+2*x+3;else{d=d+2(x-y)+5;y--;}x++;Circle_Points(x,y,color);}}使用中點(diǎn)畫圓算法繪制一個1/8光柵圓程序voidCircle_Points(intx,inty,intcolor){Putpixel(x,y,color);Putpixel(x,-y,color);Putpixel(-x,y,color);Putpixel(-x,-y,color);Putpixel(y,x,color);Putpixel(y,-x,color);Putpixel(-y,x,color);Putpixel(-y,-x,color);}例:利用中點(diǎn)畫圓算法,繪制一條圓弧:中心在坐標(biāo)原點(diǎn),半徑R為10,從

x=0到x=y的1/8圓弧.解判別式d的初始值為:d0=1-R=1-10=-9

初始點(diǎn)(x0,y0)的坐標(biāo)為(0,10),則

2x0=0,2y0=20

繪制初始點(diǎn)(0,10),并確定沿圓弧路徑的其余像素位置為:xyd010-9110-6210-1310649-3598685

776在d≥0的情況下，取右下方像素,d的增量:d=d+2(x-y)+5在d<0的情況下，取正右方像素,d的增量:d=d+2x+348為了進(jìn)一步提高算法的效率，可以將上面的算法中的浮點(diǎn)數(shù)改寫成整數(shù)，將乘法運(yùn)算改成加法運(yùn)算，即僅用整數(shù)實(shí)現(xiàn)中點(diǎn)畫圓法。使用e=d-0.25代替de0=1-R3.3.2中點(diǎn)畫圓算法(y,x)(-y,x)(-x,y)(-x,-y)(-y,-x)(y,-x)(x,-y)

八分法畫圓51解決問題：圖1/8圓弧3.3.2中點(diǎn)畫圓算法圖5.13中點(diǎn)Bresenham畫圓的原理Bresenham算法是生成圓弧算法的最有效算法之一。 設(shè)圓的半徑為r。先考慮圓心在（0,0），并從x=0,y=r開始的順時針方向的1/8圓周的生成過程。在這種情況下，x每步增加1。從x=0開始，到x=y結(jié)束。即有：

xi+1=xi+1

相應(yīng)的yi+1則在兩種可能中選擇：

yi+1=yi，或者yi+1=yi-1

選擇的原則是考察精確值y靠近yi還是靠近yi-1。3.3.3Bresenham畫圓法3.3.3Bresenham畫圓法y的計算式為:y2=r2-(xi+1)2令d1、d2分別為yi到y(tǒng),yi-1到y(tǒng)的距離，可知：

d1=yi2-y2=yi2-r2+(xi+1)2d2=yi2-(yi-1)2=r2-(xi+1)2-(yi-1)2令判別式di+1=d1-d2,并代入d1、d2,則有判別式：

di+1=2(xi+1)2+yi2+(yi-1)2-2r2

判斷式d的初始值為：(x0=0,y0=r,代入上式得)d0=3-2r。如果di+1>=0，則y=yi-1，選擇右下方點(diǎn)(p2)

xi+1=xi+1,yi+1=yi-1,

di+2=2(xi+2)2+(yi-1)2+(yi-2)2-2r2=2xi2+8xi+8+yi2+yi2-2yi+1-4yi+4-2r2=di+1+

4(xi-yi)+10如果di+1<0，則y=yi，選擇正右方點(diǎn)(p1)di+2=di+1+4xi+6通過比較距離的平方，避免平方根的計算Rd0=3-2r=3-20=-17

d1=-17+4*0+6=-11d2=-11+4*1+6=-1d3=-1+4*2+6=13d4=13+4*(3-10)+10=-5d5=-5+4*4+6=17d6=17+4*(5-9)+10=11例:Bresenham畫圓算法舉例圓半徑r=10如果di+1>=0，則y=yi-1，選擇右下方點(diǎn)(p2)

xi+1=xi+1,yi+1=yi-1

di+2=di+1+4(xi-yi)+10如果di+1<0，則y=yi，選擇正右方點(diǎn)(p1)xi+1=xi+1,yi+1=yi

di+2=di+1+4xi+6Bresenham生成圓弧的程序如下：

根據(jù)算法，可得Bresenham生成圓弧的程序如下：voidBresenham_Circle(intR,intcolor){intx,y,d;x=0;y=R;d=3-2*R;while(x<y){Circle_Points(x,y,color);if(d<0)d+=4*x+6;else{d+=4*(x-y)+10;y-=1;}x++;}

if(x==y)Circle_Points(x,y,color);}voidCircle_Points(intx,inty,intcolor){Putpixel(x,y,color);Putpixel(x,-y,color);Putpixel(-x,y,color);Putpixel(-x,-y,color);Putpixel(y,x,color);Putpixel(y,-x,color);Putpixel(-y,x,color);Putpixel(-y,-x,color);}演示作業(yè)講解:P36/2.4答:22*22*22=64P89/3.13.1請用偽代碼程序描述使用DDA算法掃描轉(zhuǎn)換一條斜率介于45°和－45°（即|m|>1)之間的直線所需的步驟。解答：假設(shè)線段的兩個端點(diǎn)（x1,y1）和（x2，y2），且y1<y2

int

x,y=y1; floatxf=x1,m=(x2－x1)/(y2–y1)；

while(y<=y2) { x=int(xf+0.5);

setPixel(x,y);

xf=xf+m;y++;}區(qū)域dxdy1a(1)1k1b(2)1/k12a(4)-1k2b(3)-1/k13a(5)-1-k3b(6)-1/k-14a(8)1-k4b(7)1/k-157補(bǔ)充題:請用偽代碼程序描述使用斜截式方程畫一條斜率介于45°和－45°（即|m|>1）之間的直線所需的步驟。

解答：假設(shè)線段的兩個端點(diǎn)為（x1，y1）和（x2，y2），且y1<y2 intx=x1,y=y1; floatxf, m=（y2－y1）/（x2－x1）, b=y1

－mx1; setPixel(x,y);

/*畫一個像素點(diǎn)*/ while(y<y2) { y++; xf=(y－b)/m; x=int(xf+0.5); setPixel(x,y);}

DDA的算法基本思想

選定x2－x1和y2－y1中較大者作為步進(jìn)方向（假設(shè)x2－x1較大）取該方向上的Δx為一個像素單位長，即x每次遞增一個像素，然后利用前面公式計算相應(yīng)的y值，把每次計算出的（xi＋l,yi＋1）經(jīng)取整后順序輸出到顯示器，則得光柵化后的直線。為什么取x2－xl和y2－y1中較大者步進(jìn)方向？此圖中Y2－Y1＝8>X2-X1=4若取△x為一個像素單位，則由yi＋1=yi＋·Δx則可能出現(xiàn)像素點(diǎn)不連續(xù)的情況若取△y為一個像素單位，則由xi＋1=xi＋·Δy則像素點(diǎn)連續(xù)今天作業(yè)”P893.2,3.43.2

請指出用Bresenham算法掃描轉(zhuǎn)換從像素點(diǎn)（1，1）到（8，5）的線段時的像素位置。

dx=x2-x1=8-1=7dy=y2-y1=5-1=4d1=2*dy-dx=8-7=1td1=2(dy-dx)=2(4-7)=-6td2=2*dy=2*4=8d1=2dy-dxd>=0,x=x+1,y=y+1di+1=d+2(dy-dx)td1=2(dy-dx)d<0,x=x+1,y=ydi+1=d+2dytd2=2*dy61下周上機(jī)時間:10月27日地點(diǎn):15#407機(jī)房內(nèi)容:3.4區(qū)域填充區(qū)域填充即給出一個區(qū)域的定義，要求對此區(qū)域范圍內(nèi)的所有像素賦予指定的顏色代碼。只要算法設(shè)計合理，運(yùn)用著色的方法就可以使光柵圖形的畫面色彩逼真，更能形象而具有真實(shí)感地利用二維光柵技術(shù)顯示三維圖形。多邊形可以是構(gòu)成平面圖形的幾何元素，也可以是構(gòu)成三維物體表面的投影。如果物體的表面是曲面，也可由適當(dāng)?shù)亩噙呅稳ケ平?。因此，區(qū)域填充中最常用的是多邊形填色。對于區(qū)域填充來說，它要解決兩個問題：①確定需要填充哪些象素，②確定用什么顏色或圖案。區(qū)域填充就是將區(qū)域內(nèi)的像素置成新的顏色值或圖案處于一個封閉輪廓線內(nèi)的所有像素點(diǎn)即構(gòu)成一個區(qū)域3.4區(qū)域填充3.4.1區(qū)域的表示和類型在計算機(jī)圖形學(xué)中，區(qū)域有兩種重要的表示方法：頂點(diǎn)表示和點(diǎn)陣表示。