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

第3章基本圖形生成

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

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

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

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

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

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

4）邊界的種類：①單域②復合域

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

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

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

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

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

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

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

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

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

算法特點

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

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

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

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

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

累計角度法

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

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

⑤活性邊表實時刷新a)調(diào)整兩個指針值，確保掃描正常進行；b)調(diào)整兩個指針之間邊元素值；④構造活性邊表活性邊：與當前掃描線相交的邊界線的邊。3掃描線算法利用區(qū)域的連續(xù)性、掃描線的連續(xù)性、邊界連續(xù)性。

1）區(qū)域連續(xù)性梯形：部分在內(nèi)，部分在外，間隔排列。

2）掃描線連續(xù)性交點：⑴交點數(shù)為偶數(shù);

⑵奇到偶數(shù)點在域內(nèi)，偶到奇數(shù)點在域外。123456123456789101234

3）邊界連續(xù)性把邊界的端點按其y坐標排列：

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

0≤

k≤

n-1

設掃描線,y=d，y10≤

d≤

y2,交點有4個。

⑴交點數(shù)相等；⑵同編號的點位于同一條邊上。

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

1)把區(qū)域邊界頂點按Y坐標排序；

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

3）構建邊界邊的活性邊表；

4）求交點；

5）交點排序；

6）交點配對；

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

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

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

1)影線描述

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

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

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

③

引入特征值，描述邊界線的形狀和類型；D△yyx具體定義如下：a)直線：特征值為0；b)假想線：特征值為10-10；c)圓?。禾卣髦禐椤繰，R＞0：圓弧由起點逆時針畫至終點，R＜0：圓弧由起點順時針畫至終點。

④引入有序頂點環(huán)表，表示不同類型邊界線的位置點。a)直線段用起、終端點表示；b)圓弧用起、圓心點和終點表示；

⑤特征值賦值：a)直線由終點攜帶邊界特征值；b)圓弧的特征值由圓心點攜帶；c)圓弧的終點特征值賦為10-10；d)第一點起點的特征值為邊界輪廓頂點總數(shù)。3）確定影線的總數(shù)①求出邊界上通過各頂點影線在y軸上的截距bi；②求出bi中最大和最小截距bmax和bmin；③求出△b的值，△b=/cosa，a為影線的傾角；④確定影線的總數(shù)，N=(bmax－bmin)/△b；4）確定第一條影線的位置

取第一條影線的截距，b=bmin+△b，而第一條影線的方程，y=kx+b。5）求影線與邊界的交點若把第i條影線記為L(i)，輪廓線傭R(j)表示，交點為P(i,j)時，則有：P(i，j)=L(i)∩R(j)對于P(i，j)，存在有三種類型的點：①無效點：交點在邊界有效線段之外，應當舍棄；②有效點：交點在邊界有效線段上，應當紀錄；③雙重點：交點位于邊界頂點處，采用“起閉終開”規(guī)則，舍棄重點，記錄有效點。

7）顯示影線段影線交點的順序規(guī)律：奇點—偶點時，影線段在域內(nèi)，顯示影線段；偶點—奇點時，影線段在域外，不顯示影線段。

6)對交點進行排序按照坐標大小，對有效交點進行從小到大的順序排隊。3.3.5圖象填充區(qū)域算法1圖像方式:1）位圖不透明方式；2）位圖透明方式；3）像素圖填充方式。YX圖像空間區(qū)域定義1）使圖像在水平和垂直方向周期性排列，直到所定義的區(qū)域全被不重迭的圖像所覆蓋。2）假定每個圖像的尺寸是M×N，通過周期性排列構成圖像空間。3）建立區(qū)域中各像素與圖像各單元間的映射關系。2處理過程3建立映射關系1)整個繪圖空間與圖像空間的1-1映射2)區(qū)域局部坐標空間與圖像空間的1-1映射(x,y)(x1,y1)3.4字符的生成字符生成方法有點陣式、矢量式和編碼式。常用的字符有：①

ASCII碼，②

漢字字符，

③

其它字符，④其它工程專用符號。1.點陣式字符

1)定義模式點陣式字符將字符表示為一個矩形點陣，由點陣中點的不同值表達字符的形狀。

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

①使用點陣式字符時，需將字庫中的矩形點陣拷貝到buffer中指定的單元中去。

②在拷貝過程中，施加變換，可獲得簡單的變化。

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

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

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

①

矢量編碼：用有限的方向編碼來表達一個字符，通常采用8個或16個方向。

②

專用編碼：采用專用的編碼和格式，每一個編碼定義了特定的操作和特定的格式。3）按結(jié)構保存編碼。4）定義并保存結(jié)束標志。5）建立字符庫。以AutoCAD形文件的定義為例：文件格式：一個標題行，若干個描述行。標題行：*〈形編號〉，<字節(jié)大小>，<形名稱>。描述行:由編碼和操作數(shù)組成。采用矢量編碼，最高位0表示為十六進制數(shù)，后面兩位表示高四位和低四位，高四位表示矢量長度，低四位表示畫矢量的方向。二極管符號的定義形式如下：*133，11，EJG040,044,04c,062,04c,040,048,04c,066,04c,0。從字庫的字模中讀出字符，在顯示器或打印機上輸出。①計算或確定字符或字符串左下角點的坐標；②讀取字符數(shù)據(jù)：根據(jù)編碼取出每個節(jié)點的數(shù)據(jù)；讀取字符數(shù)據(jù)時，應注意考慮以下參數(shù)：a)字符的定位點，一般選擇字符的左下角點；b)確定字符的類型和字符的個數(shù)；c)字符的方向，方向常選取與x軸的夾角，單位為度；d)確定字符寬度和字符高度，通常選擇高度作參數(shù)，把寬度看成高度的比例系數(shù)；e)確定字符的間距，間距選擇字符高度的比例系數(shù)；③進行坐標變換和處理：可以對字符進行任何操作，如放大、旋轉(zhuǎn)，甚至透視等；④在確定的位置顯示字符。6）顯示字符3.5反走樣3.5.1.光柵圖樣走樣現(xiàn)象

1）階梯狀的圖形或邊界

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

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

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

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

★方法簡單，但代價非常大。

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

★只能減輕而不能消除鋸齒問題2）從軟件考慮提高分辨率1111算術平均122142121加權平均

★高分辨率計算，低分辨率顯示把每個像素分為四個子像素，掃描轉(zhuǎn)換算法求得各子像素的灰度值，然后對四像素的灰度值簡單平均，作為該像素灰度值?！锵袼丶毞旨夹g，相當于后置濾波

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

1）簡單的區(qū)域取樣在整個像素區(qū)域內(nèi)進行采樣，該技術稱為區(qū)域取樣。利用一種求相交區(qū)域的近似面積的離散計算方法：(1)將屏幕象素分割成n個更小的子象素，(2)計算中心落在直線段內(nèi)的子象素的個數(shù)m，(3)m/n為線段與象素相交區(qū)域面積的近似值。特點：(1)直線段像素亮度與其重疊區(qū)域的面積成正比；(2)相同面積重疊區(qū)域的像素灰度值或顏色值相同；(3)不適用動態(tài)圖形顯示。1）加權區(qū)域取樣

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

作業(yè)：

1.認