第2章 圖形基元顯示

1、1y=ax+b 0 x102345 圖形系統(tǒng)提出畫一條線段的要求通常是圖形系統(tǒng)提出畫一條線段的要求通常是給出線段的兩個端點，線段掃描轉(zhuǎn)換算法的給出線段的兩個端點，線段掃描轉(zhuǎn)換算法的任務(wù)是根據(jù)端點位置求出構(gòu)成該線段的所有任務(wù)是根據(jù)端點位置求出構(gòu)成該線段的所有象素位置的坐標(biāo)。象素位置的坐標(biāo)。62121122121, (2.2)yyx yx ymbxxxx (2.1)ymxb7),(11yx),(22yx1m1m89象限象限|dx|dydxdy1ay1m1bn1/m12bn-1/m12ay-1m3ay-1-m3bn-1/m-14bn1/m-14ay1-ma區(qū)，x=x1，y=ymb區(qū)，y=y1，x=x

2、1/m1011 (2.3)iiiiyyymxxx由由(2.3)(2.3)得得 ，于是知使，于是知使 增增1，即，即 時，為畫線精確，時，為畫線精確，應(yīng)使相鄰的畫出點的坐標(biāo)值相差最大為應(yīng)使相鄰的畫出點的坐標(biāo)值相差最大為1，得到畫線段的數(shù)值微分分析器得到畫線段的數(shù)值微分分析器DDA ( (Digital Differential Analyzer)算法如下：算法如下： )(11iiiixxmyyix11iixx11void DDALine(int x1,int y1,int x2,int y2)double dx,dy,e,x,y; dx=x2-x1; dy=y2-y1;e=(fabs(dx)fa

3、bs(dy)?fabs(dx):fabs(dy);dx/=e;dy/=e;12 x=x1;y=y1;for(int i=1;i0；直線下方的點，直線下方的點，F(xiàn)(x，y)0。16定義判別式定義判別式dd=F(M) =F(xi+1,yi+0.5)=a(xi+1)+b(yi+0.5)+c當(dāng)當(dāng)d0時，則取正右方的時，則取正右方的P1當(dāng)當(dāng)d=0時，二者皆可，約定取時，二者皆可，約定取P117對每一個象素計算判別式對每一個象素計算判別式d，根據(jù)它的，根據(jù)它的符號確定符號確定下一個下一個象素。象素。 當(dāng)當(dāng)d0時，取正右方象素時，取正右方象素P1，判斷，判斷再再下一個下一個象素應(yīng)取哪個，應(yīng)計算象素應(yīng)取哪個，

4、應(yīng)計算 d1=F(xi+2,yi+0.5) =a(xi+2)+b(yi+0.5)+c =d+a 故故d 的增量為的增量為a1819再看再看d 的初始值的初始值。顯然，第一個象素應(yīng)。顯然，第一個象素應(yīng)取左端點取左端點(x0，y0)，相應(yīng)的判別式值為，相應(yīng)的判別式值為d0 = F (x0 +1，y0 +0.5 ) =( x0 +1 )+ b ( y0 +0.5 ) + c = a x0 + b y0 + c + a + 0.5b =F ( x0，y0 ) + a + 0.5b 但由于但由于(x0,y0)在直線上，故在直線上，故F(x0,y0)=0。 因此，因此，d 的初始值為的初始值為d0 = a

5、+0.5b 考慮用考慮用2d來代替來代替d的計算的計算20void MidpointLine(int x0, int y0, int x1,int y1) int a,b,delta1,delta2,d,x,y ;a = y0 - y1; b = x1 - x0; d = 2 * a + b ; delta1 = 2 * a ; delta2 = 2 *( a + b); x = x0 ; y = y0 ;SetPixel(x,y);while( xx1 ) if( d0 ) x +; y +; d+= delta2; else x +; d+= delta1; SetPixel(x,y);

6、/* while */ /* MidpointLine */ 21xyd00110-321331-1425521 兩端點：兩端點：(0,0)、(5,2) a = y0 -y1 = -2，b = x1 - x0 = 5，d = 2*a + b = 1 d0: d=d +2a , x+ d 0: d=d+2(a+b) , x+, y+ 222312xx 01m),(iiyx),(iiyxiixx 24 在在 處 直 線 上 點 的處 直 線 上 點 的 y 值值是是 ，該點到點，該點到點 和點和點 的距離分別是的距離分別是 和和 ：1ixxbxmy) 1(), 1(iiyx ) 1, 1(iiyx

7、1d2d25122 (1)221iiddm xyb12(1)(1)(1)(1)iiiiidy ym xb ydyyym xb 12dd，下一個象素點取下一個象素點取 (1,1)iixy12dd，下一個象素點取，下一個象素點取 12dd，取兩象素點中的任意一個，取兩象素點中的任意一個 ), 1(iiyx 26cyxxypiii1112212()22iiipx ddy xx yc )(2211iiiiyyxypp0ip ，應(yīng)取11iyiy)(21xyppii12xxx12yyy) 12(2bxyc27，應(yīng)取應(yīng)取 iyiy1確定初始判別量確定初始判別量 p1 ,令令i=1，可計算求出，可計算求出：

8、yppii210ipbxxyyyxx11111, xyp 2128void BresenhamLine(int x1,int y1, int x2,int y2)int x,y,dx,dy,p;x=x1;y=y1;dx=x2-x1; dy=y2-y1;p=2*dy-dx;for(;x=0) y+;p+=2*(dy-dx);elsep+=2*dy;30第二節(jié)第二節(jié) 圓的掃描轉(zhuǎn)換算法圓的掃描轉(zhuǎn)換算法 22222 xyRyRxcossinxRyR假定圓心是原點，要畫出半徑為假定圓心是原點，要畫出半徑為R的圓。的圓。31(/2,/2)RR32 一、中點畫圓法一、中點畫圓法 3334構(gòu)造判別式構(gòu)造判別式

9、222)5 . 0() 1()5 . 0, 1()(RyxyxFMFdiiii若若d0，取，取P P1 1作為下一個象素，且再下一個作為下一個象素，且再下一個象素的判別式為象素的判別式為 32)5 . 0()2()5 . 0, 2(222iiiiixdRyxyxFd35若若d0，應(yīng)取，應(yīng)取P P2 2作為下一個象素，且再下作為下一個象素，且再下一個象素的判別式一個象素的判別式 222(2,1.5)(2)(1.5)(23)( 22)225iiiiiiiidF xyxyRdxydxy 第一個象素是第一個象素是(0,R )，判別式，判別式d 的初始值為的初始值為 d0=F(1,R-0.5)=1+(R

10、-0.5)2-R2=1.25-R。36void MidpointCircle(int R) int x,y;double d;x=0; y=R; d=1.25-R;SetPixel(x,y);while(xy) if(d0) d+=2*x+3; x+; else d+=2*(x-y)+5; x+; y-; SetPixel(x,y); 37對算法進行簡化：在算法中全部使用整數(shù)，對算法進行簡化：在算法中全部使用整數(shù)，使用使用e=d-0.25代替代替d。顯然，初始化運算顯然，初始化運算d d=1.25-R對應(yīng)于對應(yīng)于e=1-R。判別式判別式d0對應(yīng)于對應(yīng)于e-0.25。 算法中可把算法中可把d直接

11、換成直接換成e。又由于。又由于e的初值為的初值為整數(shù)，且在運算過程中的增量也是整數(shù)，整數(shù)，且在運算過程中的增量也是整數(shù)，故故e始終是整數(shù)，所以始終是整數(shù)，所以e-0.25等價于等價于e0。 3839 上述算法還可以進一步改進。以提高上述算法還可以進一步改進。以提高效率。注意到效率。注意到d 的增量是的增量是x、y的線性函數(shù)，的線性函數(shù)，每當(dāng)每當(dāng)x遞增遞增1 1，d遞增遞增x=2=2。每當(dāng)。每當(dāng)y遞減遞減1 1，d遞增遞增y =2 =2。由于初始象素為。由于初始象素為(0,R)，所以，所以x的初值為的初值為3 3，y的初值為的初值為-2R+2。 d=d+x x=2x+3d=d+x+y y =2-

12、2y40不含乘法，僅用整數(shù)實現(xiàn)的中點算法不含乘法，僅用整數(shù)實現(xiàn)的中點算法void MidpointCircle2(int R) int x,y,deltax,deltay,d;x=0;y=R;d=1-R;deltax=3;deltay=2-R-R;SetPixel(x,y);while(xy) if(d0和和dD0 若若pi0，即，即dH 0，必有，必有pi0，dD0，必有，必有pi0。 結(jié)論：結(jié)論： pi做判別量，做判別量， pi0時，選時，選H點為下一點為下一個象素點，當(dāng)個象素點，當(dāng)pi0時，選時，選D點為下一個象素點。點為下一個象素點。451222) 1(2222Ryyxpiiii122

13、2) 1(22121211Ryyxpiiii64)(212211iiiiiiixyyyypp將上式中用i換為i+1，得（11）（12）（13）4611iiyyiiyy110)(41iiiiyxpp641iiixpp47Rp23148void BresenhamCircle(int R) int x,y,p;x=0; y=R;p=3-2*R;for(;x=0) p+=4*(x-y)+10; y-; else p +=4*x+6;49 只需修改語句只需修改語句SetPixel(x,y)SetPixel(x,y)，畫八，畫八個對稱的點，就可以畫出全部圓周。若個對稱的點，就可以畫出全部圓周。若加一個平

14、移，就可以畫出圓心在任意位加一個平移，就可以畫出圓心在任意位置的圓周。置的圓周。 BresenhamBresenham畫圓算法也做到了只需要畫圓算法也做到了只需要整數(shù)加法和乘整數(shù)加法和乘2 2運算，因此有較高的效率。運算，因此有較高的效率。50 第三節(jié)第三節(jié) 區(qū)域填充區(qū)域填充 區(qū)域區(qū)域是指光柵網(wǎng)格上的一組象素。是指光柵網(wǎng)格上的一組象素。區(qū)域填充區(qū)域填充是把某個確定的象素值送入到是把某個確定的象素值送入到區(qū)域內(nèi)部的所有象素中。區(qū)域內(nèi)部的所有象素中。 5152通過象素值來定義區(qū)域有兩種常用的方法通過象素值來定義區(qū)域有兩種常用的方法: :內(nèi)定義區(qū)域內(nèi)定義區(qū)域：定義方法是指出區(qū)域內(nèi)部所具有：定義方法是

15、指出區(qū)域內(nèi)部所具有的象素值的象素值, ,此時區(qū)域內(nèi)部所有象素有某個原值此時區(qū)域內(nèi)部所有象素有某個原值oldvalue，區(qū)域邊界上的所有象素都不具有那個區(qū)域邊界上的所有象素都不具有那個原值。原值。 邊界定義區(qū)域邊界定義區(qū)域：定義方法是指出區(qū)域邊界所具：定義方法是指出區(qū)域邊界所具有的象素值。此時區(qū)域邊界上所有象素具有某個有的象素值。此時區(qū)域邊界上所有象素具有某個邊界邊界boundaryvalue。區(qū)域的邊界應(yīng)該是封閉的，。區(qū)域的邊界應(yīng)該是封閉的，并且應(yīng)該指明區(qū)域的內(nèi)部。并且應(yīng)該指明區(qū)域的內(nèi)部。 以象素為基礎(chǔ)的區(qū)域填充主要是依據(jù)區(qū)域的以象素為基礎(chǔ)的區(qū)域填充主要是依據(jù)區(qū)域的連通性連通性進行。進行。 5

16、354四連通區(qū)域四連通區(qū)域: :從區(qū)域中的從區(qū)域中的一個象素出發(fā)，經(jīng)連續(xù)地一個象素出發(fā)，經(jīng)連續(xù)地向上下左右四個相鄰象素向上下左右四個相鄰象素的移動，就可以到達(dá)區(qū)域的移動，就可以到達(dá)區(qū)域內(nèi)的任意另一個象素。內(nèi)的任意另一個象素。八連通區(qū)域八連通區(qū)域: :如果除了要如果除了要經(jīng)上下左右的移動，還要經(jīng)上下左右的移動，還要經(jīng)左上、右上、左下和右經(jīng)左上、右上、左下和右下的移動，才能由一個象下的移動，才能由一個象素走到區(qū)域中另外任意一素走到區(qū)域中另外任意一個象素。個象素。55內(nèi)點表示的八連通域 邊界表示的八連通域 4連通域與8連通域56 利用區(qū)域的連通性進行區(qū)域填充，除了需利用區(qū)域的連通性進行區(qū)域填充，除了

17、需要區(qū)域應(yīng)該明確定義外，還需要事先給定一個要區(qū)域應(yīng)該明確定義外，還需要事先給定一個區(qū)域內(nèi)部象素區(qū)域內(nèi)部象素，這個象素稱為，這個象素稱為種子種子。 做區(qū)域填充時，要進行對光柵網(wǎng)格的做區(qū)域填充時，要進行對光柵網(wǎng)格的遍歷遍歷，找出由種子出發(fā)能達(dá)到而又不穿過邊界的所有找出由種子出發(fā)能達(dá)到而又不穿過邊界的所有象素。象素。 這種利用連通性的填充，其主要優(yōu)點是不這種利用連通性的填充，其主要優(yōu)點是不受區(qū)域不規(guī)則性的影響，主要缺點是需要事先受區(qū)域不規(guī)則性的影響，主要缺點是需要事先知道一個內(nèi)部象素。知道一個內(nèi)部象素。 57void Floodfill(int x,int y,COLORREF oldvalue,

18、COLORREF newvalue)/ /* *(x(x，y)y)為種子為種子 oldvalue是原值是原值 newvalue是是新值，應(yīng)不等于原值。新值，應(yīng)不等于原值。* */ / if (GetPixel(x,y) = oldvalue) SetPixel(x,y,newvalue);/賦值為新值賦值為新值 Floodfill(x,y-1,oldvalue,newvalue);/四向擴散四向擴散 Floodfill(x,y+1,oldvalue,newvalue); Floodfill(x-1,y,oldvalue,newvalue); Floodfill(x+1,y,oldvalue,n

19、ewvalue); 58void Boundaryfill(int x,int y,COLORREF boundaryvalue,COLORREF newvalue)/ /* *(x,y) 為種子位置為種子位置, ,boundaryvalue是邊界象素值是邊界象素值newvalue是區(qū)域內(nèi)象素新值，未填充前區(qū)域內(nèi)不是區(qū)域內(nèi)象素新值，未填充前區(qū)域內(nèi)不應(yīng)有值為應(yīng)有值為newvalue的象素。的象素。* */ / if( GetPixel(x,y)!=boundaryvalue & GetPixel(x,y)!=newvalue) / / 未達(dá)邊界且未訪問過未達(dá)邊界且未訪問過59 SetPixel(

20、x,y,newvalue); /賦以新值賦以新值 Boundaryfill(x,y-1,boundaryvalue,newvalue); /向四個方向擴散。向四個方向擴散。 Boundaryfill(x,y+1,boundaryvalue,newvalue); Boundaryfill(x-1,y,boundaryvalue,newvalue); Boundaryfill(x+1,y,boundaryvalue,newvalue);6061 掃描線種子填充算法掃描線種子填充算法 將區(qū)域內(nèi)由邊界點限定的同一行內(nèi)相將區(qū)域內(nèi)由邊界點限定的同一行內(nèi)相連接的不具有新值連接的不具有新值newvalue的一

21、組象素稱的一組象素稱為一個為一個象素段象素段，象素段用它最右邊的象素，象素段用它最右邊的象素來標(biāo)識。來標(biāo)識。 626364用偽用偽C C語言寫出的掃描線填充算法：語言寫出的掃描線填充算法：void ScanlineSeedfill(int x, int y, COLORREF boundaryvalue,COLORREF newvalue)int x0,xl,xr,y0,xid;int flag;Stack s; Point p; 65s.push(Point(x,y); /種子象素入棧種子象素入棧while(!s.isempty()p=s.pop(); /棧頂象素出棧棧頂象素出棧x=p.x;

22、y=p.y;SetPixel(x ,y ,newvalue); x0= x+1;while(GetPixel(x0,y)!=boundaryvalue)/填充右方象素填充右方象素66 SetPixel(x0 ,y ,newvalue);x0+;xr=x0-1; /最右象素最右象素x0= x-1;while(GetPixel(x0,y)!=boundaryvalue) /填充左方象素填充左方象素SetPixel(x0 ,y ,newvalue);x0-;67 xl=x0+1; /最左象素最左象素/檢查上一條掃描線和下一條掃描線，檢查上一條掃描線和下一條掃描線，/若存在非邊界且未填充的象素，若存在

23、非邊界且未填充的象素，/則選取代表各連續(xù)區(qū)間的種子象素入棧。則選取代表各連續(xù)區(qū)間的種子象素入棧。y0=y;for(int i=1;i=-1;i-=2) x0=xr; /x0取最右象素取最右象素 y=y0+i; 68 while(x0=xl) flag=0; /標(biāo)記是否找到象素段標(biāo)記是否找到象素段 while(GetPixel(x0,y)!=boundaryvalue)&(GetPixel(x0,y)!=newvalue) & (x0=xl) if(flag=0) flag=1; xid=x0; /新種子點新種子點 69 x0-; if(flag=1) s.push(Point(xid,y);

24、/ 將最右側(cè)可填充象素壓入棧中將最右側(cè)可填充象素壓入棧中 flag=0; /檢查當(dāng)前填充行是否被中斷，若被中斷，檢查當(dāng)前填充行是否被中斷，若被中斷，尋找左方第一個可填充象素尋找左方第一個可填充象素70while(GetPixel(x0,y)=boundaryvalue) /判斷當(dāng)前點是否為邊界點判斷當(dāng)前點是否為邊界點|(GetPixel(x0,y)=newvalue)&(x0=xl) /判斷當(dāng)前點是否為已填充點判斷當(dāng)前點是否為已填充點 x0-; /若當(dāng)前點為邊界點或已填充點，根據(jù)前面的判若當(dāng)前點為邊界點或已填充點，根據(jù)前面的判斷，當(dāng)前點必然未超出左邊界，則當(dāng)前點向左移斷，當(dāng)前點必然未超出左邊界

25、，則當(dāng)前點向左移動動 /while(x0=xl) /for(int i=1;i=-1;i-=2)/while(!s.isempty()717273 多邊形的掃描轉(zhuǎn)換算法多邊形的掃描轉(zhuǎn)換算法 以多邊形為基礎(chǔ)的區(qū)域填充把區(qū)域看做是以多邊形為基礎(chǔ)的區(qū)域填充把區(qū)域看做是由多邊形所圍成。設(shè)多邊形用其頂點坐標(biāo)的逆由多邊形所圍成。設(shè)多邊形用其頂點坐標(biāo)的逆時針方向的序列來確定，即沿頂點序列前行時時針方向的序列來確定，即沿頂點序列前行時多邊形內(nèi)部在左側(cè)。多邊形內(nèi)部在左側(cè)。 對對多邊形多邊形圍成區(qū)域進行填充，也就是做圍成區(qū)域進行填充，也就是做多多邊形掃描轉(zhuǎn)換邊形掃描轉(zhuǎn)換，是要找出所有位于多邊形內(nèi)部，是要找出所有位

26、于多邊形內(nèi)部的象素，并賦以適當(dāng)?shù)南笏刂?，使能產(chǎn)生面填的象素，并賦以適當(dāng)?shù)南笏刂担鼓墚a(chǎn)生面填充的圖形。充的圖形。 74757677u 特殊點的處理：特殊點的處理： 正確的解決辦法是，當(dāng)頂點表現(xiàn)為是正確的解決辦法是，當(dāng)頂點表現(xiàn)為是局部局部極大或局部極小極大或局部極小時，就看做是二個，否則時，就看做是二個，否則看做一個。這里一個頂點是局部極大，如看做一個。這里一個頂點是局部極大，如果這個頂點的前面和后面各有一些相鄰頂果這個頂點的前面和后面各有一些相鄰頂點的點的y y坐標(biāo)，都小于該頂點的坐標(biāo)，都小于該頂點的y y坐標(biāo)。局部坐標(biāo)。局部極小可類似地確定。極小可類似地確定。 實際處理這個問題可以有一個簡便辦實際處理這個問題可以有一個簡便辦法，那就是對應(yīng)該看做是一個的頂點，將法，那就是對應(yīng)該看做是一個的頂點，將其上面的邊其上面的邊縮短縮短兩條相鄰掃描線對應(yīng)的一兩條相鄰掃描線對應(yīng)的一個單位。個單位。 7879mxxii11yiyi+1xi+1xi80數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)：n 活躍邊表活躍邊表AET(Active-Edge-T