【正文】 生成 多邊形的掃描轉(zhuǎn)換 概述 掃描線算法 其它算法 區(qū)域填充 簡單種子填充 掃描線種子填充 圖案填充 字符 58 簡單 種子填充算法 ? 設(shè) G為一 內(nèi)點(diǎn)表示 的區(qū)域， (x,y)為區(qū)域內(nèi)一點(diǎn)，old_color為 G的原色。 邊界點(diǎn) 內(nèi) 點(diǎn) 55 區(qū)域填充 ? 區(qū)域填充 ? 先將區(qū)域內(nèi)的一點(diǎn)賦予指定的顏色，然后將該顏色擴(kuò)展到整個區(qū)域的過程。 54 區(qū)域填充 ? 區(qū)域可采用兩種表示形式 : ? 內(nèi)點(diǎn)表示 ? 枚舉區(qū)域內(nèi)部的所有像素； ? 內(nèi)部的所有像素著同一個顏色； ? 邊界像素著不同的顏色。 ? 點(diǎn)陣表示（區(qū)域） ? 用象素的集合 (邊界 /內(nèi)部 )來刻畫多邊形。 52 第 4章 二維填充圖元生成 多邊形的掃描轉(zhuǎn)換 概述 掃描線算法 其它算法 區(qū)域填充 簡單種子填充 掃描線種子填充 圖案填充 字符 53 區(qū)域填充 ? 多邊形的兩種表示方法： ? 頂點(diǎn)表示（多邊形） ? 用多邊形頂點(diǎn)的序列來刻劃多邊形。 ? 用軟件實(shí)現(xiàn)時(shí)，掃描線算法與邊界標(biāo)志算法的執(zhí)行速度幾乎相同。 51 3. 邊界標(biāo)志算法 ? 優(yōu)點(diǎn)：對每個象素只訪問一次。 ? Inside 的初始值為假，每當(dāng)當(dāng)前訪問象素為被打上邊界標(biāo)志的點(diǎn)，就把 inside取反。 2. 填充：對每條與多邊形相交的掃描線，按從左到右的順序，逐個訪問該掃描線上的象素。 0 2 4 6 8 10 12 2 4 6 8 10 50 3. 邊界標(biāo)志算法 ? 也稱輪廓填充算法－改進(jìn)的邊緣填充法。對未打標(biāo)志的點(diǎn)， inside不變。 ? 減少了象素重復(fù)訪問數(shù)目，但不徹底。 ? 柵欄 ：與掃描線垂直的直線，通常過一頂點(diǎn)，且把多邊形分為左右二部分。 48 2. 柵欄填充算法 ? 邊緣填充算法的改進(jìn)。 ? 優(yōu)點(diǎn)： ? 算法簡單， 數(shù)據(jù)結(jié)構(gòu)和程序結(jié)構(gòu)都比掃描線法簡單。 1. 邊緣填充算法 MM? ? M A M M X o r AM M X o r A X o r A M? ? ???46 1. 邊緣填充算法 － 以邊為中心的算法 1. 將繪畫窗口的背景置為 ； 2. 從多邊形的每一條非水平邊上的象素開始向右求余。這一規(guī)律應(yīng)用于多邊形掃描轉(zhuǎn)換，就是 邊緣填充算法 。即， A=0xFFFFFFFF )，則 M的余定義為 A – M, 記為 。 ? 思考： ? 多邊形的水平邊對算法有何影響？ ? 上述算法中交點(diǎn)如何實(shí)現(xiàn)所述規(guī)則的取舍？ ? 算法是否能處理自交多邊形？ 42 掃描線算法 －思考 A B C D E F G H I J X Y ?水平邊對算法有何影響？ ?水平邊對算法沒有影響，可在預(yù)處理階段去除。 0 2 4 6 8 10 12 2 4 6 8 10 41 掃描線算法 －小結(jié) ? 優(yōu)點(diǎn)：充分利用了區(qū)域的連貫性，算法的效率比逐點(diǎn)填充法高很多。 ? 共享交點(diǎn)的兩條邊處于掃描線的上方，這時(shí)交點(diǎn)取 2個，如掃描線 y=1。 ? ：“下閉上開”，即丟棄上頂點(diǎn)。 ? 若 x為整數(shù)，即交點(diǎn)落于像素點(diǎn)上（邊界象素）。 掃描線算法 －幾點(diǎn)規(guī)則 38 掃描線算法 －幾點(diǎn)規(guī)則 ? 假定非水平邊與掃描線 y=e相交，交點(diǎn)的橫坐標(biāo)為 x。 0 2 4 6 8 10 12 2 4 6 8 10 37 ? 交點(diǎn)的取整 ? 利用連貫性計(jì)算出的交點(diǎn)可能導(dǎo)致部分像素位于多邊形之外。 ? 檢查該頂點(diǎn)的兩相鄰邊在掃描線的哪一側(cè)： 只要檢查頂點(diǎn)的兩條邊的另外兩個端點(diǎn)的 Y值，兩個 Y值中大于交點(diǎn) Y值的個數(shù)是 0， 1， 2， 來決定取 0， 1， 2個 交點(diǎn)。 ? 邊的結(jié)構(gòu) “ Edge”由以下四個域組成： ? ymax： 邊的上端點(diǎn)的 y坐標(biāo)； ? x：在 ET中表示邊的下端點(diǎn)的 x坐標(biāo)；在 AEL中則表示邊 與掃描線的交點(diǎn)的 x坐標(biāo)； ? Δx：邊的斜率的倒數(shù)； ? next：指向下一 “ 邊 ” 的指針。它由 邊 分類 表 ET（ Edge Table）和 活化邊表 AEL（ Active Edge List）兩部分組成。有多少條掃描線，就設(shè)多少類。下端點(diǎn)的 y坐標(biāo)值等于 i的邊歸入第 i類(在該掃描線第一次出現(xiàn)的邊 )。 0 2 4 6 8 10 12 2 4 6 8 10 P3 P2 P1 P4 P5 P6 e3 e4 e2 e1 e5 e6 ymax x Δx ? ET中每個對象需要存放的信息： ymax：邊所交的最高掃描線； x：邊的下端點(diǎn)的 x坐標(biāo)； Δx： 從當(dāng)前掃描線到下一條掃描線之間的 x增量 (邊的斜率的倒數(shù) )； next：指向下一對象的指針。同一類中，各邊按 x值（ x值相等時(shí)，按 Δx的值）遞增的順序排列。 y=6， AEL： y=7， AEL： y=6 y=7 0 2 4 6 8 10 12 2 4 6 8 10 P3 P2 P1 P4 P5 P6 e3 e4 e2 e1 e5 e6 e2 e5 9 2 0 11 13 0 ^ ymax x Δx e2 e3 9 2 0 9 7 e4 e5 11 7 11 13 0 ^ ? 建立一個新的數(shù)據(jù)結(jié)構(gòu) ： ? 邊分類表 ET 活化邊表 AEL ? 邊 分類 表 ET （ Edge Table） ： 按掃描線 i對非水平邊進(jìn)行分類的指針數(shù)組。 y=6， AEL： y=6 y=7 0 2 4 6 8 10 12 2 4 6 8 10 P3 P2 P1 P4 P5 P6 e3 e4 e2 e1 e5 e6 e2 e5 9 2 0 11 13 0 ^ ymax x Δx ? AEL中每個對象需要存放的信息： ymax：邊所交的最高掃描線； x：當(dāng)前掃描線與邊的交點(diǎn)； Δx： 從當(dāng)前掃描線到下一條掃描線之間的 x增量 next：指向下一對象的指針。 ? 求交點(diǎn)、排序、配對、 填色 ? 利用鏈表：與當(dāng)前掃描線相交的邊稱為 活化邊 (Active Edge)，把它們按與掃描線交點(diǎn) x坐標(biāo)遞增的順序存入一個鏈表中，稱為 活化邊表 AEL (AEL， Active Edge List)。 ? 求交點(diǎn)、排序、配對、填色 0 2 4 6 8 10 12 2 4 6 8 10 21 掃描線算法 － 數(shù)據(jù)結(jié)構(gòu)及實(shí)現(xiàn) ? 算法中采用較靈活的數(shù)據(jù)結(jié)構(gòu)。 ? 如何具體實(shí)現(xiàn)（如何找到入點(diǎn)、出點(diǎn)）？ 掃描線算法 －原理 0 2 4 6 8 10 12 2 4 6 8 10 1 2 3 4 入點(diǎn) 出點(diǎn) 內(nèi)部點(diǎn) 20 掃描線算法 －原理 ? 根據(jù)區(qū)域的連貫性，分為 3個步驟： (1)求出掃描線與多邊形所有邊的交點(diǎn)； (2)把這些交點(diǎn)按 x坐標(biāo)值以升序排列； (3)對排序后的交點(diǎn)進(jìn)行奇偶配對，對每一對交點(diǎn)間的區(qū)域進(jìn)行填充。（ 區(qū)域的連貫性在相鄰兩掃描線上的反映） y=i Xe1 Xe2 Xe3 Xe4 Xe8 Xe7 y=i+1 Xd1 Xd2 Xd3 Xd4 Xd8 Xd7 P0 P8 P7 P1 P2 P3 P4 P5 P6