《計算機(jī)圖形學(xué)》課程實驗張玉娟實驗一直線段生成算法實現(xiàn)1、數(shù)值微分法（DDA）基本思想：從直線段的起點像素出發(fā),依據(jù)直線的微分方程依次確定描述直線的各個像素點。微分方程:dy/dx=m,yi+1=yi+m(xi+1-xi)若xi+1=xi+1yi+1=yi+m(0<m<1)算法原理：設(shè)一直線段的起點和終點坐標(biāo)分別為(xs,ys)和(xe,ye)。則直線段在X和Y方向的增量分別為：△x=xe-xs，△y=ye-ys設(shè)△t=max(|△x|,|△y|)取時間步長為1/△t,若當(dāng)前像素點坐標(biāo)為(xi,yi),則下一個像素點的坐標(biāo)可由以下兩式確定：xi+1=xi+dx=xi+Dx/Dtyi+1=yi+dy=yi+Dy/Dt2、中點直線生成算法:假定直線斜率0<m<1，且已確定點亮象素點P（Xi,Yi）,則下一個與直線最接近的像素只能是P1點或P2點。設(shè)M為中點，Q為交點，現(xiàn)需確定下一個點亮的象素。當(dāng)M在Q的下方->P2離直線更近更近->取P2。M在Q的上方->P1離直線更近更近->取P1M與Q重合，P1、P2任取一點。設(shè)直線方程為：ax+by+c=0其中a=y0-y1,b=x1-x0,c=x0y1-x1y0F(x,y)=0點在直線上面F(x,y)>0點在直線上方F(x,y)<0點在直線下方

欲判斷M點是在Q點上方還是在Q點下方，只需把M代入F(x,y),并檢查它的符號。令d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c當(dāng)d<0，M在直線下方，取右上方P2；當(dāng)d>0，M在直線上方，取右方P1；當(dāng)d=0，選P1或P2均可，約定取P1；若d0->M在直線上方->取P1;此時再下一個象素的判別式為d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c=a(xp+1)+b(yp+0.5)+c+a=d+a；增量為a若d<0->M在直線下方->取P2;此時再下一個象素的判別式為d2=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=a(xp+1)+b(yp+0.5)+c+a+b=d+a+b；增量為a＋b

畫線從(x0,y0)開始，d的初值 d0=F(x0+1,y0+0.5)=a(x0+1)+b(y0+0.5)+c=F(x0,y0)+a+0.5b=a+0.5b由于只用d的符號作判斷，為了只包含整數(shù)運算,可以用2d代替d來擺脫小數(shù)，提高效率。同時d每次的增量也已相應(yīng)乘2操作。3、Bresenham畫線算法

基本思想：根據(jù)直線的斜率確定選擇X或者Y方向作為計長方向,在此方向上每次遞增一個單位步長(或者一個像素單位),另一個方向上是否同時產(chǎn)生一個單位增量由一個計算量很小的判別式來判斷。算法原理：以斜率在0~1之間的直線段為例，在第一象限內(nèi)piDC這種情況下,選擇X方向為計長方向，即增量dx=1。，設(shè)Pi(xi,yi)是已選定的離直線最近的像素,現(xiàn)在要決定Pi+1是D還是C顯然,若d<0.5,則C靠近直線,應(yīng)選C；若d>=0.5,則應(yīng)選D。(m=△y/△x)

令e=d-0.5(初值為m-0.5),即有：e<0時,選Pi+1(xi+1,yi),更新e=e+m;e>=0時,選Pi+1(xi+1,yi+1),更新e=e+m-1;為計算簡便(整數(shù)計算),將判別式e替換為e=2e△x;初值e=-△x結(jié)論：得到遞推公式e<0時,選Pi+1(xi+1,yi);e=e+2△ye>=0時,選Pi+1(xi+1,yi+1);e=e+2△y-2△x其中,△x=xe-xs;△y=ye-ys實驗二：圓生成算法的實現(xiàn)

1.圓的中點生成算法：利用圓的對稱性，只須討論1/8圓。第二個8分圓P（Xp,Yp）為當(dāng)前點亮象素，那么，下一個點亮的象素可能是P1（Xp+1，Yp）或P2（Xp+1，Yp+1)。構(gòu)造函數(shù)：F（X，Y）=X2+Y2-R2；則F（X，Y）=0（X，Y）在圓上；F（X，Y）<0（X，Y）在圓內(nèi)；F（X，Y）>0（X，Y）在圓外。設(shè)M為P1、P2間的中點，M=(Xp+1,Yp-0.5)F（M）<0->M在圓內(nèi)->取P1F（M）>=0->M在圓外->取P2令判別式d=F(M)=F(Yp+1,Yp-0.5)=(Yp+1)2+(Yp-0.5)2-R2若d<0,取P1d1=F(Xp+2,Yp-0.5)=(Xp+2)2+(Yp-0.5)2-R2=d+2Xp+3d的增量為2Xp+3d>=0,取P2d2=F(xp+2,yp-1.5)=(xp+2)2+(yp-1.5)2-R2

=d+（2xp+3）+（-2yp+2）d的增量為2(xp-yp)+5

d的初值:d0=F(1,R-0.5)=1+(R-0.5)2-R2=1.25–R將d=0與d>0看成一種情況，每次d的增量為整型值，因此此時0.25對d的符號沒有影響，可將d的初始值定為1-R。2.圓的Bresenham生成算法Pi-1HiLi應(yīng)取Hi還是取LiB現(xiàn)在從A點開始向右下方逐點來尋找弧AB要用的點。如圖中點Pi-1是已選中的一個表示圓弧上的點，根據(jù)弧AB的走向，下一個點應(yīng)該從Hi或者Li中選擇。顯然應(yīng)選離AB最近的點作為顯示弧AB的點。假設(shè)圓的半徑為R，顯然，當(dāng)xhi2+yhi2-R2≥R2-(xli2+yli2)時，應(yīng)該取Li。否則取Hi。令di=xhi2+yhi2+xli2+yli2-2R2顯然，當(dāng)di≥0時應(yīng)該取Li。否則取Hi。剩下的問題是如何快速的計算di。設(shè)圖中Pi-1的坐標(biāo)為(xi-1,yi-1)，則Hi和Li的坐標(biāo)為(xi,yi-1)和(xi,yi-1-1)di=xi2+(yi-1)2+xi2+(yi-1-1)2-2R2=2xi2+2yi-12-2yi-1-2R2di+1=(xi+1)2+yi2+(xi+1)2+(yi-1)2-2R2=2xi2+4xi+2yi2-2yi-2R2+3當(dāng)di<0時取Hiyi=yi-1，di+1=di+4xi-1+6當(dāng)di≥0時取Liyi=yi-1-1，di+1=di+4(xi-1-yi-1)+10

易知x0=0，y0=R,x1=x0+1因此d0=12+y02+12+(y0-1)2-2R2

=3-2y0=3-2R實驗三二維圖形幾何變換的實現(xiàn)1.平移變換：將平面上的點(x,y)沿平行于x軸方向移動Tx，沿平行于y軸方向移動Ty后，得到點(x’,y’)，則有：x’=x+Txy’=y+Ty2.縮放變換：相對于原點將平面上的點(x,y)，沿x軸方向乘以常數(shù)Sx，沿y方向乘以常數(shù)Sy后，得到點(x’,y’)，則有：x’=x×Sxy’=y×Sy3.旋轉(zhuǎn)變換：將圖形相對于原點轉(zhuǎn)動一定的角度。給定以逆時針方向為正方向，假設(shè)(x,y)相對于原點旋轉(zhuǎn)角后得到點(x’,y’),則有：x’=x×cosA-y×sinAy’=x×sinA+y×cosA

4.對稱變換將圖形相對于x軸、y軸、、、原點作對稱圖形得到原圖形的變換圖形，假設(shè)點經(jīng)對稱變換后得到新點則有：①相對于x軸對稱，②相對于y軸對稱，③相對于對稱，④相對于對稱，⑤相對于原點對稱，5.錯切變換錯切包括沿x方向錯切和沿y方向錯切,點(x,y)沿x軸方向錯切的系數(shù)為b，沿y軸方向錯切的系數(shù)為d，得到點(x’,y’)，則有：x’=x+b×yy’=y+d×x實驗四Bezier曲線生成算法的實現(xiàn)1.二次Bezier曲線方程: