基本圖形的生成二ppt課件(編輯修改稿)
2025-05-25 22:57 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 yi1 yi)(yi+1 yi)≥0 ，則稱(chēng)頂點(diǎn) Pi為極值點(diǎn)；否則稱(chēng) Pi為非極值點(diǎn)。 ? 規(guī)定：奇點(diǎn)是極值點(diǎn)時(shí)，該點(diǎn)按兩個(gè)交點(diǎn)計(jì)算，否則按一個(gè)交點(diǎn)計(jì)算。 ? 奇點(diǎn)的預(yù)處理： 數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟 2022/5/25 內(nèi)蒙古大學(xué)計(jì)算機(jī)圖形學(xué) 29 算法基本思想： 首先取 d=yin。 容易求得掃描線y=d上的交點(diǎn)序列為 xdj1,xdj2,… xdjn ， 這一序列由位于掃描線 y=d上的多邊形 P的頂點(diǎn)組成。 由 yin的交點(diǎn)序列 開(kāi)始，根據(jù)多邊形的邊的連貫性，按從上到下的順序求得各條掃描線的交點(diǎn)序列；根據(jù)掃描線的連貫性，可確定各條掃描線上位于多邊形 P內(nèi)的區(qū)段，并表示成點(diǎn)陣形式。 2022/5/25 內(nèi)蒙古大學(xué)計(jì)算機(jī)圖形學(xué) 30 數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟 即算法中采用較靈活的數(shù)據(jù)結(jié)構(gòu)。它由邊的分類(lèi)表 ET（ Edge Table）和邊的活化鏈表 AEL（ Active Edge List） 兩部分組成。 表結(jié)構(gòu) ET和 AEL中的基本元素為多邊形的邊。邊的結(jié)構(gòu)由以下四個(gè)域組成： ymax 邊的上端點(diǎn)的 y坐標(biāo)； x 在 ET中表示邊的下端點(diǎn)的 x坐標(biāo)，在AEL中則表示邊與掃描線的交點(diǎn)的坐標(biāo)； Δ x 邊的斜率的倒數(shù)； next 指向下一條邊的指針。 數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟 2022/5/25 內(nèi)蒙古大學(xué)計(jì)算機(jī)圖形學(xué) 31 邊的分類(lèi)表 ET是按邊的下端點(diǎn)的 y坐標(biāo)對(duì)非水平邊進(jìn)行分類(lèi)的指針數(shù)組。下端點(diǎn)的 y坐標(biāo)的值等于 i的邊歸入第 i類(lèi)。有多少條掃描線，就設(shè)多少類(lèi)。同一類(lèi)中，各邊按 x值（ x值相等時(shí)，按 Δ x的值）遞增的順序排列成行。 數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟 2022/5/25 內(nèi)蒙古大學(xué)計(jì)算機(jī)圖形學(xué) 32 與當(dāng)前掃描線相交的邊稱(chēng)為活性邊（ active edge)，把它們按與掃描線交點(diǎn) x坐標(biāo)遞增的順序存入一個(gè)鏈表中，邊的活化鏈表 （ AEL, Active edge table)。它記錄了多邊形邊沿掃描線的交點(diǎn)序列。 例子 2022/5/25 內(nèi)蒙古大學(xué)計(jì)算機(jī)圖形學(xué) 33 ? 已知多邊形P=(P0P1P2P3P4P5P6P0)；其各邊坐標(biāo)分別為 ? [（ 2， 5）（ 2， 10）（ 9， 6）（ 16， 11）（ 16， 4）（ 12， 2）（ 7， 2） ] ? 建立其邊表和邊的活化鏈表 例子 2022/5/25 內(nèi)蒙古大學(xué)計(jì)算機(jī)圖形學(xué) 34 邊表 2022/5/25 內(nèi)蒙古大學(xué)計(jì)算機(jī)圖形學(xué) 35 2022/5/25 內(nèi)蒙古大學(xué)計(jì)算機(jī)圖形學(xué) 36 活動(dòng)邊表的例子 y=3 Y=8 算法實(shí)現(xiàn)步驟 2022/5/25 內(nèi)蒙古大學(xué)計(jì)算機(jī)圖形學(xué) 37 這樣，當(dāng)建立了邊的分類(lèi)表 ET后，掃描線算法可按下列步驟進(jìn)行： （ 1）取掃描線縱坐標(biāo) y的初始值為 ET中非空元素的最小序號(hào)。 （ 2）將邊的活化鏈表 AEL設(shè)置為空。 （ 3）按從下到上的順序?qū)v坐標(biāo)值為 y的掃描線（當(dāng)前掃描線）執(zhí)行下列步驟，直到邊的分類(lèi)表 ET和邊的活化鏈表都變成空為止。 算法實(shí)現(xiàn)步驟 2022/5/25 內(nèi)蒙古大學(xué)計(jì)算機(jī)圖形學(xué) 38 1）如邊分類(lèi)表 ET中的第 y類(lèi)元素非空，則將屬于該類(lèi)的所有邊從 ET中取出并插入邊的活化鏈表中。遞增方向排序。 2）若相對(duì)于當(dāng)前掃描線，邊的活化鏈表 AEL非空，則將 AEL中的邊兩兩依次配對(duì)，依此類(lèi)推。并填色。 3）將邊的活化鏈表 AEL中滿足 y=ymax的邊刪去。 4） x:=x+Δ x。 5） y:=y+1。 掃描線算法 2022/5/25 內(nèi)蒙古大學(xué)計(jì)算機(jī)圖形學(xué) 39 ?特點(diǎn)：算法效率比逐點(diǎn)填充法高很多。 ?缺點(diǎn)：對(duì)各種表的維持和排序開(kāi)銷(xiāo)太大，適合軟件實(shí)現(xiàn)而不適合硬件實(shí)現(xiàn)。 掃描線算法 2022/5/25 內(nèi)蒙古大學(xué)計(jì)算機(jī)圖形學(xué) 40 問(wèn)題： 如何處理多邊形的水平邊？ 如何修改掃描線算法，使它能處理邊自交的多邊形？有孔的多邊形如何處理？ 如何處理圓、橢圓的掃描線算法？ 邊緣填充算法 2022/5/25 內(nèi)蒙古大學(xué)計(jì)算機(jī)圖形學(xué) 41 ▼ 求余運(yùn)算 ：假定 A為一個(gè)正整數(shù)，則 M的余定義為 A – M, 記為 。計(jì)算機(jī)中取 A為 n位能表示的最大整數(shù)。即， A=0xFFFFFFFF ▼ 由來(lái) ：光柵圖形中，如果某區(qū)域已著上值為 M的顏色值做偶數(shù)次求余運(yùn)算，該區(qū)域顏色不變；而做奇數(shù)次求余運(yùn)算，則該區(qū)域顏色變?yōu)橹禐? 的顏色。這一規(guī)律應(yīng)用于多邊形掃描轉(zhuǎn)換，就為邊緣填充算法。 ▼算法基本思想 ：對(duì)于每條掃描線和每條多邊形邊的交點(diǎn)，將該掃描線上交點(diǎn)右方的所有象素取余。 MM算法 1（以掃描線為中心的邊緣填充算法） 2022/5/25 內(nèi)蒙古大學(xué)計(jì)算機(jī)圖形學(xué) 42 將當(dāng)前掃描線上的 所有象素著上 顏色； 求余： for(i = 0。i = m。 i++)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1