計算機圖形學(xué)第七章-文庫吧
2025-04-22 15:31 本頁面
【正文】 描線 y=d上的交點序列為 xdj1,xdj2,… ,xdjk。 若多邊形 P的邊 Pr1Pr與掃描線 y=e和y=d都相交，則 xer和 xdr滿足： rdrdrer mxxxx1?????怎樣得到 y=e上的交點序列 通過遞推式可以算出與 y=e和 y=d都相交的點 若再求出與掃描線 y=d不相交但與下一掃描線 y=e相交的所有邊 PqPq+1上的交點 xeq 然后把這些點按底層的順序排列，就能得到了 y=e上的交點序列 邊的連貫性 當(dāng)取某一整數(shù) k， 0=k=n1， 使 1)兩序列元素數(shù)個數(shù)相等 2)點 (xeir,e)與 (xdjr,d)位于多邊形同一條邊上，即 ir=jr， 得到 由上式就可遞推出 xeir。 kiki ydey ,1, , ???rjrdire mxx1, ??奇點的處理 當(dāng)掃描線與多邊形 P的邊界的交點是 P的頂點時，該交點稱為奇點。 由于連貫性，每一條掃描線與多邊形 P的邊界交點個數(shù)都是偶數(shù)。但是過奇點的掃描線可能出現(xiàn)奇數(shù)。 出現(xiàn)奇點的兩種情況的討論 極值點就是附近的點都比其小或都比其大，滿足數(shù)學(xué)表達式為 (yi1yi)(yi+1yi)0 不是極值點的頂點稱為非極值點。 對于奇點的兩種情況的處理 掃描線算法的數(shù)據(jù)結(jié)構(gòu) 邊的分類表 ET 邊的分類表 ET是按邊下端點的縱坐標(biāo) y對非水平邊進行分類的鏈表數(shù)組。 邊的活化表 AEL 邊的活化表 AEL由與當(dāng)前掃描線相交的所有多邊形的邊組成，它記錄了多邊形邊沿掃描線的交點序列，并根據(jù)遞推式： rjrdire mxx1, ???不斷刷新交點序列。 掃描線算法的描述 步驟 1： (y初始化 )建立 ET表，并且取掃描線縱坐標(biāo) y的初始值為 ET中非空元素的最小序列。 步驟 2： (AEL初始化 )將邊的活化鏈表AEL設(shè)置為空。 步驟 3：按從下到上的順序?qū)v坐標(biāo)值為y的掃描線 (當(dāng)前掃描線 )執(zhí)行子算法，直到 ET和 AEL都變?yōu)榭諡橹埂? 子算法步驟 1)如果邊分類表 ET中第 y類元素為非空，則將屬于該類的所有邊從 ET中取出并插入邊的活化鏈表 AEL中， AEL中各邊按 x的值 (當(dāng) x的值相等時，按 Δ x值 )遞增方式排序。 子算法步驟 2)若相對于當(dāng)前掃描線，邊的活化鏈表AEL非空，則將 AEL中邊兩兩依次配對 (位置位于 1,2的配對；位置位于 3,4的配對 )，依次配對的邊的內(nèi)部點 (像素 )按多邊形的顏色屬性進行著色。 子算法步驟 3)將邊的活化鏈表 AEL中 ymax＝ y的邊刪去 4)將邊的活化鏈表 AEL剩下的每一條邊的x域累加 Δ x， 即 x:=x+Δ x 5)將當(dāng)前掃描線的縱坐標(biāo)值 y累加 1，即y:=y+1 掃描線算法的優(yōu)缺點 優(yōu)點：效率高。 缺點：程序復(fù)雜，需要排序。 邊緣填充算法 由于掃描線算法需要對多邊形的邊進行排序，如果采用求余的方法，就不用對邊進行排序了。 什么是求余？ 數(shù)學(xué)上： A為一個給定的正數(shù)，數(shù) M的余是指 AM的差。記為 ,易得 光柵圖形上：若某區(qū)域已著上值為 M的某種顏色，對 M作偶數(shù)次求余運算后，此區(qū)域顏色不變，作奇數(shù)次求余運算后，區(qū)域顏色變?yōu)? 。 M MM
高考資料相關(guān)推薦
鄂ICP備17016276號-1