計算機圖形學第七章.ppt

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

2、)是否在多邊形P內(nèi)的布爾函數(shù)。,Inside函數(shù)的實現(xiàn)原理,計算從(x,y)到(+,y)的射線與多邊形的交點個數(shù)。 若交點個數(shù)是奇數(shù)的話，就表明該點在多邊形內(nèi)部，否則該點在多邊形外部。,逐點判斷算法的具體實現(xiàn),假設(shè)framebuffer(x,y)是與(x,y)對應的幀緩沖器中的元素，用以存放對應像素的顏色值。設(shè)polygon_color為多邊形內(nèi)的顏色值，background_color為背景顏色。,逐點判斷算法的偽代碼程序,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),逐點判斷算法的優(yōu)缺點,優(yōu)點：簡單，易于理解。 缺點：忽略了像素與像素之間的聯(lián)系，如果整個平面有幾千萬個像素，也要一一進行判別，要做大量的計算工作，效率太低。,掃描線算法,掃描線算法利用了相鄰像素之間的連貫性，避免了反復求交的運算。 掃描線算法綜合利用了區(qū)域的連貫性，掃描線的連貫性和邊的連貫性。,區(qū)域的連貫性,假設(shè)多邊形P的頂點Pi(xi,yi),i=0,1,2n 各個頂點Pi的縱坐標

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

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

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

7、有的頂點,極值點,非極值點,對于奇點的兩種情況的處理,交點個數(shù)加一,交點個數(shù)不變,掃描線算法的數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),邊的分類表ET,邊的活化鏈表AEL,Ymax:邊的上端點的y坐標,x:在ET中表示邊的下端點 的x坐標，在AEL中則表示 邊與掃描線交點的x坐標,x:邊的斜率的倒數(shù),next:指向下一條邊的指針,邊的分類表ET,邊的分類表ET是按邊下端點的縱坐標y對非水平邊進行分類的鏈表數(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由與當前掃描線相交的所有多邊形的邊組成，它記錄了多邊形邊

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

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

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

11、有x坐標大于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)缺點,優(yōu)點：數(shù)據(jù)結(jié)構(gòu)和程序都比較簡單。 缺點：需對幀緩沖器中大批元素反復賦值，速度并不比掃描線算法快。,邊界標志算法,邊界標志算法采用先畫邊界后填色的方法，對幀緩沖器中每個元素賦值不超過2次。,邊界標志算法的算法思想,算法思想：先把多邊形邊界用另一種顏色標識出來，由于邊界已經(jīng)標識出來了，

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

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

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

15、G外，不能取為種子，停止填充； 否則置該象素顏色為new_color，再對上、下、左、右四個象素遞歸調(diào)用本身函數(shù)。,算法程序(內(nèi)點表示的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ào)用和停止條件。,其他形式的區(qū)域表示如何變動,若是邊界表示的4連通區(qū)域的程序只要改動判斷條件就行了。 if getpixel(framebuffer,x,y)boundary_color and getpixel(framebuffer,x,y)new_color,遞歸算法的優(yōu)缺點和作業(yè),優(yōu)點：程序簡單明了。 缺點：數(shù)據(jù)和函數(shù)反復進出系統(tǒng)堆棧，費時費內(nèi)存。 作業(yè)：內(nèi)點表

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

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

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