計算機圖形學(xué)-圖形填充正規(guī)版資料

計算機圖形(túxíng)學(xué)圖形(túxíng)填充第一頁，共50頁。圖形分類線段圖形直線、圓以及自由曲線等，用于表現(xiàn)物體的幾何輪廓實面積圖形封閉圖形，在其封閉的區(qū)域內(nèi)具有相同的顏色。既表現(xiàn)了物體的幾何輪廓，也反映了物體表面(biǎomiàn)的色彩。 在計算機屏幕上表現(xiàn)為：處于封閉圖形內(nèi)部區(qū)域的屏幕象素具有相同的亮度和色彩。第二頁，共50頁。實面積圖形的表示頂點表示法以封閉多邊形的頂點坐標(biāo)數(shù)據(jù)（或者，閉合曲線(qūxiàn)的特征數(shù)據(jù)）來描述實面積圖形；其內(nèi)部以用戶指定的顏色填充；基本填充方法：多邊形填充。點陣表示法 以點陣數(shù)組的方式描述實面積圖形；圖形的內(nèi)部以用戶指定的顏色包圍或者組成，易于面著色；基本填充方法：種子填充。頂點(dǐngdiǎn)表示點陣表示:多邊形的掃描轉(zhuǎn)換。第三頁，共50頁。多邊形分為凸多邊形、凹多邊形、含內(nèi)環(huán)的多邊形。注意(zhùyì)：凹、凸點的判斷第四頁，共50頁。實區(qū)域(qūyù)填充算法確定(quèdìng)待填充的象素，即檢查光柵的每一像素是否位于多邊形區(qū)域內(nèi)解決的主要(zhǔyào)問題是什么？圖案填充還有一個什么象素填什么顏色的問題曲線圍成的區(qū)域，可用多邊形逼近第五頁，共50頁。多邊形的填充原理多邊形填充的任務(wù):把多邊形的頂點表示轉(zhuǎn)換為點陣表示。即，找出所有位于多邊形內(nèi)部的像素點，以所要求的像素值畫這些像素點?？赡艿淖龇ǎ罕闅v屏幕上的像素點，判斷是否在多邊形內(nèi)部，然后填充。問題：逐點判斷，速度太慢；不是(bùshi)所有對多邊形都容易作內(nèi)部判斷。關(guān)鍵：尋找一種快速而通用的內(nèi)部判斷方法。第六頁，共50頁。掃描線:點陣圖形在屏幕(píngmù)上的像素點，可以認為是由位于一條條水平直線上的像素點構(gòu)成的.對每一條切割多邊形的掃描線，決定掃描線上哪些像素點是在多邊形內(nèi)部，并對這些相應(yīng)的像素點賦以合適的值表示某種顏色或灰度，就能對整個多邊形進行掃描轉(zhuǎn)換。第七頁，共50頁。一條(yītiáo)掃描線與一個多邊形的關(guān)系:相交或不相交.若相交,則直線被多邊形分割成不同的直線段,其中一些在多邊形內(nèi),另外一些在多邊形外.并且這些多邊形內(nèi)外的直線段大多數(shù)情況下相互交替出現(xiàn).第八頁，共50頁。掃描線連貫性(scanlinecoherence)：當(dāng)像素點位于多邊形內(nèi)(外)的直線段上時,它就位于多邊形內(nèi)(外).也就是說，與多邊形相交的一條(yītiáo)掃描線上總會有一組相互相連的像素點都位于多邊形之內(nèi)。每一個像素點—像素點所在的直線段第九頁，共50頁。分析 從掃描線的一端出發(fā)(chūfā),當(dāng)前在多邊形外,當(dāng)沿掃描線前進到達與多邊形的第一個交點時,就進入多邊形內(nèi)；由于掃描線的另一端是在多邊形外,繼續(xù)沿掃描線前進一定會走出多邊形內(nèi)部,于是一定會遇到第二個交點。這時可以看到,第一和第二個交點之間的直線段就位于多邊形內(nèi)； 如果沒有更多的交點,則該掃描線上只有一段直線段位于多邊形內(nèi)。否則,繼續(xù)沿掃描線前進,此時位于多邊形外,直到遇到第三個交點后,重新進入多邊形內(nèi)。類似前面的分析,一定有第四個交點。于是第三,第四個交點給出的直線段就位于多邊形內(nèi)； 如果還有更多的交點,就重復(fù)這樣的過程,直到?jīng)]有新的交點為止。因為交點個數(shù)是有限的,這一過程是一定可以結(jié)束的。第十頁，共50頁。射線交點計數(shù)的方法： 從多邊形外一點，引水平射線（即掃描線）穿過(chuānɡuò)多邊形，記錄掃描線與多邊形邊的交點個數(shù)情況，當(dāng)交點數(shù)為奇數(shù)時，掃描線處在多邊形內(nèi)部，當(dāng)交點數(shù)為偶數(shù)時，掃描線處在多邊形外部。多邊形與同一掃描線的交點按x方向大小順序排列，并兩兩配對，則可得掃描線在多邊形內(nèi)的直線段，從而可實現(xiàn)多邊形填充。第十一頁，共50頁。奇點問題 奇點：當(dāng)掃描線與多邊形的交點是頂點。如果奇點存在,上述判別過程就不能正確地進行多邊形頂點的潛在問題這個問題與交點的求解方法有關(guān). 所有交點通過掃描線所在(suǒzài)直線依次與多邊形各邊所在(suǒzài)直線段求解出。如果某個交點恰恰是其中一個邊的端點：重復(fù)計算。水平邊問題 水平邊重合于某一條掃描線：無數(shù)多交點，不予處理第十二頁，共50頁?？赡?kěnéng)情況圖示： 第十三頁，共50頁。奇點的處理(chǔlǐ)多邊形的頂點(dǐngdiǎn)可分為兩類：極值奇點和非極值奇點。如果(yi-1-yi)(yi+1-yi)≥0，則稱頂點(dǐngdiǎn)Pi為極值點；否則稱Pi為非極值點。規(guī)定：奇點是極值點時，該點按兩個交點計算，否則按一個交點計算。第十四頁，共50頁。x3y310：字符的筆畫(bǐhuà)不經(jīng)過此位，該像素置為背景顏色設(shè)G為一內(nèi)點表示的區(qū)域，(x,y)為區(qū)域內(nèi)一點，old_color為G的原色。（1）確定多邊形所占有的最大掃描線數(shù)，得到多邊形頂點的最小和最大y值（ymin和ymax）。第四十二頁，共50頁。FloodFill4(x,y-1,oldColor,newColor);不透明填充1：前景色邊界表示法中，由于邊界以特殊(tèshū)顏色指定，填充算法可逐個像素地向外處理，直到遇到邊界顏色為止。第三十二頁，共50頁。區(qū)域填充指先將區(qū)域的一點(yīdiǎn)賦予指定的顏色，然后將該顏色擴展到整個區(qū)域的過程。區(qū)域指已經(jīng)表示成點陣形式的填充圖形，它是象素的集合。直線方程：ax+by+c=0顯示步驟：從字庫檢索字符數(shù)據(jù)提出端點(duāndiǎn)坐標(biāo)幾何變換根據(jù)標(biāo)志位顯示另一種預(yù)處理辦法是，通過判斷每條斜邊的端點y值是否單調(diào)來找出奇點，對極值端點不作處理，而對非極值端點則縮短(suōduǎn)其中一條斜邊的端點。(2)出棧：若?？談t結(jié)束。檢查交于該頂點(dǐngdiǎn)的兩條邊的另外兩個端點的y值大于該頂點(dǐngdiǎn)y值的個數(shù)奇點的計數(shù)問題543210P1P2P3P4I1I2I3I4P5掃描線5掃描線4掃描線3掃描線2掃描線1I5I6檢查交于該頂點(dǐngdiǎn)的兩條邊的另外兩個端點的y值大于該頂點(dǐngdiǎn)y值的個數(shù)計數(shù)(jìshù)0次計數(shù)(jìshù)1次計數(shù)2次第十五頁，共50頁。12/13/202215總結(jié)：簡單地數(shù)交點不能解決所有的問題，需要補充規(guī)則(guīzé)完善此射線交點計數(shù)法： （1）忽略多邊形的水平邊； （2）與多邊形的極值點端點相交時，該點算做兩個； （3）其余的非極值點端點，僅計算一次。實際操作任務(wù)：（1）判斷水平邊；（2）判斷奇點；在求交點過程中，因為是依次計算掃描線與各條邊的交點，因此奇點也自然被計算兩次。但造成另一個問題是非極值點的頂點也被計算了兩次。第十六頁，共50頁。 對此問題的一種處理辦法是，計算前，先將每條斜邊的低端點在y方向上縮小一個(yīɡè)屏幕坐標(biāo)單位，這將忽略極小值 第十七頁，共50頁。另一種預(yù)處理辦法是，通過判斷每條斜邊的端點y值是否單調(diào)來找出奇點，對極值端點不作處理，而對非極值端點則縮短(suōduǎn)其中一條斜邊的端點。此法的缺點是，填充的圖形(túxíng)可能會出現(xiàn)殘缺第十八頁，共50頁。這樣處理(chǔlǐ)后，極值點仍計算兩次，而非極值點的斜邊交點只計算一次。經(jīng)上述約定及處理(chǔlǐ)后，可保證同一掃描線與多邊形的交點成對出現(xiàn)，因此只要算出交點，填充就可以利用畫直線算法快速完成。第十九頁，共50頁。枚舉出邊界上所有(suǒyǒu)的像素對每一條切割多邊形的掃描線，決定掃描線上哪些像素點是在多邊形內(nèi)部，并對這些相應(yīng)的像素點賦以合適的值表示某種顏色或灰度，就能對整個多邊形進行掃描轉(zhuǎn)換。4連通(liántōng)、8連通(liántōng)、16連通(liántōng)在計算機屏幕上表現(xiàn)為：處于封閉圖形內(nèi)部區(qū)域的屏幕象素具有相同的亮度和色彩。確定需要填充(tiánchōng)的區(qū)域與當(dāng)前掃描線的相交區(qū)間區(qū)域填充指先將區(qū)域的一點(yīdiǎn)賦予指定的顏色，然后將該顏色擴展到整個區(qū)域的過程。第三十七頁，共50頁。多邊形的掃描轉(zhuǎn)換轉(zhuǎn)化為區(qū)域填充問題：當(dāng)給定多邊形內(nèi)一點為種子點，并用Bresenham或DDA算法將多邊形的邊界表示(biǎoshì)成八連通區(qū)域后，則多邊形的掃描轉(zhuǎn)換轉(zhuǎn)化為區(qū)域填充。填充圖元生成(shēnɡchénɡ)原理多邊形與同一掃描線的交點按x方向大小順序排列，并兩兩配對，則可得掃描線在多邊形內(nèi)的直線段，從而可實現(xiàn)多邊形填充。設(shè)G為一內(nèi)點表示的區(qū)域，(x,y)為區(qū)域內(nèi)一點，old_color為G的原色。區(qū)域填充—掃描線算法(suànfǎ)（舉例分析）這樣處理(chǔlǐ)后，極值點仍計算兩次，而非極值點的斜邊交點只計算一次。連通(liántōng)性如果還有更多的交點,就重復(fù)這樣的過程,直到?jīng)]有新的交點為止。掃描線算法步驟如下：（1）確定多邊形所占有的最大掃描線數(shù)，得到多邊形頂點的最小和最大y值（ymin和ymax）。（2）從y=ymin到y(tǒng)=ymax，每次用一條掃描線進行(jìnxíng)填充。（3）對一條掃描線填充的過程可分為四個步驟：a、求交：計算掃描線與多邊形各邊的交點；b、排序：把所有交點按遞增順序進行(jìnxíng)排序；c、交點配對：第一個與第二個，第三個與第四個等等，每對交點就代表掃描線與多邊形的一個相交區(qū)間；d、區(qū)間填色：把這些相交區(qū)間內(nèi)的像素置成不同于背景色的填充色。

第二十頁，共50頁。如何計算下一條掃描線與邊的交點(jiāodiǎn)。直線方程：ax+by+c=0當(dāng)前交點(jiāodiǎn)坐標(biāo)：(xi,yi)下一交點(jiāodiǎn)坐標(biāo)：(xi+1,yi+1)xi+1=((-byi+1)-c)/a=((-byi+1)-c)/a=xi-b/a=xi+1/mi第二十一頁，共50頁。掃描線算法(suànfǎ)特點特點：算法效率較高。缺點：對各種表的維持和排序開銷(kāixiāo)太大，適合軟件實現(xiàn)而不適合硬件實現(xiàn)。第二十二頁，共50頁。填充圖元生成(shēnɡchénɡ)原理多邊形掃描轉(zhuǎn)換區(qū)域(qūyù)填充第二十三頁，共50頁。區(qū)域(qūyù)填充區(qū)域指已經(jīng)表示成點陣形式的填充圖形，它是象素的集合。區(qū)域填充指先將區(qū)域的一點(yīdiǎn)賦予指定的顏色，然后將該顏色擴展到整個區(qū)域的過程。區(qū)域填充算法要求區(qū)域是連通的。第二十四頁，共50頁。區(qū)域(qūyù)填充表示方法：內(nèi)點表示、邊界表示內(nèi)點表示枚舉出區(qū)域內(nèi)部的所有(suǒyǒu)像素內(nèi)部的所有(suǒyǒu)像素著同一個顏色邊界像素著與內(nèi)部像素不同的顏色邊界表示枚舉出邊界上所有(suǒyǒu)的像素邊界上的所有(suǒyǒu)像素著同一顏色內(nèi)部像素著與邊界像素不同的顏色

第二十五頁，共50頁。區(qū)域(qūyù)填充—區(qū)域(qūyù)的連通性連通(liántōng)性 4連通(liántōng)、8連通(liántōng)、16連通(liántōng)4連通(liántōng)像素（P(xp,yp)）N4(p)={r|d4(p,r)=1}d4(p,r)=|xp-xr|+|yp-yr|8連通(liántōng)N8(p)={r|d8(p,r)=1}d8(p,r)=max(|xp-xr|,|yp-yr|)prrrrrrrrprrrr第二十六頁，共50頁。區(qū)域(qūyù)填充—區(qū)域(qūyù)的連通性16連通N16(p)=N8(p)∪Nk(p)Nk(p)={dk(p,r)=1}:馬步(mǎbù)鄰域馬步(mǎbù)距離rrrrprrrrrrrrrrrr第二十七頁，共50頁。區(qū)域(qūyù)填充—區(qū)域(qūyù)的連通性4連通與8連通區(qū)域的區(qū)別連通性：4連通可看作8連通區(qū)域，但對邊界(biānjiè)有要求對邊界(biānjiè)的要求第二十八頁，共50頁。區(qū)域連通方式對填充(tiánchōng)結(jié)果的影響4連通區(qū)域邊界填充算法(suànfǎ)的填充結(jié)果8連通區(qū)域邊界填充算法(suànfǎ)的填充結(jié)果第二十九頁，共50頁。區(qū)域(qūyù)填充—區(qū)域(qūyù)內(nèi)外測試填充過程：確定種子點—種子著色—區(qū)域擴展問題：如何判斷種子合適？方法：奇偶規(guī)則：射線法。判斷射線與多邊形邊的交點數(shù)奇數(shù)：內(nèi)部點偶數(shù)：外部(wàibù)點要求：射線不過頂點第三十頁，共50頁。區(qū)域(qūyù)填充—區(qū)域(qūyù)內(nèi)外測試用于鑒別物體內(nèi)外(nèiwài)點（內(nèi)部種子點）非零環(huán)繞規(guī)則環(huán)繞數(shù)：多邊形以逆時針方向環(huán)繞某一特定點的次數(shù).多邊形內(nèi)部點環(huán)繞數(shù)非零判斷方法差乘法：vAuu*e>0環(huán)繞數(shù)+1u*e<0環(huán)繞數(shù)-1點乘法Bve>0環(huán)繞數(shù)+1ve<0環(huán)繞數(shù)-1e=VB-VA第三十一頁，共50頁。區(qū)域填充(tiánchōng)—邊界填充(tiánchōng)算法邊界表示法中，由于邊界以特殊(tèshū)顏色指定，填充算法可逐個像素地向外處理，直到遇到邊界顏色為止。這種方法稱為邊界填充算法。填充算法可以讓藝術(shù)家或設(shè)計師首先勾畫圖的輪廓，選擇填充顏色和填充模式，然后拾取內(nèi)部點，系統(tǒng)就可以自動給圖的內(nèi)部涂上所需的顏色和圖案填充算法的輸入是種子點坐標(biāo)（x，y），填充色和邊界顏色。算法從（x，y）開始檢測相鄰位置是否是邊界顏色，若不是，就用填充色著色，并檢測其相鄰位置。該過程延續(xù)到已經(jīng)檢測完區(qū)域邊界顏色范圍內(nèi)的所有像素為止。下面使用棧結(jié)構(gòu)來實現(xiàn)4-連通邊界填充算法?？梢院苋菀椎貙⑺鼣U充成8-連通邊界填充算法，只要把檢查(jiǎnchá)4-鄰接點改為檢查(jiǎnchá)8-鄰接點即可。步驟如下：第三十二頁，共50頁。設(shè)G為一內(nèi)點表示的區(qū)域，(x,y)為區(qū)域內(nèi)一點，old_color為G的原色?，F(xiàn)取(x,y)為種子點對區(qū)域G進行填充：即先置像素(x,y)的顏色為new_color，然后逐步將整個區(qū)域G都置為同樣的顏色。步驟如下(rúxià)：種子象素入棧，當(dāng)棧非空時，執(zhí)行如下(rúxià)三步操作：（1）棧頂象素出棧；（2）將出棧象素置成多邊形色；（3）按上、下、左、右的順序檢查與出棧象素相鄰的四個象素，若其中某個象素不在邊界上且未置成多邊形色，則把該象素入棧。區(qū)域填充—邊界(biānjiè)填充算法第三十三頁，共50頁。區(qū)域填充—邊界(biānjiè)填充算法遞歸算法可實現(xiàn)(shíxiàn)如下voidFloodFill4(intx,inty,intoldColor,intnewColor){if(GetPixel(x,y)!=oldColor){PutPixel(x,y,newColor);FloodFill4(x,y+1,oldColor,newColor);FloodFill4(x,y-1,oldColor,newColor);FloodFill4(x-1,y,oldColor,newColor);FloodFill4(x+1,y,oldColor,newColor);}}/*endofFloodFill4() */

第三十四頁，共50頁。該算法也可以填充(tiánchōng)有孔區(qū)域。缺點： (1)有些象素會入棧多次，降低算法效率；棧結(jié)構(gòu)占空間。 (2)遞歸執(zhí)行，算法簡單，但效率不高，區(qū)域內(nèi)每一象素都引起一次遞歸，進/出棧，費時費內(nèi)存。 (3)區(qū)域內(nèi)若已有具有填充(tiánchōng)色的點，遞歸停止。改進算法，減少遞歸次數(shù)，提高效率。 解決方法是用掃描線填充(tiánchōng)算法區(qū)域填充(tiánchōng)—邊界填充(tiánchōng)算法第三十五頁，共50頁。區(qū)域填充(tiánchōng)—掃描線算法掃描線算法目標(biāo)：減少遞歸層次適用于邊界表示的4連通區(qū)域算法思想：在任意不間斷區(qū)間中只取一個種子(zhǒngzi)像素（不間斷區(qū)間指在一條掃描線上一組相鄰元素），填充當(dāng)前掃描線上的該段區(qū)間；然后確定與這一區(qū)段相鄰的上下兩條掃描線上位于區(qū)域內(nèi)的區(qū)段，并依次把它們保存起來，反復(fù)進行這個過程，直到所保存的各區(qū)段都填充完畢。第三十六頁，共50頁。區(qū)域填充(tiánchōng)—掃描線算法(1)初始化：堆棧置空。將種子點（x，y）入棧。(2)出棧：若?？談t結(jié)束。否則取棧頂元素（x，y），以y作為當(dāng)前掃描線。(3)填充并確定種子點所在區(qū)段：從種子點（x，y）出發(fā)，沿當(dāng)前掃描線向左、右兩個方向填充，直到邊界。分別標(biāo)記區(qū)段的左、右端點(duāndiǎn)坐標(biāo)為xl和xr。(4)并確定新的種子點：在區(qū)間[xl，xr]中檢查與當(dāng)前掃描線y上、下相鄰的兩條掃描線上的象素。若存在非邊界、未填充的象素，則把每一區(qū)間的最右象素作為種子點壓入堆棧，返回第（2）步。上述算法對于每一個待填充區(qū)段，只需壓棧一次；因此，掃描線填充算法提高了區(qū)域填充的效率。第三十七頁，共50頁。區(qū)域填充—掃描線算法(suànfǎ)（舉例分析）該算法(suànfǎ)也可以填充有孔區(qū)域。像素中的序號標(biāo)指它所在(suǒzài)區(qū)段位于堆棧中的位置第三十八頁，共50頁。區(qū)域(qūyù)填充—掃描線算法（舉例分析）第三十九頁，共50頁。區(qū)域填充(tiánchōng)—掃描線算法（舉例分析）第四十頁，共50頁。區(qū)域填充—掃描線算法(suànfǎ)（舉例分析）第四十一頁，共50頁。區(qū)域(qūyù)填充—泛濫填充問題：邊界有多種顏色 區(qū)域內(nèi)部有多種顏色解決：替換顏色統(tǒng)一像素顏色，種子(zhǒngzi)填充第四十二頁，共50頁。區(qū)域填充(tiánchōng)—圖像填充(tiánchōng)用一種圖案來填充平面區(qū)域。均勻(jūnyún)著色填充方式位圖不透明位圖透明像素圖填充確定區(qū)域內(nèi)像素點查詢圖案位圖的對應(yīng)位置寫像素透明填充1：前景色0：不改變不透明填充1：前景色0：背景色關(guān)鍵：確定區(qū)域與圖像間的位置關(guān)系

第四十三頁，共50頁。填充(tiánchōng)方法:圖案為M*N位圖，由數(shù)組存放確定需要填充(tiánchōng)的區(qū)域與當(dāng)前掃描線的相交區(qū)間確定相交區(qū)間內(nèi)像素點(x,y),圖案位圖pattern(x%M,y%N)不透明填充(tiánchōng)或透明填充(tiánchōng)

用透明方式寫不透明方式寫第四十四頁，共50頁。多邊形掃描轉(zhuǎn)換與區(qū)域(qūyù)填充方法比較聯(lián)系：都是光柵圖形面著色，用于真實感圖形顯示?？上嗷マD(zhuǎn)換。多邊形的掃描轉(zhuǎn)換轉(zhuǎn)化為區(qū)域填充問題：當(dāng)給定多邊形內(nèi)一點為種子點，并用Bresenham或DDA算法將多邊形的邊界表示(biǎoshì)成八連通區(qū)域后，則多邊形的掃描轉(zhuǎn)換轉(zhuǎn)化為區(qū)域填充。區(qū)域填充轉(zhuǎn)化為多邊形的掃描轉(zhuǎn)換；若已知給定多邊形的頂點，則區(qū)域填充轉(zhuǎn)化為多邊形的掃描轉(zhuǎn)換。第四十五頁，共50頁。多邊形掃描轉(zhuǎn)換與區(qū)域填充(tiánchōng)方法比較不同點：1.基本思想不同；前者是頂點表示轉(zhuǎn)換成點陣表示，后者只改變區(qū)域內(nèi)填充顏色，沒有改變表示方法(fāngfǎ)。2.對邊界的要求不同前者只要求掃描線與多邊形邊界交點個數(shù)為偶數(shù)。后者：區(qū)域封閉，防止遞歸填充跨界。3.基本的條件不同前者：從邊界頂點信息出發(fā)。后者：區(qū)域內(nèi)種子點。第四十六頁，共50頁。字符(zìfú)生成字符：計算機在文本方式下能夠在屏幕上顯示的數(shù)字、字母、音標(biāo)、標(biāo)點符號、數(shù)學(xué)符號、漢字等符號。編碼標(biāo)準ASCII碼：信息交換用標(biāo)準代碼集7位二進制編碼G