第3章基本圖形

生成算法

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

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

AGEFDCB外部（b）非零環繞數規則

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

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

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

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

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

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

邊表的建立：先按下端點的y坐標值對所有的邊進行分組，若某邊的下低端點y值為ymin，則該邊就放在ymin所對應的桶中；然后用排序方法，按下端點的x坐標值遞增的順序將同一組中的邊排列成行。

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

其中，各符號的含義為：

ymax：邊的上端點的y坐標

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

1/k：邊的斜率的倒數

next：指向下一條邊的指針

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

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

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

區域填充要求區域是連通的連通性

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

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

基本思想：從多邊形內部任一點（像素）出發，依“左上右下”順序判斷相鄰像素，若其不是邊界像素且沒有被填充過，對其填充，并重復上述過程，直到所有像素填充完畢。 可以使用棧結構來實現該算法，算法的執行步驟如下： 種子像素入棧，當棧非空時，重復執行如下三步操作： （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簡單種子填充算法簡單種子填充算法會把太多的象素壓入棧，這一方面需要大量的棧空間，又要較長的處理時間。可改進該算法，得到另一種種子填充算法，這就是下面介紹的掃描線種子填充算法。

2掃描線種子填充算法

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

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

2．矢量字符

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

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

點陣字符優點：定義簡單，顯示速度快。缺點：點陣字符不易修改，且需耗費大量的存儲空間。Eg:保存一個掩模尺寸為16*16的漢字，就需256位，即32字節。常用漢字67637個，共需211k字節。矢量字符顯示步驟：1、從字庫中取出字符信息。2、取出端點坐標，對其進行適當的幾何變換，再根據各端點的標志顯示出字符。缺點：比點陣字符的顯示要慢。3.5.2字符屬性 顯示的字符的外觀由字體、字形、字號、字間距、行間距等屬性控制。一般來說，字體確定風格，字形確定外觀，字號確定尺寸。 1．單個字符屬性 2．文本屬性

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

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

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

方刷

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

倍。

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

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

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

3.6.3線型處理

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

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

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

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

走樣現象舉例不光滑(階梯狀）的圖形邊界走樣現象舉例圖形細節失真走樣現象舉例狹小圖形的遺失與動態圖形的閃爍（a）

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

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