維填充圖元生成ppt課件(編輯修改稿)
2025-05-30 04:43 本頁面
【文章內(nèi)容簡(jiǎn)介】 AEL= 算法示例 e2 e5 e1 e6 e3 e4 :ET 0 2 4 6 8 10 12 2 4 6 8 10 P3 P2 P1 P4 P5 P6 e3 e4 e2 e1 e5 e6 9 7 11 7 ^ 11 13 0 ^ 9 2 0 ^ 3 7 5 7 ^ 7 6 ^ 5 4 ^ 3 2 ^ 1 0 ^ y=7 AEL= (2， 7) → (7， 7) (7， 7) → (13， 7) (2， 6) → (13， 6) AEL： 9 2 0 9 7 11 7 11 13 0 ^ 9 2 0 11 13 0 ^ y=6 AEL= y=8 AEL= (2， 8) → (， 8) (， 8) → (13， 8) 9 2 0 9 11 11 13 0 ^ y=9 AEL= (10， 9) → (13， 9) 11 10 11 13 0 ^ 算法示例 e2 e5 e1 e6 e3 e4 :ET 0 2 4 6 8 10 12 2 4 6 8 10 P3 P2 P1 P4 P5 P6 e3 e4 e2 e1 e5 e6 9 7 11 7 ^ 11 13 0 ^ 9 2 0 ^ 3 7 5 7 ^ 7 6 ^ 5 4 ^ 3 2 ^ 1 0 ^ y=10 AEL= (， 10) → (13， 10) AEL： 11 y=9 AEL= (10， 9) → (13， 9) 11 10 11 13 0 ^ 11 13 0 ^ y=11 AEL= 空 算法示例 33 練習(xí) ? 寫出如圖所示的多邊形的邊分類表（ ET）及 y=7和 y=1對(duì)應(yīng)的活性邊表（ AEL） 0 2 4 6 8 10 12 2 4 6 8 10 P1(2,2) e3 e4 e2 e1 e5 y=1 y=7 P2(5,1) P3(11,3) P4(11,8) P5(2,7) 0 2 4 6 8 10 12 2 4 6 8 10 P1(2,2) e3 e4 e2 e1 e5 y=1 y=7 P2(5,1) P3(11,3) P4(11,8) P5(2,7) e3 e5 e1 e2 e4 8 2 9 ^ 8 11 0 ^ 2 5 3 3 5 3 ^ 7 6 ^ 5 ^ 4 ^ 3 2 1 0 ^ 7 2 0 ^ ymax x Δx 0 2 4 6 8 10 12 2 4 6 8 10 P1(2,2) e3 e4 e2 e1 e5 y=1 y=7 P2(5,1) P3(11,3) P4(11,8) P5(2,7) y=7， AET： y=1， AET： e4 e3 8 2 9 8 11 0 ^ ymax x Δx e1 e2 2 5 3 3 5 3 ^ 36 掃描線算法 －幾點(diǎn)規(guī)則 ? 求交點(diǎn)、排序、配對(duì)、填色 ? 還需解決的問題： ? 交點(diǎn) x坐標(biāo)可能是小數(shù)，如何取整？ ? 填充擴(kuò)大化的問題，及邊界像素的取舍問題。 0 2 4 6 8 10 12 2 4 6 8 10 37 ? 交點(diǎn)的取整 ? 利用連貫性計(jì)算出的交點(diǎn)可能導(dǎo)致部分像素位于多邊形之外。 ? 目的：使生成的像素盡量位于多邊形之內(nèi)，并且避免 填充擴(kuò)大化。 掃描線算法 －幾點(diǎn)規(guī)則 38 掃描線算法 －幾點(diǎn)規(guī)則 ? 假定非水平邊與掃描線 y=e相交，交點(diǎn)的橫坐標(biāo)為 x。若 x為小數(shù)，即交點(diǎn)落于掃描線上兩個(gè)相鄰像素之間時(shí)，規(guī)則如下： (a) 交點(diǎn)位于左邊之上 (入點(diǎn) )，向右取整； (b) 交點(diǎn)位于右邊之上 (出點(diǎn) )，向左取整； y=e (x,e) (a) y=e (x,e) (b) 39 掃描線算法 －幾點(diǎn)規(guī)則 ? 邊界象素的取舍問題，避免填充擴(kuò)大化。 ? 若 x為整數(shù)，即交點(diǎn)落于像素點(diǎn)上（邊界象素）。 ? 落在右邊界的象素 (出點(diǎn) )不予填充； ? “ 左閉右開 ” y=e (x,e) (a) y=e (x,e) (b) 40 掃描線算法 －幾點(diǎn)規(guī)則 ? : “ 左閉右開” ，將左邊界的點(diǎn)算為內(nèi)部，而將右邊界的點(diǎn)算為外部。 ? ：“下閉上開”，即丟棄上頂點(diǎn)。 ? 掃描線交于一頂點(diǎn)，共享交點(diǎn)的兩條邊分另處于掃描線的兩邊，這時(shí)交點(diǎn)只取 1個(gè)，如掃描線 y=3，根據(jù) “ 下閉上開 ” 原則，該點(diǎn)被填充 1次。 ? 共享交點(diǎn)的兩條邊處于掃描線的上方，這時(shí)交點(diǎn)取 2個(gè)，如掃描線 y=1。 ? 共享交點(diǎn)的兩條邊處于掃描線的下方，這時(shí)交點(diǎn)取 0個(gè)，如掃描線 y=9，無交點(diǎn)，不填充。 0 2 4 6 8 10 12 2 4 6 8 10 41 掃描線算法 －小結(jié) ? 優(yōu)點(diǎn)：充分利用了區(qū)域的連貫性，算法的效率比逐點(diǎn)填充法高很多。 ? 缺點(diǎn)：對(duì)各種表的維持和排序開銷太大，適合軟件實(shí)現(xiàn)而不適合硬件實(shí)現(xiàn)。 ? 思考： ? 多邊形的水平邊對(duì)算法有何影響？ ? 上述算法中交點(diǎn)如何實(shí)現(xiàn)所述規(guī)則的取舍？ ? 算法是否能處理自交多邊形？ 42 掃描線算法 －思考 A B C D E F G H I J X Y ?水平邊對(duì)算法有何影響？ ?水平邊對(duì)算法沒有影響，可在預(yù)處理階段去除。 43 第 4章 二維填充圖元生成 多邊形的掃描轉(zhuǎn)換 概述 掃描線算法 其它算法 區(qū)域填充 簡(jiǎn)單種子填充 掃描線種子填充 圖案填充 字符 44 其它算法 1. 邊緣填充法 2. 柵欄填充法 3. 邊界標(biāo)志法 45 ? 求余運(yùn)算 ：假定 A為一個(gè)正整數(shù) (計(jì)算機(jī)中取 A為 n位能表示的最大整數(shù)。即， A=0xFFFFFFFF )，則 M的余定義為 A – M, 記為 。 ? 求余可用異或顯示模式實(shí)現(xiàn)： ? 光柵圖形中，如果某區(qū)域已著上值為 M的顏色值，做偶數(shù)次求余運(yùn)算，該區(qū)域顏色不變；而做奇數(shù)次求余運(yùn)算，則該區(qū)域顏色變?yōu)橹禐? 的顏色。這一規(guī)律應(yīng)用于多邊形掃描轉(zhuǎn)換，就是 邊緣填充算法 。 ? 算法基本思想 ：對(duì)于每條掃描線和每條多邊形邊的交點(diǎn)，將該掃描線上交點(diǎn)右方的所有象素取余。 1. 邊緣填充算法 MM? ? M A M M X o r AM M X o r A X o r A M? ? ???46 1. 邊緣填充算法 － 以邊為中心的算法 1. 將繪畫窗口的背景置為 ； 2. 從多邊形的每一條非水平邊上的象素開始向右求余。 M47 1. 邊緣填充算法 －與掃描線算法的比較 ? 適合用于具有幀緩存的圖形系統(tǒng)。 ? 優(yōu)點(diǎn)： ? 算法簡(jiǎn)單， 數(shù)據(jù)結(jié)構(gòu)和程序結(jié)構(gòu)都比掃描線法簡(jiǎn)單。 ? 缺點(diǎn)： ? 對(duì)于復(fù)雜圖形，每一象素可能被訪問多次，輸入、輸出的量比掃描線填充算法大得多； ? 要對(duì)幀緩存的大量象素反復(fù)賦值，速度較慢； ? 并難于用圖案填充。 48 2. 柵欄填充算法 ? 邊緣填充算法的改進(jìn)。引入柵欄，以減少填充算法重復(fù)訪問象素的次數(shù)。 ? 柵欄 ：與掃描線垂直的直線，通常過一頂點(diǎn)，且把多邊形分為左右二部分
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1