計(jì)算機(jī)圖形學(xué)課件第3講：多邊形的掃描轉(zhuǎn)換與區(qū)域填充

多邊形的掃描轉(zhuǎn)換與區(qū)域填充區(qū)域的表示方法區(qū)域的表示方法頂點(diǎn)表示（幾何表示）用區(qū)域的頂點(diǎn)序列來表示區(qū)域，經(jīng)過數(shù)學(xué)計(jì)算可知區(qū)域是由什么樣的相連直線或曲線構(gòu)成其輪廓線的點(diǎn)陣表示（像素表示）用位于多邊形內(nèi)的像素集合來刻畫多邊形2區(qū)域填充的概念掃描轉(zhuǎn)換（scanconversion）多邊形將多邊形頂點(diǎn)表示形式轉(zhuǎn)換成點(diǎn)陣表示形式區(qū)域填充（regionfill）要求對此區(qū)域范圍內(nèi)的所有像素賦予指定的顏色代碼確定哪些像素位于填充區(qū)域的內(nèi)部用指定顏色繪制這些像素3逐點(diǎn)判斷法（暴力）基本原理判斷繪圖窗口內(nèi)的像素是否位于多邊形內(nèi)，若是，則用指定顏色繪制該像素問題如何判斷點(diǎn)在多邊形的內(nèi)外關(guān)系？射線法累計(jì)角度法4(xmin,ymin)(xmax,ymax)P1P2射線法若交點(diǎn)數(shù)=偶數(shù)（包括0），則點(diǎn)在多邊形之外5BDEPABCDEPAC若交點(diǎn)數(shù)=奇數(shù)，則點(diǎn)在多邊形之內(nèi)掃描線算法特點(diǎn)程序簡單測試點(diǎn)是否在多邊形內(nèi)的算法速度太慢，效率低改進(jìn)逐點(diǎn)判斷法孤立考慮各個(gè)像素與多邊形的內(nèi)外關(guān)系利用內(nèi)部點(diǎn)的連貫性（Coherence）6掃描轉(zhuǎn)換與區(qū)域填充暴力算法不能很好地利用空間連貫性空間連貫性性（Spatialcoherence）若當(dāng)前像素在多邊形內(nèi)部時(shí)，與其空間臨近的像素亦很有可能在多邊形內(nèi)部掃描轉(zhuǎn)換區(qū)域填充7掃描轉(zhuǎn)換與區(qū)域填充掃描轉(zhuǎn)換算法區(qū)域填充算法8掃描轉(zhuǎn)換算法算法目標(biāo)利用相鄰像素之間的連貫性，提高算法效率處理對象：簡單多邊形非自交多邊形（邊與邊之間除了頂點(diǎn)外無其它交點(diǎn)）掃描線(ScanningLine)平行于坐標(biāo)軸的直線一般取平行于X軸區(qū)間：掃描線與邊的交點(diǎn)間的線段9多邊形10X11需要找出掃描線上與多邊形相交的像素，填充之約定：至底向上掃描(x1,y1)(x3,y3)(x2,y2)掃描線算法依順序取出每一條射線，求其與多邊形邊界的交點(diǎn)，并對每一對交點(diǎn)中的像素進(jìn)行填充12射線abcd掃描線算法掃描線算法求交計(jì)算掃描線與多邊形各邊的交點(diǎn)排序把所有交點(diǎn)按x值遞增順序排序配對第1個(gè)與第2個(gè)，第3個(gè)與第4個(gè)等，每對交點(diǎn)代表一個(gè)相交區(qū)間填色把相交區(qū)間內(nèi)：多邊形顏色相交區(qū)間外：背景色13C射線1BADEF2341abdc奇點(diǎn)取舍問題當(dāng)射線與多邊形頂點(diǎn)相交時(shí)，稱該交點(diǎn)為奇點(diǎn)。如果奇點(diǎn)的計(jì)數(shù)不正確，會(huì)導(dǎo)致填充錯(cuò)誤14射線4與多邊形相交時(shí)，有一個(gè)奇點(diǎn)。如果奇點(diǎn)計(jì)數(shù)為奇數(shù)個(gè)，則總共得到3個(gè)交點(diǎn)，此時(shí)多邊形會(huì)將區(qū)域外部填充，而區(qū)域內(nèi)部不予填充，出現(xiàn)錯(cuò)誤。射線2與多邊形相交時(shí)，有一個(gè)奇點(diǎn)。如果奇點(diǎn)計(jì)數(shù)依照上述計(jì)為偶數(shù)個(gè)，則總共得到3個(gè)交點(diǎn)，仍然會(huì)造成錯(cuò)誤填充。C射線4射線1射線2射線3BAabcd2兩個(gè)交點(diǎn)1兩個(gè)交點(diǎn)掃描線算法解決方法當(dāng)奇點(diǎn)在多邊形兩邊之下時(shí)，該點(diǎn)計(jì)2次，如A、D、H點(diǎn)當(dāng)奇點(diǎn)在多邊形兩邊之上時(shí)，該點(diǎn)計(jì)0次，如B、F、I點(diǎn)當(dāng)奇點(diǎn)在多邊形兩邊中間時(shí)，該點(diǎn)計(jì)1次，如C、E、G點(diǎn)15FBCGEAIDH掃描線算法取整問題掃描線與多邊形邊界交點(diǎn)坐標(biāo)值不為整數(shù)解決方法當(dāng)掃描線與多邊形邊界交點(diǎn)坐標(biāo)為小數(shù)值時(shí)，如果多邊形在此邊界右側(cè)，則將該小數(shù)值進(jìn)1作為邊界點(diǎn)，否則舍去小數(shù)部分并進(jìn)行填充，這樣可使多邊形不擴(kuò)大16掃描線算法水平邊問題掃描線與多邊形的水平邊相交時(shí)，交點(diǎn)理論上是無窮多個(gè)解決方法對于多邊形的水平邊，不計(jì)它與射線的交點(diǎn)17掃描線算法掃描線算法填充擴(kuò)大化問題若將多邊形邊界看成是多邊形內(nèi)部，并對它們填充，則該多邊形會(huì)被放大解決方法采取“左閉右開，下閉上開”的方法，即將左、下邊界像素視為多邊形內(nèi)部，需填充，而右、上邊界則為多邊形外部，不予填充18123123掃描線算法簡單（naive）掃描線算法每條掃描線都要求交點(diǎn)解決：空間連貫性（spatialcoherence）19掃描線算法（改進(jìn)）連貫性(Coherence)邊的連貫性(EdgeCoherence)某條邊與當(dāng)前掃描線相交，也可能與下一條掃描線相交掃描線的連貫性(Scan-lineCoherence)當(dāng)前掃描線與各邊的交點(diǎn)順序與下一條掃描線與各邊的交點(diǎn)順序可能相同或類似區(qū)間的連貫性(SpanCoherence)同一區(qū)間上的像素取同一顏色屬性20√√掃描線算法（改進(jìn)）計(jì)算交點(diǎn)分類第一類交點(diǎn)：位于同一條邊上的后繼交點(diǎn)--(P2,P4)第二類交點(diǎn)：新出現(xiàn)的邊與掃描線的交點(diǎn)--(P3)計(jì)算：y＝e＋1的交點(diǎn)第一類交點(diǎn)：邊的連貫性！x’＝x＋1/k第二類交點(diǎn)：線段的下端點(diǎn)即為交點(diǎn)21P3P4P0P2P1增量算法掃描線算法(改進(jìn))排序掃描線連貫性采用插入排序復(fù)雜度為O(n)22掃描線算法(改進(jìn))數(shù)據(jù)結(jié)構(gòu)——加速結(jié)構(gòu)求交問題空間換時(shí)間邊表（Edgetable,ET）動(dòng)記錄與當(dāng)前掃描態(tài)表（活性邊表，ActiveEdgetable，AET）鏈表形式23掃描線算法(改進(jìn))ET定義每條掃描線，對應(yīng)一個(gè)鏈表鏈表中每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)x1/kymaxnext24typedefstruct{int ymax;float x;float deltax;Edge* nextEdge;}Edge;

x：交點(diǎn)x

坐標(biāo)Deltax（1/k）：邊的斜率的倒數(shù)ymax：邊的上端點(diǎn)的y坐標(biāo)值（何時(shí)不再相交）nextEdge：下一條邊的指針掃描線算法(改進(jìn))下一條掃描線的邊表（邊的連續(xù)性）活性邊表（AET）更新交點(diǎn)的計(jì)算——增量算法：當(dāng)掃描線y=ymax

，說明該掃描線與此邊不相交（上開下閉），將該邊從AET中刪除Deltax不變問題初始交點(diǎn)如何計(jì)算新邊如何得到25掃描線算法(改進(jìn))新邊表（NewEdgeTable，NET）按邊的下端點(diǎn)y坐標(biāo)，對非水平邊進(jìn)行分類的鏈表每條掃描線（y坐標(biāo)）：建立它的新邊表作用避免盲目求交（增量算法的初值）計(jì)算第二類交點(diǎn)坐標(biāo)26掃描線算法(改進(jìn))AET的建立先按下端點(diǎn)的y坐標(biāo)值對所有的邊進(jìn)行分組對每條邊：若低端點(diǎn)y值為ymin，則該邊就放在ymin所對應(yīng)的桶中桶中的各邊：按下端點(diǎn)的x坐標(biāo)值排序2728∧∧∧∧7-5/2373/25∧209∧13011∧0128765437-5/2973/211∧224466810128101214（7，7）（2，9）（13，11）（13，5）（7，1）（2，3）l1l2l3l4l5l6l1l6l2l5l3l4掃描線算法(改進(jìn))建立NET;AET為空;foreach掃描線i

NET[i]按x順序插入AET;

按AET邊順序產(chǎn)生區(qū)間; 填充區(qū)間; 遍歷AET，刪除y_max=i的結(jié)點(diǎn)，對y_max<i的結(jié)點(diǎn)，令x=x+deltax;29例：活性邊表的更新。30∧∧7-5/2373/25∧20913011∧0128765437-5/2973/211l1l6l2l5l3l49101117/23/25∧13011∧103/25∧20923/23/25∧20920920920917/23/21113011∧103/2117-5/2913011∧13011∧23/23/21113011∧224466810128101214（7，7）（2，9）（13，11）（13，5）（7，1）（2，3）l1l2l3l4l5l6掃描線算法(改進(jìn))9/2-5/23掃描線算法(改進(jìn))優(yōu)點(diǎn)：每個(gè)像素只訪問一次，避免了反復(fù)求交點(diǎn)等大量運(yùn)算與設(shè)備無關(guān)缺點(diǎn)數(shù)據(jù)結(jié)構(gòu)復(fù)雜只適合軟件來實(shí)現(xiàn)31掃描轉(zhuǎn)換在GIS上的應(yīng)用多邊形的矢量-柵格轉(zhuǎn)換32掃描轉(zhuǎn)換的邊界標(biāo)志算法柵格算法掃描填充算法閱讀33掃描轉(zhuǎn)換與區(qū)域填充掃描轉(zhuǎn)換算法區(qū)域填充算法34種子填充算法區(qū)域：點(diǎn)陣表示的圖形，像素集合表示方法內(nèi)點(diǎn)表示區(qū)域內(nèi)的所有像素具有同一顏色，而區(qū)域外的所有像素具有另一種顏色邊界表示區(qū)域邊界上的所有像素具有特定的顏色（可以是填充色），在區(qū)域內(nèi)的所有像素均不能具有這一特定顏色，而且邊界外的像素也不能具有與邊界相同的顏色35種子填充算法基本思想：假設(shè)在多邊形區(qū)域內(nèi)部至少有一個(gè)像素是已知的（此像素稱為種子像素），由此出發(fā)找到區(qū)域內(nèi)所有其他像素，并對其進(jìn)行填充空間連貫性種子填充算法要求區(qū)域是連通的36種子填充算法4連通區(qū)域：區(qū)域中任意兩點(diǎn)可通過上下左右四個(gè)方向互相到達(dá)8連通區(qū)域：區(qū)域中任意兩點(diǎn)可通過上下左右和對角線八個(gè)方向互相到達(dá)37種子填充算法4連通與8連通區(qū)域的區(qū)別連通性：4連通可看作8連通區(qū)域，但對邊界有不同要求依據(jù)區(qū)域內(nèi)點(diǎn)能否訪問到區(qū)域外的點(diǎn)，對邊界的要求是4連通區(qū)域，邊界只要8連通即可8連通區(qū)域，邊界必須是4連通例：如左圖（1）4連通區(qū)域，邊界為像素（2）8連通區(qū)域，邊界為和像素38種子填充算法分類四向算法從四個(gè)方向?qū)ふ蚁乱幌袼攸c(diǎn)有時(shí)不能通過狹窄區(qū)域，因而不能填滿多邊形八向算法允許從八個(gè)方向搜索下一像素點(diǎn)有時(shí)會(huì)填出多邊形的邊界39種子填充算法40voidBoundaryFill4(intx,inty,intoldColor,intnewColor){ color=GetPixel(x,y);if((color!=oldColor)&&(color!=newColor)){ SetPixel(x,y,newColor);BoundaryFill4(x+1,y,oldColor,newColor);BoundaryFill4(x,y+1,oldColor,newColor);BoundaryFill4(x-1,y,oldColor,newColor);BoundaryFill4(x,y-1,oldColor,newColor);}}簡單的種子填充算法(四向算法)種子填充算法棧實(shí)現(xiàn)的種子填充算法(四向算法)41voidBoundaryFill4(intx,inty,intboundColor,intnewColor){intpx=x,py=y;stackPush(px,py);while(!stackEmpty()){ stackPop(&px,&py); SetPixel(x,y,newColor);

color=GetPixel(px+1,py); if((color!=boundColor)&&(color!=newColor)) stackPush(px+1,py); color=GetPixel(px,py+1); if((color!=boundColor)&&(color!=newColor)) stackPush(px,py+1); color=GetPixel(px-1,py); if((color!=boundColor)&&(color!=newColor)) stackPush(px-1,py); color=GetPixel(px,py-1); if((color!=boundColor)&&(color!=newColor)) stackPush(px,py-1);}}//填充//入棧6754S9328S24793847948479568479684797847984799479479S799填充S填充2填充3填充4填充5填充6填充7填充8填充946532897S42種子填充算法種子填充算法簡單的種子填充算法的缺陷有些像素會(huì)多次入棧，降低算法效率要求有很大的存儲(chǔ)空間來實(shí)現(xiàn)棧結(jié)構(gòu)遞歸執(zhí)行，算法簡單，但效率不高，區(qū)域內(nèi)每一像素都引起一次遞歸，需要進(jìn)行入/出棧操作不沿四方向盲目填充有指定方向掃描線算法43區(qū)域填充的掃描線算法在任意不間斷區(qū)間中只取一個(gè)種子像素不間斷區(qū)間指在一條掃描線上一組相鄰元素填充當(dāng)前掃描線上的不間斷區(qū)間；在當(dāng)前填充區(qū)間上下掃描線上尋找新的種子點(diǎn)，作為新的填充區(qū)間可以填充有孔區(qū)域，對于每一個(gè)待填充區(qū)段，只需入棧一次，因此提高了區(qū)域填充的效率44區(qū)域填充的掃描線算法初始化：堆棧置空，將種子(x