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

第3章基本圖形生成

§3.1直線圖形生成§3.2圓及二次曲線生成§3.3區(qū)域圖形填充

§3.4字符生成§3.5反走樣第3章二維圖形生成技術(shù)

本次課內(nèi)容：§3.3區(qū)域填充算法§3.4字符的生成

線框多邊形物體填充多邊形物體區(qū)域填充應(yīng)用實(shí)例§3.3區(qū)域填充算法單色填充圖案填充區(qū)域填充解決的問(wèn)題：1描述區(qū)域邊界曲線圍成的區(qū)域，可用多邊形逼近；2確定待填充的象素檢查每一像素是否位于多邊形區(qū)域內(nèi)；3確定填充要素顏色或圖案。名詞解釋

1)區(qū)域：一組相鄰而且又相連的像素，而且具有相同屬性的封閉區(qū)域。

3)區(qū)域填充：在區(qū)域內(nèi)確定種子，并將這種屬性擴(kuò)展到整個(gè)區(qū)域的過(guò)程。

4）邊界的種類：①單域②復(fù)合域

2)種子：具有一定填充屬性單位的像素或像素組合。

5)區(qū)域的建立方式：內(nèi)定區(qū)域邊界定義區(qū)域。

①內(nèi)定區(qū)域：在所定義的區(qū)域內(nèi)所有的像素具有相同的屬性（如顏色等）,而區(qū)域邊界上的像素著不同的顏色；

②邊界定義區(qū)域：區(qū)域以的屬性來(lái)劃分，區(qū)域內(nèi)的像素和邊界上的像素可具有不同得屬性。邊界定義區(qū)域內(nèi)定區(qū)域

區(qū)域填充算法：1)種子填充算法——內(nèi)部一個(gè)點(diǎn)出發(fā)簡(jiǎn)單種子算法掃描線種子算法2)掃描線填充算法——掃描線順序

有序邊表算法邊填充算法3)圖案填充算法——填充有結(jié)構(gòu)的圖形影線填充算法圖像填充算法1區(qū)域的連通性3.3.1種子填充算法

4連通區(qū)域：從區(qū)域上的一點(diǎn)出發(fā)，通過(guò)訪問(wèn)已知點(diǎn)的4鄰接點(diǎn)，在不越出區(qū)域的前提下，遍歷區(qū)域內(nèi)的所有象素點(diǎn)。

8連通區(qū)域：從區(qū)域上的一點(diǎn)出發(fā)，通過(guò)訪問(wèn)已知點(diǎn)的8鄰接點(diǎn)，在不越出區(qū)域的前提下，遍歷區(qū)域內(nèi)的所有象素點(diǎn)。prrrrprrrrrrrr4－連通區(qū)域8－連通區(qū)域4連通與8連通區(qū)域區(qū)別2基本原理假設(shè)區(qū)域內(nèi)一點(diǎn)已知，以此為種子。從該點(diǎn)出發(fā)，沿著區(qū)域連通的方向搜索與種子相鄰且位于區(qū)域內(nèi)的點(diǎn)，使其成為新種子，接著繼續(xù)遞歸地搜索下去。若相鄰的點(diǎn)不在區(qū)域內(nèi)，即達(dá)到邊界。常用算法有：簡(jiǎn)單種子填充算法、掃描線種子填充算法。連通區(qū)域擴(kuò)展過(guò)程4連通填充8連通填充3簡(jiǎn)單種子算法1）算法步驟

①確定邊界和邊界的屬性；②確定區(qū)域填充的屬性值；③測(cè)試區(qū)域內(nèi)一點(diǎn)的屬性值，判定其是否在填充區(qū)域內(nèi)；且未被填充，④若在區(qū)域內(nèi)且和邊界的屬性值不同，賦予填充屬性，以此點(diǎn)為種子；⑤沿四連通(或八連通)方向，測(cè)試其它點(diǎn)；⑥每測(cè)試一個(gè)點(diǎn)都與邊界屬性比較，若不同，賦予填充屬性；⑦若相同，即到達(dá)邊界，然后轉(zhuǎn)向另一種連通方向；⑧整個(gè)點(diǎn)的測(cè)試采用循環(huán)遞歸的方式實(shí)現(xiàn)。掃描線種子填充算法過(guò)程2)

算法特點(diǎn)

①算法簡(jiǎn)單，便于硬件實(shí)現(xiàn)；

②像素測(cè)試效率比較低。4掃描線種子填充算法

1）算法的基本思想用掃描線從上到下掃描由點(diǎn)線段構(gòu)成的多段多邊形。每根掃描線與多邊形各邊產(chǎn)生一系列交點(diǎn)。將交點(diǎn)按照x(或y)坐標(biāo)進(jìn)行分類，然后成對(duì)取出，作為兩個(gè)端點(diǎn)，用填充顏色畫水平直線。掃描線填充算法：y－x算法x－y算法。2）算法的基本過(guò)程：

當(dāng)給定種子點(diǎn)時(shí)，首先填充種子點(diǎn)所在的掃描線上的位于給定區(qū)域的一個(gè)區(qū)段，然后確定與這一區(qū)段相通的上下兩條掃描線上位于給定區(qū)域內(nèi)的區(qū)段，并依次保存下來(lái)。反復(fù)這個(gè)過(guò)程，直到填充結(jié)束。3.3.2多邊形填充算法1多邊形表示頂點(diǎn)表示：用多邊形的頂點(diǎn)序列描述多邊形。P1P2P4P0點(diǎn)陣表示：用位于多邊形內(nèi)的像素幾何描述多邊形。把多邊形的頂點(diǎn)表示轉(zhuǎn)換為點(diǎn)陣表示。或求出位于多邊形內(nèi)的各個(gè)像素點(diǎn)并賦予特定的屬性。射線法任作一條射線,求其與邊界的交點(diǎn),若交點(diǎn)數(shù)為偶數(shù),則該點(diǎn)在邊界之外,否則在邊界之內(nèi)。12323412主要技術(shù)處理

①區(qū)域內(nèi)點(diǎn)的快速測(cè)試方法

累計(jì)角度法

計(jì)算各邊的夾角的和，若代數(shù)和為零，該點(diǎn)∈域外；若代數(shù)和為2π，該點(diǎn)∈域內(nèi)。ABCDEPABCDEPP1P2P3P4P5

②重合點(diǎn)的處理:當(dāng)掃描線和邊界相交于邊界頂點(diǎn)時(shí)，同時(shí)產(chǎn)生兩個(gè)交點(diǎn)，通常采用“起閉終開(kāi)”或“起開(kāi)終閉”。③水平邊處理：水平邊不參加求交計(jì)算，跳過(guò)。[P1,p2)[P4，P5)[P2,p3)[P5,p1)活性邊的構(gòu)造方法：a)去除水平邊，根據(jù)環(huán)方向進(jìn)行開(kāi)閉區(qū)間處理；b)按照端點(diǎn)的Y坐標(biāo)大小對(duì)各邊進(jìn)行排序，按從大到小把邊存入線性表中；c)在線性表中加入兩個(gè)指針，形成活性邊表。

⑤活性邊表實(shí)時(shí)刷新a)調(diào)整兩個(gè)指針值，確保掃描正常進(jìn)行；b)調(diào)整兩個(gè)指針之間邊元素值；④構(gòu)造活性邊表活性邊：與當(dāng)前掃描線相交的邊界線的邊。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)在域外。123456123456789101234

3）邊界連續(xù)性把邊界的端點(diǎn)按其y坐標(biāo)排列：

y0,y1,…..,yiyik≥yik+1

0≤

k≤

n-1

設(shè)掃描線,y=d，y10≤

d≤

y2,交點(diǎn)有4個(gè)。

⑴交點(diǎn)數(shù)相等；⑵同編號(hào)的點(diǎn)位于同一條邊上。

4掃描線算法實(shí)現(xiàn)步驟

1)把區(qū)域邊界頂點(diǎn)按Y坐標(biāo)排序；

2）確定掃描線的區(qū)間；

3）構(gòu)建邊界邊的活性邊表；

4）求交點(diǎn)；

5）交點(diǎn)排序；

6）交點(diǎn)配對(duì)；

7）填充顏色012345671234567yx88910P4P1P2P3P5I1I2I3I4掃描線區(qū)間3.3.3邊填充算法

優(yōu)點(diǎn)：★最適合于有幀緩存的顯示器★可按任意順序處理多邊形的邊★僅訪問(wèn)與該邊有交點(diǎn)的掃描線上右方的像素，算法簡(jiǎn)單缺點(diǎn)：★對(duì)復(fù)雜圖形，每一像素可能被訪問(wèn)多次，輸入/輸出量大★圖形輸出不能與掃描同步進(jìn)行，只有全部畫完才能打印

也稱正負(fù)相消法，對(duì)每一掃描線依次求其與邊的交點(diǎn)，對(duì)交點(diǎn)右側(cè)像素取補(bǔ)，并多邊形每條邊排序。3.3.4影線填充算法圖案填充：是在區(qū)域內(nèi)填充有規(guī)律的圖形組合，而圖形可以分解成一族或數(shù)族不同類型的線型組合。影線填充：用一組等距離的平行線(其各段的起、終端點(diǎn)位于區(qū)域邊界上)填充區(qū)域的過(guò)程。填充圖案影線填充的算法步驟

1)影線描述

影線采用斜截式定義：y=kx+b2)區(qū)域邊界描述

①區(qū)域邊界描述應(yīng)考慮如下因素：a)邊界線的形狀，直線和圓?。籦)邊界線的位置；c)區(qū)域的類型，單域和復(fù)域；d)邊界是封閉性。

②引入假想線，使復(fù)域轉(zhuǎn)變成閉合的單域；

③

引入特征值，描述邊界線的形狀和類型；D△yyx具體定義如下：a)直線：特征值為0；b)假想線：特征值為10-10；c)圓?。禾卣髦禐椤繰，R＞0：圓弧由起點(diǎn)逆時(shí)針畫至終點(diǎn)，R＜0：圓弧由起點(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）確定影線的總數(shù)①求出邊界上通過(guò)各頂點(diǎn)影線在y軸上的截距bi；②求出bi中最大和最小截距bmax和bmin；③求出△b的值，△b=/cosa，a為影線的傾角；④確定影線的總數(shù)，N=(bmax－bmin)/△b；4）確定第一條影線的位置

取第一條影線的截距，b=bmin+△b，而第一條影線的方程，y=kx+b。5）求影線與邊界的交點(diǎn)若把第i條影線記為L(zhǎng)(i)，輪廓線傭R(j)表示，交點(diǎn)為P(i,j)時(shí)，則有：P(i，j)=L(i)∩R(j)對(duì)于P(i，j)，存在有三種類型的點(diǎn)：①無(wú)效點(diǎn)：交點(diǎn)在邊界有效線段之外，應(yīng)當(dāng)舍棄；②有效點(diǎn)：交點(diǎn)在邊界有效線段上，應(yīng)當(dāng)紀(jì)錄；③雙重點(diǎn)：交點(diǎn)位于邊界頂點(diǎn)處，采用“起閉終開(kāi)”規(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)行排序按照坐標(biāo)大小，對(duì)有效交點(diǎn)進(jìn)行從小到大的順序排隊(duì)。3.3.5圖象填充區(qū)域算法1圖像方式:1）位圖不透明方式；2）位圖透明方式；3）像素圖填充方式。YX圖像空間區(qū)域定義1）使圖像在水平和垂直方向周期性排列，直到所定義的區(qū)域全被不重迭的圖像所覆蓋。2）假定每個(gè)圖像的尺寸是M×N，通過(guò)周期性排列構(gòu)成圖像空間。3）建立區(qū)域中各像素與圖像各單元間的映射關(guān)系。2處理過(guò)程3建立映射關(guān)系1)整個(gè)繪圖空間與圖像空間的1-1映射2)區(qū)域局部坐標(biāo)空間與圖像空間的1-1映射(x,y)(x1,y1)3.4字符的生成字符生成方法有點(diǎn)陣式、矢量式和編碼式。常用的字符有：①

ASCII碼，②

漢字字符，

③

其它字符，④其它工程專用符號(hào)。1.點(diǎn)陣式字符

1)定義模式點(diǎn)陣式字符將字符表示為一個(gè)矩形點(diǎn)陣，由點(diǎn)陣中點(diǎn)的不同值表達(dá)字符的形狀。

常用的點(diǎn)陣大小有8×8、16×16、32×32等等。2）點(diǎn)陣字符的處理

①使用點(diǎn)陣式字符時(shí)，需將字庫(kù)中的矩形點(diǎn)陣拷貝到buffer中指定的單元中去。

②在拷貝過(guò)程中，施加變換，可獲得簡(jiǎn)單的變化。

③作任意角度的旋轉(zhuǎn)等復(fù)雜變換，比較困難。2.矢量式字符矢量式字符將字符表達(dá)為一個(gè)點(diǎn)坐標(biāo)的序列，相鄰兩點(diǎn)表示一條矢量，字符的形狀便由矢量序列刻劃。

1）定義字模采用正方形網(wǎng)格8×8、32×32、64×64、128×128等。

2）定義字符表達(dá)字符的內(nèi)容：定位點(diǎn)坐標(biāo)、走筆方向和標(biāo)志等。采用兩種形式

①

矢量編碼：用有限的方向編碼來(lái)表達(dá)一個(gè)字符，通常采用8個(gè)或16個(gè)方向。

②

專用編碼：采用專用的編碼和格式，每一個(gè)編碼定義了特定的操作和特定的格式。3）按結(jié)構(gòu)保存編碼。4）定義并保存結(jié)束標(biāo)志。5）建立字符庫(kù)。以AutoCAD形文件的定義為例：文件格式：一個(gè)標(biāo)題行，若干個(gè)描述行。標(biāo)題行：*〈形編號(hào)〉，<字節(jié)大小>，<形名稱>。描述行:由編碼和操作數(shù)組成。采用矢量編碼，最高位0表示為十六進(jìn)制數(shù)，后面兩位表示高四位和低四位，高四位表示矢量長(zhǎng)度，低四位表示畫矢量的方向。二極管符號(hào)的定義形式如下：*133，11，EJG040,044,04c,062,04c,040,048,04c,066,04c,0。從字庫(kù)的字模中讀出字符，在顯示器或打印機(jī)上輸出。①計(jì)算或確定字符或字符串左下角點(diǎn)的坐標(biāo)；②讀取字符數(shù)據(jù)：根據(jù)編碼取出每個(gè)節(jié)點(diǎn)的數(shù)據(jù)；讀取字符數(shù)據(jù)時(shí)，應(yīng)注意考慮以下參數(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.5反走樣3.5.1.光柵圖樣走樣現(xiàn)象

1）階梯狀的圖形或邊界

2）圖形細(xì)節(jié)失真

2）狹小圖形的遺失與動(dòng)態(tài)圖形的閃爍用離散量表示連續(xù)量引起的失真現(xiàn)象稱之為走樣。3.5.2.常用反走樣技術(shù)

用于減少或消除走樣現(xiàn)象的技術(shù)稱為反走樣。1提高分辨率（過(guò)取樣，或后濾波）

1）從硬件考慮提高分辨率

★方法簡(jiǎn)單，但代價(jià)非常大。

★幀緩存容量則增加到原來(lái)的4倍，掃描轉(zhuǎn)換要花4倍時(shí)間。

★只能減輕而不能消除鋸齒問(wèn)題2）從軟件考慮提高分辨率1111算術(shù)平均122142121加權(quán)平均

★高分辨率計(jì)算，低分辨率顯示把每個(gè)像素分為四個(gè)子像素，掃描轉(zhuǎn)換算法求得各子像素的灰度值，然后對(duì)四像素的灰度值簡(jiǎn)單平均，作為該像素灰度值?！锵袼丶?xì)分技術(shù)，相當(dāng)于后置濾波

只能減輕，不能消除2區(qū)域取樣（或前濾波）

1）簡(jiǎn)單的區(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)圖形顯示。1）加權(quán)區(qū)域取樣

假想一個(gè)連續(xù)的加權(quán)曲面（或過(guò)濾函數(shù)）覆蓋象素。當(dāng)直線條經(jīng)過(guò)該象素時(shí)，該象素的灰度值是在二者重疊區(qū)域上對(duì)濾波器（過(guò)濾函數(shù)）進(jìn)行積分的積分值。特點(diǎn)：(1)接近理想直線的象素將被分配更多的灰度值；(2)相鄰兩個(gè)象素的濾波器相交，有利于縮小直線條上相鄰象素的灰度差。常用過(guò)濾函數(shù)內(nèi)容回顧：

作業(yè)：

1.認(rèn)