1、第二章 圖形基元的顯示 掃描轉(zhuǎn)換 將圖形描述轉(zhuǎn)換成用象素矩陣表示的過程圖形基元（輸出圖形元素）圖形系統(tǒng)能產(chǎn)生的最基本圖形 線段、圓、橢圓、多邊形 第一節(jié) 直線掃描轉(zhuǎn)換算法 第二節(jié) 圓的掃描轉(zhuǎn)換算法第三節(jié) 橢圓掃描轉(zhuǎn)換算法第四節(jié) 線寬與線型的處理第五節(jié) 區(qū)域填充第一節(jié) 直線掃描轉(zhuǎn)換算法DDA直線掃描轉(zhuǎn)換算法 中點畫線法 Bresenham畫線算法 端點 (x1,y1)和(x2,y2)， 假定 x1fabs(dy)?fabs(dx):fabs(dy);dx/=e; dy/=e; x=x1;y=y1;for(int i=1;i0 ；直線下方的點，F(xiàn)(x，y)0。 將M代入F(x，y) d = F(M

2、) = F( xi+1，yi+0.5 ) =a ( xi+1 ) + b ( yi+0.5 ) + c當(dāng) d 0，則取正右方的P1。當(dāng)d=0時，二者一樣合適，取P1。 對每一個象素計算判別式d，根據(jù)它的符號確定下一象素。 d0 時，取正右方象素P1 ，判斷再下一個象素應(yīng)取哪個，應(yīng)計算d1 = F ( xi+2 ，yi+0.5 ) = a ( xi+2 ) + b ( yi+0.5 ) +c = d + a故d的增量為a。 而若d0，則取右上方象素P2。要判斷再下一個象素，則要計算d2 = F ( xi+2，yi+1.5 )= a ( xi+2 ) +b ( yi+1.5 ) + c= d+a+

3、b 故在第二種情況,d的增量為a+b 再看d的初始值。顯然，第一個象素應(yīng)取左端點(x0,y0)，相應(yīng)的判別式值為 d0 = F (x0 +1，y0 +0.5 ) =a(x0+1)+b( y0 +0.5 )+c= ax0+by0 +c+a+0.5b=F (x0,y0) + a + 0.5b 由于(x0，y0)在直線上， 故F(x0，y0)=0。因此,d的初始值為d0 = a+0.5b 考慮用2d來代替d的計算void MidpointLine (int x0,int y0,int x1,int y1)int a,b,delta1,delta2,d,x,y ; a = y0 - y1;b = x1

4、 - x0; d = 2 * a + b ;delta1 = 2 * a ; delta2 = 2 *( a + b); x = x0 ; y = y0 ;SetPixel(x,y,color);while( xx1 )if( d0 ) x +;y +; d+= delta2;else x +; d+= delta1; SetPixel(x,y,color); /* while */* MidpointLine */ xyd001(-4)10-3(+6)213(-4)31-1(+6)425(-4)521(x=x1=5)(0，0)、(5，2) a = y0 -y1 = -2，b = x1 - x

5、0 = 5 d0 = 2 * a + b = 1 Bresenham算法 2-122-132-142-152-16確定P1 ,將其代入式 2-12，令i=1，可計算求出 2-172-18void 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;第二節(jié) 圓的掃描轉(zhuǎn)換算法 x2+y2=R2 x=Rcos() y=Rsin()中點畫圓法 點(0,R)至( ， )的八分之一圓弧構(gòu)造函

6、數(shù)：F(x,y)=x2+y2-R2圓上的點，F(xiàn)(x,y)=0圓外的點，F(xiàn)(x,y)0圓內(nèi)的點，F(xiàn)(x,y)0 P1和P2的中點為 M=( xi+1,yi-0.5) F(M)0時，M在圓外，取P2F(M)=0時，P1或P2隨取一個即可，取P2 構(gòu)造判別式 若d0，取P1作為下一個象素，而且再下一個象素的判別式為 而若d0，應(yīng)取P2作為下一個象素，而且再下一個象素的判別式 第一個象素是(0,R)，判別式d的初始值為 d0=F(1,R-0.5)=1+(R-0.5)2-R2=1.25-R。void MidpointCircle(int R) int x,y;double d;x=0;y=R;d=1.2

7、5-R;SetPixel(x,y,color);while(xy)if(d0) d+=2*x+3;x+; elsed+=2*(x-y)+5;x+;y-;SetPixel(x,y,color); 在上述算法中，使用了浮點數(shù)來表示判別式d。 簡化算法，在算法中全部使用整數(shù)，使用e=d-0.25代替d。 顯然，初始化運算d=1.25-R對應(yīng)于e=1-R。 判別式d0對應(yīng)于e-0.25。 算法中可把d直接換成e。又由于e的初值為整數(shù)，且在運算過程中的增量也是整數(shù)，故e始終是整數(shù)，所以e-0.25等價于e0。 增量計算技術(shù)若d0，P1為下一個像素，d的增量為若d0，P2為下一個像素，d的增量為 x和y的

8、變化都將影響2的值。 每當(dāng)x遞增1，1遞增2，2遞增2。 每當(dāng)y遞減1，2遞增2。 若d0，P1為下一個像素，x遞增1， 1遞增2，2遞增2； 若d0，P2為下一個像素，x遞增1， y遞減1，1遞增2，2遞增4。初始像素為(0,R)，所以1的初值為3，2的初值為-2R+5。 void MidpointCircle2(int R) int x,y,deltax,deltay,d;x=0;y=R;d=1-R;deltax=3;deltay=5-R-R;SetPixel(x,y,color);while(xy) if(d0和dD0若pi0，即dH 0，必有pi0，dD0，必有pi0。 得出結(jié)論： p

9、i做判別量， pi0選H點為下一個象素點，當(dāng)pi0 0時，選D點為下一個象素點。從 計算 當(dāng)pi0時，應(yīng)選D點，即選 當(dāng)pi0時，應(yīng)選H，即選 畫圓的起始點是(0，R)，即x1=0，y1=R，代入前式，令i=1，就得到： void 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; 修改語句SetPixel(x,y,color)，畫八個對稱的點，就可以畫出全部圓周。若加一個平移，就可以畫出圓心在任意位置的圓周。第三節(jié) 橢圓掃描轉(zhuǎn)換算法 橢圓上橢圓外橢圓內(nèi)橢圓上部分曲

10、線選下一個待選像素從 、二者挑選其一。其像素中點為選下一對候選像素就是和其中點為 確定上部分的初始判別式為開始畫點，所以則第一點的中點坐標(biāo)為相應(yīng)判別式為 對于下部分，當(dāng)前點下一對候選像素的是中點是判別式為選下一對候選像素就是和其中點為 中點的判別式為 選的下一對候選像素就是和中點為判別式為 下部分中點判別式初始值的處理如下 當(dāng)前點（上部分）：當(dāng)前點（下部分）：void MidpointEllipse(int a,int b)int x,y;double d1,d2;x=0;y=b;d1=b*b+a*a*(-b+0.25);SetPixel(x,y,color);while(b*b*(x+1)a

11、*a*(y-0.5) if(d10)if(d20)d2+=b*b*(2*x+2)+a*a*(-2*y+3);x+;y-;elsed2+=a*a*(-2*y+3);y-;SetPixel(x,y,color);第四節(jié) 線型與線寬的處理 線型處理:實線段長度、間距線型：實線、虛線和點線等虛線：實線段(畫線)與空白段相間點線：短畫線與空白段像素模板(Pixel Mask) 數(shù)字0和1組成的串直線線寬的處理 （依賴輸出設(shè)備） 線刷子和方刷子（光柵設(shè)備）垂直刷子 水平刷子線段端點：線帽(Line Cap) ：方帽、凸方帽和圓帽等。 缺點：斜線、水平線線寬不同；線寬為偶數(shù)時，中心偏移；端點只能水平或豎直。

12、斜角連接(Miter Join)通過延伸兩條線的外邊界直到它們相交；圓連接(Round Join)通過用直徑等于線寬的圓弧邊界將兩線段連接而成；斜切連接(Bevel Join)則是通過用方帽和在兩線段相交處的三角形間隙中填充來生成。 方刷其它線寬處理方式區(qū)域填充或像素模板(a)像素模版 (b)用該模版進行線寬處理曲線的線型和線寬 像素模板 線刷、方刷 第五節(jié) 區(qū)域填充 種子填充算法 區(qū)域是指光柵網(wǎng)格上的一組象素。 區(qū)域填充是把某確定的象素值送入 到區(qū)域內(nèi)部的所有象素中。 區(qū)域填充方法分為兩大類。 區(qū)域由多邊形圍成，區(qū)域由多邊形的頂點序列來定義;另一類方法是通過象素的值來定義區(qū)域的內(nèi)部，相應(yīng)的技

13、術(shù)稱為是以象素為基礎(chǔ)的. 內(nèi)定義區(qū)域，定義方法是指出區(qū)域內(nèi)部所具有的象素值,此時區(qū)域內(nèi)部所有象素有某個原值oldvalue; 邊界定義區(qū)域，定義方法是指出區(qū)域邊界所具有的象素值。此時區(qū)域邊界上所有象素具有某個邊界boundaryvalue。區(qū)域的邊界應(yīng)該是封閉的，并且應(yīng)該指明區(qū)域的內(nèi)部。 以象素為基礎(chǔ)的區(qū)域填充主要是依據(jù)區(qū)域的連通性進行。 四連通:從區(qū)域中的一個象素出發(fā)，經(jīng)連續(xù)地向上下左右四個相鄰象素的移動，就可以到達區(qū)域內(nèi)的任意另一個象素. 八連通:如果除了要經(jīng)上下左右的移動，還要經(jīng)左上、右上、左下和右下的移動，才能由一個象素走到區(qū)域中另外任意一個象素. 利用區(qū)域的連通性進行區(qū)域填充，除了需

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

15、ill(x,y-1,oldvalue,newvalue); /四向擴散 Floodfill(x,y+1,oldvalue,newvalue);Floodfill(x-1,y,oldvalue,newvalue);Floodfill(x+1,y,oldvalue,newvalue); /四連通內(nèi)定義區(qū)域填充算法void Boundaryfill(int x,int y,COLORREF boundaryvalue,COLORREF newvalue)/*(x,y) 為種子位置boundaryvalue是邊界象素值newvalue是區(qū)域內(nèi)象素新值，未填充前區(qū)域內(nèi)不應(yīng)有值為newvalue的象素。*

16、/ if( GetPixel(x,y)!=boundaryvalue & GetPixel(x,y)!=newvalue) / 未達邊界且未訪問過 SetPixel(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);/四連通邊界定義區(qū)域填充算法 掃

17、描線種子填充算法 將區(qū)域內(nèi)由邊界點限定的同一行內(nèi)相連接的不具有新值newvalue的一組象素稱為一個象素段，象素段用它最右邊的象素來標(biāo)識。 算法的步驟如下： 1對種子所在象素段進行填充。 2從右至左檢查種子所在行的上一橫行，將查得的象素段依次編號存入堆棧。接著對種子所在行的下一橫行同樣處理。 3若堆棧為空則算法結(jié)束，否則從堆棧頂部取出一個象素段。就以這個象素為新的種子，返回到1。void ScanlineSeedfill(CDC* pDC,int x,int y,COLORREF boundaryvalue,COLORREF newvalue)using namespace std; int

18、x0,xl,xr,y0,xid,count=0;bool flag;stack s; CPoint p;s.push(CPoint(x,y);/種子入棧while(!s.isempty()p=s.pop(); /讀棧頂元素 s.top(); /棧頂象素出棧 x=p.x; y=p.y; pDC-SetPixel(x ,y ,newvalue); x0= x+1;while(pDC-GetPixel(x0,y) !=boundaryvalue &pDC-GetPixel(x0,y)!=newvalue) pDC-SetPixel(x0,y ,newvalue);x0+;xr=x0-1;/最右象素x

19、0= x-1;while(pDC-GetPixel(x0,y)!=boundaryvalue &pDC-GetPixel(x0,y)!=newvalue)pDC-SetPixel(x0,y,newvalue); x0-;xl=x0+1;/最左象素/檢查上一條掃描線和下一條掃描線/若存在非邊界且未填充的象素，/則選取代表各連續(xù)區(qū)間的種子象素入棧。y0=y;for(int i=1;i=-1;i-=2) x0=xr; y=y0+i; while(x0=xl) flag=false;while(pDC-GetPixel(x0,y)!=boundaryvalue) & (pDC-GetPixel(x0,

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

21、i=1;i=-1;i-=2)/while(!s.isempty() 多邊形的掃描轉(zhuǎn)換算法“奇偶性：“相切” 可以分如下三個步驟來做： 1找出掃描線與多邊形邊界線的所有交點；2按x坐標(biāo)增加順序?qū)稽c排序；3在交點對之間進行填充。 相切點的解決方法：當(dāng)頂點表現(xiàn)為是局部極大或局部極小時，就看做是二個，否則看做一個。局部極大，如果這個頂點的前面和后面各有一些相鄰頂點的y坐標(biāo)，都小于該頂點的y坐標(biāo)。局部極小可類似地確定。 實際處理這個問題可以有一個簡便辦法，那就是對應(yīng)該看做是一個的頂點，將其上面的邊縮短兩條相鄰掃描線對應(yīng)的一個單位。 計算掃描線與多邊形邊界線的交點： 若掃描線yi與多邊形邊界線交點x的坐

22、標(biāo)是xi，則對下一條掃描線yi+l，它與那條邊界線的交點的x坐標(biāo)xi+1，可如下求出： 活躍邊表AET(ActiveEdgeTable)，用這個表存貯與當(dāng)前掃描線相交的各邊。每次離開一條掃描線進入下一條之前，將表中有但與下一條掃描線不相交的邊清除出表，將與下一條掃描線相交而表中沒有的邊加入表中。 邊表ET(EdgeTable)，ET中各登記項按y坐標(biāo)遞增排序，每一登記項下的“吊桶”按所記x坐標(biāo)遞增排序，“吊桶”中各項的內(nèi)容依次是： 1.邊的上端點y坐標(biāo)ymax。2. 邊的下端點的x坐標(biāo)xmin。3.斜率的倒數(shù)，即1/m。Void Polygonfill(EdgeTable ET, COLORR

23、EF color) 1. y=邊表ET中各登記項對應(yīng)的y坐 標(biāo)中最小的值; 2.活躍邊表AET初始化為空表; 3.while(ET表中仍有掃描線未被處 理) /處理ET表中的每一條掃描線 3.1 將ET中登記項y對應(yīng)的各“ 吊桶”合并到表AET中，將 AET中各吊桶按x坐標(biāo)遞增排序；3.2 在掃描線y上,按照AET表提供 的x 坐標(biāo)對，用color實施填充；3.3 將AET表中有y=ymax的各項 清除出表；3.4 對AET中留下的各項,分別將 x換為x+1/m.3.5 由于前一步可能破壞了AET表中 各項x坐標(biāo)的遞增次序，故按x坐 標(biāo)重新排序； 3.6 y=y+1，去處理下一條掃描線。邊填充

24、算法(正負相消法) 基本思想：對于每一條掃描線和每條多邊形邊的交點 ，都將該掃描線上交點右方的所有像素取補，并對多邊形的每條邊按一定順序(逆時針、順時針均可)做此處理 待填充區(qū)域 D對區(qū)域的每一條邊與掃描線的每一個交點當(dāng) 做沿D的邊界經(jīng)歷一周后，只要則否則Dvoid EdgeFill(PointArray& ptArray,COLORREF color) for(y=y1;y=y2;y+) for(x=x1;x=x2;x+) MASKyx=false; for(區(qū)域D內(nèi)的每一條邊PiPi+1) xs=xi; dxs=( xi+1- xi)/( yi+1- yi); for(ys=yi; ys=

25、 yi+1;ys+) xs= xs +dxs; Ixs =int(xs +0.5); for(x= Ixs;x=x2;x+) MASKysx =!MASKysx; for(y=y1;y=y2;y+)for(x=x1;x=x2;x+)if(MASKyx)SetPixel(x,y,color);柵欄(一條與掃描線垂直的直線) 柵欄填充基本思想： 對于每條掃描線與多邊形的交點，將交點與柵欄之間的掃描線上的像素取補邊標(biāo)志算法(輪廓填充算法) 對每個像素訪問一次邊標(biāo)志算法分為兩個步驟： 第一步:邊界像素打標(biāo)志； 第二步:填充內(nèi)部像素。邊標(biāo)志算法的程序如下：void EdgeMarkFill(PointArray& ptArray,COLORREF color) for(y=y1;y=y2;y+) for(x=x1;x=x2;x+) MASKyx=false; /形成輪廓線for(區(qū)域D內(nèi)的每一條邊PiPi+1) xs=xi; dxs=(xi+1-xi)/(yi+