計(jì)算機(jī)圖形學(xué)第2章-圖形基元的顯示課件

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

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

3、再看d的初始值。顯然，第一個(gè)象素應(yīng)取左端點(diǎn)(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的計(jì)算void 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 +

4、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); /* 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 - x0 = 5 d0 = 2 * a + b = 1 斜率m在0到

5、1之間，并且 設(shè)在第i步已經(jīng)確定第i個(gè)象素點(diǎn)是 ，它是直線上點(diǎn) 的最接近位置( )現(xiàn)在看第i+1步如何確定第i+1個(gè)象素點(diǎn)的位置。d1d2,下一個(gè)象素點(diǎn)取 ，下一個(gè)象素點(diǎn)取 ，取兩象素點(diǎn)中的任意一個(gè) ,應(yīng)取,應(yīng)取 確定P1 ,令i=1，可計(jì)算求出： void 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 中點(diǎn)畫圓法 討論如何從點(diǎn)(

6、0，R)至 ( ， )的18圓周 x坐標(biāo)為xi的象素(xi,yi)下一個(gè)象素只能是(xi+1,yi) 的P1點(diǎn)或 (xi+1,yi-1) 的P2點(diǎn)M構(gòu)造函數(shù)：F(x,y)=x2+y2-R2圓上的點(diǎn)，F(xiàn)(x,y)=0圓外的點(diǎn)，F(xiàn)(x,y)0圓內(nèi)的點(diǎn)，F(xiàn)(x,y)0 P1和P2的中點(diǎn)為 M=( xi+1,yi-0.5) F(M)0時(shí)，M在圓外，取P2F(M)=0時(shí)，P1或P2隨取一個(gè)即可，取P2 構(gòu)造判別式 若d0，取P1作為下一個(gè)象素，而且再下一個(gè)象素的判別式為 而若d0，應(yīng)取P2作為下一個(gè)象素，而且再下一個(gè)象素的判別式 第一個(gè)象素是(0,R)，判別式d的初始值為 d0=F(1,R-0.5)=1

7、+(R-0.5)2-R2=1.25-R。void 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+; elsed+=2*(x-y)+5;x+;y-;SetPixel(x,y); 在上述算法中，使用了浮點(diǎn)數(shù)來表示判別式d。 簡(jiǎn)化算法，在算法中全部使用整數(shù)，使用e=d-0.25代替d。 顯然，初始化運(yùn)算d=1.25-R對(duì)應(yīng)于e=1-R。 判別式d0對(duì)應(yīng)于e-0.25。 算法中可把d直接換成e。又由于e的初值為整數(shù)，且在運(yùn)算過程中的增量也是整數(shù)，故e始終是

8、整數(shù)，所以e-0.25等價(jià)于e0。 上述算法還可以進(jìn)一步改進(jìn)。以提高效率。注意到d的增量是x、y的線性函數(shù)，每當(dāng)x遞增1，d遞增x=2。每當(dāng)y遞減1，d遞增y =2。由于初始象素為(0,R)，所以x的初值為3，y的初值為-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);while(xy) if(d0和dD0若pi0，即dH 0，必有pi0，dD0，必有pi0。 得出結(jié)論： pi做判別量， pi0選H點(diǎn)為下一個(gè)象素點(diǎn)，當(dāng)pi0 0

9、時(shí)，選D點(diǎn)為下一個(gè)象素點(diǎn)。從 計(jì)算 當(dāng)pi0時(shí)，應(yīng)選D點(diǎn)，即選 當(dāng)pi0時(shí)，應(yīng)選H，即選 畫圓的起始點(diǎn)是(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)，畫八個(gè)對(duì)稱的點(diǎn)，就可以畫出全部圓周。若加一個(gè)平移，就可以畫出圓心在任意位置的圓周。 區(qū)域填充 種子填充算法 區(qū)域是指光柵網(wǎng)格上的一組象素。 區(qū)域填充是把某確定的象素值送入 到區(qū)域內(nèi)部的所有象素中。 區(qū)

10、域填充方法分為兩大類。 區(qū)域由多邊形圍成，區(qū)域由多邊形的頂點(diǎn)序列來定義;另一類方法是通過象素的值來定義區(qū)域的內(nèi)部，相應(yīng)的技術(shù)稱為是以象素為基礎(chǔ)的. 內(nèi)定義區(qū)域，定義方法是指出區(qū)域內(nèi)部所具有的象素值,此時(shí)區(qū)域內(nèi)部所有象素有某個(gè)原值oldvalue; 邊界定義區(qū)域，定義方法是指出區(qū)域邊界所具有的象素值。此時(shí)區(qū)域邊界上所有象素具有某個(gè)邊界boundaryvalue。區(qū)域的邊界應(yīng)該是封閉的，并且應(yīng)該指明區(qū)域的內(nèi)部。 以象素為基礎(chǔ)的區(qū)域填充主要是依據(jù)區(qū)域的連通性進(jìn)行。 四連通:從區(qū)域中的一個(gè)象素出發(fā)，經(jīng)連續(xù)地向上下左右四個(gè)相鄰象素的移動(dòng)，就可以到達(dá)區(qū)域內(nèi)的任意另一個(gè)象素. 八連通:如果除了要經(jīng)上下左右的

11、移動(dòng)，還要經(jīng)左上、右上、左下和右下的移動(dòng)，才能由一個(gè)象素走到區(qū)域中另外任意一個(gè)象素. 利用區(qū)域的連通性進(jìn)行區(qū)域填充，除了需要區(qū)域應(yīng)該明確定義外，還需要事先給定一個(gè)區(qū)域內(nèi)部象素，這個(gè)象素稱為種子。 做區(qū)域填充時(shí)，要進(jìn)行對(duì)光柵網(wǎng)格的遍歷，找出由種子出發(fā)能達(dá)到而又不穿過邊界的所有象素。 這種利用連通性的填充，其主要優(yōu)點(diǎn)是不受區(qū)域不規(guī)則性的影響，主要缺點(diǎn)是需要事先知道一個(gè)內(nèi)部象素。 void Floodfill(int x,int y,COLORREF oldvalue,COLORREF newvalue)/*(x，y)為種子 oldvalue是原值 newvalue是新值，應(yīng)不等于原值。*/ if

12、(GetPixel(x,y) = oldvalue) SetPixel(x,y,newvalue);/賦新值 Floodfill(x,y-1,oldvalue,newvalue); /四向擴(kuò)散 Floodfill(x,y+1,oldvalue,newvalue);Floodfill(x-1,y,oldvalue,newvalue);Floodfill(x+1,y,oldvalue,newvalue); 演示void Boundaryfill(int x,int y,COLORREF boundaryvalue,COLORREF newvalue)/*(x,y) 為種子位置boundaryval

13、ue是邊界象素值newvalue是區(qū)域內(nèi)象素新值，未填充前區(qū)域內(nèi)不應(yīng)有值為newvalue的象素。*/ if( GetPixel(x,y)!=boundaryvalue & GetPixel(x,y)!=newvalue) / 未達(dá)邊界且未訪問過 SetPixel(x,y,newvalue);/賦以新值Boundaryfill(x,y-1,boundaryvalue,newvalue); /向四個(gè)方向擴(kuò)散。Boundaryfill(x,y+1,boundaryvalue,newvalue);Boundaryfill(x-1,y,boundaryvalue,newvalue);Boundaryf

14、ill(x+1,y,boundaryvalue,newvalue); 掃描線種子填充算法 將區(qū)域內(nèi)由邊界點(diǎn)限定的同一行內(nèi)相連接的不具有新值newvalue的一組象素稱為一個(gè)象素段，象素段用它最右邊的象素來標(biāo)識(shí)。 算法的步驟如下： 1對(duì)種子所在象素段進(jìn)行填充。 2從右至左檢查種子所在行的上一橫行，將查得的象素段依次編號(hào)存入堆棧。接著對(duì)種子所在行的下一橫行同樣處理。 3若堆棧為空則算法結(jié)束，否則從堆棧頂部取出一個(gè)象素段。就以這個(gè)象素為新的種子，返回到1。 下面我們用偽C語言寫出掃描線填充算法。 void ScanlineSeedfill(int x,int y,COLORREF boundaryv

15、alue,COLORREF newvalue)int x0,xl,xr,y0,xid;int flag;Stack s; Point p;s.push(Point(x,y);/種子入棧while(!s.isempty()p=s.pop(); /棧頂象素出棧x=p.x;y=p.y;SetPixel(x ,y ,newvalue); x0= x+1;while(GetPixel(x0,y)!=boundaryvalue)/填充右方象素SetPixel(x0 ,y ,newvalue);x0+;xr=x0-1;/最右象素x0= x-1;while(GetPixel(x0,y)!=boundaryva

16、lue)/填充左方象素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=0;while(GetPixel(x0,y)!=boundaryvalue)& (GetPixel(x0,y)!=newvalue)& (x0 xl)if(flag=0) flag=1; xid=x0;x0-;/將最右側(cè)可填充象素壓入棧中if(flag=1)s.push(

17、Point(xid,y); flag=0;/檢查當(dāng)前填充行是否被中斷，若被中斷，尋找左方第一個(gè)可填充象素while(GetPixel(x0,y)=boundaryvalue)/判斷當(dāng)前點(diǎn)是否為邊界點(diǎn)|(GetPixel(x0,y)=newvalue) /判斷當(dāng)前點(diǎn)是否為已填充點(diǎn)x0-;/若當(dāng)前點(diǎn)為邊界點(diǎn)或已填充點(diǎn)，根據(jù)前面的判斷，當(dāng)前點(diǎn)必然未超出左邊界，則當(dāng)前點(diǎn)向左移動(dòng)/while(x0=xl) /for(int i=1;i=-1;i-=2)/while(!s.isempty() 多邊形的掃描轉(zhuǎn)換算法 多邊形掃描轉(zhuǎn)換產(chǎn)生面填充的圖形。多邊形掃描轉(zhuǎn)換可以依據(jù)區(qū)域的一種“奇偶”性質(zhì)，即一條直線與任

18、意封閉的曲線相交時(shí)，總是從第一個(gè)交點(diǎn)進(jìn)入內(nèi)部，再?gòu)牡诙€(gè)交點(diǎn)退出，以下交替的進(jìn)入退出，即奇數(shù)次進(jìn)入，偶數(shù)次退出。當(dāng)然可能有一些“相切”的點(diǎn)應(yīng)特殊處理。 可以分如下三個(gè)步驟來做： 1找出掃描線與多邊形邊界線的所有交點(diǎn)；2按x坐標(biāo)增加順序?qū)稽c(diǎn)排序；3在交點(diǎn)對(duì)之間進(jìn)行填充。 相切點(diǎn)的解決方法：當(dāng)頂點(diǎn)表現(xiàn)為是局部極大或局部極小時(shí)，就看做是二個(gè)，否則看做一個(gè)。局部極大，如果這個(gè)頂點(diǎn)的前面和后面各有一些相鄰頂點(diǎn)的y坐標(biāo)，都小于該頂點(diǎn)的y坐標(biāo)。局部極小可類似地確定。 實(shí)際處理這個(gè)問題可以有一個(gè)簡(jiǎn)便辦法，那就是對(duì)應(yīng)該看做是一個(gè)的頂點(diǎn)，將其上面的邊縮短兩條相鄰掃描線對(duì)應(yīng)的一個(gè)單位。 計(jì)算掃描線與多邊形邊界線的交點(diǎn)：注意到若掃描線yi與多邊形邊界線交點(diǎn)x的坐標(biāo)是xi，則對(duì)下一條掃描線yi+l，它與那條邊界線的交點(diǎn)的x坐標(biāo)xi+1，可如下求出： 活躍邊表AET(ActiveEdgeTable)，用這個(gè)表存貯與當(dāng)前掃描線相交的各邊。每次離開一條掃描線進(jìn)入下一條之前，將表中有但與下一條掃描線不相交的邊清除出表，將與下一條掃描線相交而表中沒有的邊加入表中。 邊表ET(EdgeTable)，ET中各登記項(xiàng)按y坐標(biāo)遞增排序，每一登記項(xiàng)下的“吊桶”按所記x坐標(biāo)遞增排序，“吊桶”中各項(xiàng)的內(nèi)容依次是： 1. 邊的另端點(diǎn)的較大的y坐標(biāo)ymax。2. 與較小的y坐標(biāo)對(duì)應(yīng)的邊的端點(diǎn)的x坐 標(biāo)xm