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

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

第二十頁，共50頁。如何計(jì)算下一條掃描線與邊的交點(diǎn)(jiāodiǎn)。直線方程：ax+by+c=0當(dāng)前交點(diǎn)(jiāodiǎn)坐標(biāo)：(xi,yi)下一交點(diǎn)(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ǎ)特點(diǎn)特點(diǎn)：算法效率較高。缺點(diǎn)：對(duì)各種表的維持和排序開銷(kāixiāo)太大，適合軟件實(shí)現(xiàn)而不適合硬件實(shí)現(xiàn)。第二十二頁，共50頁。填充圖元生成(shēnɡchénɡ)原理多邊形掃描轉(zhuǎn)換區(qū)域(qūyù)填充第二十三頁，共50頁。區(qū)域(qūyù)填充區(qū)域指已經(jīng)表示成點(diǎn)陣形式的填充圖形，它是象素的集合。區(qū)域填充指先將區(qū)域的一點(diǎn)(yīdiǎn)賦予指定的顏色，然后將該顏色擴(kuò)展到整個(gè)區(qū)域的過程。區(qū)域填充算法要求區(qū)域是連通的。第二十四頁，共50頁。區(qū)域(qūyù)填充表示方法：內(nèi)點(diǎn)表示、邊界表示內(nèi)點(diǎn)表示枚舉出區(qū)域內(nèi)部的所有(suǒyǒu)像素內(nèi)部的所有(suǒyǒu)像素著同一個(gè)顏色邊界像素著與內(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ū)域，但對(duì)邊界(biānjiè)有要求對(duì)邊界(biānjiè)的要求第二十八頁，共50頁。區(qū)域連通方式對(duì)填充(tiánchōng)結(jié)果的影響4連通區(qū)域邊界填充算法(suànfǎ)的填充結(jié)果8連通區(qū)域邊界填充算法(suànfǎ)的填充結(jié)果第二十九頁，共50頁。區(qū)域(qūyù)填充—區(qū)域(qūyù)內(nèi)外測(cè)試填充過程：確定種子點(diǎn)—種子著色—區(qū)域擴(kuò)展問題：如何判斷種子合適？方法：奇偶規(guī)則：射線法。判斷射線與多邊形邊的交點(diǎn)數(shù)奇數(shù)：內(nèi)部點(diǎn)偶數(shù)：外部(wàibù)點(diǎn)要求：射線不過頂點(diǎn)第三十頁，共50頁。區(qū)域(qūyù)填充—區(qū)域(qūyù)內(nèi)外測(cè)試用于鑒別物體內(nèi)外(nèiwài)點(diǎn)（內(nèi)部種子點(diǎn)）非零環(huán)繞規(guī)則環(huán)繞數(shù)：多邊形以逆時(shí)針方向環(huán)繞某一特定點(diǎn)的次數(shù).多邊形內(nèi)部點(diǎn)環(huán)繞數(shù)非零判斷方法差乘法：vAuu*e>0環(huán)繞數(shù)+1u*e<0環(huán)繞數(shù)-1點(diǎn)乘法Bve>0環(huán)繞數(shù)+1ve<0環(huán)繞數(shù)-1e=VB-VA第三十一頁，共50頁。區(qū)域填充(tiánchōng)—邊界填充(tiánchōng)算法邊界表示法中，由于邊界以特殊(tèshū)顏色指定，填充算法可逐個(gè)像素地向外處理，直到遇到邊界顏色為止。這種方法稱為邊界填充算法。填充算法可以讓藝術(shù)家或設(shè)計(jì)師首先勾畫圖的輪廓，選擇填充顏色和填充模式，然后拾取內(nèi)部點(diǎn)，系統(tǒng)就可以自動(dòng)給圖的內(nèi)部涂上所需的顏色和圖案填充算法的輸入是種子點(diǎn)坐標(biāo)（x，y），填充色和邊界顏色。算法從（x，y）開始檢測(cè)相鄰位置是否是邊界顏色，若不是，就用填充色著色，并檢測(cè)其相鄰位置。該過程延續(xù)到已經(jīng)檢測(cè)完區(qū)域邊界顏色范圍內(nèi)的所有像素為止。下面使用棧結(jié)構(gòu)來實(shí)現(xiàn)4-連通邊界填充算法?？梢院苋菀椎貙⑺鼣U(kuò)充成8-連通邊界填充算法，只要把檢查(jiǎnchá)4-鄰接點(diǎn)改為檢查(jiǎnchá)8-鄰接點(diǎn)即可。步驟如下：第三十二頁，共50頁。設(shè)G為一內(nèi)點(diǎn)表示的區(qū)域，(x,y)為區(qū)域內(nèi)一點(diǎn)，old_color為G的原色?，F(xiàn)取(x,y)為種子點(diǎn)對(duì)區(qū)域G進(jìn)行填充：即先置像素(x,y)的顏色為new_color，然后逐步將整個(gè)區(qū)域G都置為同樣的顏色。步驟如下(rúxià)：種子象素入棧，當(dāng)棧非空時(shí)，執(zhí)行如下(rúxià)三步操作：（1）棧頂象素出棧；（2）將出棧象素置成多邊形色；（3）按上、下、左、右的順序檢查與出棧象素相鄰的四個(gè)象素，若其中某個(gè)象素不在邊界上且未置成多邊形色，則把該象素入棧。區(qū)域填充—邊界(biānjiè)填充算法第三十三頁，共50頁。區(qū)域填充—邊界(biānjiè)填充算法遞歸算法可實(shí)現(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ū)域。缺點(diǎn)： (1)有些象素會(huì)入棧多次，降低算法效率；棧結(jié)構(gòu)占空間。 (2)遞歸執(zhí)行，算法簡(jiǎn)單，但效率不高，區(qū)域內(nèi)每一象素都引起一次遞歸，進(jìn)/出棧，費(fèi)時(shí)費(fèi)內(nèi)存。 (3)區(qū)域內(nèi)若已有具有填充(tiánchōng)色的點(diǎn)，遞歸停止。改進(jìn)算法，減少遞歸次數(shù)，提高效率。 解決方法是用掃描線填充(tiánchōng)算法區(qū)域填充(tiánchōng)—邊界填充(tiánchōng)算法第三十五頁，共50頁。區(qū)域填充(tiánchōng)—掃描線算法掃描線算法目標(biāo)：減少遞歸層次適用于邊界表示的4連通區(qū)域算法思想：在任意不間斷區(qū)間中只取一個(gè)種子(zhǒngzi)像素（不間斷區(qū)間指在一條掃描線上一組相鄰元素），填充當(dāng)前掃描線上的該段區(qū)間；然后確定與這一區(qū)段相鄰的上下兩條掃描線上位于區(qū)域內(nèi)的區(qū)段，并依次把它們保存起來，反復(fù)進(jìn)行這個(gè)過程，直到所保存的各區(qū)段都填充完畢。第三十六頁，共50頁。區(qū)域填充(tiánchōng)—掃描線算法(1)初始化：堆棧置空。將種子點(diǎn)（x，y）入棧。(2)出棧：若棧空則結(jié)束。否則取棧頂元素（x，y），以y作為當(dāng)前掃描線。(3)填充并確定種子點(diǎn)所在區(qū)段：從種子點(diǎn)（x，y）出發(fā)，沿當(dāng)前掃描線向左、右兩個(gè)方向填充，直到邊界。分別標(biāo)記區(qū)段的左、右端點(diǎn)(duāndiǎn)坐標(biāo)為xl和xr。(4)并確定新的種子點(diǎn)：在區(qū)間[xl，xr]中檢查與當(dāng)前掃描線y上、下相鄰的兩條掃描線上的象素。若存在非邊界、未填充的象素，則把每一區(qū)間的最右象素作為種子點(diǎn)壓入堆棧，返回第（2）步。上述算法對(duì)于每一個(gè)待填充區(qū)段，只需壓棧一次；因此，掃描線填充算法提高了區(qū)域填充的效率。第三十七頁，共50頁。區(qū)域填充—掃描線算法(suànfǎ)（舉例分析）該算法(suànfǎ)也可以填充有孔區(qū)域。像素中的序號(hào)標(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)像素點(diǎn)查詢圖案位圖的對(duì)應(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)像素點(diǎn)(x,y),圖案位圖pattern(x%M,y%N)不透明填充(tiánchōng)或透明填充(tiánchōng)

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