光柵圖形的轉(zhuǎn)換與區(qū)域填充-文庫(kù)吧資料
2025-05-21 16:41本頁(yè)面
【正文】 3）將邊的活化鏈表 AEL中滿足 y=ymax的邊刪去。 2）若相對(duì)于當(dāng)前掃描線，邊的活化鏈表 AEL非空，則將AEL中的邊兩兩依次配對(duì)，即 1， 2邊為一對(duì)， 3， 4邊為一對(duì)，依次類推。 （ 3）按從下到上的順序?qū)v坐標(biāo)值為 y的掃描線（當(dāng)前掃描線）執(zhí)行下列步驟，直到邊的分類表 ET和邊的活化鏈表都變成空為止。 算法實(shí)現(xiàn)步驟 這樣，當(dāng)建立了邊的分類表 ET后，掃描線算法可按下列步驟進(jìn)行： （ 1）取掃描線縱坐標(biāo) y的初始值為 ET中非空元素的最小序號(hào)。 Edge *nextEdge。 數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟 typedef struct {int ymax。有多少條掃描線，就設(shè)多少類。 數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟 邊的分類表 ET是按邊的下端點(diǎn)的 y坐標(biāo)對(duì)非水平邊進(jìn)行分類的指針數(shù)組。 表結(jié)構(gòu) ET和 AEL中的基本元素為多邊形的邊。 存放的信息： x：掃描線與該邊的初始交點(diǎn) dx： x的增量 ymax：該邊的最大 y值 數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟 算法中采用較靈活的數(shù)據(jù)結(jié)構(gòu)。 只需對(duì)當(dāng)前掃描線的活動(dòng)邊表作更新，即可得到下一條掃描線的活動(dòng)邊表。 如何判斷多邊形的一條邊與掃描線是否相交？ 與當(dāng)前掃描線相交的邊稱為 活性邊 （ active edge)，把它們按與掃描線交點(diǎn) x坐標(biāo)遞增的順序存入一個(gè)鏈表中，稱為 活化邊表 （ AEL, Active edge table)。 所有的邊和掃描線求交，效率很低。 容易求得掃描線 y=d上的交點(diǎn)序列為xdj1,xdj2,… xdjn ， 這一序列由位于掃描線y=d上的多邊形 P的頂點(diǎn)組成。 ? 規(guī)定 ：奇點(diǎn)是極值點(diǎn)時(shí)，該點(diǎn)按兩個(gè)交點(diǎn)計(jì)算，否則按一個(gè)交點(diǎn)計(jì)算。 奇點(diǎn)的處理 ? 多邊形 P的頂點(diǎn)可分為兩類： 極值奇點(diǎn) 和 非極值奇點(diǎn) 。那么如何保證交點(diǎn)數(shù)為偶數(shù)呢？ 奇點(diǎn)的處理 ? 若奇點(diǎn)做一個(gè)交點(diǎn)處理，則情況 A，交點(diǎn)個(gè)數(shù)不是偶數(shù)。 ?以上所述多邊形的三種形式的連貫性都基于這樣的幾何事實(shí)：每一條掃描線與多邊形 P的邊界的交點(diǎn)個(gè)數(shù)都是偶數(shù)。 以上性質(zhì)稱為邊的連貫性，它是區(qū)域的連貫性在相鄰兩掃描線上的反映。 邊的連貫性 特別是當(dāng)存在某一個(gè)整數(shù) k,0≤k≤n 1,使得 yike, dyik+1 成立時(shí)，則由區(qū)域的連貫性可知 d的交點(diǎn)序列和 e的交點(diǎn)序列之間有以下關(guān)系： 1）兩序列元素的個(gè)數(shù)相等，如上圖所示。 邊的連貫性 于是，可利用 d的交點(diǎn)序列計(jì)算 e的交點(diǎn)序列，即先運(yùn)用遞推關(guān)系式 (1)求得與掃描線 y=e和y=d都相交的所有多邊形上的交點(diǎn) xer,再求得與掃描線 y=d不相交但與掃描線 y=e相交的所有邊PqPq+1上的交點(diǎn) xeq。 設(shè)位于掃描線 y=d上的交點(diǎn)序列為 xdj1,xdj2,xdj3,… ,xdjk 現(xiàn)在來(lái)討論掃描線 d， e交點(diǎn)序列之間的關(guān)系。 以上性質(zhì)稱為掃描線的連貫性，它是多邊形區(qū)域連貫性在一條掃描線上的反映。由區(qū)域的連貫性可知，此交點(diǎn)序列具有以下性質(zhì)： 掃描線的連貫性 1） l是偶數(shù)。 若掃描線 y=e與多邊形 P的Pi1Pi相交，則記其交點(diǎn)的橫坐標(biāo)為 xei。 區(qū)域的連貫性 根據(jù)這些性質(zhì)，實(shí)際上只需知道該長(zhǎng)方形區(qū)域內(nèi)任一梯形內(nèi)一點(diǎn)關(guān)于多邊形 P的內(nèi)外關(guān)系后，即可確定區(qū)域內(nèi)所有梯形關(guān)于 P的內(nèi)外關(guān)系 。 2）這些梯形可分為兩類：一類位于多邊形 P的內(nèi)部；另一類在多邊形 P的外部。掃描轉(zhuǎn)換算法綜合利用了 區(qū)域的連貫性、掃描線連貫性 和 邊的連貫性 等三種形式的連貫性。與逐點(diǎn)判斷算法相比，掃描線算法充分利用了相鄰象素之間的連貫性，避免了對(duì)象素的逐點(diǎn)判斷和反復(fù)求交的運(yùn)算，達(dá)到了減少了計(jì)算量和提高速度的目的。 只要檢查頂點(diǎn)的兩條邊的另外兩個(gè)端點(diǎn)的 Y值，兩個(gè) Y值中大于交點(diǎn) Y值的個(gè)數(shù)是 0， 1， 2，來(lái)決定取 0， 1， 2個(gè)交點(diǎn)。 具體實(shí)現(xiàn)時(shí)，只要對(duì)掃描線與多邊形的相交區(qū)間左閉右開 掃描線算法 規(guī)則 3： 掃描線與多邊形的頂點(diǎn)相交時(shí)，交點(diǎn)的取舍，保證交點(diǎn)正確配對(duì)。 逐點(diǎn)判斷法 掃描線算法 目標(biāo)：利用相鄰像素之間的連貫性，提高算法效率 ?處理對(duì)象：非自交多邊形 （邊與邊之間除了頂點(diǎn)外無(wú)其它交點(diǎn)） ?交點(diǎn)的取整規(guī)則 ?要求：使生成的像素全部位于多邊形之內(nèi) ?用于線畫圖元掃描轉(zhuǎn)換的四舍五入原則導(dǎo)致部分像素位于多邊形之外，從而不可用 ?假定非水平邊與掃描線 y=e 相交，交點(diǎn)的橫坐標(biāo)為 x, 規(guī)則如下 掃描線算法 由中點(diǎn)算法求出的多邊形邊界上的像素 規(guī)則 1： X為小數(shù)，即交點(diǎn)落于掃描線上兩個(gè)相鄰像素之間 (a)交點(diǎn)位于
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1