《線(xiàn)上線(xiàn)下混合式計(jì)算機(jī)圖形學(xué)基礎(chǔ)實(shí)驗(yàn)教程》課件-第7章

第7章圖元填充7.1實(shí)驗(yàn)內(nèi)容簡(jiǎn)述和實(shí)驗(yàn)?zāi)繕?biāo)7.2掃描線(xiàn)填充任意多邊形7.3課外拓展性實(shí)驗(yàn)

7.1實(shí)驗(yàn)內(nèi)容簡(jiǎn)述和實(shí)驗(yàn)?zāi)繕?biāo)

基本實(shí)驗(yàn)內(nèi)容為掃描線(xiàn)填充任意多邊形。同時(shí)，配備了一個(gè)課外拓展性實(shí)驗(yàn)。完成本實(shí)驗(yàn)后，讀者能夠：

(1)熟記和描述光柵多邊形填充原理(布魯姆知識(shí)模型：記憶和理解)；

(2)熟記和描述掃描線(xiàn)填充多邊形的原理和過(guò)程(布魯姆知識(shí)模型：記憶、理解)；

(3)熟記和描述種子點(diǎn)填充多邊形區(qū)域的原理和過(guò)程(布魯姆知識(shí)模型：記憶、理解)；

(4)判斷光柵掃描轉(zhuǎn)換填充多邊形過(guò)程中邊界異常點(diǎn)的取舍(布魯姆知識(shí)模型：應(yīng)用)；

(5)結(jié)合OpenGL編程實(shí)現(xiàn)掃描線(xiàn)填充任意多邊形(布魯姆知識(shí)模型：應(yīng)用)。

7.2掃描線(xiàn)填充任意多邊形

掃描線(xiàn)填充多邊形的基本思想：將多邊形填充分解到一系列連續(xù)的線(xiàn)掃描求交和填充上來(lái)，即計(jì)算每條掃描線(xiàn)與多邊形的相交情況，進(jìn)而確定多邊形內(nèi)部區(qū)域的直線(xiàn)段(內(nèi)部需要填充的區(qū)域)，實(shí)現(xiàn)多邊形內(nèi)部填充。然而，直接開(kāi)展上述求交填充的運(yùn)算量非常大，為了提高算法效率，需充分利用多邊形的邊界(邊)連貫性，采用增量的方式進(jìn)行填充。

1.關(guān)鍵數(shù)據(jù)結(jié)構(gòu)

同時(shí)，為了充分利用多邊形邊的連貫性或相鄰關(guān)系，采用常見(jiàn)的邊表(ET)來(lái)分類(lèi)保存多邊形的所有邊——?按照每條邊的兩端點(diǎn)y坐標(biāo)最小值對(duì)多邊形的非水平邊進(jìn)行分類(lèi)表示的指針數(shù)組，有多少條掃描線(xiàn)，ET就有多少分類(lèi)，同一類(lèi)中的所有邊先按照x值遞增排序，其次按邊的reciprocal_K遞增排序。

隨著掃描線(xiàn)順序更迭，為了能快速確定哪些邊與當(dāng)前掃描線(xiàn)有交點(diǎn)(避免真正開(kāi)展求交計(jì)算)，采用了活化邊表(AET)，用來(lái)把與當(dāng)前掃描線(xiàn)存在相交情況的所有邊進(jìn)行統(tǒng)一處理，同時(shí)依據(jù)它們與掃描線(xiàn)的交點(diǎn)坐標(biāo)的x值，按遞增的順序存放。

2.算法關(guān)鍵步驟

(1)生成多邊形對(duì)應(yīng)的ET表。

(2)將掃描線(xiàn)縱坐標(biāo)y的初值置為ET中非空元素的最小序號(hào)。

(3)置AET為空。

(4)執(zhí)行下列步驟直至ET和AET都為空：

①如ET中的第y類(lèi)非空，則將其中的所有邊取出并插入AET中。

②新邊插入AET時(shí)與AET中原有邊重新排序。

③對(duì)AET中的邊兩兩配對(duì)，將每對(duì)邊中的x坐標(biāo)按規(guī)則取整，獲得有效的填充區(qū)段，將AET每條邊中的x遞增reciprocal_K。

④將當(dāng)前掃描線(xiàn)縱坐標(biāo)y值遞增1。

⑤將AET中滿(mǎn)足y項(xiàng)與遞增后的y值相同的邊刪去。

⑥迭代步驟④，直到y(tǒng)達(dá)到最大值。

3.關(guān)鍵代碼實(shí)現(xiàn)

4.案例效果

如圖7-1(a)所示為未進(jìn)行填充的多邊形，執(zhí)行掃描線(xiàn)填充后，最終效果如圖7-1(b)所示。

圖7-1掃描線(xiàn)填充任意多邊形示意圖