計算機圖形學(xué)PPT課件

.,第二章光柵圖形學(xué),2.1直線段的掃描轉(zhuǎn)換算法2.2圓弧的掃描轉(zhuǎn)換算法2.3多邊形的掃描轉(zhuǎn)換與區(qū)域填充2.4字符2.5裁剪2.6反走樣2.7消隱,.,2.1直線段的掃描轉(zhuǎn)換算法,數(shù)值微分法（DDA算法）中點畫線法Bresenham畫線算法,.,數(shù)值微分法（DigitalDifferentialAnalyzer）,基本思想假定直線的起點、終點分別為：（x0,y0),(x1,y1)，且都為整數(shù)。已知過端點P0(x0,y0),P1(x1,y1)的直線段L(P0,P1);直線斜率為,按照y=kx+b計算相應(yīng)的y坐標(biāo)。,.,數(shù)值微分(DDA)法,設(shè)步長為x，有xi+1=xi+x則yi+1=kxi+1+b=kxi+kx+b=yi+kx因為光柵點的單位是1，對每一個x方向的增量x=1時;有yi+1=yi+k。即：當(dāng)x每遞增1，y遞增k(即直線斜率)。經(jīng)過round()函數(shù)處理得到顯示的光柵點(x,round(y)坐標(biāo)。xi+1=xi+1yi+1=yi+k,.,voidDDALine(intx0,inty0,intx1,inty1,intcolor)intx；floatdx,dy,y,k;dx=x1-x0;dy=y1-y0;k=dy/dx;y=y0;for(x=x0;xx1;x+)drawpixel(x,int(y+0.5),color);y=y+k;,數(shù)值微分(DDA)法,例：畫直線段P0(0,0)-P1(5,2),xy+0.5int(y+0.5),00+0.50,10.4+0.50,20.8+0.51,31.2+0.51,41.6+0.52,52.0+0.52,優(yōu)點：在同一坐標(biāo)上,不可能連續(xù)停留兩次。缺點：在此算法中，y、k必須是float，且每一步都必須對y進行舍入取整，不利于硬件實現(xiàn)。,算法特點:,注意：網(wǎng)格點表示像素,.,增量算法：在一個迭代算法中，如果每一步的x、y值是用前一步的值加上一個增量來獲得，則稱為增量算法。DDA算法就是一個增量算法。缺點注意上述分析的算法僅適用于k1的情形。在這種情況下，x每增加1,y最多增加1。當(dāng)k1時，必須把x，y地位互換，y每增加1，x相應(yīng)增加1/k。在此算法中，y、k必須是float，且每一步都必須對y進行舍入取整，有浮點數(shù)取整運算,不利于硬件實現(xiàn)。效率低,數(shù)值微分(DDA)法,.,原理：,假定直線斜率0取P2。M在Q的上方-P1離直線更近更近-取P1M與Q重合，P1、P2任取一點。,算法原理,如何判斷M點在Q點上方還是在Q點下方？,.,已知：線段兩端點(x0,y0)，(x1,y1)直線方程為：F(x,y)=ax+by+c=0其中a=y0-y1,b=x1-x0,c=x0y1-x1y0,M,中點畫線法,欲判斷M點是在Q點上方還是在Q點下方，只需把M代入F(x,y),并檢查它的符號。,.,構(gòu)造判別式：d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c當(dāng)d0，M在直線(Q點)上方，取右方P1；當(dāng)d=0，選P1或P2均可，約定取P1；能否采用增量算法呢？,中點畫線法,.,若d0，中點M在直線上方，取正右方像素P1(Xp+1,Yp)再下一個像素的判別式為：d1=F(Xp+1)+1,Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c=d+ad的增量為a若d0，中點M在直線下方，取右上方像素P2(Xp+1,Yp+1)再下一個像素的判別式為：d2=F(Xp+1)+1,(Yp+1)+0.5)=a(Xp+2)+b(Yp+1.5)+c=d+a+bd的增量為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ù)，提高效率。優(yōu)點：只有整數(shù)運算，不含乘除法可用硬件實現(xiàn),中點畫線法,因(X0,Y0)在直線上，所以F(X0,Y0)=0,.,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(xx1)if(d0)x+;y+;d+=d2;elsex+;d+=d1;drawpixel(x,y,color);/*while*/*midPointLine*/,中點畫線法,例：用中點畫線法P0(0,0)P1(5,2)a=y0-y1=-2b=x1-x0=5d0=2a+b=1d1=2a=-4d2=2(a+b)=6,Ixiyid,1001,210-3,3213,431-1,5425,6521,.,Bresenham算法,基本思想過各行各列像素中心構(gòu)造一組虛擬網(wǎng)格線。按直線從起點到終點的順序計算直線與各垂直網(wǎng)格線的交點，然后根據(jù)誤差項的符號確定該列像素中與此交點最近的像素。,.,設(shè)直線方程為：，其中k=dy/dx。因為直線的起始點在像素中心，所以誤差項d的初值d00。X下標(biāo)每增加1，d的值相應(yīng)遞增直線的斜率值k，即ddk。一旦d1，就把它減去1，這樣保證d在0、1之間。當(dāng)d0.5時，最接近于當(dāng)前像素的右上方像素（xi1，yi1）而當(dāng)d0)thene=e-2x,.,算法步驟：1.輸入直線的兩端點P0(x0,y0)和P1(x1,y1)。2.計算初始值x、y、e=-x、x=x0、y=y0。3.繪制點(x,y)。4.e更新為e+2y，判斷e的符號。若e0，則(x,y)更新為(x+1,y+1)，同時將e更新為e-2x；否則(x,y)更新為(x+1,y)。5.當(dāng)直線沒有畫完時，重復(fù)步驟3和4。否則結(jié)束。,Bresenham算法,.,程序如下：BresenhamLine(intx0,inty0,intx1,inty1,intcolor)intx,y,dx,dy,e;dx=x1-x0;dy=y1-y0;e=-dx;x=x0;y=y0;for(i=0;i=0)y+;e=e-2*dx;,優(yōu)點整數(shù)運算，速度快精度高乘2運算可用移位實現(xiàn)，適于硬件實現(xiàn),.,斜率不同時：以上討論的是0k1的情況，即0yx的情況；若是0xy的情況，則需將x和y的位置交換。方向不同時：若y0或x0時，要將算法中的yy1換成yy1、xx1換成xx1。,思考討論：,.,幾種畫線算法的比較,DDA算法直觀，易于實現(xiàn)，但是x、y、和k必須用浮點數(shù)表示，而且每一步都需要對x和y進行舍入取整，不利于硬件實現(xiàn)。中點算法可以替換成整數(shù)運算，便于硬件實現(xiàn)。Bresenham算法不計算斜率，不用浮點數(shù)，只做整數(shù)的加減運算或乘2運算，而乘2運算可以用移位操作來實現(xiàn)，因此Bresenham算法是速度最快的。,.,實驗一直線的生成,在VisualC+6.0環(huán)境中設(shè)計MFC單文檔程序，利用消息處理函數(shù)，搭建能運行圖形算法程序的平臺。實現(xiàn)直線段的3種生成算法：DDA算法(考慮k大于或小于等于1的情況)、中點法和Bresenham算法（原算法和改進算法）。,.,第二章光柵圖形學(xué),2.1直線段的掃描轉(zhuǎn)換算法2.2圓弧的掃描轉(zhuǎn)換算法2.3多邊形的掃描轉(zhuǎn)換與區(qū)域填充2.4字符2.5裁剪2.6反走樣2.7消隱,.,2.2圓弧的掃描轉(zhuǎn)換算法,直接離散生成算法中點畫圓法Bresenham畫圓算法橢圓的中點畫法,.,圓弧掃描算法,下面僅以圓心在原點、半徑R為整數(shù)的圓為例，討論圓的生成算法。假設(shè)圓的方程為：x2+y2=R2圓的八對稱性可以用四條對稱軸x0，y0，xy，xy把圓分成8等份。只要繪制出第一象限內(nèi)的1/8圓弧，根據(jù)對稱性就可繪制出整圓，這稱為八分法畫圓算法。,P（y，x）P（y，x）,P（x,y）,P（x，y），P（y，x），P（y，x），P（x，y）。,假定第一象限內(nèi)的任意點為P（x，y），可以確定另外7個點：,.,圓弧掃描算法,兩種直接離散生成方法離散點開方運算離散角度三角函數(shù)運算缺點：計算量大所畫像素位置間的間距不一致、不均勻,.,圓弧掃描算法,SimpleCircle(intr,intcolor)intx,y;for（x=0;x=r;x+)y=Round(sqrt(r*r-x*x)；circlepoints(x,y,color);ParameterCircle(intr,intcolor)intx,y;for（floatt=0;t=/2;t+=0.05)x=Round(r*cos(t)；y=Round(r*sin(t)；circlepoints(x,y,color);,.,第二個8分圓P（Xp，Yp）P為當(dāng)前點亮像素，那么，下一個點亮的像素可能是P1（Xp+1，Yp）或P2（Xp+1，Yp-1)。,中點畫圓法,.,中點畫圓法,F(X,Y)=X2+Y2-R2=0中點M=(Xp+1,Yp-0.5)當(dāng)F(M)0時，M在圓內(nèi)，P1距離圓弧近，取P1當(dāng)F(M)0時，M在圓外，P2距離圓弧近，取P2,.,中點畫圓法,若d=0,取P1為下一像素，再下一像素的判別式為初始像素是（0,R），判別式d的初值為,P1(Xp+1,Yp),P2(Xp+1,Yp-1),.,算法步驟：1.輸入圓的半徑R。2.計算初始值d=1.25-R、x=0、y=R。3.繪制點(x,y)及其在八分圓中的另外七個對稱點。4.判斷d的符號。若d0，則先將d更新為d+2x+3，再將(x,y)更新為(x+1,y)；否則先將d更新為d+2(x-y)+5，再將(x,y)更新為(x+1,y-1)。5.當(dāng)xy時，重復(fù)步驟3和4。否則結(jié)束。,中點畫圓法（一般算法）,.,MidpointCircle(intr,intcolor)intx,y;floatd;x=0;y=r;d=1.25-r;circlepoints(x,y,color);while(xy)if(d0)d+=2*x+3;x+elsed+=2*(x-y)+5;x+;y-;circlepoints(x,y,color);,中點畫圓法（一般算法）,思考題：如何將上面算法中的浮點數(shù)改寫成整數(shù)，將乘法運算改成加法運算，即僅用整數(shù)實現(xiàn)中點畫圓法，以進一步提高算法的效率？,.,為了進一步提高算法的效率，可以將上面的算法中的浮點數(shù)改寫成整數(shù)，將乘法運算改成加法運算，即僅用整數(shù)實現(xiàn)中點畫圓法。因為中點畫圓算法的半徑是整數(shù)，而用于該算法符號判別的變量d采用浮點運算，會花費較多的時間。為了將其改造成整數(shù)計算，對d作如下變換：使用d=d-0.25代替dd=1-R判別式d0等價于d-0.25,在d為整數(shù)的情況下，d-0.25與d0等價，仍將d寫成d，可得到中點圓整數(shù)算法,中點畫圓法,.,算法步驟：1.輸入圓的半徑R。2.計算初始值d=1-R、x=0、y=R。3.繪制點(x,y)及其在八分圓中的另外七個對稱點。4.判斷d的符號。若d0，則先將d更新為d+2x+3，再將(x,y)更新為(x+1,y)；否則先將d更新為d+2(x-y)+5，再將(x,y)更新為(x+1,y-1)。5.當(dāng)xy時，重復(fù)步驟3和4。否則結(jié)束。程序,中點畫圓法（整數(shù)算法）,.,MidpointCircleInt(intr,intcolor)intx,y,d;x=0;y=r;d=1-r;circlepoints(x,y,color);while(xy)if(d0)d+=2*x+3;x+elsed+=2*(x-y)+5;x+;y-;circlepoints(x,y,color);,中點畫圓法（整數(shù)算法）,.,如圖中點Pi-1是已選中的一個表示圓弧上的點，根據(jù)弧的走向，下一個點應(yīng)該從Hi或者Li中選擇。選擇的原則是：考察精確值是靠近Hi還是Li，即精確值y是靠近yi還是yi-1假設(shè)圓的半徑為R，計算式為y2=R2-(xi+1)2令d1、d2分別為yi(Hi)到y(tǒng)和yi-1(Li)到y(tǒng)的距離，可知：d1=yi2-y2=yi2-R2+(xi+1)2d2=y2-(yi-1)2=R2-(xi+1)2-(yi-1)2,Bresenham畫圓算法,（1）如果di0，則y=yi，即選擇當(dāng)前像素的正右方作為下一個像素，遞推公式為：（2）如果di0，則y=yi-1，即選擇當(dāng)前像素的右下方作為下一個像素，遞推公式為：（3）計算判別式的初值。初始點為（0，R），則：,令判斷式di=d1-d2，并代入d1、d2，則有：,.,Bresenham畫圓算法,算法步驟：1.求誤差初值d1=3-2r，i=1，畫點（0，r）。2.求下一個光柵位置，其中xi+1=xi+1，如果di0：,判別式遞推公式為：,判別式的初始值,p(x,i,y,i,),p,l,(x,i,y,i-1,),p,r,(x,i+1,y,i-1,),M,(x,i+1,y,i-0.5,),下半部分橢圓弧的繪制原理,再來推導(dǎo)橢圓弧下半部分的繪制公式原理,設(shè)橢圓當(dāng)前點為pi(xi,yi),對應(yīng)的下一候選像素是正下方的pl(xi,yi-1),或右下方的pr(xi+1,yi-1),判別式其中點是M(xi+0.5,yi-1),若d20，中點在橢圓外，取正下方像素Pl(xi,yi-1)若d20，中點在橢圓內(nèi)，取右下方像素Pr