計(jì)算機(jī)圖形學(xué)多邊形的掃描轉(zhuǎn)換

計(jì)算機(jī)圖形學(xué)多邊形的掃描轉(zhuǎn)換第2頁(yè),共25頁(yè)，2024年2月25日，星期天多邊形:用一系列首尾相連線段構(gòu)成的封閉圖形。

分為凸多邊形、凹多邊形、含內(nèi)環(huán)的多邊形。凸多邊形:如果在多邊形內(nèi)任選兩個(gè)點(diǎn)，將這兩個(gè)點(diǎn)用線段連接后，此線段上所有的點(diǎn)都在多邊形內(nèi)。

凹多邊形:非凸多邊形。4.1實(shí)面積圖形的概念第3頁(yè),共25頁(yè)，2024年2月25日，星期天(1)頂點(diǎn)表示：用多邊形頂點(diǎn)的序列來(lái)刻畫多邊形。(2)點(diǎn)陣表示：用位于多邊形內(nèi)的象素的集合來(lái)刻畫多邊形。多邊形的表示方法第4頁(yè),共25頁(yè)，2024年2月25日，星期天3.多邊形的掃描轉(zhuǎn)換

將多邊形的描述從頂點(diǎn)表示法變換到點(diǎn)陣表示法的過(guò)程，稱為多邊形的掃描轉(zhuǎn)換。即從多邊形的頂點(diǎn)信息出發(fā)，求出多邊形內(nèi)部的各個(gè)像素點(diǎn)信息。4.1.3多邊形的填充確定穿越多邊形內(nèi)部的掃描線的覆蓋區(qū)間。首先確定多邊形覆蓋的掃描線條數(shù)（y＝y(tǒng)min～ymax），對(duì)每一條掃描線，計(jì)算掃描線與多邊形邊界的交點(diǎn)區(qū)間（xmin～xmax），再將該區(qū)間內(nèi)的像素賦予指定的顏色。在掃描線從多邊形頂點(diǎn)的最小值ymin到多邊形頂點(diǎn)的最大值ymax的移動(dòng)過(guò)程中，重復(fù)上述工作，就可以填充多邊形。第5頁(yè),共25頁(yè)，2024年2月25日，星期天掃描線算法基本思想：按掃描線順序，計(jì)算掃描線與多邊形的相交區(qū)間，再用要求的顏色顯示這些區(qū)間的象素，即完成填充工作。對(duì)于一條掃描線填充過(guò)程可以分為四個(gè)步驟：（1）求交：I4,I3,I2,I1（2）排序：I1,I2,I3,I4（3）配對(duì)：(I1,I2),(I3,I4)（4）填色：第6頁(yè),共25頁(yè)，2024年2月25日，星期天4.2有效邊表填充算法4.2.1填充原理4.2.2邊界像素的處理原則4.2.3有效邊和有效邊表4.2.4桶表和邊表第7頁(yè),共25頁(yè)，2024年2月25日，星期天4.2.1填充原理

多邊形的有效邊表填充算法的基本原理是按照掃描線從小到大的移動(dòng)順序，計(jì)算當(dāng)前掃描線與有效邊的交點(diǎn)，然后把這些交點(diǎn)按x值遞增的順序進(jìn)行排序、配對(duì)，以確定填充區(qū)間，然后用指定顏色設(shè)置填充區(qū)間內(nèi)的所有像素，即完成填充工作。

第8頁(yè),共25頁(yè)，2024年2月25日，星期天圖4-5用一條掃描線填充多邊形內(nèi)部

P0P1P2P3P4P5P6

圖中多邊形覆蓋了12條掃描線。掃描線y＝3與多邊形有4個(gè)交點(diǎn)（2.3，3），(4.5，3），（7，3）和（9，3）。對(duì)交點(diǎn)進(jìn)行圓整處理后的結(jié)果為（2，3），(5，3），（7，3）和（9，3）。按x值遞增的順序?qū)稽c(diǎn)進(jìn)行排序、配對(duì)后的填充區(qū)間為[2，5]和[7，9]，共有7個(gè)像素點(diǎn)需要填充為指定顏色。第9頁(yè),共25頁(yè)，2024年2月25日，星期天4.2.2邊界像素的處理原則

在實(shí)際填充過(guò)程中，需要考慮到邊界像素影響問(wèn)題：圖4-6中正方形P0P2P4P6被等分為4個(gè)小正方形。圖4-7邊界像素的處理

圖4-6邊界像素的問(wèn)題

P0P1P2P3P4P5P6P7P8P0P1P2P3P4P5P6P7P8P1P8和P7P8應(yīng)該填充為哪一個(gè)小正方形的顏色？同理，P8P5

和P8P3應(yīng)該填充為哪一個(gè)小正方形的顏色？第10頁(yè),共25頁(yè)，2024年2月25日，星期天圖4-8面積3×3圖4-9面積2×2

在實(shí)際填充過(guò)程中，也要考慮到像素面積大小的影響問(wèn)題：對(duì)左下角為（1，1），右上角為（3，3）的正方形進(jìn)行填充時(shí)，若邊界上的所有像素全部填充，就得到圖4-8所示的結(jié)果。所填像素覆蓋的面積為3×3個(gè)單位，而正方形的面積實(shí)際只有2×2個(gè)單位。第11頁(yè),共25頁(yè)，2024年2月25日，星期天怎么處理？采用“下閉上開”和“左閉右開”的原則對(duì)邊界像素進(jìn)行處理。圖4-6的處理結(jié)果如圖4-7所示，每個(gè)小正方形的右邊界像素和上邊界像素都沒(méi)有填充。圖4-8的處理結(jié)果如圖4-9所示，上面一行像素和右面一列像素沒(méi)有填充。第12頁(yè),共25頁(yè)，2024年2月25日，星期天P2是邊P3P2的終點(diǎn)，同時(shí)也是邊P2P1的起點(diǎn)。按照“下閉上開”的原則，可以自動(dòng)處理。圖4-10局部點(diǎn)的處理P0P1P2P3P4P5P61.P2點(diǎn)的處理原則第13頁(yè),共25頁(yè)，2024年2月25日，星期天2.P0、P3、P5點(diǎn)和P4點(diǎn)的處理原則掃描線與多邊形的頂點(diǎn)相交時(shí)，交點(diǎn)的取舍，保證交點(diǎn)正確配對(duì)。解決方法：檢查兩相鄰邊在掃描線的哪一側(cè)。只要檢查頂點(diǎn)的兩條邊的另外兩個(gè)端點(diǎn)的Y值，兩個(gè)Y值中大于交點(diǎn)Y值的個(gè)數(shù)是0，1，2，來(lái)決定取0，1，2個(gè)交點(diǎn)。第14頁(yè),共25頁(yè)，2024年2月25日，星期天4.2.3有效邊和有效邊表

1.有效邊

多邊形內(nèi)與當(dāng)前掃描線相交的邊稱為有效邊。在處理一條掃描線時(shí)僅對(duì)有效邊進(jìn)行求交運(yùn)算，可以避免與多邊形的所有邊求交，提高了算法效率。有效邊上的掃描線由起點(diǎn)到終點(diǎn)每次加1，即像素點(diǎn)的y坐標(biāo)為：y＝y(tǒng)+1，x坐標(biāo)的變化可以按如下方法推導(dǎo)。第15頁(yè),共25頁(yè)，2024年2月25日，星期天設(shè)有效邊的斜率為k。假定有效邊與當(dāng)前掃描線yi的交點(diǎn)為（xi，yi），則有效邊與下一條掃描線yi+1

的交點(diǎn)

yi+1=yi+1，說(shuō)明隨著掃描線的移動(dòng)，掃描線與有效邊交點(diǎn)的x坐標(biāo)從起點(diǎn)開始可以按增量1/k計(jì)算出來(lái)。（xi+1，yi+1）（xi，yi）1/k圖4-11有效邊交點(diǎn)相關(guān)性1第16頁(yè),共25頁(yè)，2024年2月25日，星期天

圖4-12有效邊表結(jié)點(diǎn)2.有效邊表

把有效邊按照與掃描線交點(diǎn)x坐標(biāo)遞增的順序存放在一個(gè)鏈表中，稱為有效邊表第17頁(yè),共25頁(yè)，2024年2月25日，星期天P0P1P2P3P4P5P6圖4-13示例多邊形對(duì)于圖4-13所示的多邊形，頂點(diǎn)表示法為：P0（7,8）,P1（3,12）,P2（1,7）,P3（3,1）,P4（6,5）,P5（8,1）,P6（12,9）。第18頁(yè),共25頁(yè)，2024年2月25日，星期天

掃描線的最大值為Smax＝12，最小值為Smin＝1，共有12條掃描線，每條掃描線之間間隔1個(gè)像素單位。每條掃描線的有效邊表為如圖4～18所示。第19頁(yè),共25頁(yè)，2024年2月25日，星期天第20頁(yè),共25頁(yè)，2024年2月25日，星期天

這條掃描線處理完畢后對(duì)于P3P4和P4P5兩條邊，因?yàn)橄乱粭l掃描線S=5和ymax相等，根據(jù)“下閉上開”的原則予以刪除。第21頁(yè),共25頁(yè)，2024年2月25日，星期天這條掃描線處理完畢后對(duì)于P2P3邊，因?yàn)橄乱粭l掃描線S=7和ymax相等，根據(jù)“下閉上開”的原則予以刪除。當(dāng)S＝7時(shí)，添加上新邊P1、P2。第22頁(yè),共25頁(yè)，2024年2月25日，星期天當(dāng)S＝8時(shí)，添加上新邊P0P1和P0P6。

這條掃描線處理完畢后對(duì)于P5P6邊和P0P6邊，因?yàn)橄乱粭l掃描線S=9和ymax相等，根據(jù)“下閉上開”的原則予以刪除。第23頁(yè),共25頁(yè)，2024年2月25日，星期天S=11的掃描線處理完畢后對(duì)于P1P2邊和P0P1邊，因?yàn)橄乱粭l掃描線S=12和ymax相等，根據(jù)“下閉上開”的原則予以刪除。至此，全部有效邊表已經(jīng)給出。第24頁(yè),共25頁(yè)，2024年2月25日，星期天4.2.4桶表和邊表