【正文】 19 ? 根據(jù)掃描線的連貫性可知：一條掃描線與多邊形的交點(diǎn)中，入點(diǎn) 和 出點(diǎn) 之間所有點(diǎn)都是多邊形的內(nèi)部點(diǎn)。 ? 掃描線的連貫性 ：區(qū)域的連貫性在一條掃描線上的反映； ? 邊的連貫性： 某條邊與當(dāng)前掃描線相交，也可能與下一條掃描線相交。 18 掃描線算法 ? 區(qū)域 的連貫性 ：相鄰兩條掃描線構(gòu)成一個(gè)水平 長方形 區(qū)域，并被多邊形的邊分割為若干梯形（ 一類位于多邊形的內(nèi)部；另一類在多邊形的外部，且間隔排列）。 17 掃描線算法 ? 開發(fā)和利用相鄰象素之間的連貫性是光柵圖形 學(xué) 算法的重要 技巧 。 15 第 4章 二維填充圖元生成 多邊形的掃描轉(zhuǎn)換 概述 掃描線算法 其它算法 區(qū)域填充 簡單種子填充 掃描線種子填充 圖案填充 字符 16 掃描線算法 ? 掃描線算法是掃描轉(zhuǎn)換多邊形的常用算法，它充分利用了相鄰像素之間的連貫性，避免了逐點(diǎn)判斷和反復(fù)求交計(jì)算，達(dá)到了減少計(jì)算量和提高算法效率的目的。 ? 主要是由于該算法割斷了各象素之間的聯(lián)系，孤立地考察各象素與多邊形的內(nèi)外關(guān)系，使得 幾十萬甚至幾百萬個(gè)象素 都要一一判別，每次判別又要多次求交點(diǎn)，花費(fèi)很多時(shí)間。 ? 如何判斷點(diǎn)在多邊形的內(nèi)外？ 14 2. 逐點(diǎn)判斷法 ? 逐點(diǎn)判斷的算法雖然程序簡單，但不可取。 for ( y = rectymin； y rectymax； y++ ) for ( x = rectxmin； x rectxmax； x++ ) SetPixel ( x， y， color )。 12 1. 掃描轉(zhuǎn)換矩形 ? 設(shè)矩形的四條邊分另為xmin， xmax， ymin， ymax。 } /*end of FillRectangle ()*/ 11 1. 掃描轉(zhuǎn)換矩形 BL(x,y) TR(x+5,y+5) Area=6*6 =36 pixels Area=5*5 =25 pixels ? 矩形面積為： 6*6＝ 36 pixels ? 矩形實(shí)際面積應(yīng)為 : [(x+5)x]*[(y+5)y] ＝ 25 pixels ? 采用 左閉右開，下閉上開 的原則對邊界象素進(jìn)行處理可保證矩形的面積不被擴(kuò)大。 void FillRectangle ( Rectangle *rect， int color ) { int x， y。 ? 邊界像素重繪問題； ? 填充擴(kuò)大化問題。 ? 共享邊界將會(huì)被重繪兩次，如何處理？ 屬于誰？ ? 原則：左、下邊的象素屬于矩形，而右、上邊的象素不屬于矩形。 for ( y = rectymin； y = rectymax； y++ ) for ( x = rectxmin； x = rectxmax； x++ ) SetPixel ( x， y， color )。 ? 只要填充從 ymin到 ymax的每條掃描線上位于 xmin和xmax之間的象素。 ? 也就是從多邊形的給定邊界出發(fā)，求出位于其內(nèi)部的各個(gè)象素，并給幀緩沖器內(nèi)對應(yīng)元素設(shè)置相應(yīng)的灰度，通常稱這種轉(zhuǎn)換為 多邊形的掃描轉(zhuǎn)換 。 ? 失去了許多重要的幾何信息； ? 便于光柵系統(tǒng)顯示。 ? 直觀、幾何意義強(qiáng)、占內(nèi)存少、易于幾何變換； ? 不能直接用于光柵系統(tǒng)顯示。如果是曲線的話： ? 求出邊界像素 → 區(qū)域填充； ? 可以采用直線段逼近 → 多邊形的掃描轉(zhuǎn)換。1 第 4章 二維填充圖元生成 2 第 4章 二維填充圖元生成 多邊形的掃描轉(zhuǎn)換 概述 掃描線算法 其它算法 區(qū)域填充 簡單種子填充 掃描線種子填充 圖案填充 字符 3 第 4章 二維填充圖元生成 ? 二維填充圖元 ? 用顏色或圖案填充一個(gè)二維區(qū)域 (由封閉的輪廓線包圍 )。 ? 輪廓線通常是多邊形。 4 第 4章 二維填充圖元生成 ? 多邊形的兩種表示方法： ? 頂點(diǎn)表示（多邊形） ? 用多邊形頂點(diǎn)的序列來刻劃多邊形。 ? 點(diǎn)陣表示（區(qū)域） ? 用象素的集合 (邊界 /內(nèi)部 )來刻畫多邊形。 5 第 4章 二維填充圖元生成 ? 多邊形分類： 凸多邊形 凹多邊形 含內(nèi)環(huán)的多邊形 6 第 4章 二維填充圖元生成 多邊形的掃描轉(zhuǎn)換 概述 掃描線算法 其它算法 區(qū)域填充 簡單種子填充 掃描線種子填充 圖案填充 字符 7 概述 －多邊形的掃描轉(zhuǎn)換 ? 多邊形的掃描轉(zhuǎn)換： ? 把多邊形的頂點(diǎn)表示轉(zhuǎn)換為點(diǎn)陣表示 。 ? 方法： ? 逐點(diǎn)判斷法、掃描線算法、邊緣填充法、柵欄填充法、邊界標(biāo)志法 … 8 1. 掃描轉(zhuǎn)換矩形 ? 設(shè)矩形的四條邊分另為xmin， xmax， ymin， ymax。 ymax ymin xmin xmax void FillRectangle ( Rectangle *rect， int color ) { int x， y。 } /*end of FillRectangle ()*/ 9 1. 掃描轉(zhuǎn)換矩形 ? 矩形也是多邊形，那么為什么要單獨(dú)處理矩形？ ? 掃描轉(zhuǎn)換多邊形的算法復(fù)雜，而矩形的應(yīng)用非常多 (窗口 )，所以對其單獨(dú)處理以提高效率。 ? 左閉右開，下閉上開。 10 1. 掃描轉(zhuǎn)換矩形 ? 考慮填充從 BL(x， y)到 TR（ x+5， y+5）的矩形。 for ( y = rectymin； y = rectymax； y++ ) for ( x = rectxmin； x = rectxmax； x++ ) SetPixel ( x， y， color )。 ? 對 FillRectangle ()進(jìn)行修改。 ymax ymin xmin xmax void FillRectangle ( Rectangle *rect， int color ) { int x， y。 } /*end of FillRectangle ()*/ 13 2. 逐點(diǎn)判斷法 ? 它是掃描轉(zhuǎn)換多邊形的最簡單算法，即逐個(gè)判斷繪圖窗口內(nèi)的象素是否在多邊形內(nèi)部。原因是速度太慢。 ? 不適于實(shí)際使用，很少采用。 ? 處理對象：非自交多邊形 （邊與邊之間除了頂點(diǎn)外無其它交點(diǎn)）。 ? 掃描 線 算法綜合利用了 區(qū)域的連貫性、掃描線 的 連貫性 和 邊的連貫性 等三種形式的連貫性。只需知道該區(qū)域內(nèi)任一梯形中一點(diǎn)關(guān)于多邊形的內(nèi)外關(guān)系，即可確定區(qū)域內(nèi)所有梯形關(guān)于多邊形的內(nèi)外關(guān)系 ?？赏ㄟ^與當(dāng)前掃描線的交點(diǎn)計(jì)算與下一掃描線的交點(diǎn)(利用斜率 )。 ? 所以，對所有的掃描線填充入點(diǎn)到出點(diǎn)之間的點(diǎn)就可填充多邊形。 ? 步驟 (3)如上圖：對 y＝ 8的掃描線，對交點(diǎn)序列按 x坐標(biāo)升序排序得到的交點(diǎn)序列是 (2,4,9,13)，然后對交點(diǎn) 2與 4之間、9與 13之間的所有象素點(diǎn)進(jìn)行填充。它由 邊 分類 表 ET（ Edge Table）和 活化邊表 AEL（ Active Edge List） 兩部分組成。它記錄了多邊形邊沿掃描線的交點(diǎn)序列。 活化邊表 AEL ? 求交、排序、配對、 填色 ? 隨掃描線的遞增如何更新 AEL？ ? 邊的加入、刪除，交點(diǎn)的更新。下端點(diǎn)的 y坐標(biāo)值等于 i的