計算機(jī)圖形學(xué)-10 基本圖形生成算法（填充反走樣）

第3章基本圖形

生成算法

（填充，反走樣）3.4多邊形的掃描轉(zhuǎn)換與區(qū)域填充3.4.1相關(guān)概念頂點表示：也稱為幾何表示，是用區(qū)域的頂點序列來表示區(qū)域。點陣表示：也稱為像素表示，是用位于多邊形內(nèi)的像素集合來刻畫多邊形。內(nèi)點表示：區(qū)域內(nèi)的所有像素著同一顏色，而區(qū)域外的所有像素具有另一種顏色；

(a)多邊形的點陣表示(b)多邊形的頂點表示P7P1P2P3P4P5P6光柵圖形的一個重要問題是把多邊形的頂點表示轉(zhuǎn)換為點陣表示。這種轉(zhuǎn)換也稱為多邊形的掃描轉(zhuǎn)換。內(nèi)外點的判別：內(nèi)部起始點(14,11)AGEFDCB外部（a）奇偶規(guī)則

AGEFDCB外部（b）非零環(huán)繞數(shù)規(guī)則

內(nèi)部1.奇偶規(guī)則由平面任意點P向多邊形引射線（算法中為水平射線，代表掃描線），若與該射線相交的多邊形邊的數(shù)目為奇數(shù)，則P是多邊形內(nèi)部點，否則P是外部點。P11P4P6P2P3圖3.18掃描線與多邊形相交時交點的處理P5為了保證防止填充區(qū)域被擴(kuò)大或縮小，規(guī)定落在右/上邊界上的像素不予填充，而落在左/下邊界上的像素予以填充。2.非零環(huán)繞數(shù)規(guī)則

其基本思想是：(1)首先使多邊形的邊變?yōu)槭噶浚?2)將環(huán)繞數(shù)初始化為零；(3)從任意位置p作一條射線,當(dāng)從p點沿射線方向移動時對在每個方向上穿過射線的邊計數(shù)，每當(dāng)多邊形的邊從右到左穿過射線時，環(huán)繞數(shù)加1，從左到右時，環(huán)繞數(shù)減1；(4)處理完多邊形的所有相關(guān)邊之后，若環(huán)繞數(shù)為非零，則p是內(nèi)部點，否則，p是外部點。3.轉(zhuǎn)角法3.多邊形的分類

（a）凸多邊形（b）凹多邊形（c）含內(nèi)環(huán)的多邊形多邊形的種類如果在它內(nèi)部任選兩個頂點，則此二點間連線上所有點均落在多邊形內(nèi)部。相反若任意兩頂點間的連線有不在多邊形內(nèi)的部分則為凹多邊形。

區(qū)域填充算法分為兩大類：多邊形的掃描轉(zhuǎn)換填充算法；原理：通過確定橫越區(qū)域的掃描線覆蓋間隔來填充一般用來填充多邊形、圓，橢圓和其它簡單圖形區(qū)域填充算法原理：從給定位置開始涂描直到指定邊界條件為止用于具有復(fù)雜形狀邊界的圖形以及交互式涂描系統(tǒng)中3.4.2多邊形的掃描轉(zhuǎn)換主要有：掃描線算法、邊界標(biāo)志算法1.掃描線算法

掃描線算法又常稱為有序邊表填充算法。它是按掃描線順序，計算掃描線與多邊形的相交區(qū)間，再用要求的顏色顯示這些區(qū)間的像素，即完成填充工作。對于一條掃描線，多邊形的填充過程可以分為四個步驟：求交排序配對填色有序邊表填充算法3.20求交排序配對填色為了計算每條掃描線與多邊形各邊的交點，最簡單的方法是把多邊形的所有邊存放在一個邊表中。

把與當(dāng)前這條掃描線相交的邊稱為該掃描線的活性邊或有效邊。并把它們按與掃描線交點x坐標(biāo)由小到大的順序存放在一個鏈表中，稱此鏈表為活性邊表(AET).

邊表的建立：先按下端點的y坐標(biāo)值對所有的邊進(jìn)行分組，若某邊的下低端點y值為ymin，則該邊就放在ymin所對應(yīng)的桶中；然后用排序方法，按下端點的x坐標(biāo)值遞增的順序?qū)⑼唤M中的邊排列成行。

假定當(dāng)前掃描線與多邊形某一條邊的交點的x坐標(biāo)為x，則下一條掃描線與該邊的交點不要重新計算，只要在此基礎(chǔ)上，加一個增量△x即可。設(shè)該邊的直線方程為：ax+by+c=0；若y＝y(tǒng)i，x=xi；則當(dāng)y=yi+1時，其中△x=-b/a為常數(shù)，ET和AEL中的基本元素為多邊形的邊。邊表示成結(jié)點的形式，每個邊結(jié)點由以下四個域組成：

其中，各符號的含義為：

ymax：邊的上端點的y坐標(biāo)

x：在ET中表示邊的下端點的x坐標(biāo)，在AEL中表示邊與掃描線的交點的x坐標(biāo)

1/k：邊的斜率的倒數(shù)

next：指向下一條邊的指針

當(dāng)建立了邊表ET后，掃描線多邊形填充算法可按如下步驟進(jìn)行： （1）初始化AEL，使之為空，取掃描線縱坐標(biāo)y的初始值為ET中非空元素的最小序號。 （2）按從下到上的順序?qū)γ織l掃描線重復(fù)以下各步，直至AEL和ET為空。 ①將ET中與當(dāng)前y有關(guān)的結(jié)點加入至AEL，同時保存AEL中按x值從小到大實現(xiàn)的排序序列 ②對于AEL中的掃描線y，在一對交點之間填充所需要的像素值 ③從AEL中刪掉y>=ymax的結(jié)點 ④對于留在AEL中的每個結(jié)點，執(zhí)行xi+1=xi+1/k ⑤對AEL中的各結(jié)點按x值從小到大排序 ⑥y=y+1，成為下一條掃描線的坐標(biāo)2.邊界標(biāo)志算法基本思想在幀緩沖器中，對多邊形的每條邊進(jìn)行直線掃描轉(zhuǎn)換，亦即對多邊形邊界所經(jīng)過的象素打上標(biāo)志。然后再采用和掃描線算法類似的方法將位于多邊形內(nèi)的各個區(qū)段著上指定的顏色。

正方形內(nèi)切n個圓的邊界標(biāo)志算法邊界標(biāo)志算法 對多邊形邊界所在像素置一個特殊標(biāo)志；對于每條與多邊形相交的掃描線，從左至右逐個訪問該掃描線上的像素。使用一個布爾變量inside來指示當(dāng)前點的狀態(tài)，若點在多邊形內(nèi)，則inside為真。若點在多邊形外，則inside為假。inside的初始值為假，每當(dāng)當(dāng)前訪問像素為被打上標(biāo)志的點，就把inside取反。對未打標(biāo)志的點，inside不變。若訪問當(dāng)前像素時，對inside作必要操作之后，inside為真，則把該像素置為多邊形要填充的顏色。 對每個像素只訪問一次，硬件執(zhí)行速度快。

3.4.3區(qū)域填充算法區(qū)域填充算法要求區(qū)域是連通的，因為只有在連通區(qū)域中，才可能將種子點的顏色擴(kuò)展到區(qū)域內(nèi)的其它點。區(qū)域按連通情況又可分為四連通區(qū)域和八連通區(qū)域。

區(qū)域填充要求區(qū)域是連通的連通性

4連通、8連通4連通：8連通種子填充算法

基本思想：假設(shè)在多邊形區(qū)域內(nèi)部至少有一個像素是已知的（此像素稱為種子像素），由此出發(fā)找到區(qū)域內(nèi)所有其他像素，并對其進(jìn)行填充。 由于區(qū)域可采用邊界定義和內(nèi)點定義兩種方式，區(qū)域按連通性又可分為四連通區(qū)域和八連通區(qū)域兩類，所以常用的種子填充算法有：邊界表示的四連通區(qū)域種子填充算法內(nèi)點表示的四連通區(qū)域種子填充算法邊界表示的八連通區(qū)域種子填充算法內(nèi)點表示的八連通區(qū)域種子填充算法1．簡單種子填充算法

基本思想：從多邊形內(nèi)部任一點（像素）出發(fā)，依“左上右下”順序判斷相鄰像素，若其不是邊界像素且沒有被填充過，對其填充，并重復(fù)上述過程，直到所有像素填充完畢。 可以使用棧結(jié)構(gòu)來實現(xiàn)該算法，算法的執(zhí)行步驟如下： 種子像素入棧，當(dāng)棧非空時，重復(fù)執(zhí)行如下三步操作： （1）棧頂像素出棧； （2）將出棧像素置成多邊形填充的顏色； （3）按左、上、右、下的順序檢查與出棧像素相鄰的四個像素，若其中某個像素不在邊界上且未置成多邊形色，則把該像素入棧。012345432102，32，23，32，41，3按左、上、右、下順序壓棧2，32，23，32，41，21，32，23，32，41，21，42，41，42，42，23，32，41，21，22，23，32，42，22，22，23，32，42，13，23，22，23，32，43，32，13，32，23，32，42，12，12，23，32，42，43，32，2簡單種子填充算法簡單種子填充算法會把太多的象素壓入棧，這一方面需要大量的?？臻g，又要較長的處理時間?？筛倪M(jìn)該算法，得到另一種種子填充算法，這就是下面介紹的掃描線種子填充算法。

2掃描線種子填充算法

掃描線種子填充算法可由下列四個步驟實現(xiàn)：(1)初始化：設(shè)置一個空棧，將種子點（x，y）入棧。(2)出棧：若?？眨瑒t結(jié)束；否則取出棧頂元素（x，y），以y作為當(dāng)前掃描線。(3)填充并確定種子點所在區(qū)段：從種子點（x，y）出發(fā)，沿當(dāng)前掃描線向左、右兩個方向填充，直到邊界。將區(qū)段左、右端點的x坐標(biāo)分別標(biāo)記為xl和xr。(4)確定新的種子點：在區(qū)間[xl，xr]中檢查與當(dāng)前掃描線y上、下相鄰的兩條掃描線上的象素,若存在非邊界、未填充的象素，則把每一區(qū)間的最右象素作為種子點壓入堆棧，并返回第（2）步。掃描線種子填充算法在任意不間斷掃描線曲段中，只取一個種子像素。像素中的序號標(biāo)指它所在區(qū)段位于堆棧中的位置掃描線種子填充掃描線種子填充掃描線種子填充方法1：建立整個繪圖空間與圖案空間的1-1映射圖案（紋理）3.4.4區(qū)域填充圖案適用：動畫中漫游圖案方法2：將圖案原點與圖形區(qū)域某點對齊區(qū)域填充圖案圖案（紋理）用圖案填充平面區(qū)域的基本步驟是首先利用“模板”來預(yù)定義圖案，然后修改前述掃描轉(zhuǎn)換算法中寫象素的語句：在確定了區(qū)域內(nèi)一象素點之后，不是馬上往該象素填色，而是先查詢模板位圖的對應(yīng)位置。若是以透明方式填充圖案，則當(dāng)摸板位圖的對應(yīng)位置為1時，用前景顏色寫象素，否則，不改變該象素的值。而若以不透明方式填充圖案，則要根據(jù)摸板位圖對應(yīng)位置是1還是0，決定是用前景顏色還是背景顏色去寫象素。多邊形掃描轉(zhuǎn)換與區(qū)域填充方法比較不同點：1.基本思想不同；前者是頂點表示轉(zhuǎn)換成點陣表示，后者只改變區(qū)域內(nèi)填充顏色，沒有改變表示方法。2.對邊界的要求不同前者只要求掃描線與多邊形邊界交點個數(shù)為偶數(shù)。后者：區(qū)域封閉，防止遞歸填充跨界。3.基本的條件不同前者：從邊界頂點信息出發(fā)。后者：區(qū)域內(nèi)種子點。我國除采用ASCII碼外，還另外制定了漢字編碼的國家標(biāo)準(zhǔn)字符集例如：GB2312－80。該字符集分為94個區(qū)，94個位，每個符號由一個區(qū)碼和一個位碼共同標(biāo)識。區(qū)碼和位碼各用一個字節(jié)表示。為了能夠區(qū)分ASCII碼與漢字編碼，采用字節(jié)的最高位來標(biāo)識：最高位為0表示ASCII碼；最高位為1表示漢字編碼。共收錄了6763個常用漢字。2000年3月信息產(chǎn)業(yè)部和國家質(zhì)量技術(shù)監(jiān)督局又頒布了GB18030-2000國家標(biāo)準(zhǔn)"信息交換用漢字編碼字符集基本集的擴(kuò)充"。它共收錄了2.7萬多個漢字，總編碼空間超過150萬個碼位，采用單/雙/四字節(jié)混合編碼，與現(xiàn)有絕大多數(shù)操作系統(tǒng)、中文平臺在內(nèi)碼一級兼容，可支持現(xiàn)有應(yīng)用系統(tǒng),并包容了其中收錄的所有漢字和蒙、藏、彝、維等少數(shù)民族文字。3.5.1字符存儲與顯示1．點陣字符

每個字符都是利用掩膜來定義，并將其寫入幀緩存保存和顯示。 點陣字符的顯示：首先從字庫中將它的位圖檢索出來，然后將檢索到的位圖寫到幀緩沖器中。讀取幀緩存中這些像素值，就可以在屏幕上顯示此字符。如果將保存在幀緩存中某字符掩膜相應(yīng)像素值均置成背景色或背景光強(qiáng)，就可以擦除幀緩存中的該字符。

2．矢量字符

矢量字符被表達(dá)為一個點坐標(biāo)的序列，相鄰兩點表示一條矢量，字符的形狀便由矢量序列刻劃。 矢量字符的顯示：首先從字庫中讀它的字符信息。然后取出端點坐標(biāo)，對其進(jìn)行適當(dāng)?shù)膸缀巫儞Q，再根據(jù)各端點的標(biāo)志顯示出字符。目前常用的矢量字符表示是輪廓字形法。輪廓字形法是當(dāng)今國際上最流行的一種字符表示方法，其壓縮比大，且能保證字符質(zhì)量。輪廓線構(gòu)成一個或若干個封閉的平面區(qū)域。輪廓線定義加上一些指示橫寬、豎寬、基點、基線等等控制信息就構(gòu)成了字符的壓縮數(shù)據(jù)。點陣字符的顯示分為兩步：從字庫中將它的位圖檢索出來，將檢索到的位圖寫到幀緩沖器中。

在實際應(yīng)用中，同一個字符有多種字體（如宋體、楷體等），每種字體又有多種大小型號，因此字庫的存儲空間十分龐大。為了減少存儲空間，一般采用壓縮技術(shù)。

點陣字符優(yōu)點：定義簡單，顯示速度快。缺點：點陣字符不易修改，且需耗費大量的存儲空間。Eg:保存一個掩模尺寸為16*16的漢字，就需256位，即32字節(jié)。常用漢字67637個，共需211k字節(jié)。矢量字符顯示步驟：1、從字庫中取出字符信息。2、取出端點坐標(biāo)，對其進(jìn)行適當(dāng)?shù)膸缀巫儞Q，再根據(jù)各端點的標(biāo)志顯示出字符。缺點：比點陣字符的顯示要慢。3.5.2字符屬性 顯示的字符的外觀由字體、字形、字號、字間距、行間距等屬性控制。一般來說，字體確定風(fēng)格，字形確定外觀，字號確定尺寸。 1．單個字符屬性 2．文本屬性

3.6線寬和線型處理（a）直線|斜率|<1的情況(b)直線|斜率|>1的情況三個象素寬的直線3.6.1直線線寬的處理

常用方法是采用線刷和方刷。線刷：線刷的原理是將線刷中心對準(zhǔn)直線一端，然后讓刷子中心沿直線往另一端移動，即可刷出帶有一定寬度的直線。垂直或水平擺放線刷線刷繪制直線所產(chǎn)生的缺口線刷的特點：①原理簡單，效率高，因為它不必象方刷那樣重復(fù)寫象素。②線條起始點與終止點總是水平或垂直的，當(dāng)直線較寬時看起來不自然；接近水平的線與接近垂直的線匯合時將會產(chǎn)生一個缺口。③同一把線刷在畫不同斜率的線條時其粗細(xì)不同，接近水平或垂直時最粗，其寬度就是刷子的寬度，450時線條最細(xì)，為刷子寬度的0.707倍。④當(dāng)線寬為偶數(shù)個象素點時，線的中心將偏離半個象素。

2可添加“線帽”，使線端的形狀得以調(diào)整。(a)方帽(b)圓帽(c)突方帽(a)斜角連接(b)圓連接(c)斜切連接粗線的連接

方刷

畫線時，讓正方形的中心對準(zhǔn)單象素寬的線條上各個象素作平行移動，并把正方形內(nèi)的全部象素置成線條的顏色。方刷繪制帶線寬的直線無需移動刷子方向①繪制過程中會重復(fù)寫象素，這是因為對應(yīng)于相鄰兩象素的正方形一般會重迭，使得算法效率較低。②直線的兩端總是水平或垂直的。③同一把刷子所畫出線段的粗細(xì)不同。線條接近水平或垂直時最細(xì)，為刷子的寬度；斜率為450時線條最寬，是刷子的

倍。

圓刷子：各方向一樣，效果較好。23.6.2圓弧線寬的處理線刷子（90~45度）垂直刷子（0~45度）水平刷子垂直或水平時，最粗，45度時最細(xì)。

方刷子：無需移動刷子方向

(a)線刷繪制的圓弧(b)方刷繪制帶的圓弧

3.6.3線型處理

線型可以通過象素模板定義。象素模板是由數(shù)字0和1組成的一個特定的串。

實線虛線點劃線雙點劃線圓點線例如，一個占4個字節(jié)的整數(shù)共有32位，可以存放32個0或1。用這樣的整數(shù)作象素模板時，線型必須以32個象素為周期進(jìn)行重復(fù)。if(位串[i%32])putpixel(x,y,color);

其中i為循環(huán)控制變量，在掃描轉(zhuǎn)換算法的內(nèi)循環(huán)中，每處理一個象素i遞增1，然后除以32取余。相同數(shù)目象素顯示的虛線不等長3.7反走樣

用離散量表示連續(xù)量引起的失真現(xiàn)象稱之為走樣；階梯狀邊界；圖形細(xì)節(jié)失真；狹小圖形遺失：動畫序列中時隱時現(xiàn)，產(chǎn)生閃爍。用于減少或消除這種現(xiàn)象的技術(shù)稱為反走樣。反走樣方法主要有：提高分辨率區(qū)域取樣（ArenSampling）區(qū)域取樣又可分為簡單區(qū)域取樣和加權(quán)區(qū)域取樣。

走樣現(xiàn)象舉例不光滑(階梯狀）的圖形邊界走樣現(xiàn)象舉例圖形細(xì)節(jié)失真走樣現(xiàn)象舉例狹小圖形的遺失與動態(tài)圖形的閃爍（a）

屏幕上的一條直線（b）把顯示器分辨率提高一倍后的結(jié)果方法簡單，但是不經(jīng)濟(jì)，而且只能減輕而不能消除鋸齒現(xiàn)象。3.7.1提高分辨率反走樣提高分辨率把顯示器分辨率提高一倍直線經(jīng)過兩倍的象素，鋸齒也增加一倍，但同時每個階梯的寬度也減小了一倍，所以顯示出的直線段看起來就平直光滑了一些。用中點算法掃描轉(zhuǎn)換的一條直線顯示器分辨率提高一倍后的結(jié)果這種反走樣方法是以4倍的存儲器代價和掃描轉(zhuǎn)換時間獲得的。因此，增加分辨率雖然簡單，但不是經(jīng)濟(jì)的方法，而且它也只能減輕而不能消除鋸齒問題。

3.7.2簡單區(qū)域取樣方法由來兩點假設(shè)1、象素是數(shù)學(xué)上抽象的點，它的面積為0，它的亮度由覆蓋該點的圖形的亮度所決定；2、直線段是數(shù)學(xué)上抽象直線段，它的寬度為0?，F(xiàn)實像素的面積不為0；直線段的寬度至少為1個像素；假設(shè)與現(xiàn)實的矛盾是導(dǎo)致混淆出現(xiàn)的原因之一簡單區(qū)域取樣解決方法：改變直線段模型，由此產(chǎn)生算法方法步驟：1、將直線段看作具有一定寬度的狹長矩形；2、當(dāng)直線段與某象素有交時，求出兩者相交區(qū)域的面積；3、根據(jù)相交區(qū)域的面積，確定該象素的亮度值簡單區(qū)域取樣