1、第七章,光柵圖形的掃描轉(zhuǎn)換與區(qū)域填色,多邊形的兩種表示方法,多邊形的表示方法,頂點(diǎn)表示用多邊形的頂點(diǎn)來(lái)表示,點(diǎn)陣表示用多邊形內(nèi)的象素來(lái)表示,兩種表示方法的優(yōu)缺點(diǎn),頂點(diǎn)表示：,直觀，幾何意義強(qiáng)，占內(nèi)存少，用得 普遍，但不能直接用于面著色。,點(diǎn)陣表示：,便于用幀緩沖器表示圖形，便于面著色。,什么是多邊形的掃描轉(zhuǎn)換,頂點(diǎn)表示,點(diǎn)陣表示,多邊形的掃描轉(zhuǎn)換,逐點(diǎn)判斷算法,算法思想：逐個(gè)像素判別，檢測(cè)其是否在多邊形內(nèi)部，從而給出位于多邊形內(nèi)部的像素集合。,逐點(diǎn)判斷算法的具體實(shí)現(xiàn),假設(shè)P=P0P1P2PnP0為一個(gè)給定多邊形，P0,P1,P2Pn為其頂點(diǎn)表示。 假設(shè)inside(P,x,y)是驗(yàn)證點(diǎn)(x,y

2、)是否在多邊形P內(nèi)的布爾函數(shù)。,Inside函數(shù)的實(shí)現(xiàn)原理,計(jì)算從(x,y)到(+,y)的射線與多邊形的交點(diǎn)個(gè)數(shù)。 若交點(diǎn)個(gè)數(shù)是奇數(shù)的話，就表明該點(diǎn)在多邊形內(nèi)部，否則該點(diǎn)在多邊形外部。,逐點(diǎn)判斷算法的具體實(shí)現(xiàn),假設(shè)framebuffer(x,y)是與(x,y)對(duì)應(yīng)的幀緩沖器中的元素，用以存放對(duì)應(yīng)像素的顏色值。設(shè)polygon_color為多邊形內(nèi)的顏色值，background_color為背景顏色。,逐點(diǎn)判斷算法的偽代碼程序,for y:=screen_ymin to screen_ymax do for x:=screen_xmin to screen_xmax do if inside(P

3、,x+0.5,y+0.5) then setpixel(framebuffer,x,y,polygon_color) else setpixel(framebuffer,x,y,background_color),逐點(diǎn)判斷算法的優(yōu)缺點(diǎn),優(yōu)點(diǎn)：簡(jiǎn)單，易于理解。 缺點(diǎn)：忽略了像素與像素之間的聯(lián)系，如果整個(gè)平面有幾千萬(wàn)個(gè)像素，也要一一進(jìn)行判別，要做大量的計(jì)算工作，效率太低。,掃描線算法,掃描線算法利用了相鄰像素之間的連貫性，避免了反復(fù)求交的運(yùn)算。 掃描線算法綜合利用了區(qū)域的連貫性，掃描線的連貫性和邊的連貫性。,區(qū)域的連貫性,假設(shè)多邊形P的頂點(diǎn)Pi(xi,yi),i=0,1,2n 各個(gè)頂點(diǎn)Pi的縱坐標(biāo)

4、按yi遞減排序： yi0, yi1, yi2 yin 其中yi,k= yi,k+1,區(qū)域的分割,現(xiàn)在作兩條掃描線y=yi,k和y=yi,k+1，這兩條掃描線之間的區(qū)域被多邊形分割成若干個(gè)梯形。 梯形上下兩底分別為兩條掃描線，腰在多邊形P的邊上或在顯示屏幕的邊界上。,分割后區(qū)域的分類,這些梯形分為兩類：在多邊形P內(nèi)部和在多邊形P外部。 兩類梯形交替地排列在長(zhǎng)方形區(qū)域內(nèi)。 如果知道了某點(diǎn)q所在區(qū)域在多邊形內(nèi)(或外)，就能知道整個(gè)長(zhǎng)方形區(qū)域內(nèi)的梯形排列情況。 此性質(zhì)稱為區(qū)域的連貫性。,掃描線的連貫性,假設(shè)e為一整數(shù)滿足 若掃描線y=e與多邊形P的邊Pi-1Pi相交，則記其交點(diǎn)的橫坐標(biāo)xei。 現(xiàn)在假

5、設(shè)xei1,xei2,xeil為掃描線與P的邊界各交點(diǎn)的橫坐標(biāo)的遞增序列，稱為交點(diǎn)序列。,交點(diǎn)序列的性質(zhì),l是偶數(shù)。 在該掃描線上只有區(qū)段(xeik,xei,k+1)，(k=1,3,5l-1)位于多邊形P內(nèi)，其余均在多邊形P外，兩種區(qū)段沿掃描線相間排列。 此性質(zhì)稱為掃描線的連貫性。,交點(diǎn)序列,若d=e-1，則位于掃描線y=d上的交點(diǎn)序列為xdj1,xdj2,xdjk。 若多邊形P的邊Pr-1Pr與掃描線y=e和y=d都相交，則xer和xdr滿足：,怎樣得到y(tǒng)=e上的交點(diǎn)序列,通過(guò)遞推式可以算出與y=e和y=d都相交的點(diǎn) 若再求出與掃描線y=d不相交但與下一掃描線y=e相交的所有邊PqPq+1上

6、的交點(diǎn)xeq 然后把這些點(diǎn)按底層的順序排列，就能得到了y=e上的交點(diǎn)序列,邊的連貫性,當(dāng)取某一整數(shù)k，0=k=n-1，使 1)兩序列元素?cái)?shù)個(gè)數(shù)相等 2)點(diǎn)(xeir,e)與(xdjr,d)位于多邊形同一條邊上，即ir=jr，得到 由上式就可遞推出xeir。,奇點(diǎn)的處理,當(dāng)掃描線與多邊形P的邊界的交點(diǎn)是P的頂點(diǎn)時(shí)，該交點(diǎn)稱為奇點(diǎn)。 由于連貫性，每一條掃描線與多邊形P的邊界交點(diǎn)個(gè)數(shù)都是偶數(shù)。但是過(guò)奇點(diǎn)的掃描線可能出現(xiàn)奇數(shù)。,出現(xiàn)奇點(diǎn)的兩種情況,出現(xiàn)奇點(diǎn)的兩種情況的討論,極值點(diǎn)就是附近的點(diǎn)都比其小或都比其大，滿足數(shù)學(xué)表達(dá)式為(yi-1-yi)(yi+1-yi)0 不是極值點(diǎn)的頂點(diǎn)稱為非極值點(diǎn)。,P所

7、有的頂點(diǎn),極值點(diǎn),非極值點(diǎn),對(duì)于奇點(diǎn)的兩種情況的處理,交點(diǎn)個(gè)數(shù)加一,交點(diǎn)個(gè)數(shù)不變,掃描線算法的數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),邊的分類表ET,邊的活化鏈表AEL,Ymax:邊的上端點(diǎn)的y坐標(biāo),x:在ET中表示邊的下端點(diǎn) 的x坐標(biāo)，在AEL中則表示 邊與掃描線交點(diǎn)的x坐標(biāo),x:邊的斜率的倒數(shù),next:指向下一條邊的指針,邊的分類表ET,邊的分類表ET是按邊下端點(diǎn)的縱坐標(biāo)y對(duì)非水平邊進(jìn)行分類的鏈表數(shù)組。,2,10,2,16,1,2,3,4,5,6,e7,e5,e7,e5,e4,e4,e1,e1,e2,e2,e3,e3,邊的活化表AEL,邊的活化表AEL由與當(dāng)前掃描線相交的所有多邊形的邊組成，它記錄了多邊形邊

8、沿掃描線的交點(diǎn)序列，并根據(jù)遞推式：,AEL,e1,e2,e3,e4,AEL在y=8的掃描線上的狀態(tài),不斷刷新交點(diǎn)序列。,掃描線算法的描述,步驟1：(y初始化)建立ET表，并且取掃描線縱坐標(biāo)y的初始值為ET中非空元素的最小序列。 步驟2：(AEL初始化)將邊的活化鏈表AEL設(shè)置為空。 步驟3：按從下到上的順序?qū)v坐標(biāo)值為y的掃描線(當(dāng)前掃描線)執(zhí)行子算法，直到ET和AEL都變?yōu)榭諡橹埂?子算法步驟,1)如果邊分類表ET中第y類元素為非空，則將屬于該類的所有邊從ET中取出并插入邊的活化鏈表AEL中，AEL中各邊按x的值(當(dāng)x的值相等時(shí)，按x值)遞增方式排序。,子算法步驟,2)若相對(duì)于當(dāng)前掃描線，邊

9、的活化鏈表AEL非空，則將AEL中邊兩兩依次配對(duì) (位置位于1,2的配對(duì)；位置位于3,4的配對(duì))，依次配對(duì)的邊的內(nèi)部點(diǎn)(像素)按多邊形的顏色屬性進(jìn)行著色。,子算法步驟,3)將邊的活化鏈表AEL中ymaxy的邊刪去 4)將邊的活化鏈表AEL剩下的每一條邊的x域累加x，即x:=x+x 5)將當(dāng)前掃描線的縱坐標(biāo)值y累加1，即y:=y+1,掃描線算法的優(yōu)缺點(diǎn),優(yōu)點(diǎn)：效率高。 缺點(diǎn)：程序復(fù)雜，需要排序。,邊緣填充算法,由于掃描線算法需要對(duì)多邊形的邊進(jìn)行排序，如果采用求余的方法，就不用對(duì)邊進(jìn)行排序了。,什么是求余？,數(shù)學(xué)上：A為一個(gè)給定的正數(shù)，數(shù)M的余是指A-M的差。記為 ,易得 光柵圖形上：若某區(qū)域已著

10、上值為M的某種顏色，對(duì)M作偶數(shù)次求余運(yùn)算后，此區(qū)域顏色不變，作奇數(shù)次求余運(yùn)算后，區(qū)域顏色變?yōu)?。,求余運(yùn)算的函數(shù)表示,Complement(framebuffer,x,y)為實(shí)施求余運(yùn)算的函數(shù)，其作用為 framebuffer(x,y):=A-framebuffer(x,y),邊緣填充算法的描述,假設(shè)x1,x2,xm為掃描線與多邊形P的交點(diǎn)的數(shù)列(不要求是遞增序列)。 步驟1:在y=e上所有像素都上值為 的顏色： for x:=screen_xmin to screen_xmax do setpixel(framebuffer,x,e,M),邊緣填充算法的描述,步驟2：對(duì)位于掃描線y=e上的所

11、有x坐標(biāo)大于xi(I=1,2,m)的像素求余。稱為向右求余: for i:=1 to m do for x:=xi to screen_xmax do Complement(framebuffer,x,y) 這樣，多邊形內(nèi)被著色M，多邊形外被著色 。,邊緣填充算法的圖示,邊緣填充算法的邊界求余,邊緣填充算法的優(yōu)缺點(diǎn),優(yōu)點(diǎn)：數(shù)據(jù)結(jié)構(gòu)和程序都比較簡(jiǎn)單。 缺點(diǎn)：需對(duì)幀緩沖器中大批元素反復(fù)賦值，速度并不比掃描線算法快。,邊界標(biāo)志算法,邊界標(biāo)志算法采用先畫邊界后填色的方法，對(duì)幀緩沖器中每個(gè)元素賦值不超過(guò)2次。,邊界標(biāo)志算法的算法思想,算法思想：先把多邊形邊界用另一種顏色標(biāo)識(shí)出來(lái)，由于邊界已經(jīng)標(biāo)識(shí)出來(lái)了，

12、邊界之間的各個(gè)區(qū)段要么填上多邊形內(nèi)部的顏色，要么填上背景色。,步驟1：以值為boundary_color的特殊顏色勾畫多邊形P的邊界。見(jiàn)書(shū)上的程序。 步驟2：逐條掃描線對(duì)多邊形著色。因?yàn)橐呀?jīng)標(biāo)志為特殊顏色的邊界是兩兩配對(duì)的。一對(duì)邊界點(diǎn)中間可能是多邊形區(qū)域內(nèi)的點(diǎn)，也可能是多邊形區(qū)域外的點(diǎn)。,邊界標(biāo)志算法的描述,如何判斷邊對(duì)中間的點(diǎn)是否在多邊形內(nèi)部,采用一個(gè)布爾變量interior_point，如果當(dāng)前像素位于多邊形內(nèi)，則為true，應(yīng)著polygon_color，否則為false，應(yīng)著background_color。,interior_point如何變化,此布爾變量起始在多邊形外，初始值為fa

13、lse，每碰到一個(gè)邊界像素，就取反。,邊界標(biāo)志算法的優(yōu)缺點(diǎn),優(yōu)點(diǎn)：避免了對(duì)幀緩沖器中大量元素的多次賦值，速度與掃描線算法相當(dāng)。 缺點(diǎn)：需逐條掃描線對(duì)幀緩沖器中的元素進(jìn)行搜索和比較。,區(qū)域填充,區(qū)域填充是指先將區(qū)域內(nèi)一點(diǎn)賦予給定顏色,然后將這種顏色擴(kuò)展到整個(gè)區(qū)域的過(guò)程。 最先的那點(diǎn)也叫做種子點(diǎn)。,區(qū)域的表示法,內(nèi)點(diǎn)表示法：把所給區(qū)域內(nèi)所有象素一一列舉出來(lái)。 邊界表示法：把所給區(qū)域邊界上的象素一一列舉出來(lái)。,區(qū)域的連通性,在區(qū)域填充算法中要求區(qū)域具有一定的連通性。,4連通性,4連通：區(qū)域任意兩點(diǎn)，從一點(diǎn)出發(fā)通過(guò)上、下、左、右方向，只經(jīng)過(guò)區(qū)域內(nèi)的點(diǎn)可到達(dá)另一點(diǎn)。,8連通性,8連通：區(qū)域任意兩點(diǎn)，從一

14、點(diǎn)出發(fā)通過(guò)水平、垂直和對(duì)角線方向，只經(jīng)過(guò)區(qū)域內(nèi)的點(diǎn)可到達(dá)另一點(diǎn)。,具體表現(xiàn)形式,內(nèi)點(diǎn)表示的4連通區(qū)域 邊界表示的4連通區(qū)域 內(nèi)點(diǎn)表示的8連通區(qū)域 邊界表示的8連通區(qū)域,兩種連通性的邊界不同,同一個(gè)區(qū)域可以看成是4連通區(qū)域，也可以看成是8連通區(qū)域，但是兩者的邊界是不同的。 4連通區(qū)域的邊界是8連通區(qū)域； 8連通區(qū)域的邊界是4連通區(qū)域。,遞歸算法,算法思想：先選取一個(gè)種子象素(x,y)，然后設(shè)此象素(x,y)為new_color，然后逐步按照連通性進(jìn)行遞歸調(diào)用將整個(gè)區(qū)域G都設(shè)置為new_color。,遞歸算法的算法步驟,先測(cè)試象素(x,y)的顏色是否等于old_color，若不是則說(shuō)明該象素在區(qū)域

15、G外，不能取為種子，停止填充； 否則置該象素顏色為new_color，再對(duì)上、下、左、右四個(gè)象素遞歸調(diào)用本身函數(shù)。,算法程序(內(nèi)點(diǎn)表示的4連通),Procedure flood-fill-4(x,y,old_color,new_color:integer) Begin if getpixel(framebuffer,x,y)=old_color then begin setpixel(framebuffer,x,y,new_color) flood-fill-4(x,y+1,old_color,new_color) flood-fill-4(x,y-1,old_color,new_color)

16、 flood-fill-4(x-1,y,old_color,new_color) flood-fill-4(x+1,y,old_color,new_color) end end,遞歸算法的特點(diǎn),遞歸這種方法必須包含兩個(gè)部分：自身調(diào)用和停止條件。,其他形式的區(qū)域表示如何變動(dòng),若是邊界表示的4連通區(qū)域的程序只要改動(dòng)判斷條件就行了。 if getpixel(framebuffer,x,y)boundary_color and getpixel(framebuffer,x,y)new_color,遞歸算法的優(yōu)缺點(diǎn)和作業(yè),優(yōu)點(diǎn)：程序簡(jiǎn)單明了。 缺點(diǎn)：數(shù)據(jù)和函數(shù)反復(fù)進(jìn)出系統(tǒng)堆棧，費(fèi)時(shí)費(fèi)內(nèi)存。 作業(yè)：內(nèi)點(diǎn)表

17、示的8連通區(qū)域、邊界表示的8連通區(qū)域的遞歸算法的程序。,掃描線算法,區(qū)域填充的掃描線算法適用于邊界表示的4連通區(qū)域。,掃描線算法的算法思想,首先填充種子點(diǎn)所在的當(dāng)前掃描線上位于給定區(qū)域內(nèi)的一區(qū)段。 然后確定與這一區(qū)段相鄰的上下兩條掃描線上位于區(qū)域內(nèi)的區(qū)段，并依次把這些區(qū)段的右端點(diǎn)入棧。 然后不斷取出棧頂?shù)姆N子重復(fù)繼續(xù)上一過(guò)程，直到?？?。,算法的實(shí)現(xiàn)（1）,1）初始化:將種子點(diǎn)壓入初始化后的棧。 2）出棧：如果棧為空，算法結(jié)束；否則取棧頂元素為當(dāng)前種子點(diǎn)。 3）區(qū)段填充：從當(dāng)前種子點(diǎn)開(kāi)始沿水平掃描線向左右兩個(gè)方向逐個(gè)像素進(jìn)行填色，直至抵達(dá)邊界為止。 4）定范圍：以XLEFT和XRIGHT分別表示

18、第三步中填充的區(qū)段兩個(gè)端點(diǎn)的橫坐標(biāo)。,算法的實(shí)現(xiàn)（2）,5）進(jìn)棧：分別在于當(dāng)前掃描線相鄰的上下兩條掃描線上，確定位于區(qū)間【XLEFT,XRIGHT】?jī)?nèi)的給定區(qū)域的區(qū)段。如果這些區(qū)段內(nèi)的像素顏色值為內(nèi)部點(diǎn)或邊界點(diǎn)的顏色的話，則轉(zhuǎn)到第二步，否則從XLEFT開(kāi)始向右逐點(diǎn)判斷，直到碰到邊界點(diǎn)停下，此時(shí)把邊界點(diǎn)左端的點(diǎn)（區(qū)段右端點(diǎn)）入棧。向右繼續(xù)逐點(diǎn)判斷是否還存在空白區(qū)段，如果有，把這些區(qū)段的右端點(diǎn)依次入棧。,實(shí)例,算法的優(yōu)點(diǎn)和缺點(diǎn),優(yōu)點(diǎn)：只需把掃描線右端種子入棧，而無(wú)須把全部象素入棧，進(jìn)出棧次數(shù)大為減少，內(nèi)存節(jié)省很多，速度提高很快。 缺點(diǎn)：對(duì)于已經(jīng)填充的直線可能會(huì)多次地重復(fù)檢查是否已經(jīng)填充。,多邊形掃

19、描轉(zhuǎn)換與區(qū)域填充的互相轉(zhuǎn)化,若把多邊形內(nèi)一點(diǎn)作為種子點(diǎn)，并用以前學(xué)過(guò)的直線生成算法將多邊形的邊界表示為8連通區(qū)域的話，多邊形的掃描轉(zhuǎn)換問(wèn)題可以轉(zhuǎn)換為區(qū)域填充問(wèn)題。 反過(guò)來(lái)，若已知多邊形的頂點(diǎn)表示，則區(qū)域填充問(wèn)題可以轉(zhuǎn)換為多邊形的掃描轉(zhuǎn)換問(wèn)題。,多邊形的掃描轉(zhuǎn)換和區(qū)域填充的不同（1）,基本思想不同： 多邊形的掃描轉(zhuǎn)換：將多邊形的頂點(diǎn)表示轉(zhuǎn)換為點(diǎn)陣表示，利用多邊形各種形式的連貫性。 區(qū)域填充：只改變區(qū)域內(nèi)的顏色，不改變區(qū)域表示方法，利用區(qū)域的連通性。,多邊形的掃描轉(zhuǎn)換和區(qū)域填充的不同（2）,對(duì)邊界的要求不同： 多邊形的掃描轉(zhuǎn)換：要求每一條掃描線與多邊形邊界的交點(diǎn)個(gè)數(shù)是偶數(shù)。 區(qū)域填充：要求4連通區(qū)域邊界為封閉8連通區(qū)域，要求8連通區(qū)域邊界為封閉4連通區(qū)域。,多邊形的掃描轉(zhuǎn)換和區(qū)域填充的不同（3）,出發(fā)點(diǎn)（初始點(diǎn)）不同： 多邊形的掃描轉(zhuǎn)換：要求多邊形頂點(diǎn)要依次給出。 區(qū)域填充：要求指定區(qū)域內(nèi)一點(diǎn)為種子點(diǎn)，但對(duì)任意多邊形來(lái)說(shuō)，要確定某點(diǎn)為多邊形內(nèi)部一點(diǎn)要做大量的計(jì)算。,光柵圖形的走樣現(xiàn)象,邊界階梯形：采用離散量表示連續(xù)量而引起的,細(xì)節(jié)失真,狹小圖形遺失,運(yùn)動(dòng)圖形的閃光現(xiàn)象：出現(xiàn)在緩慢移動(dòng)的物體中,線段反走樣算法的要點(diǎn),線段有一定的寬度，應(yīng)把線段看作狹長(zhǎng)的矩形。 線段有一定的面積，當(dāng)