河南理工大學(xué)計(jì)算機(jī)圖形學(xué)3章-3區(qū)域填充

1、第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)- -區(qū)域填充區(qū)域填充第第3 3章章- - 2 2/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第第3 3章章 基本圖形生成基本圖形生成 3.1 3.1 直線圖形生成直線圖形生成3.2 3.2 圓及二次曲線生成圓及二次曲線生成 3.3 3.3 區(qū)域圖形填充區(qū)域圖形填充 3.4 3.4 字符生成字符生成3.5 3.5 反走樣反走樣 第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)- -區(qū)域填充區(qū)域填充第第3 3章章- - 3 3/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 本次課內(nèi)容：本

2、次課內(nèi)容： 3.3 3.3 區(qū)域填充算法區(qū)域填充算法 3.4 3.4 字符的生成字符的生成 線框多邊形物體填充多邊形物體區(qū)域填充應(yīng)用實(shí)例第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)- -區(qū)域填充區(qū)域填充第第3 3章章- - 5 5/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院3.3 3.3 區(qū)域填充算法區(qū)域填充算法單色填充單色填充圖案填充圖案填充區(qū)域填充解決的問題： 1 描述區(qū)域邊界 曲線圍成的區(qū)域，可用多邊形逼近； 2 確定待填充的象素 檢查每一像素是否位于多邊形區(qū)域內(nèi)； 3 確定填充要素 顏色或圖案。第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)- -區(qū)

3、域填充區(qū)域填充第第3 3章章- - 6 6/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院名詞解釋名詞解釋 1) 區(qū)域：一組相鄰而且又相連的像素，而且具有相同屬 性的封閉區(qū)域。 3) 區(qū)域填充：在區(qū)域內(nèi)確定種子，并將這種屬性擴(kuò)展到 整個(gè)區(qū)域的過程。 4）邊界的種類：單域 復(fù)合域 2) 種子：具有一定填充屬性單位的像素或像素組合。第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)- -區(qū)域填充區(qū)域填充第第3 3章章- - 7 7/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 5) 區(qū)域的建立方式：內(nèi)定區(qū)域 邊界定義區(qū)域。 內(nèi)定區(qū)域：在所定義

4、的區(qū)域內(nèi)所有的像素具有相同 的屬性（如顏色等）,而區(qū)域邊界上的像素著不 同的顏色； 邊界定義區(qū)域：區(qū)域以的屬性來劃分，區(qū)域內(nèi)的像 素和邊界上的像素可具有不同得屬性。邊界定義區(qū)域內(nèi)定區(qū)域第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)- -區(qū)域填充區(qū)域填充第第3 3章章- - 8 8/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 區(qū)域填充算法：區(qū)域填充算法：1) 種子填充算法內(nèi)部一個(gè)點(diǎn)出發(fā) 簡單種子算法 掃描線種子算法2) 掃描線填充算法掃描線順序 有序邊表算法 邊填充算法3) 圖案填充算法填充有結(jié)構(gòu)的圖形 影線填充算法 圖像填充算法第第3 3章章 基本圖形生成技術(shù)

5、基本圖形生成技術(shù)- -區(qū)域填充區(qū)域填充第第3 3章章- - 9 9/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院1 區(qū)域的連通性3.3.1 種子填充算法種子填充算法 4 4連通區(qū)域：連通區(qū)域：從區(qū)域上的一點(diǎn)出發(fā)，通過訪問已知點(diǎn)的4鄰接點(diǎn)，在不越出區(qū)域的前提下，遍歷區(qū)域內(nèi)的所有象素點(diǎn)。 8 8連通區(qū)域：連通區(qū)域：從區(qū)域上的一點(diǎn)出發(fā)，通過訪問已知點(diǎn)的8鄰接點(diǎn)，在不越出區(qū)域的前提下，遍歷區(qū)域內(nèi)的所有象素點(diǎn)。prrrrrrrr第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)- -區(qū)域填充區(qū)域填充第第3 3章章- - 1010/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與

6、技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4 4連通區(qū)域連通區(qū)域8 8連通區(qū)域連通區(qū)域4連通與8連通區(qū)域區(qū)別第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)- -區(qū)域填充區(qū)域填充第第3 3章章- - 1111/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2 基本原理 假設(shè)區(qū)域內(nèi)一點(diǎn)已知，以此為種子。從該點(diǎn)出發(fā)，沿著區(qū)域連通的方向搜索與種子相鄰且位于區(qū)域內(nèi)的點(diǎn)，使其成為新種子，接著繼續(xù)遞歸地搜索下去。若相鄰的點(diǎn)不在區(qū)域內(nèi)，即達(dá)到邊界。常用算法有： 簡單種子填充算法、 掃描線種子填充算法。第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)- -區(qū)域填充區(qū)域填充第第3 3章章- - 1

7、212/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院連通區(qū)域擴(kuò)展過程連通區(qū)域擴(kuò)展過程4連通填充連通填充8連通填充連通填充第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)- -區(qū)域填充區(qū)域填充第第3 3章章- - 1313/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院3 簡單種子算法 1）算法步驟 確定邊界和邊界的屬性； 確定區(qū)域填充的屬性值； 測試區(qū)域內(nèi)一點(diǎn)的屬性值，判定其是否在填充區(qū)域內(nèi)；且未被填充， 若在區(qū)域內(nèi)且和邊界的屬性值不同，賦予填充屬性，以此點(diǎn)為種子； 沿四連通(或八連通)方向，測試其它點(diǎn)； 每測試一個(gè)點(diǎn)都與邊界屬性比較，

8、若不同，賦予填充屬性； 若相同，即到達(dá)邊界，然后轉(zhuǎn)向另一種連通方向； 整個(gè)點(diǎn)的測試采用循環(huán)遞歸的方式實(shí)現(xiàn)。第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)- -區(qū)域填充區(qū)域填充第第3 3章章- - 1414/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院掃描線種子填充算法過程掃描線種子填充算法過程第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)- -區(qū)域填充區(qū)域填充第第3 3章章- - 1515/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 2) 算法特點(diǎn) 算法簡單，便于硬件實(shí)現(xiàn)； 像素測試效率比較低。4 掃描線種子填充算法掃描線種子填

9、充算法 1）算法的基本思想 用掃描線從上到下掃描由點(diǎn)線段構(gòu)成的多段多邊形。每根掃描線與多邊形各邊產(chǎn)生一系列交點(diǎn)。將交點(diǎn)按照x(或y)坐標(biāo)進(jìn)行分類，然后成對(duì)取出，作為兩個(gè)端點(diǎn)，用填充顏色畫水平直線。 掃描線填充算法：yx算法 xy算法。 第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)- -區(qū)域填充區(qū)域填充第第3 3章章- - 1616/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2）算法的基本過程： 當(dāng)給定種子點(diǎn)時(shí)，首先填充種子點(diǎn)所在的掃描線上的位于給定區(qū)域的一個(gè)區(qū)段，然后確定與這一區(qū)段相通的上下兩條掃描線上位于給定區(qū)域內(nèi)的區(qū)段，并依次保存下來。反復(fù)這個(gè)過程，直到

10、填充結(jié)束。第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)- -區(qū)域填充區(qū)域填充第第3 3章章- - 1717/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院3.3.2 多邊形填充算法多邊形填充算法1 多邊形表示 頂點(diǎn)表示：用多邊形的頂點(diǎn)序列描述多邊形。P1P2P4P0 點(diǎn)陣表示：用位于多邊形內(nèi)的像素幾何描述多邊形。 把多邊形的頂點(diǎn)表示轉(zhuǎn)換為點(diǎn)陣表示。或求出位于多邊形內(nèi)的各個(gè)像素點(diǎn)并賦予特定的屬性。第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)- -區(qū)域填充區(qū)域填充第第3 3章章- - 1818/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技

11、術(shù)學(xué)院射射 線線 法法 任作一條射線,求其與邊界的交點(diǎn),若交點(diǎn)數(shù)為偶數(shù)偶數(shù),則該點(diǎn)在邊界之外,否則在邊界之內(nèi)。 1 12 23 32 23 34 41 1 2 2 主要技術(shù)處理主要技術(shù)處理 區(qū)域內(nèi)點(diǎn)的快速測試方法 第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)- -區(qū)域填充區(qū)域填充第第3 3章章- - 1919/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院累計(jì)角度法累計(jì)角度法 計(jì)算各邊的夾角的和，若代數(shù)和為零，該點(diǎn)域外；若代數(shù)和為2，該點(diǎn)域內(nèi)。ABCDEPABCDEP第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)- -區(qū)域填充區(qū)域填充第第3 3章章- - 20

12、20/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院P1P2P3P4P5 重合點(diǎn)的處理:當(dāng)掃描線和邊界相交于邊界頂點(diǎn)時(shí)，同時(shí)產(chǎn)生兩個(gè)交點(diǎn)，通常采用 “起閉終開”或“起開終閉” 。 水平邊處理： 水平邊不參加求交計(jì)算，跳過。第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)- -區(qū)域填充區(qū)域填充第第3 3章章- - 2121/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 活性邊的構(gòu)造方法： a) 去除水平邊，根據(jù)環(huán)方向進(jìn)行開閉區(qū)間處理； b) 按照端點(diǎn)的Y坐標(biāo)大小對(duì)各邊進(jìn)行排序，按從大到小 把邊存入線性表中； c) 在線性表中加入兩個(gè)指針，

13、形成活性邊表。 活性邊表實(shí)時(shí)刷新 a) 調(diào)整兩個(gè)指針值，確保掃描正常進(jìn)行； b) 調(diào)整兩個(gè)指針之間邊元素值；構(gòu)造活性邊表活性邊：與當(dāng)前掃描線相交的邊界線的邊。第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)- -區(qū)域填充區(qū)域填充第第3 3章章- - 2222/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 3 3 掃描線算法掃描線算法 利用區(qū)域的連續(xù)性、掃描線的連續(xù)性、邊界連續(xù)性。 1）區(qū)域連續(xù)性 梯形：部分在內(nèi)，部分在外，間隔排列。 2）掃描線連續(xù)性 交點(diǎn)： 交點(diǎn)數(shù)為偶數(shù); 奇到偶數(shù)點(diǎn)在域內(nèi)，偶到奇數(shù)點(diǎn)在域外。123456第第3 3章章 基本圖形生成技術(shù)基本圖形生

14、成技術(shù)- -區(qū)域填充區(qū)域填充第第3 3章章- - 2323/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院123456789101234 3）邊界連續(xù)性 把邊界的端點(diǎn)按其y坐標(biāo)排列： y0,y1,.,yi yikyik+1 0 k n-1 設(shè)掃描線,y=d ， y10 d y2, 交點(diǎn)有4個(gè)。第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)- -區(qū)域填充區(qū)域填充第第3 3章章- - 2424/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 4 4 掃描線算法實(shí)現(xiàn)步驟掃描線算法實(shí)現(xiàn)步驟 1) 把區(qū)域邊界頂點(diǎn)按Y坐標(biāo)排序； 2）確定掃描線的區(qū)

15、間； 3）構(gòu)建邊界邊的活性邊表； 4）求交點(diǎn)； 5）交點(diǎn)排序； 6）交點(diǎn)配對(duì)； 7）填充顏色012345671234567yx88910P4P1P2P3P5I1I2I3I4掃描線區(qū)間第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)- -區(qū)域填充區(qū)域填充第第3 3章章- - 2525/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院3.3.3 邊填充算法邊填充算法 優(yōu)點(diǎn)優(yōu)點(diǎn)：最適合于有幀緩存的顯示器可按任意順序處理多邊形的邊僅訪問與該邊有交點(diǎn)的掃描線上右方的像素，算法簡單缺點(diǎn)：缺點(diǎn)：對(duì)復(fù)雜圖形，每一像素可能被訪問多次，輸入/輸出量大圖形輸出不能與掃描同步進(jìn)行，只有全部畫

16、完才能打印 也稱正負(fù)相消法，對(duì)每一掃描線依次求其與邊的交點(diǎn)，對(duì)交點(diǎn)右側(cè)像素取補(bǔ)，并多邊形每條邊排序。P5P1P2P3P4P5P1P2P3P4P5P1P2P3P4P5P1P2P3P4P5P1P2P3P4(a)(b)(c)(d)(e)第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)- -區(qū)域填充區(qū)域填充第第3 3章章- - 2626/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院3.3.4影線填充算法影線填充算法 圖案填充：是在區(qū)域內(nèi)填充有規(guī)律的圖形組合，而圖形可以分解成一族或數(shù)族不同類型的線型組合。影線填充：用一組等距離的平行線(其各段的起、終端點(diǎn)位于區(qū)域邊界上) 填

17、充區(qū)域的過程。 填充圖案第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)- -區(qū)域填充區(qū)域填充第第3 3章章- - 2727/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 1) 1) 影線描述影線描述 影線采用斜截式定義：y=kx+b2) 區(qū)域邊界描述 區(qū)域邊界描述應(yīng)考慮如下因素： a) 邊界線的形狀，直線和圓??； b) 邊界線的位置； c) 區(qū)域的類型，單域和復(fù)域； d) 邊界是封閉性。 引入假想線，使復(fù)域轉(zhuǎn)變成閉合的單域； 引入特征值，描述邊界線的形狀和類型；D Dy yy yx x第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)- -區(qū)域填充區(qū)域填充第第3

18、3章章- - 2828/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院具體定義如下： a) 直線：特征值為0； b) 假想線：特征值為10-10； c) 圓?。禾卣髦禐镽，R0：圓弧由起點(diǎn)逆時(shí)針 畫至終點(diǎn)，R0：圓弧由起點(diǎn)順時(shí)針畫至終點(diǎn)。 引入有序頂點(diǎn)環(huán)表，表示不同類型邊界線的位置點(diǎn)。 a) 直線段用起、終端點(diǎn)表示； b) 圓弧用起、圓心點(diǎn)和終點(diǎn)表示； 特征值賦值： a) 直線由終點(diǎn)攜帶邊界特征值； b) 圓弧的特征值由圓心點(diǎn)攜帶； c) 圓弧的終點(diǎn)特征值賦為10-10； d) 第一點(diǎn)起點(diǎn)的特征值為邊界輪廓頂點(diǎn)總數(shù)。 第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)

19、- -區(qū)域填充區(qū)域填充第第3 3章章- - 2929/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院3）確定影線的總數(shù)確定影線的總數(shù) 求出邊界上通過各頂點(diǎn)影線在y軸上的截距bi； 求出bi中最大和最小截距bmax和bmin； 求出b的值，b=/cosa，a為影線的傾角； 確定影線的總數(shù)， N=(bmaxbmin)/b；4）確定第一條影線的位置確定第一條影線的位置 取第一條影線的截距，b= bmin+b， 而第一條影線的方程，y=kx+b。5）求影線與邊界的交點(diǎn)求影線與邊界的交點(diǎn) 若把第i條影線記為L(i)，輪廓線傭R(j)表示，交點(diǎn)為P(i,j)時(shí)，則有： P(i，

20、j)=L(i)R(j)第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)- -區(qū)域填充區(qū)域填充第第3 3章章- - 3030/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院對(duì)于P(i，j)，存在有三種類型的點(diǎn)： 無效點(diǎn)：交點(diǎn)在邊界有效線段之外，應(yīng)當(dāng)舍棄； 有效點(diǎn)：交點(diǎn)在邊界有效線段上，應(yīng)當(dāng)紀(jì)錄； 雙重點(diǎn)：交點(diǎn)位于邊界頂點(diǎn)處，采用“起閉終開”規(guī) 則，舍棄重點(diǎn)，記錄有效點(diǎn)。 7）顯示顯示影線段影線段 影線交點(diǎn)的順序規(guī)律： 奇點(diǎn)偶點(diǎn)時(shí)，影線段在域內(nèi)，顯示影線段； 偶點(diǎn)奇點(diǎn)時(shí)，影線段在域外，不顯示影線段。 6) 對(duì)交點(diǎn)進(jìn)行排序?qū)稽c(diǎn)進(jìn)行排序 按照坐標(biāo)大小，對(duì)有效交點(diǎn)進(jìn)行從小到

21、大的順序排隊(duì)。第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)- -區(qū)域填充區(qū)域填充第第3 3章章- - 3131/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院3.3.5 圖象填充區(qū)域算法圖象填充區(qū)域算法 1 1 圖像方式圖像方式: : 1）位圖不透明方式；2）位圖透明方式；3）像素圖填充方式。YX圖像空間區(qū)域定義 1）使圖像在水平和垂直方向周期性排列，直到所定義的區(qū)域全被不重迭的圖像所覆蓋。2）假定每個(gè)圖像的尺寸是MN，通過周期性排列構(gòu)成圖像空間。3）建立區(qū)域中各像素與圖像各單元間的映射關(guān)系。2 2 處理過程處理過程3 3 建立映射關(guān)系建立映射關(guān)系1)整個(gè)繪圖空

22、間與圖像空間的1-1映射2)區(qū)域局部坐標(biāo)空間與圖像空間的1-1映射(x,y)(x1,y1)第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)- -區(qū)域填充區(qū)域填充第第3 3章章- - 3232/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院字符生成方法有點(diǎn)陣式、矢量式和編碼式。常用的字符有： ASCII碼， 漢字字符， 其它字符， 其它工程專用符號(hào)。 點(diǎn)陣式字符將字符表示為一個(gè)矩形點(diǎn)陣，由點(diǎn)陣中點(diǎn)的不同值表達(dá)字符的形狀。 常用的點(diǎn)陣大小有88、1616、 3232等等。 第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)- -區(qū)域填充區(qū)域填充第第3 3章章- - 333

23、3/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2）點(diǎn)陣字符的處理點(diǎn)陣字符的處理 使用點(diǎn)陣式字符時(shí)，需將字庫中的矩形點(diǎn)陣拷貝到buffer中指定的單元中去。 在拷貝過程中 ，施加變換，可獲得簡單的變化 。 作任意角度的旋轉(zhuǎn)等復(fù)雜變換，比較困難。 矢量式字符將字符表達(dá)為一個(gè)點(diǎn)坐標(biāo)的序列，相鄰兩點(diǎn)表示一條矢量，字符的形狀便由矢量序列刻劃。 1）定義字模 采用正方形網(wǎng)格88、3232、6464、128128等。 2）定義字符 表達(dá)字符的內(nèi)容：定位點(diǎn)坐標(biāo)、走筆方向和標(biāo)志等。 第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)- -區(qū)域填充區(qū)域填充第第3 3章章- - 343

24、4/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院采用兩種形式 矢量編碼：用有限的方向編碼來表達(dá)一個(gè)字符， 通常采用8個(gè)或16個(gè)方向。 專用編碼：采用專用的編碼和格式，每一個(gè)編碼 定義了特定的操作和特定的格式。3）按結(jié)構(gòu)保存編碼。4）定義并保存結(jié)束標(biāo)志。5）建立字符庫。 第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)- -區(qū)域填充區(qū)域填充第第3 3章章- - 3535/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院以AutoCAD形文件的定義為例：文件格式：一個(gè)標(biāo)題行， 若干個(gè)描述行。標(biāo)題行：*形編號(hào)， ，。描述行: 由編碼和操作數(shù)組成

25、。 采用矢量編碼，最高位0表示為十六進(jìn)制數(shù)，后面兩位表示高四位和低四位，高四位表示矢量長度，低四位表示畫矢量的方向。 二極管符號(hào)的定義形式如下：*133，11，EJG040, 044, 04c, 062, 04c, 040, 048, 04c, 066, 04c, 0。第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)- -區(qū)域填充區(qū)域填充第第3 3章章- - 3636/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院從字庫的字模中讀出字符，在顯示器或打印機(jī)上輸出。 計(jì)算或確定字符或字符串左下角點(diǎn)的坐標(biāo)； 讀取字符數(shù)據(jù)：根據(jù)編碼取出每個(gè)節(jié)點(diǎn)的數(shù)據(jù)；讀取字符數(shù)據(jù)時(shí)，應(yīng)注意

26、考慮以下參數(shù)： a) 字符的定位點(diǎn)，一般選擇字符的左下角點(diǎn)； b) 確定字符的類型和字符的個(gè)數(shù)； c) 字符的方向，方向常選取與x軸的夾角，單位為度； d) 確定字符寬度和字符高度，通常選擇高度作參數(shù)， 把寬度看成高度的比例系數(shù)； e) 確定字符的間距，間距選擇字符高度的比例系數(shù)； 進(jìn)行坐標(biāo)變換和處理：可以對(duì)字符進(jìn)行任何操作，如 放大、旋轉(zhuǎn)，甚至透視等； 在確定的位置顯示字符。6）顯示字符 第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)- -區(qū)域填充區(qū)域填充第第3 3章章- - 3737/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 1）階梯狀的圖形或邊界 2）

27、圖形細(xì)節(jié)失真 2）狹小圖形的遺失與動(dòng)態(tài)圖形的閃爍用離散量表示連續(xù)量引起的失真現(xiàn)象稱之為走樣。第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)- -區(qū)域填充區(qū)域填充第第3 3章章- - 3838/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院用于減少或消除走樣現(xiàn)象的技術(shù)稱為反走樣。1 提高分辨率（過取樣，或后濾波） 1）從硬件考慮提高分辨率 方法簡單，但代價(jià)非常大。 幀緩存容量則增加到原來的4倍，掃描轉(zhuǎn)換要花4倍時(shí)間。 只能減輕而不能消除鋸齒問題第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)- -區(qū)域填充區(qū)域填充第第3 3章章- - 3939/40/40計(jì)算機(jī)圖形學(xué)

28、計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 2）從軟件考慮提高分辨率1111算術(shù)平均122142121加權(quán)平均高分辨率計(jì)算，低分辨率顯示把每個(gè)像素分為四個(gè)子像素，掃描轉(zhuǎn)換算法求得各子像素的灰度值，然后對(duì)四像素的灰度值簡單平均，作為該像素灰度值。像素細(xì)分技術(shù)，相當(dāng)于后置濾波 第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)- -區(qū)域填充區(qū)域填充第第3 3章章- - 4040/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2 區(qū)域取樣（或前濾波） 1）簡單的區(qū)域取樣 在整個(gè)像素區(qū)域內(nèi)進(jìn)行采樣，該技術(shù)稱為區(qū)域取樣。 利用一種求相交區(qū)域的近似面積的離散計(jì)算方法： (1)將屏幕象素分割成n個(gè)更小的子象素， (2)計(jì)算中心落在直線段內(nèi)的子象素的個(gè)數(shù)m， (3)m/n為線段與象素相交區(qū)域面積的近似值。 特點(diǎn)： (1)直線段像素亮度與其重疊區(qū)域的面積成正比； (2)相同面積重疊區(qū)域的像素灰度值或顏色值相同； (3)不適用動(dòng)態(tài)圖形顯示。第第3 3章章 基本圖形生成技術(shù)基本圖形生成技術(shù)- -區(qū)域填充區(qū)域填充第第3 3章章- - 4141/40/40計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院1）加權(quán)區(qū)域取樣 假想一個(gè)連續(xù)的加權(quán)曲面（或過濾函數(shù)）覆蓋象素。當(dāng)直線條經(jīng)過該象素時(shí)，該象素的灰度值是在二者