【文章內(nèi)容簡介】 換為點(diǎn)陣表示，即從多邊形的給定邊界出發(fā)，求出位于其內(nèi)部的各個(gè)像素，并為幀緩存內(nèi)的各個(gè)對應(yīng)元素設(shè)置相應(yīng)的灰度或顏色。 32 掃描線算法 特點(diǎn) ：充分利用了相鄰像素之間的 連續(xù)性 ，避免對像素的逐 點(diǎn)判斷和反復(fù)求交運(yùn)算，減少了計(jì)算量，提高了算法速度。 基本概念： 1） 掃描線的連續(xù)性 2） 邊的連續(xù)性 3） 奇點(diǎn) 基本思想 先求出掃描線與多邊形邊的交點(diǎn)，利用 掃描線的連續(xù)性 求出多邊形與掃描線相交的連續(xù)區(qū)域，然后利用多邊形 邊的連續(xù)性 ，求出下一條掃描線與多邊形的交點(diǎn)，對所有掃描線由下到上依次處理。 掃描線算法是按 掃描線的順序 計(jì)算出掃描線與多邊形的 相 交區(qū)間 ，然后用要求的顏色填充這些區(qū)間內(nèi)的像素。 33 1 掃描線的連續(xù)性 設(shè)多邊形 P的頂點(diǎn) ，將各頂點(diǎn) 的縱坐標(biāo) 按 遞減順序 排列 , 即 設(shè)當(dāng)前掃描線 ， ， 與多邊形 P的邊 的交點(diǎn)記為 。設(shè) 為 與 P的邊界各交點(diǎn)橫坐標(biāo)的 遞增 序列，該序列稱為交點(diǎn)序列。 ( , ) , 0 , 1 , ,i i iP x y i n?? iPiy 01, , , ny y y? ? ?1 , 0 1kky y k n???? ? ? ?ey? 0 ny e y???? ey?1iiPP? ( , )eixe1 2 3, , , , le i e j e k e mx x x x() ey? 當(dāng)知道一條掃描線上 一點(diǎn) 與多邊形的內(nèi)外關(guān)系時(shí)，即可確定該 掃描線上所有點(diǎn) 與多邊形之間的內(nèi)外關(guān)系。 34 交點(diǎn)序列具有以下 性質(zhì) ： 1) 交點(diǎn)個(gè)數(shù) l 是偶數(shù)； 2) 掃描線上的區(qū)間 l–1位于多邊形 P內(nèi)（圖 ），其余區(qū)間都在 P 外（圖），兩類區(qū)間沿掃描線相間排列。這些性質(zhì)就稱為 掃描線的連續(xù)性 。 1( , ) , 1 , 3 , 5 , ,kke i e jx x k? ?P0 P1 P2 P3 P4 P5 P6 P7 P8 xe01 xe22 xe33 xe74 xe65 xe46 圖 掃描線的連續(xù)性 圖中 表示在多邊形外的區(qū)間 ── 表示在多邊形內(nèi)的區(qū)間 根據(jù)掃描線的連續(xù)性，只需求出掃描線與多邊形 P的邊界的所有交點(diǎn)，就可確定掃描線位于多邊形 P內(nèi)的區(qū)間。 35 2 邊的連續(xù)性 掃描線的連續(xù)性知，序列（ ）和（ ）的點(diǎn)滿足以下關(guān)系： （ 1）兩序列元素的個(gè)數(shù)相等，即 ； （ 2）點(diǎn)（ ）與（ ）位于多邊形 P的同一邊 上（見圖 ），所以 可由下式計(jì)算 () 以上性質(zhì)稱為 邊的連續(xù)性 。 若 , 成立，則掃描線 與掃描線 和多邊形 P相同的邊相交，由 kye? ? 1kdy???ey? yd?lh?ex rei , dx rdi , ()i i iy m x x y? ? ?rdix1/rrdi e i ix x m??圖 邊的連續(xù)性 P0 P1 P2 P3 P4 P5 P6 P7 P8 xe01 xe22 xe33 xe74 xe65 xe46 xd01 xd65 xd46 設(shè)當(dāng)前掃描線 的下一條掃描線為 ， ，且 ,設(shè)位于掃描線 上的交點(diǎn)序列為 ey?yd?1??edndy??yd?1 2 3, , , , hdi dj dk dlx x x x（ ） 36 但當(dāng)掃描線與多邊形 P 的邊界的交點(diǎn)恰好是 P的頂點(diǎn)時(shí)（該交點(diǎn)稱為 奇點(diǎn) ），必須按不同的情況區(qū)別對待。 3 奇點(diǎn)的處理 上述兩種形式的連續(xù)性都基于一個(gè)幾何事實(shí)：每一條掃描線與多邊形 P 的邊界的 交點(diǎn)個(gè)數(shù)都是偶數(shù) （包括零）。 設(shè)多邊形 P 的頂點(diǎn)為 這些頂點(diǎn)可分為兩類： 極值點(diǎn)和非極值點(diǎn) 。如果 ，則稱頂點(diǎn) 為極值點(diǎn)（如圖 ）；否則稱為非極值點(diǎn)（如圖 ）。 ,1,0),( niyxP iii ???0))(( 11 ??? ?? iiii yyyyiP 1 2 3 5 6 8, , , , ,P P P P P P iP0 4 7,P P P圖 一個(gè)多邊形與若干條掃描線 P8 P0 P1 P2 P3 P4 P5 P6 P7 37 為使每一條掃描線與多邊形 P 的邊界的交點(diǎn)個(gè)數(shù)始終為偶數(shù)，規(guī)定當(dāng)奇點(diǎn)是多邊形 P 的 極值點(diǎn) 時(shí)，該點(diǎn)按 兩個(gè)交點(diǎn) 計(jì)算， 否則 按 一個(gè)交點(diǎn) 計(jì)算。 圖 非極值點(diǎn)的處理 （ a） （ b） 1iy?iyy?1iy?1iy?iyy?1iy?iP iP實(shí)際計(jì)算中，可如下 處理非極值點(diǎn) ：若 是非極值點(diǎn)，則將 , 兩邊中位于掃描線 上方的那條邊在 處截去一個(gè)單位長，這樣就能保證掃描線 只和 ， 中的一邊相交，只有一個(gè)交點(diǎn)。 iPii PP1? 1?iiPPiyy?iyy?ii PP1? 1?iiPPiP38 4 算法的實(shí)現(xiàn)步驟與數(shù)據(jù)結(jié)構(gòu) 對于每一條掃描線，多邊形的填充過程可分為以下 4步： 計(jì)算掃描線與多邊形各邊的 交點(diǎn) ，設(shè)交點(diǎn)個(gè)數(shù)為 n； 把所有的交點(diǎn)按 x值遞增的順序進(jìn)行 排列 ； 將排序后的第 1個(gè)與第 2個(gè)交點(diǎn)，第 3個(gè)與第 4個(gè)交點(diǎn)， …… 第 n1個(gè)與第 n個(gè)交點(diǎn) 配對 ，每對交點(diǎn)就代表掃描 線與多邊形的一個(gè)相交區(qū)間； 把 相交區(qū)間內(nèi)的像素置成多邊形的顏色 ，相交區(qū)間外 的像素置成背景色。 1 2 3 4 上述方法要計(jì)算每一條掃描線與所有邊的交點(diǎn)，計(jì)算量很大。 為提高效率，可以對每一條掃描線，僅對與它 相交的多邊形 進(jìn)行 求交運(yùn)算 。 39 使用增量計(jì)算時(shí)，還要知道一條邊何時(shí)不再與下一條掃描線相交，以及時(shí)地把該邊從活性邊表中刪除，因此需要記錄下與該邊相交的 最高掃描線號 。 活性邊表 與當(dāng)前掃描線相交的邊稱為 活性邊 。把活性邊與掃描線的交點(diǎn)按 x坐標(biāo)遞增的順序放在一個(gè)鏈表中，該鏈表就稱為活性邊表 （ Active Edge List, AEL）。 設(shè)多邊形某一條邊的方程為 ，當(dāng)前掃描線 與該邊的交點(diǎn)坐標(biāo)為 ， 則下一條掃描線 與該邊的交點(diǎn) 不需要重新計(jì)算，只要加一個(gè)增量 即可。因?yàn)榇藭r(shí)有 0ax by c? ? ? iyy?( , )iixy 1iyy??11( , )iixy?? x?111 ()i i i ib c b bx b y c y xa a a a a??? ? ? ? ? ? ? ? ? ? ?其中 為常數(shù)，并規(guī)定 時(shí)， 。 /x b a? ? ? 0a? 0x??40 maxy綜上， AEL中的節(jié)點(diǎn)應(yīng)由如下 四 個(gè)域組成： :邊的上端點(diǎn)的 y坐標(biāo)，即與該邊相交的最高掃描線號。 x :邊與掃描線的交點(diǎn)的 x坐標(biāo)。 :從當(dāng)前掃描線到下一條掃描線間的 x坐標(biāo)的增量，即邊的斜率的倒數(shù)。 Next :指向下一條邊的指針。 x?新邊表 為方便活性邊表的建立與更新，還要為每一條掃描線建立一個(gè) 新邊表 （ New Edge List, NEL），存放在該掃描線上第一次出現(xiàn)的邊。也就是說，如果某邊的 較低端點(diǎn)為 ，則該邊放在掃描線 的新邊表中。 miny miny注意：水平邊不放到任何掃描線的 NEL中，即水平邊不參加分類。 NEL中的節(jié)點(diǎn)結(jié)構(gòu)與 AEL相同，只是 x 在這里不再表示邊與掃描線的交點(diǎn)，而是表示該邊 較低端點(diǎn) 的 x 坐標(biāo)值。 41 具體例子 圖 的新邊表 NEL和活性邊表 AEL。在左圖中 表示邊 ，各頂點(diǎn)為 [P0P1… P6]=[(2,5)(2,10)(9,6) (16,9)(16,4)(12,2)(7,2)] 其中， 是非極值點(diǎn)，在分類前已對邊 作了預(yù)處理，即分別在 處把它們截去一個(gè)單位長，這樣保證掃描線 只和 兩邊中的一邊相交，求得一個(gè)交點(diǎn)， 是水平邊，不參加分類。 )( 0610 PPPPP ??ie ii PP1?40,PP41,ee 40,PPiyy? 11 , ?? iiii PPPP11 , ?? iiii PPPP6e圖 邊形 P0P1… P6P0 P3 P4 e4 10 15 5 P1 P2 P5 P6 P0 e0 e2 e3 e5 e1 e6 42 5/3 5 16/3 AEL e0 e5 4 2 14 AEL在 y=3掃描線上的狀態(tài) AEL 5/3 5 11/3 e0 e5 4 2 16 AEL在 y=4掃描線上的狀態(tài) AEL 5/3 5 2 e0 e4 9 0 16 AEL在 y=5掃描線上的狀態(tài) … 0 10 2 e1 e2 10 7/4 11/2 AEL在 y=8 掃描線上 的狀態(tài) AEL 9 7/3 41/3 e3 9 0 16 e4 圖 新邊表 NEL 1 2 3 4 5 6 e1 10 0 2 △ x x ymax next e4 9 0 16 e5 4 2 12 圖 多邊形 P0P1… P6P0 P3 P4 e4 10 15 5 P1 P2 P5 P6 P0 e0 e2 e3 e5 e1 e6 e2 10 9 7/4 e3 9 9 7/3 5 7 e0 5/3 43 邊緣填充算法 特點(diǎn)： 采用對圖像進(jìn)行 逐位求補(bǔ) 的方法， 免去對邊排序