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