二維基本圖形生成

1、第二講 二維基本圖形生成所謂圖元的生成，是指完成圖元的參數(shù)表示形式（由圖形軟件包的使用者指定）到點陣表示形式（光柵顯示系統(tǒng)刷新時所需的表示形式）的轉(zhuǎn)換。通常也稱掃描轉(zhuǎn)換圖元1 簡單的二維圖形顯示流程2 直線段的掃描轉(zhuǎn)換3 圓弧的掃描轉(zhuǎn)換4 易畫曲線的正負(fù)法5 線畫圖元的屬性控制8/20/20221掃描轉(zhuǎn)換直線段 DDA算法 中點畫線法 Bresenham算法圓弧、橢圓弧掃描轉(zhuǎn)換 中點算法 Bresenham算法 內(nèi)接多邊形迫近法* 等面積多邊形逼近法*8/20/202221 簡單的二維圖形顯示流程8/20/20223圖形顯示前需要：掃描轉(zhuǎn)換+裁剪 裁剪 -掃描轉(zhuǎn)換：最常用，節(jié)約計算時間。 掃描

2、轉(zhuǎn)換 -裁剪：算法簡單； 掃描轉(zhuǎn)換到畫布 -位塊拷貝：算法簡單，但耗時耗內(nèi)存。常用于字符顯示。8/20/202242 直線段的掃描轉(zhuǎn)換 目標(biāo)：求與直線段充分接近的像素集 兩點假設(shè)直線段的寬度為1直線段的斜率: 像素間均勻網(wǎng)格整型坐標(biāo)系8/20/20225基本圖形點陣轉(zhuǎn)換算法評價所顯示圖形的精度算法的時間和空間復(fù)雜性 兩者沖突，權(quán)衡折衷8/20/20226 描繪線條圖形的要求直線段要顯得筆直線段端點位置要準(zhǔn)確線段的亮度要均勻轉(zhuǎn)換算法速度要快8/20/20227條件：待掃描轉(zhuǎn)換的直線段：斜率：直線方程：直接求交算法：劃分區(qū)間x0,x1:計算縱坐標(biāo)：取整：DDA（ digital different

3、ial analyzer）算法8/20/20228復(fù)雜度：乘法+加法+取整DDA算法（增量算法）復(fù)雜度：加法+取整程序8/20/20229DDA畫線算法程序void LineDDA(int x0,int y0,int x1,int y1,int color) /* 假定x0 x1,-1=k=1 */ int x,y； float dx, dy, k; dx= float(x1-x0); dy= float(y1-y0); k=dy/dx; y=y0; for(x=x0; x 1時，必須把x，y地位互換，y每增加1，x相應(yīng)增加1/k。特點2 在這個算法中，y與k必須用浮點數(shù)表示，而且每一步都要對

4、y進(jìn)行四舍五入后取整。這使得它不利于硬件實現(xiàn) 8/20/202212改進(jìn)算法（增量DDA） 增加斜率判斷并改變循環(huán)參數(shù)8/20/202213DDA畫線算法程序（改進(jìn)）void LineDDA(int x0,int y0,int x1,int y1,int color) int x,y；float dx, dy,k,l,m; dx= float(x1-x0); dy= float(y1-y0); k=dy/dx; if abs(k)1) for(x=x0; x= x1, x+) Setpixel(x, int(y+0.5), color); y+=k; else for(y=y0; y x1怎么

5、辦？8/20/202214DDA直線生成算法的偽語言描述如下： begin if abs(x2x1)abs(y2y1) then lenghtabs(x2x1) else lenghtabs(y2y1) endif x(x2x1)/lenght y(y2y1)/lenght xx1 yy1 k1 while(klenght) putpixel(x,y) xxx yyy kk1 endwhile end8/20/202215DDA直線繪制的C+實現(xiàn)void DDA直線繪制(HDC hdc) int k; double x1=50,y1=50, x2=300,y2=350; double x,y,

6、deltx,delty,length; if (fabs(x2-x1)=fabs(y2-y1) length=fabs(x2-x1); else length=fabs(y2-y1); deltx=(x2-x1)/length; delty=(y2-y1)/length;x=x1; y=y1; k=1; while(k0; down: F(x, y)0; 直線的正負(fù)劃分性8/20/202219 欲判斷中M在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點上方，取P

7、1為下一個象素； 當(dāng)d=0，選P1或P2均可，約定取P1為下一個象素8/20/202220問題：判斷距直線最近的下一個象素點 構(gòu)造判別式：d=F(M)=F(Xp+1,Yp+0.5) 由d0，0可判定下一個象素，PP2P18/20/202221要判定再下一個象素，分兩種情形考慮： 1）若d0，取正右方象素P1，再下一個象素判定， 由：d1=F(Xp+2,Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c=d+a，d的增量是a 2）若d0，取右上方象素P2，再下一個象素，由：d2=F(Xp+2,Yp+1.5)=d+a+b d的增量為a+bP2PP18/20/202222d的初始值 d0=F(X

8、0+1,Y0+0.5)=F(X0,Y0)+a+0.5*b 因(X0,Y0)在直線上，F(xiàn)(X0，Y0)=0,所以，d0=a+0.5*bd的增量都是整數(shù)，只有初始值包含小數(shù)，可以用2d代替d, 2a改寫成a+a。算法中只有整數(shù)變量，不含乘除法，可用硬件實現(xiàn)。8/20/202223中點算法程序 MidPointLine(x0,y0,x1,y1,color)int x0,y0,x1,y1,color; int a,b,d1,d2,x,y; a = y0-y1; b = x1 x0; d = 2 * a +b; d1 = 2*a; d2 = 2*(a+b); x = x0; y = y0; SetPix

9、el(x,y,color); while (xx1) if (d0) x+; y+; d +=d2; else x+; d +=d1;SetPixel(x,y,color);8/20/202224舉例 用中點畫線方法掃描轉(zhuǎn)換連接兩點P0（0,0）和P1（5,2）的直線段a=y0-y1=-2; b=x1-x0=5;d0=2*a+b=1; d1=2*a=-4; d2=2*(a+b)=6x y d0 0 11 0 -3 d12 1 3 d23 1 -1 d14 2 5 d25 2 18/20/202225畫線Bresenham算法 Bresenham算法是計算機圖形學(xué)領(lǐng)域使用最廣泛的直線掃描轉(zhuǎn)換算法

10、。該方法類似于中點法，由誤差項符號決定下一個象素取右邊點還是右上點。 本算法由Bresenham在1965年提出該方法最初是為數(shù)字繪圖儀設(shè)計的，后來被廣泛地應(yīng)用于光柵圖形顯示和數(shù)控（NC）加工算法原理如下：過各行各列象素中心構(gòu)造一組虛擬網(wǎng)格線。按直線從起點到終點的順序計算直線與各垂直網(wǎng)格線的交點，然后確定該列象素中與此交點最近的象素。該算法的巧妙之處在于采用增量計算，使得對于每一列，只要檢查一個誤差項的符號，就可以確定該列的所求象素。 8/20/202226工作原理：根據(jù)直線的斜率在x或y的方向每次都只遞增一個象素單位，另一個方向的增量為0或18/20/202227設(shè)直線方程為y=kx+b，其

11、中k=dy/dx。 假設(shè)x列的象素已經(jīng)確定為xi，其行坐標(biāo)為yi。那么下一個象素的列坐標(biāo)為xi1，而行坐標(biāo)要么不變?yōu)閥i，要么遞增1為yi1。是否增1取決于如圖所示誤差項d的值。因為直線的起始點在象素中心，所以誤差項d的初值d00。X下標(biāo)每增加1，d的值相應(yīng)遞增直線的斜率值k，即ddk。當(dāng)d0.5時，直線與xi1列垂直網(wǎng)格交點最接近于當(dāng)前象素（xi，yi）的右上方象素（xi1，yi1）；而當(dāng)d0.5時，更接近于右方象素（xi1，yi）。8/20/202228為方便計算，令ed0.5，e的初值為0.5，增量為k。當(dāng)e0時，取當(dāng)前象素（xi，yi）的右上方象素（xi1，yi1）；而當(dāng)e0時，更接近

12、于右方象素（xi1，yi）。 8/20/202229Bresenham畫線算法程序void Bresenhamline (int x0,int y0,int x1, int y1,int color) int x, y, dx, dy; float k, e; dx = x1-x0;dy = y1- y0; k=dy/dx; e=-0.5;x=x0;y=y0; for (i=0; i= 0) y+, e=e-1; 8/20/202230舉例：用Bresenham方法掃描轉(zhuǎn)換連接兩點P0（0,0）和P1（5,2）的直線段。x y e0 0 -0.51 0 -0.1 0.3-12 1 -0.73

13、1 -0.3 0.1-14 2 -0.95 2 -0.58/20/202231上述bresenham算法在計算直線斜率與誤差項時用到小數(shù)與除法。可以改用整數(shù)以避免除法。由于算法中只用到誤差項的符號，因此可作如下替換：e=e*2dx改進(jìn)的Bresenham畫線算法程序：void InterBresenhamline (int x0,int y0,int x1, int y1,int color) dx = x1-x0; dy = y1- y0; e=-dx; x=x0; y=y0; for (i=0; i= 0) y+; e=e-2*dx; 8/20/202232掃描轉(zhuǎn)換圓弧處理對象：圓心在原點

14、的圓弧圓的八對稱性8/20/202233兩種直接離散方法：離散點: 離散角度:開根，三角函數(shù)運算，計算量大，不可取。 8/20/202234掃描轉(zhuǎn)換圓弧圓弧的正負(fù)劃分性圓弧外的點：F(X，Y)0圓弧內(nèi)的點：F(X，Y)08/20/202235掃描轉(zhuǎn)換圓弧生成圓弧的中點算法考慮對象：第二個八分圓， 第一象限的八分之一圓弧 PP1P28/20/202236問題：與直線情形類似圓弧的隱函數(shù)：F(X,Y)=X2+Y2-R2=0 切線斜率m in -1,0中點 M=(Xp+1,Yp-0.5), 當(dāng)F(M)0時，M在圓內(nèi)，說明P1距離圓弧更近，取P1； 當(dāng)F(M)0時，P取P2P2P1P8/20/2022

15、37構(gòu)造判別式 d=F(M)=F(Xp+1,Yp-0.5)=(Xp+1)2+(Yp-0.5)2-R2 1）若d0，取P1，再下一個象素的判別式為： d1=F(Xp+2,Yp-0.5)=d+2Xp+3， 沿正右方向，d的增量為2Xp+3； 2）若d0，取P2，再下一個象素的判別式為： d2=F(Xp+2,Yp-1.5)=d+(2Xp+3)+(-2Yp+2) 沿右下方向，d的增量為2(Xp-Yp)+5d的初始值(在第一個象素(0,R)處),d0=F(1, R-0.5)=1.25-R算法中有浮點數(shù)，用e=d-0.25代替8/20/202238所以：初始化運算d0 = 1.25 R 對應(yīng)于 e 0=

16、1- R判別式 d 0 對應(yīng)于 e -0.25 又因為：e的初值e0為整數(shù)，運算過程中的分量也為整數(shù)，故e始終為整數(shù)所以： e -0.25 等價于 e 0程序如下（完全用整數(shù)實現(xiàn)）：MidpointCircle(r,color)Int r, color; int x,y,d; x = 0; y = r; d = 1-r; putpixcel(x,y,color); while( x y) if (d 0) d += 2*x+3; x+; else d += 2*(x-y)+5; x+ ; y-; putpixcel(x,y,color); 8/20/202239Bresenham畫圓算法（1/

17、7）順時針畫第一四分圓，下一步選擇哪個點？基本思想：通過比較像素與圓的距離平方來避免開方運算下一像素有3種可能的選擇mH=|(xi+1)2+yi2-R2|mD=|(xi+1)2+(yi-1)2-R2|mV=|xi2 +(yi-1)2-R2 |選擇像素的原則使其與實際圓弧的距離平方達(dá)到最小(xi,yi)HPiVD(xi+1,yi)(xi,yi-1)(xi+1,yi-1)8/20/202240Bresenham畫圓算法（2/7）圓弧與點(xi,yi)附近光柵網(wǎng)格的相交關(guān)系有5種右下角像素D (xi,yi)與實際圓弧的近似程度i=(xi+1)2+(yi-1)2-R2當(dāng)i0時，D在圓外，當(dāng)i=0時，D

18、在圓上，(xi,yi)HPiVD(xi+1,yi)(xi,yi-1)(xi+1,yi-1)8/20/202241Bresenham畫圓算法（3/7）當(dāng)i0時，D在圓內(nèi)，情形，選mH ，mD 中最小者d=mH - mD =|(xi+1)2+yi2-R2| - |(xi+1)2+(yi-1)2-R2| =(xi+1)2+yi2-R2 + (xi+1)2+(yi-1)2-R2 =2 (i+yi)-1若d0，則選D若d=0，則選H情形也適用8/20/202242Bresenham畫圓算法（4/7）當(dāng)i0時，D在圓外，情形，選mv ，mD 中最小者d=mD - mV =|(xi+1)2+(yi-1)2-

19、R2 | - |xi2+(yi-1)2-R2| =(xi+1)2+(yi-1)2-R2 + xi2+(yi-1)2-R2 =2 (i-xi)-1若d0，則選V若d=0，則選D情形也適用8/20/202243Bresenham畫圓算法（5/7）當(dāng)i=0時，D在圓上，按d判別，有d0，應(yīng)選D按d判別，有d0，應(yīng)選D8/20/202244Bresenham畫圓算法（6/7）當(dāng)i0，選D當(dāng)i0時,若d 0，選D 若d0，選V當(dāng)i=0時，選D8/20/202245Bresenham畫圓算法（7/7）判別式的遞推關(guān)系當(dāng)取H(xi+1,yi)時i+1=(xi+1+1)2+(yi-1)2-R2= i+2(xi

20、+1)+1當(dāng)取V(xi,yi-1)時i+1=(xi+1)2+(yi-1-1)2-R2= i-2(yi-1)+1當(dāng)取D(xi+1,yi-1)時i+1=(xi+1+1)2+(yi-1-1)2-R2= i+2(xi+1)-2(yi-1)+28/20/202246橢圓的掃描轉(zhuǎn)換F(x,y)=b2x2+a2y2-a2b2=0橢圓的對稱性，只考慮第一象限橢圓弧生成，分上下兩部分，以切線斜率為-1的點作為分界點。橢圓上一點處的法向：N(x,y) = (F)x i + (F)y j = 2b2 x i + 2a2 y j8/20/202247在上半部分,法向量的y分量大在下半部分,法向量的x分量大上半部分下半

21、部分法向量兩分量相等M1M2在當(dāng)前中點處，法向量（ 2b2 (Xp+1) ，2a2 (Yp-0.5)的y分量比x分量大,即： b2 (Xp+1) a2 (Yp-0.5), 而在下一中點，不等式改變方向，則說明橢圓弧從上部分轉(zhuǎn)入下部分8/20/202248橢圓的中點畫法與圓弧中點算法類似：確定一個象素后，接著在兩個候選象素的中點計算一個判別式的值，由判別式的符號確定更近的點先討論橢圓弧的上部分(Xp，Yp)中點(Xp+1,Yp-0.5)d1=F(Xp+1,Yp-0.5)= b2(Xp+1)2+a2(Yp-0.5)2-a2b28/20/202249根據(jù)d1的符號來決定下一像素是取正右方的那個，還是

22、右上方的那個。 若d10，中點在橢圓內(nèi)，取正右方象素，判別式更新為：d1=F(Xp+2,Yp-0.5)=d1+b2(2Xp+3)d1的增量為b2(2Xp+3)當(dāng)d10，中點在橢圓外，取右下方象素，更新判別式：d1=F(Xp+2,Yp-1.5)=d1+b2(2Xp+3)+a2(-2Yp+2)d1的增量為b2(2Xp+3)+a2(-2Yp+2)8/20/202250d1的初始條件：橢圓弧起點為(0，b)，第一個中點為(1,b-0.5) 初始判別式： d10=F(1,b-0.5)=b*b+a*a(-b+0.25)轉(zhuǎn)入下一部分，下一象素可能是一正下方或右下方，此時判別式要初始化。d2 = F(Xp+0

23、.5,Yp-1) = b2(Xp+0.5)2+a2(Yp-1)2-a2b2 若d2=0,則d2 = F(Xp+0.5,Yp-2) = d2 + a2(-2Yp+3) 下半部分弧的終止條件為 y = 08/20/202251程序：MidpointEllipe(a,b, color)int a,b,color; int x,y; float d1,d2; x = 0; y = b; d1 = b*b +a*a*(-b+0.25); putpixel(x,y,color); while( b*b*(x+1) a*a*(y-0.5) if (d10) if (d2 0) d2 +=b*b*(2*x+2

24、)+a*a*(-2*y+3); x+; y-； else d2 += a*a*(-2*y+3); y-; putpixel(x,y,color); 8/20/202253用正多邊形近似代替圓, 顯示多邊形的邊可用掃描轉(zhuǎn)換直線段的中點算法來實現(xiàn)。生成圓弧的多邊形逼近法? 圓的正內(nèi)接多邊形迫近法? 圓的等面積正多邊形迫近法8/20/202254生成圓弧的多邊形逼近法圓的正內(nèi)接多邊形迫近法原理計算多邊形各頂點的遞推公式 Xi+1cos a- sin a Xi = Yi +1sin a cosa Yi因為: a是常數(shù)， sin a， cosa只在開始時計算一次所以，一個頂點只需4次乘法，共4n次乘法，外加直線段的中點算法的計算量。8/20/202255問題：給定最大逼近誤差（最大