gjlchp二維填充圖元的生成課件

掃描轉(zhuǎn)換矩形問(wèn)題：矩形是簡(jiǎn)單的多邊形，那么為什么要單獨(dú)處理矩形？比一般多邊形可簡(jiǎn)化計(jì)算。應(yīng)用非常多，窗口系統(tǒng)。共享邊界如何處理？ 原則：左閉右開，下閉上開屬于誰(shuí)？1/4/20231浙江大學(xué)計(jì)算機(jī)圖形學(xué)掃描轉(zhuǎn)換矩形問(wèn)題：屬于誰(shuí)？12/26/20221浙江大學(xué)計(jì)算掃描轉(zhuǎn)換矩形方法：voidFillRectangle(Rectangle*rect,intcolor) {intx,y; for(y=rect->ymin;y<=rect->ymax;y++) for(x=rect->xmin;x<=rect->xmax;x++) PutPixel(x,y,color); }/*endofFillRectangle() */1/4/20232浙江大學(xué)計(jì)算機(jī)圖形學(xué)掃描轉(zhuǎn)換矩形方法：voidFillRectangle(Re掃描轉(zhuǎn)換多邊形多邊形分為凸多邊形、凹多邊形、含內(nèi)環(huán)的多邊形。1/4/20233浙江大學(xué)計(jì)算機(jī)圖形學(xué)掃描轉(zhuǎn)換多邊形多邊形分為凸多邊形、凹多邊形、含內(nèi)環(huán)的多邊形。掃描轉(zhuǎn)換多邊形多邊形的表示方法頂點(diǎn)表示點(diǎn)陣表示頂點(diǎn)表示：用多邊形頂點(diǎn)的序列來(lái)刻劃多邊形。直觀、幾何意義強(qiáng)、占內(nèi)存少；不能直接用于面著色。點(diǎn)陣表示：用位于多邊形內(nèi)的象素的集合來(lái)刻劃多邊形。失去了許多重要的幾何信息；便于運(yùn)用幀緩沖存儲(chǔ)器表示圖形，易于面著色。1/4/20234浙江大學(xué)計(jì)算機(jī)圖形學(xué)掃描轉(zhuǎn)換多邊形多邊形的表示方法12/26/20224浙江大學(xué)多邊形的掃描轉(zhuǎn)換多邊形的掃描轉(zhuǎn)換：把多邊形的頂點(diǎn)表示轉(zhuǎn)換為點(diǎn)陣表示，也就是從多邊形的給定邊界出發(fā)，求出位于其內(nèi)部的各個(gè)象素，并給幀緩沖器內(nèi)的各個(gè)對(duì)應(yīng)元素設(shè)置相應(yīng)的灰度和顏色，通常稱這種轉(zhuǎn)換為多邊形的掃描轉(zhuǎn)換。幾種方法：逐點(diǎn)判斷法；掃描線算法；邊緣填充法；柵欄填充法；邊界標(biāo)志法。1/4/20235浙江大學(xué)計(jì)算機(jī)圖形學(xué)多邊形的掃描轉(zhuǎn)換多邊形的掃描轉(zhuǎn)換：把多邊形的頂點(diǎn)表示轉(zhuǎn)換為點(diǎn)voidFillPolygonPbyP(Polygon*P,intpolygonColor){intx,y;

for(y=ymin;y<=ymax;y++)for(x=xmin;x<=xmax;x++) if(IsInside(P,x,y)) PutPixel(x,y,polygonColor); else PutPixel(x,y,backgroundColor);}/*endofFillPolygonPbyP() */#defineMAX100Typedefstruct{intPolygonNum;//多邊形頂點(diǎn)個(gè)數(shù) Pointvertexces[MAX]//多邊形頂點(diǎn)數(shù)組 }Polygon//多邊形結(jié)構(gòu)逐點(diǎn)判斷法1/4/20236浙江大學(xué)計(jì)算機(jī)圖形學(xué)voidFillPolygonPbyP(Polygon*逐點(diǎn)判斷法逐個(gè)判斷繪圖窗口內(nèi)的像素：如何判斷點(diǎn)在多邊形的內(nèi)外關(guān)系？1）射線法：2）累計(jì)角度法3）編碼法；1/4/20237浙江大學(xué)計(jì)算機(jī)圖形學(xué)逐點(diǎn)判斷法逐個(gè)判斷繪圖窗口內(nèi)的像素：12/26/20227浙逐點(diǎn)判斷法1）射線法步驟：從待判別點(diǎn)v發(fā)出射線求交點(diǎn)個(gè)數(shù)kK的奇偶性決定了點(diǎn)與多邊形的內(nèi)外關(guān)系1/4/20238浙江大學(xué)計(jì)算機(jī)圖形學(xué)逐點(diǎn)判斷法1）射線法12/26/20228浙江大學(xué)計(jì)算機(jī)圖形逐點(diǎn)判斷法2）累計(jì)角度法步驟從v點(diǎn)向多邊形P頂點(diǎn)發(fā)出射線，形成有向角計(jì)算有相交的和，得出結(jié)論1/4/20239浙江大學(xué)計(jì)算機(jī)圖形學(xué)逐點(diǎn)判斷法2）累計(jì)角度法12/26/20229浙江大學(xué)計(jì)算機(jī)逐點(diǎn)判斷法逐點(diǎn)判斷的算法雖然程序簡(jiǎn)單，但不可取。原因是速度太慢，主要是由于該算法割斷了各象素之間的聯(lián)系，孤立地考察各象素與多邊形的內(nèi)外關(guān)系，使得幾十萬(wàn)甚至幾百萬(wàn)個(gè)象素都要一一判別，每次判別又要多次求交點(diǎn)，需要做大量的乘除運(yùn)算，花費(fèi)很多時(shí)間。1/4/202310浙江大學(xué)計(jì)算機(jī)圖形學(xué)逐點(diǎn)判斷法逐點(diǎn)判斷的算法雖然程序簡(jiǎn)單，但不可取。原因是速度太掃描線算法掃描線算法目標(biāo)：利用相鄰像素之間的連貫性，提高算法效率處理對(duì)象：非自交多邊形（邊與邊之間除了頂點(diǎn)外無(wú)其它交點(diǎn)）1/4/202311浙江大學(xué)計(jì)算機(jī)圖形學(xué)掃描線算法掃描線算法12/26/202211浙江大學(xué)計(jì)算機(jī)圖掃描線算法交點(diǎn)的取整規(guī)則要求：使生成的像素全部位于多邊形之內(nèi)假定非水平邊與掃描線y=e相交，交點(diǎn)的橫坐標(biāo)為x,規(guī)則如下1/4/202312浙江大學(xué)計(jì)算機(jī)圖形學(xué)掃描線算法交點(diǎn)的取整規(guī)則12/26/202212浙江大學(xué)計(jì)算掃描線算法●規(guī)則1：

X為小數(shù)，即交點(diǎn)落于掃描線上兩個(gè)相鄰像素之間

(a)交點(diǎn)位于左邊之上，向右取整 (b)交點(diǎn)位于右邊之上，向左取整1/4/202313浙江大學(xué)計(jì)算機(jī)圖形學(xué)掃描線算法●規(guī)則1：12/26/202213浙江大學(xué)計(jì)算機(jī)圖●規(guī)則2：

邊界上象素的取舍問(wèn)題，避免填充擴(kuò)大化。●解決方法：

邊界象素：規(guī)定落在右上邊界的象素不予填充。

具體實(shí)現(xiàn)時(shí)，只要對(duì)掃描線與多邊形的相交區(qū)間左閉右開掃描線算法1/4/202314浙江大學(xué)計(jì)算機(jī)圖形學(xué)●規(guī)則2：掃描線算法12/26/202214浙江大學(xué)計(jì)算機(jī)圖●規(guī)則3：

掃描線與多邊形的頂點(diǎn)相交時(shí)，交點(diǎn)的取舍，保證交點(diǎn)正確配對(duì)?！窠鉀Q方法： 檢查兩相鄰邊在掃描線的哪一側(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)。

掃描線算法1/4/202315浙江大學(xué)計(jì)算機(jī)圖形學(xué)●規(guī)則3：掃描線算法12/26/202215浙江大學(xué)計(jì)算機(jī)圖

掃描線算法是多邊形掃描轉(zhuǎn)換的常用算法。與逐點(diǎn)判斷算法相比，掃描線算法充分利用了相鄰象素之間的連貫性，避免了對(duì)象素的逐點(diǎn)判斷和反復(fù)求交的運(yùn)算，達(dá)到了減少了計(jì)算量和提高速度的目的。開發(fā)和利用相鄰象素之間的連貫性是光柵圖形算法研究的重要內(nèi)容。掃描轉(zhuǎn)換算法綜合利用了區(qū)域的連貫性、掃描線連貫性和邊的連貫性等三種形式的連貫性。掃描線算法1/4/202316浙江大學(xué)計(jì)算機(jī)圖形學(xué)掃描線算法是多邊形掃描轉(zhuǎn)換的常用算法

設(shè)多邊形P的頂點(diǎn)Pi=(xi,yi),i=0,1,…,n，又設(shè)yi0,yi1,…yin是各頂點(diǎn)Pi的坐標(biāo)yi的遞減數(shù)列，即yik≥yik+1,0≤k≤n-1這樣，當(dāng)yik≥yik+1,0≤k≤n-1時(shí)，屏幕上位于y=yik和y=yik+1兩條掃描線之間的長(zhǎng)方形區(qū)域被多邊形P的邊分割成若干梯形（三角形可看作其中一底邊長(zhǎng)為零的梯形），它們具有下列性質(zhì)：區(qū)域的連貫性1/4/202317浙江大學(xué)計(jì)算機(jī)圖形學(xué)設(shè)多邊形P的頂點(diǎn)Pi=(xi,yi),i=0,1,區(qū)域的連貫性1）梯形的兩底邊分別在y=yik和y=yik+1兩條掃描線上，腰在多邊形P的邊上或在顯示屏幕的邊界上。2）這些梯形可分為兩類：一類位于多邊形P的內(nèi)部；另一類在多邊形P的外部。3）兩類梯形在長(zhǎng)方形區(qū)域{yik,yik+1}內(nèi)相間的排列，即相鄰的兩梯形必有一個(gè)在多邊形P內(nèi)，另一個(gè)在P外。

1/4/202318浙江大學(xué)計(jì)算機(jī)圖形學(xué)區(qū)域的連貫性1）梯形的兩底邊分別在y=yik和y=yik+1區(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)系。1/4/202319浙江大學(xué)計(jì)算機(jī)圖形學(xué)區(qū)域的連貫性根據(jù)這些性質(zhì)，實(shí)際上只需知道該長(zhǎng)方形區(qū)域內(nèi)任一梯

設(shè)e為一整數(shù)，yi0≥e≥yin。若掃描線y=e與多邊形P的Pi-1Pi相交，則記其交點(diǎn)的橫坐標(biāo)為xei。

現(xiàn)設(shè)xei1,xei2,xei3,…,xeil是該掃描線與P的邊界各交點(diǎn)橫坐標(biāo)的遞增序列，稱此序列為交點(diǎn)序列。由區(qū)域的連貫性可知，此交點(diǎn)序列具有以下性質(zhì)：掃描線的連貫性1/4/202320浙江大學(xué)計(jì)算機(jī)圖形學(xué)設(shè)e為一整數(shù)，yi0≥e≥yin。若掃描線y=e與多掃描線的連貫性1）l是偶數(shù)。2）在該掃描線上，只有區(qū)段xeik,xeik+1）,k=1,3,5,…,l-1位于多邊形P內(nèi)，其余區(qū)段都在P外。以上性質(zhì)稱為掃描線的連貫性，它是多邊形區(qū)域連貫性在一條掃描線上的反映。1/4/202321浙江大學(xué)計(jì)算機(jī)圖形學(xué)掃描線的連貫性1）l是偶數(shù)。12/26/202221浙江大學(xué)

設(shè)d為一整數(shù)，并且d=e-1,并且yi0≥d≥yin。設(shè)位于掃描線y=d上的交點(diǎn)序列為xdj1,xdj2,xdj3,…,xdjk

現(xiàn)在來(lái)討論掃描線d，e交點(diǎn)序列之間的關(guān)系。若多邊形P的邊Pr-1Pr與掃描線y=e,y=d都相交，則交點(diǎn)序列中對(duì)應(yīng)元素xer,xdr滿足下列關(guān)系：xer=xdr+1/mr(1)其中mr為邊Pr-1Pr的斜率。

邊的連貫性1/4/202322浙江大學(xué)計(jì)算機(jī)圖形學(xué)設(shè)d為一整數(shù)，并且d=e-1,并且yi0≥d≥yi邊的連貫性可利用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。然后把這兩部分按遞增的順序排列，即可得e的交點(diǎn)序列。

1/4/202323浙江大學(xué)計(jì)算機(jī)圖形學(xué)邊的連貫性可利用d的交點(diǎn)序列計(jì)算e的交點(diǎn)序列：先運(yùn)用遞推邊的連貫性特別是當(dāng)存在某一個(gè)整數(shù)k,0≤k≤n-1,使得yik>e,d>yik+1成立時(shí)，則由區(qū)域的連貫性可知d的交點(diǎn)序列和e的交點(diǎn)序列之間有以下關(guān)系：1）兩序列元素的個(gè)數(shù)相等，如上圖所示。2）點(diǎn)(xeir,e)與(xdjr,d)位于多邊形P的同一邊上，于是xeir=xdjr+1/kjr(2)這樣，運(yùn)用遞推關(guān)系式(2)可直接由d的交點(diǎn)序列和e的獲得e的交點(diǎn)序列。以上性質(zhì)稱為邊的連貫性，它是區(qū)域的連貫性在相鄰兩掃描線上的反映。1/4/202324浙江大學(xué)計(jì)算機(jī)圖形學(xué)邊的連貫性特別是當(dāng)存在某一個(gè)整數(shù)k,0≤k≤n-1,使得12當(dāng)掃描線與多邊形P的交點(diǎn)是P的頂點(diǎn)時(shí)，則稱該交點(diǎn)為奇點(diǎn)。以上所述多邊形的三種形式的連貫性都基于這樣的幾何事實(shí)：每一條掃描線與多邊形P的邊界的交點(diǎn)個(gè)數(shù)都是偶數(shù)。但是如果把每一奇點(diǎn)簡(jiǎn)單地計(jì)為一個(gè)交點(diǎn)或者簡(jiǎn)單地計(jì)為兩個(gè)交點(diǎn)，都可能出現(xiàn)奇數(shù)個(gè)交點(diǎn)。那么如果保證交點(diǎn)數(shù)為偶數(shù)呢？奇點(diǎn)的處理1/4/202325浙江大學(xué)計(jì)算機(jī)圖形學(xué)當(dāng)掃描線與多邊形P的交點(diǎn)是P的頂點(diǎn)時(shí)，則稱該交點(diǎn)為奇點(diǎn)。奇點(diǎn)奇點(diǎn)的處理若奇點(diǎn)做一個(gè)交點(diǎn)處理，則情況A，交點(diǎn)個(gè)數(shù)不是偶數(shù)。若奇點(diǎn)做兩個(gè)交點(diǎn)處理，則情況B，交點(diǎn)個(gè)數(shù)不是偶數(shù)。1/4/202326浙江大學(xué)計(jì)算機(jī)圖形學(xué)奇點(diǎn)的處理若奇點(diǎn)做一個(gè)交點(diǎn)處理，則情況A，交點(diǎn)個(gè)數(shù)不是偶數(shù)。奇點(diǎn)的處理多邊形P的頂點(diǎn)可分為兩類：極值奇點(diǎn)和非極值奇點(diǎn)。如果(yi-1-yi)(yi+1-yi)≥0，則稱頂點(diǎn)Pi為極值點(diǎn)；否則稱Pi為非極值點(diǎn)。規(guī)定：奇點(diǎn)是極值點(diǎn)時(shí)，該點(diǎn)按兩個(gè)交點(diǎn)計(jì)算，否則按一個(gè)交點(diǎn)計(jì)算。奇點(diǎn)的預(yù)處理：1/4/202327浙江大學(xué)計(jì)算機(jī)圖形學(xué)奇點(diǎn)的處理多邊形P的頂點(diǎn)可分為兩類：極值奇點(diǎn)和非極值奇點(diǎn)。如數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟算法基本思想：首先取d=yin。容易求得掃描線y=d上的交點(diǎn)序列為xdj1,xdj2,…xdjn，這一序列由位于掃描線y=d上的多邊形P的頂點(diǎn)組成。由yin的交點(diǎn)序列開始，根據(jù)多邊形的邊的連貫性，按從上到下的順序求得各條掃描線的交點(diǎn)序列；根據(jù)掃描線的連貫性，可確定各條掃描線上位于多邊形P內(nèi)的區(qū)段，并表示成點(diǎn)陣形式。1/4/202328浙江大學(xué)計(jì)算機(jī)圖形學(xué)數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟12/26/202228浙江大學(xué)計(jì)算機(jī)圖形即算法中采用較靈活的數(shù)據(jù)結(jié)構(gòu)。它由邊的分類表ET（EdgeTable）和邊的活化鏈表AEL（ActiveEdgeList）兩部分組成。表結(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)步驟1/4/202329浙江大學(xué)計(jì)算機(jī)圖形學(xué)即算法中采用較靈活的數(shù)據(jù)結(jié)構(gòu)。它由邊的分類表ET（E數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟邊的分類表ET是按邊的下端點(diǎn)的y坐標(biāo)對(duì)非水平邊進(jìn)行分類的指針數(shù)組。下端點(diǎn)的y坐標(biāo)的值等于i的邊歸入第i類。有多少條掃描線，就設(shè)多少類。同一類中，各邊按x值（x值相等時(shí)，按Δx的值）遞增的順序排列成行。

1/4/202330浙江大學(xué)計(jì)算機(jī)圖形學(xué)數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟邊的分類表ET是按邊的下端點(diǎn)的y坐標(biāo)對(duì)非水?dāng)?shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟與當(dāng)前掃描線相交的邊稱為活性邊（activeedge)，把它們按與掃描線交點(diǎn)x坐標(biāo)遞增的順序存入一個(gè)鏈表中，邊的活化鏈表（AEL,Activeedgetable)。它記錄了多邊形邊沿掃描線的交點(diǎn)序列。1/4/202331浙江大學(xué)計(jì)算機(jī)圖形學(xué)數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟與當(dāng)前掃描線相交的邊稱為活性邊（activ例子已知多邊形P=(P0P1P2P3P4P5P6P0)；其各邊坐標(biāo)分別為[（2，5）（2，10）（9，6）（16，11）（16，4）（12，2）（7，2）]建立其邊表和邊的活化鏈表1/4/202332浙江大學(xué)計(jì)算機(jī)圖形學(xué)例子已知多邊形P=(P0P1P2P3P4P5P6P0)；其各例子1/4/202333浙江大學(xué)計(jì)算機(jī)圖形學(xué)例子12/26/202233浙江大學(xué)計(jì)算機(jī)圖形學(xué)邊表1/4/202334浙江大學(xué)計(jì)算機(jī)圖形學(xué)邊表12/26/202234浙江大學(xué)計(jì)算機(jī)圖形學(xué)y=3Y=8活動(dòng)邊表的例子1/4/202335浙江大學(xué)計(jì)算機(jī)圖形學(xué)y=3Y=8活動(dòng)邊表的例子12/26/202235浙江大學(xué)計(jì)算法實(shí)現(xiàn)步驟這樣，當(dāng)建立了邊的分類表ET后，掃描線算法可按下列步驟進(jìn)行：（1）取掃描線縱坐標(biāo)y的初始值為ET中非空元素的最小序號(hào)。（2）將邊的活化鏈表AEL設(shè)置為空。（3）按從下到上的順序?qū)v坐標(biāo)值為y的掃描線（當(dāng)前掃描線）執(zhí)行下列步驟，直到邊的分類表ET和邊的活化鏈表都變成空為止。

1/4/202336浙江大學(xué)計(jì)算機(jī)圖形學(xué)算法實(shí)現(xiàn)步驟這樣，當(dāng)建立了邊的分類表ET后，掃描線算法可按下算法實(shí)現(xiàn)步驟1）如邊分類表ET中的第y類元素非空，則將屬于該類的所有邊從ET中取出并插入邊的活化鏈表中。遞增方向排序。2）若相對(duì)于當(dāng)前掃描線，邊的活化鏈表AEL非空，則將AEL中的邊兩兩依次配對(duì)，依此類推。并填色。3）將邊的活化鏈表AEL中滿足y=ymax的邊刪去。4）x:=x+Δx。5）y:=y+1。1/4/202337浙江大學(xué)計(jì)算機(jī)圖形學(xué)算法實(shí)現(xiàn)步驟1）如邊分類表ET中的第y類元素非空，則將屬于該掃描線算法特點(diǎn)：算法效率比逐點(diǎn)填充法高很多。缺點(diǎn)：對(duì)各種表的維持和排序開銷太大，適合軟件實(shí)現(xiàn)而不適合硬件實(shí)現(xiàn)。1/4/202338浙江大學(xué)計(jì)算機(jī)圖形學(xué)掃描線算法特點(diǎn)：算法效率比逐點(diǎn)填充法高很多。12/26/20掃描線算法問(wèn)題：如何處理多邊形的水平邊？如何修改掃描線算法，使它能處理邊自交的多邊形？有孔的多邊形如何處理？如何處理圓、橢圓的掃描線算法？1/4/202339浙江大學(xué)計(jì)算機(jī)圖形學(xué)掃描線算法問(wèn)題：12/26/202239浙江大學(xué)計(jì)算機(jī)圖形學(xué)邊緣填充算法▼求余運(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)右方的所有象素取余。1/4/202340浙江大學(xué)計(jì)算機(jī)圖形學(xué)邊緣填充算法▼求余運(yùn)算：假定A為一個(gè)正整數(shù)，則M的余定義為A1、將當(dāng)前掃描線上的所有象素著上顏色；2、求余： for(i=0;i<=m;i++) 在當(dāng)前掃描線上，從橫坐標(biāo)為Xi的交點(diǎn)向右求余；

算法1（以掃描線為中心的邊緣填充算法）1/4/202341浙江大學(xué)計(jì)算機(jī)圖形學(xué)算法1（以掃描線為中心的邊緣填充算法）12/26/20224 1、將繪圖窗口的背景色置為； 2、對(duì)多邊形的每一條非水平邊做： 從該邊上的每個(gè)象素開始向右求余；算法2（以邊為中心的邊緣填充算法）1/4/202342浙江大學(xué)計(jì)算機(jī)圖形學(xué)算法2（以邊為中心的邊緣填充算法）12/26/202242浙邊緣填充算法適合用于具有幀緩存的圖形系統(tǒng)。處理后，按掃描線順序讀出幀緩存的內(nèi)容，送入顯示設(shè)備。優(yōu)點(diǎn)：算法簡(jiǎn)單缺點(diǎn)：對(duì)于復(fù)雜圖形，每一象素可能被訪問(wèn)多次，輸入/輸出的量比有序邊表算法大得多。1/4/202343浙江大學(xué)計(jì)算機(jī)圖形學(xué)邊緣填充算法適合用于具有幀緩存的圖形系統(tǒng)。處理后，按掃描線順引入柵欄，以減少填充算法訪問(wèn)象素的次數(shù)。柵欄：與掃描線垂直的直線，通常過(guò)一頂點(diǎn)，且把多邊形分為左右二半?；舅枷耄簰呙杈€與多邊形的邊求交，將交點(diǎn)與柵欄之間的象素取補(bǔ)。減少了象素重復(fù)訪問(wèn)數(shù)目，但不徹底。柵欄填充算法1/4/202344浙江大學(xué)計(jì)算機(jī)圖形學(xué)引入柵欄，以減少填充算法訪問(wèn)象素的次數(shù)。柵欄填充算法12/21.對(duì)多邊形的每一條邊進(jìn)行掃描轉(zhuǎn)換，即對(duì)多邊形邊界所經(jīng)過(guò)的象素作一個(gè)邊界標(biāo)志。2.填充。對(duì)每條與多邊形相交的掃描線，按從左到右的順序，逐個(gè)訪問(wèn)該掃描線上的象素。取一個(gè)布爾變量inside來(lái)指示當(dāng)前點(diǎn)的狀態(tài)，若點(diǎn)在多邊形內(nèi)，則inside為真。若點(diǎn)在多邊形外，則inside為假。Inside的初始值為假，每當(dāng)當(dāng)前訪問(wèn)象素為被打上標(biāo)志的點(diǎn)，就把inside取反。對(duì)未打標(biāo)志的點(diǎn)，inside不變。邊界標(biāo)志算法1/4/202345浙江大學(xué)計(jì)算機(jī)圖形學(xué)1.對(duì)多邊形的每一條邊進(jìn)行掃描轉(zhuǎn)換，即對(duì)多邊形邊界所經(jīng)過(guò)的邊界標(biāo)志算法:算法過(guò)程voidedgemark_fill(polydef,color)多邊形定義polydef；intcolor;{對(duì)多邊形polydef每條邊進(jìn)行直線掃描轉(zhuǎn)換；inside=FALSE;for(每條與多邊形polydef相交的掃描線y)for(掃描線上每個(gè)象素x){if(象素x被打上邊標(biāo)志)inside=!(inside);if(inside！=FALSE)drawpixel(x,y,color);elsedrawpixel(x,y,background); }}1/4/202346浙江大學(xué)計(jì)算機(jī)圖形學(xué)邊界標(biāo)志算法:算法過(guò)程voidedgemark_fill(邊界標(biāo)志算法用軟件實(shí)現(xiàn)時(shí)，掃描線算法與邊界標(biāo)志算法的執(zhí)行速度幾乎相同，但由于邊界標(biāo)志算法不必建立維護(hù)邊表以及對(duì)它進(jìn)行排序，所以邊界標(biāo)志算法更適合硬件實(shí)現(xiàn)，這時(shí)它的執(zhí)行速度比有序邊表算法快一至兩個(gè)數(shù)量級(jí)。1/4/202347浙江大學(xué)計(jì)算機(jī)圖形學(xué)邊界標(biāo)志算法用軟件實(shí)現(xiàn)時(shí)，掃描線算法與邊界標(biāo)志算法的執(zhí)行速度邊界標(biāo)志算法思考：如何處理邊界的交點(diǎn)個(gè)數(shù)使其成為偶數(shù)？1/4/202348浙江大學(xué)計(jì)算機(jī)圖形學(xué)邊界標(biāo)志算法思考：如何處理邊界的交點(diǎn)個(gè)數(shù)使其成為偶數(shù)？12/區(qū)域填充算法區(qū)域指已經(jīng)表示成點(diǎn)陣形式的填充圖形，它是象素的集合。區(qū)域填充指先將區(qū)域的一點(diǎn)賦予指定的顏色，然后將該顏色擴(kuò)展到整個(gè)區(qū)域的過(guò)程。區(qū)域填充算法要求區(qū)域是連通的1/4/202349浙江大學(xué)計(jì)算機(jī)圖形學(xué)區(qū)域填充算法區(qū)域指已經(jīng)表示成點(diǎn)陣形式的填充圖形，它是象素的集區(qū)域填充表示方法：內(nèi)點(diǎn)表示、邊界表示內(nèi)點(diǎn)表示枚舉處區(qū)域內(nèi)部的所有像素內(nèi)部的所有像素著同一個(gè)顏色邊界像素著與內(nèi)部像素不同的顏色邊界表示枚舉出邊界上所有的像素邊界上的所有像素著同一顏色內(nèi)部像素著與邊界像素不同的顏色1/4/202350浙江大學(xué)計(jì)算機(jī)圖形學(xué)區(qū)域填充表示方法：內(nèi)點(diǎn)表示、邊界表示12/26/202250區(qū)域填充區(qū)域填充要求區(qū)域是連通的連通性

4連通、8連通4連通：8連通1/4/202351浙江大學(xué)計(jì)算機(jī)圖形學(xué)區(qū)域填充區(qū)域填充要求區(qū)域是連通的12/26/202251浙江區(qū)域填充4連通與8連通區(qū)域的區(qū)別連通性：4連通可看作8連通區(qū)域，但對(duì)邊界有要求對(duì)邊界的要求1/4/202352浙江大學(xué)計(jì)算機(jī)圖形學(xué)區(qū)域填充4連通與8連通區(qū)域的區(qū)別12/26/202252浙江A：適合于內(nèi)點(diǎn)表示區(qū)域的填充算法設(shè)G為一內(nèi)點(diǎn)表示的區(qū)域，(x,y)為區(qū)域內(nèi)一點(diǎn)，old_color為G的原色?，F(xiàn)取(x,y)為種子點(diǎn)對(duì)區(qū)域G進(jìn)行填充：即先置像素(x,y)的顏色為new_color，然后逐步將整個(gè)區(qū)域G都置為同樣的顏色。步驟如下：種子象素入棧，當(dāng)棧非空時(shí)，執(zhí)行如下三步操作：（1）棧頂象素出棧；（2）將出棧象素置成new_color；（3）按上、下、左、右的順序檢查與出棧象素相鄰的四個(gè)象素，若其中某個(gè)象素在邊界內(nèi)且未置成new_color，則把該象素入棧。種子填充算法1/4/202353浙江大學(xué)計(jì)算機(jī)圖形學(xué)A：適合于內(nèi)點(diǎn)表示區(qū)域的填充算法種子填充算法12/26/20種子填充算法例：多邊形由P0P1P2P3P4構(gòu)成，P0(1,5)P1(5,5)P2(7,3)P3(7,1)P4(1,1)設(shè)種子點(diǎn)為（3，3），搜索的方向是上、下、左、右。依此類推，最后像素被選中并填充的次序如圖中箭頭所示

1/4/202354浙江大學(xué)計(jì)算機(jī)圖形學(xué)種子填充算法例：多邊形由P0P1P2P3P4構(gòu)成，P0(1,種子填充算法遞歸算法可實(shí)現(xiàn)如下voidFloodFill4(intx,inty,intoldColor,intnewColor){if(GetPixel(x,y)==oldColor){PutPixel(x,y,newColor);FloodFill4(x,y+1,oldColor,newColor);FloodFill4(x,y-1,oldColor,newColor);FloodFill4(x-1,y,oldColor,newColor);FloodFill4(x+1,y,oldColor,newColor);}}/*endofFloodFill4() */

1/4/202355浙江大學(xué)計(jì)算機(jī)圖形學(xué)種子填充算法遞歸算法可實(shí)現(xiàn)如下voidFloodFill4種子填充算法邊界表示的4連通區(qū)域voidBoundaryFill4(intx,inty,intboundaryColor,intnewColor){ intcolor; color=GetPixel(x,y); if((color!=boundaryColor)&&(color!=newColor)) { PutPixel(x,y,newColor); BoundaryFill4(x,y+1,oldColor,newColor); BoundaryFill4(x,y-1,oldColor,newColor); BoundaryFill4(x-1,y,oldColor,newColor); BoundaryFill4(x+1,y,oldColor,newColor); }}/*endofBoundaryFill4() */

1/4/202356浙江大學(xué)計(jì)算機(jī)圖形學(xué)種子填充算法邊界表示的4連通區(qū)域voidBoundaryF該算法也可以填充有孔區(qū)域。

缺點(diǎn)：(1)有些象素會(huì)入棧多次，降低算法效率；(2)遞歸執(zhí)行，算法簡(jiǎn)單，但效率不高，區(qū)域內(nèi)每一象素都引起一次遞歸，進(jìn)/出棧，費(fèi)時(shí)費(fèi)內(nèi)存。改進(jìn)算法，減少遞歸次數(shù)，提高效率。 解決方法是用掃描線填充算法種子填充算法1/4/202357浙江大學(xué)計(jì)算機(jī)圖形學(xué)該算法也可以填充有孔區(qū)域。種子填充算法12/26/2022掃描線算法掃描線算法目標(biāo)：減少遞歸層次適用于邊界表示的4連通區(qū)域算法思想：在任意不間斷區(qū)間中只取一個(gè)種子像素（不間斷區(qū)間指在一條掃描線上一組相鄰元素），填充當(dāng)前掃描線上的該段區(qū)間；然后確定與這一區(qū)段相鄰的上下兩條掃描線上位于區(qū)域內(nèi)的區(qū)段，并依次把它們保存起來(lái)，反復(fù)進(jìn)行這個(gè)過(guò)程，直到所保存的個(gè)區(qū)段都填充完畢。1/4/202358浙江大學(xué)計(jì)算機(jī)圖形學(xué)掃描線算法掃描線算法12/26/202258浙江大學(xué)計(jì)算機(jī)圖掃描線填充算法(1)初始化：堆棧置空。將種子點(diǎn)（x，y）入棧。(2)出棧：若?？談t結(jié)束。否則取棧頂元素（x，y），以y作為當(dāng)前掃描線。(3)填充并確定種子點(diǎn)所在區(qū)段：從種子點(diǎn)（x，y）出發(fā)，沿當(dāng)前掃描線向左、右兩個(gè)方向填充，直到邊界。分別標(biāo)記區(qū)段的左、右端點(diǎn)坐標(biāo)為xl和xr。(4)并確定新的種子點(diǎn)：在區(qū)間[xl，xr]中檢查與當(dāng)前掃描線y上、下相鄰的兩條掃描線上的象素。若存在非邊界、未填充的象素，則把每一區(qū)間的最右象素作為種子點(diǎn)壓入堆棧，返回第（2）步。上述算法對(duì)于每一個(gè)待填充區(qū)段，只需壓棧一次；因此，掃描線填充算法提高了區(qū)域填充的效率。1/4/202359浙江大學(xué)計(jì)算機(jī)圖形學(xué)掃描線填充算法(1)初始化：堆棧置空。將種子點(diǎn)（x，y）入棧掃描線算法分析（舉例分析）該算法也可以填充有孔區(qū)域。像素中的序號(hào)標(biāo)指它所在區(qū)段位于堆棧中的位置1/4/202360浙江大學(xué)計(jì)算機(jī)圖形學(xué)掃描線算法分析（舉例分析）該算法也可以填充有孔區(qū)域。像素中的掃描線算法分析（舉例分析）1/4/202361浙江大學(xué)計(jì)算機(jī)圖形學(xué)掃描線算法分析（舉例分析）12/26/202261浙江大學(xué)計(jì)掃描線算法分析（舉例分析）1/4/202362浙江大學(xué)計(jì)算機(jī)圖形學(xué)掃描線算法分析（舉例分析）12/26/202262浙江大學(xué)計(jì)掃描轉(zhuǎn)換矩形問(wèn)題：矩形是簡(jiǎn)單的多邊形，那么為什么要單獨(dú)處理矩形？比一般多邊形可簡(jiǎn)化計(jì)算。應(yīng)用非常多，窗口系統(tǒng)。共享邊界如何處理？ 原則：左閉右開，下閉上開屬于誰(shuí)？1/4/202363浙江大學(xué)計(jì)算機(jī)圖形學(xué)掃描轉(zhuǎn)換矩形問(wèn)題：屬于誰(shuí)？12/26/20221浙江大學(xué)計(jì)算掃描轉(zhuǎn)換矩形方法：voidFillRectangle(Rectangle*rect,intcolor) {intx,y; for(y=rect->ymin;y<=rect->ymax;y++) for(x=rect->xmin;x<=rect->xmax;x++) PutPixel(x,y,color); }/*endofFillRectangle() */1/4/202364浙江大學(xué)計(jì)算機(jī)圖形學(xué)掃描轉(zhuǎn)換矩形方法：voidFillRectangle(Re掃描轉(zhuǎn)換多邊形多邊形分為凸多邊形、凹多邊形、含內(nèi)環(huán)的多邊形。1/4/202365浙江大學(xué)計(jì)算機(jī)圖形學(xué)掃描轉(zhuǎn)換多邊形多邊形分為凸多邊形、凹多邊形、含內(nèi)環(huán)的多邊形。掃描轉(zhuǎn)換多邊形多邊形的表示方法頂點(diǎn)表示點(diǎn)陣表示頂點(diǎn)表示：用多邊形頂點(diǎn)的序列來(lái)刻劃多邊形。直觀、幾何意義強(qiáng)、占內(nèi)存少；不能直接用于面著色。點(diǎn)陣表示：用位于多邊形內(nèi)的象素的集合來(lái)刻劃多邊形。失去了許多重要的幾何信息；便于運(yùn)用幀緩沖存儲(chǔ)器表示圖形，易于面著色。1/4/202366浙江大學(xué)計(jì)算機(jī)圖形學(xué)掃描轉(zhuǎn)換多邊形多邊形的表示方法12/26/20224浙江大學(xué)多邊形的掃描轉(zhuǎn)換多邊形的掃描轉(zhuǎn)換：把多邊形的頂點(diǎn)表示轉(zhuǎn)換為點(diǎn)陣表示，也就是從多邊形的給定邊界出發(fā)，求出位于其內(nèi)部的各個(gè)象素，并給幀緩沖器內(nèi)的各個(gè)對(duì)應(yīng)元素設(shè)置相應(yīng)的灰度和顏色，通常稱這種轉(zhuǎn)換為多邊形的掃描轉(zhuǎn)換。幾種方法：逐點(diǎn)判斷法；掃描線算法；邊緣填充法；柵欄填充法；邊界標(biāo)志法。1/4/202367浙江大學(xué)計(jì)算機(jī)圖形學(xué)多邊形的掃描轉(zhuǎn)換多邊形的掃描轉(zhuǎn)換：把多邊形的頂點(diǎn)表示轉(zhuǎn)換為點(diǎn)voidFillPolygonPbyP(Polygon*P,intpolygonColor){intx,y;

for(y=ymin;y<=ymax;y++)for(x=xmin;x<=xmax;x++) if(IsInside(P,x,y)) PutPixel(x,y,polygonColor); else PutPixel(x,y,backgroundColor);}/*endofFillPolygonPbyP() */#defineMAX100Typedefstruct{intPolygonNum;//多邊形頂點(diǎn)個(gè)數(shù) Pointvertexces[MAX]//多邊形頂點(diǎn)數(shù)組 }Polygon//多邊形結(jié)構(gòu)逐點(diǎn)判斷法1/4/202368浙江大學(xué)計(jì)算機(jī)圖形學(xué)voidFillPolygonPbyP(Polygon*逐點(diǎn)判斷法逐個(gè)判斷繪圖窗口內(nèi)的像素：如何判斷點(diǎn)在多邊形的內(nèi)外關(guān)系？1）射線法：2）累計(jì)角度法3）編碼法；1/4/202369浙江大學(xué)計(jì)算機(jī)圖形學(xué)逐點(diǎn)判斷法逐個(gè)判斷繪圖窗口內(nèi)的像素：12/26/20227浙逐點(diǎn)判斷法1）射線法步驟：從待判別點(diǎn)v發(fā)出射線求交點(diǎn)個(gè)數(shù)kK的奇偶性決定了點(diǎn)與多邊形的內(nèi)外關(guān)系1/4/202370浙江大學(xué)計(jì)算機(jī)圖形學(xué)逐點(diǎn)判斷法1）射線法12/26/20228浙江大學(xué)計(jì)算機(jī)圖形逐點(diǎn)判斷法2）累計(jì)角度法步驟從v點(diǎn)向多邊形P頂點(diǎn)發(fā)出射線，形成有向角計(jì)算有相交的和，得出結(jié)論1/4/202371浙江大學(xué)計(jì)算機(jī)圖形學(xué)逐點(diǎn)判斷法2）累計(jì)角度法12/26/20229浙江大學(xué)計(jì)算機(jī)逐點(diǎn)判斷法逐點(diǎn)判斷的算法雖然程序簡(jiǎn)單，但不可取。原因是速度太慢，主要是由于該算法割斷了各象素之間的聯(lián)系，孤立地考察各象素與多邊形的內(nèi)外關(guān)系，使得幾十萬(wàn)甚至幾百萬(wàn)個(gè)象素都要一一判別，每次判別又要多次求交點(diǎn)，需要做大量的乘除運(yùn)算，花費(fèi)很多時(shí)間。1/4/202372浙江大學(xué)計(jì)算機(jī)圖形學(xué)逐點(diǎn)判斷法逐點(diǎn)判斷的算法雖然程序簡(jiǎn)單，但不可取。原因是速度太掃描線算法掃描線算法目標(biāo)：利用相鄰像素之間的連貫性，提高算法效率處理對(duì)象：非自交多邊形（邊與邊之間除了頂點(diǎn)外無(wú)其它交點(diǎn)）1/4/202373浙江大學(xué)計(jì)算機(jī)圖形學(xué)掃描線算法掃描線算法12/26/202211浙江大學(xué)計(jì)算機(jī)圖掃描線算法交點(diǎn)的取整規(guī)則要求：使生成的像素全部位于多邊形之內(nèi)假定非水平邊與掃描線y=e相交，交點(diǎn)的橫坐標(biāo)為x,規(guī)則如下1/4/202374浙江大學(xué)計(jì)算機(jī)圖形學(xué)掃描線算法交點(diǎn)的取整規(guī)則12/26/202212浙江大學(xué)計(jì)算掃描線算法●規(guī)則1：

X為小數(shù)，即交點(diǎn)落于掃描線上兩個(gè)相鄰像素之間

(a)交點(diǎn)位于左邊之上，向右取整 (b)交點(diǎn)位于右邊之上，向左取整1/4/202375浙江大學(xué)計(jì)算機(jī)圖形學(xué)掃描線算法●規(guī)則1：12/26/202213浙江大學(xué)計(jì)算機(jī)圖●規(guī)則2：

邊界上象素的取舍問(wèn)題，避免填充擴(kuò)大化?！窠鉀Q方法：

邊界象素：規(guī)定落在右上邊界的象素不予填充。

具體實(shí)現(xiàn)時(shí)，只要對(duì)掃描線與多邊形的相交區(qū)間左閉右開掃描線算法1/4/202376浙江大學(xué)計(jì)算機(jī)圖形學(xué)●規(guī)則2：掃描線算法12/26/202214浙江大學(xué)計(jì)算機(jī)圖●規(guī)則3：

掃描線與多邊形的頂點(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)。

掃描線算法1/4/202377浙江大學(xué)計(jì)算機(jī)圖形學(xué)●規(guī)則3：掃描線算法12/26/202215浙江大學(xué)計(jì)算機(jī)圖

掃描線算法是多邊形掃描轉(zhuǎn)換的常用算法。與逐點(diǎn)判斷算法相比，掃描線算法充分利用了相鄰象素之間的連貫性，避免了對(duì)象素的逐點(diǎn)判斷和反復(fù)求交的運(yùn)算，達(dá)到了減少了計(jì)算量和提高速度的目的。開發(fā)和利用相鄰象素之間的連貫性是光柵圖形算法研究的重要內(nèi)容。掃描轉(zhuǎn)換算法綜合利用了區(qū)域的連貫性、掃描線連貫性和邊的連貫性等三種形式的連貫性。掃描線算法1/4/202378浙江大學(xué)計(jì)算機(jī)圖形學(xué)掃描線算法是多邊形掃描轉(zhuǎn)換的常用算法

設(shè)多邊形P的頂點(diǎn)Pi=(xi,yi),i=0,1,…,n，又設(shè)yi0,yi1,…yin是各頂點(diǎn)Pi的坐標(biāo)yi的遞減數(shù)列，即yik≥yik+1,0≤k≤n-1這樣，當(dāng)yik≥yik+1,0≤k≤n-1時(shí)，屏幕上位于y=yik和y=yik+1兩條掃描線之間的長(zhǎng)方形區(qū)域被多邊形P的邊分割成若干梯形（三角形可看作其中一底邊長(zhǎng)為零的梯形），它們具有下列性質(zhì)：區(qū)域的連貫性1/4/202379浙江大學(xué)計(jì)算機(jī)圖形學(xué)設(shè)多邊形P的頂點(diǎn)Pi=(xi,yi),i=0,1,區(qū)域的連貫性1）梯形的兩底邊分別在y=yik和y=yik+1兩條掃描線上，腰在多邊形P的邊上或在顯示屏幕的邊界上。2）這些梯形可分為兩類：一類位于多邊形P的內(nèi)部；另一類在多邊形P的外部。3）兩類梯形在長(zhǎng)方形區(qū)域{yik,yik+1}內(nèi)相間的排列，即相鄰的兩梯形必有一個(gè)在多邊形P內(nèi)，另一個(gè)在P外。

1/4/202380浙江大學(xué)計(jì)算機(jī)圖形學(xué)區(qū)域的連貫性1）梯形的兩底邊分別在y=yik和y=yik+1區(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)系。1/4/202381浙江大學(xué)計(jì)算機(jī)圖形學(xué)區(qū)域的連貫性根據(jù)這些性質(zhì)，實(shí)際上只需知道該長(zhǎng)方形區(qū)域內(nèi)任一梯

設(shè)e為一整數(shù)，yi0≥e≥yin。若掃描線y=e與多邊形P的Pi-1Pi相交，則記其交點(diǎn)的橫坐標(biāo)為xei。

現(xiàn)設(shè)xei1,xei2,xei3,…,xeil是該掃描線與P的邊界各交點(diǎn)橫坐標(biāo)的遞增序列，稱此序列為交點(diǎn)序列。由區(qū)域的連貫性可知，此交點(diǎn)序列具有以下性質(zhì)：掃描線的連貫性1/4/202382浙江大學(xué)計(jì)算機(jī)圖形學(xué)設(shè)e為一整數(shù)，yi0≥e≥yin。若掃描線y=e與多掃描線的連貫性1）l是偶數(shù)。2）在該掃描線上，只有區(qū)段xeik,xeik+1）,k=1,3,5,…,l-1位于多邊形P內(nèi)，其余區(qū)段都在P外。以上性質(zhì)稱為掃描線的連貫性，它是多邊形區(qū)域連貫性在一條掃描線上的反映。1/4/202383浙江大學(xué)計(jì)算機(jī)圖形學(xué)掃描線的連貫性1）l是偶數(shù)。12/26/202221浙江大學(xué)

設(shè)d為一整數(shù)，并且d=e-1,并且yi0≥d≥yin。設(shè)位于掃描線y=d上的交點(diǎn)序列為xdj1,xdj2,xdj3,…,xdjk

現(xiàn)在來(lái)討論掃描線d，e交點(diǎn)序列之間的關(guān)系。若多邊形P的邊Pr-1Pr與掃描線y=e,y=d都相交，則交點(diǎn)序列中對(duì)應(yīng)元素xer,xdr滿足下列關(guān)系：xer=xdr+1/mr(1)其中mr為邊Pr-1Pr的斜率。

邊的連貫性1/4/202384浙江大學(xué)計(jì)算機(jī)圖形學(xué)設(shè)d為一整數(shù)，并且d=e-1,并且yi0≥d≥yi邊的連貫性可利用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。然后把這兩部分按遞增的順序排列，即可得e的交點(diǎn)序列。

1/4/202385浙江大學(xué)計(jì)算機(jī)圖形學(xué)邊的連貫性可利用d的交點(diǎn)序列計(jì)算e的交點(diǎn)序列：先運(yùn)用遞推邊的連貫性特別是當(dāng)存在某一個(gè)整數(shù)k,0≤k≤n-1,使得yik>e,d>yik+1成立時(shí)，則由區(qū)域的連貫性可知d的交點(diǎn)序列和e的交點(diǎn)序列之間有以下關(guān)系：1）兩序列元素的個(gè)數(shù)相等，如上圖所示。2）點(diǎn)(xeir,e)與(xdjr,d)位于多邊形P的同一邊上，于是xeir=xdjr+1/kjr(2)這樣，運(yùn)用遞推關(guān)系式(2)可直接由d的交點(diǎn)序列和e的獲得e的交點(diǎn)序列。以上性質(zhì)稱為邊的連貫性，它是區(qū)域的連貫性在相鄰兩掃描線上的反映。1/4/202386浙江大學(xué)計(jì)算機(jī)圖形學(xué)邊的連貫性特別是當(dāng)存在某一個(gè)整數(shù)k,0≤k≤n-1,使得12當(dāng)掃描線與多邊形P的交點(diǎn)是P的頂點(diǎn)時(shí)，則稱該交點(diǎn)為奇點(diǎn)。以上所述多邊形的三種形式的連貫性都基于這樣的幾何事實(shí)：每一條掃描線與多邊形P的邊界的交點(diǎn)個(gè)數(shù)都是偶數(shù)。但是如果把每一奇點(diǎn)簡(jiǎn)單地計(jì)為一個(gè)交點(diǎn)或者簡(jiǎn)單地計(jì)為兩個(gè)交點(diǎn)，都可能出現(xiàn)奇數(shù)個(gè)交點(diǎn)。那么如果保證交點(diǎn)數(shù)為偶數(shù)呢？奇點(diǎn)的處理1/4/202387浙江大學(xué)計(jì)算機(jī)圖形學(xué)當(dāng)掃描線與多邊形P的交點(diǎn)是P的頂點(diǎn)時(shí)，則稱該交點(diǎn)為奇點(diǎn)。奇點(diǎn)奇點(diǎn)的處理若奇點(diǎn)做一個(gè)交點(diǎn)處理，則情況A，交點(diǎn)個(gè)數(shù)不是偶數(shù)。若奇點(diǎn)做兩個(gè)交點(diǎn)處理，則情況B，交點(diǎn)個(gè)數(shù)不是偶數(shù)。1/4/202388浙江大學(xué)計(jì)算機(jī)圖形學(xué)奇點(diǎn)的處理若奇點(diǎn)做一個(gè)交點(diǎn)處理，則情況A，交點(diǎn)個(gè)數(shù)不是偶數(shù)。奇點(diǎn)的處理多邊形P的頂點(diǎn)可分為兩類：極值奇點(diǎn)和非極值奇點(diǎn)。如果(yi-1-yi)(yi+1-yi)≥0，則稱頂點(diǎn)Pi為極值點(diǎn)；否則稱Pi為非極值點(diǎn)。規(guī)定：奇點(diǎn)是極值點(diǎn)時(shí)，該點(diǎn)按兩個(gè)交點(diǎn)計(jì)算，否則按一個(gè)交點(diǎn)計(jì)算。奇點(diǎn)的預(yù)處理：1/4/202389浙江大學(xué)計(jì)算機(jī)圖形學(xué)奇點(diǎn)的處理多邊形P的頂點(diǎn)可分為兩類：極值奇點(diǎn)和非極值奇點(diǎn)。如數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟算法基本思想：首先取d=yin。容易求得掃描線y=d上的交點(diǎn)序列為xdj1,xdj2,…xdjn，這一序列由位于掃描線y=d上的多邊形P的頂點(diǎn)組成。由yin的交點(diǎn)序列開始，根據(jù)多邊形的邊的連貫性，按從上到下的順序求得各條掃描線的交點(diǎn)序列；根據(jù)掃描線的連貫性，可確定各條掃描線上位于多邊形P內(nèi)的區(qū)段，并表示成點(diǎn)陣形式。1/4/202390浙江大學(xué)計(jì)算機(jī)圖形學(xué)數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟12/26/202228浙江大學(xué)計(jì)算機(jī)圖形即算法中采用較靈活的數(shù)據(jù)結(jié)構(gòu)。它由邊的分類表ET（EdgeTable）和邊的活化鏈表AEL（ActiveEdgeList）兩部分組成。表結(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)步驟1/4/202391浙江大學(xué)計(jì)算機(jī)圖形學(xué)即算法中采用較靈活的數(shù)據(jù)結(jié)構(gòu)。它由邊的分類表ET（E數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟邊的分類表ET是按邊的下端點(diǎn)的y坐標(biāo)對(duì)非水平邊進(jìn)行分類的指針數(shù)組。下端點(diǎn)的y坐標(biāo)的值等于i的邊歸入第i類。有多少條掃描線，就設(shè)多少類。同一類中，各邊按x值（x值相等時(shí)，按Δx的值）遞增的順序排列成行。

1/4/202392浙江大學(xué)計(jì)算機(jī)圖形學(xué)數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟邊的分類表ET是按邊的下端點(diǎn)的y坐標(biāo)對(duì)非水?dāng)?shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟與當(dāng)前掃描線相交的邊稱為活性邊（activeedge)，把它們按與掃描線交點(diǎn)x坐標(biāo)遞增的順序存入一個(gè)鏈表中，邊的活化鏈表（AEL,Activeedgetable)。它記錄了多邊形邊沿掃描線的交點(diǎn)序列。1/4/202393浙江大學(xué)計(jì)算機(jī)圖形學(xué)數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟與當(dāng)前掃描線相交的邊稱為活性邊（activ例子已知多邊形P=(P0P1P2P3P4P5P6P0)；其各邊坐標(biāo)分別為[（2，5）（2，10）（9，6）（16，11）（16，4）（12，2）（7，2）]建立其邊表和邊的活化鏈表1/4/202394浙江大學(xué)計(jì)算機(jī)圖形學(xué)例子已知多邊形P=(P0P1P2P3P4P5P6P0)；其各例子1/4/202395浙江大學(xué)計(jì)算機(jī)圖形學(xué)例子12/26/202233浙江大學(xué)計(jì)算機(jī)圖形學(xué)邊表1/4/202396浙江大學(xué)計(jì)算機(jī)圖形學(xué)邊表12/26/202234浙江大學(xué)計(jì)算機(jī)圖形學(xué)y=3Y=8活動(dòng)邊表的例子1/4/202397浙江大學(xué)計(jì)算機(jī)圖形學(xué)y=3Y=8活動(dòng)邊表的例子12/26/202235浙江大學(xué)計(jì)算法實(shí)現(xiàn)步驟這樣，當(dāng)建立了邊的分類表ET后，掃描線算法可按下列步驟進(jìn)行：（1）取掃描線縱坐標(biāo)y的初始值為ET中非空元素的最小序號(hào)。（2）將邊的活化鏈表AEL設(shè)置為空。（3）按從下到上的順序?qū)v坐標(biāo)值為y的掃描線（當(dāng)前掃描線）執(zhí)行下列步驟，直到邊的分類表ET和邊的活化鏈表都變成空為止。

1/4/202398浙江大學(xué)計(jì)算機(jī)圖形學(xué)算法實(shí)現(xiàn)步驟這樣，當(dāng)建立了邊的分類表ET后，掃描線算法可按下算法實(shí)現(xiàn)步驟1）如邊分類表ET中的第y類元素非空，則將屬于該類的所有邊從ET中取出并插入邊的活化鏈表中。遞增方向排序。2）若相對(duì)于當(dāng)前掃描線，邊的活化鏈表AEL非空，則將AEL中的邊兩兩依次配對(duì)，依此類推。并填色。3）將邊的活化鏈表AEL中滿足y=ymax的邊刪去。4）x:=x+Δx。5）y:=y+1。1/4/202399浙江大學(xué)計(jì)算機(jī)圖形學(xué)算法實(shí)現(xiàn)步驟1）如邊分類表ET中的第y類元素非空，則將屬于該掃描線算法特點(diǎn)：算法效率比逐點(diǎn)填充法高很多。缺點(diǎn)：對(duì)各種表的維持和排序開銷太大，適合軟件實(shí)現(xiàn)而不適合硬件實(shí)現(xiàn)。1/4/2023100浙江大學(xué)計(jì)算機(jī)圖形學(xué)掃描線算法特點(diǎn)：算法效率比逐點(diǎn)填充法高很多。12/26/20掃描線算法問(wèn)題：如何處理多邊形的水平邊？如何修改掃描線算法，使它能處理邊自交的多邊形？有孔的多邊形如何處理？如何處理圓、橢圓的掃描線算法？1/4/2023101浙江大學(xué)計(jì)算機(jī)圖形學(xué)掃描線算法問(wèn)題：12/26/202239浙江大學(xué)計(jì)算機(jī)圖形學(xué)邊緣填充算法▼求余運(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)右方的所有象素取余。1/4/2023102浙江大學(xué)計(jì)算機(jī)圖形學(xué)邊緣填充算法▼求余運(yùn)算：假定A為一個(gè)正整數(shù)，則M的余定義為A1、將當(dāng)前掃描線上的所有象素著上顏色；2、求余： for(i=0;i<=m;i++) 在當(dāng)前掃描線上，從橫坐標(biāo)為Xi的交點(diǎn)向右求余；

算法1（以掃描線為中心的邊緣填充算法）1/4/2023103浙江大學(xué)計(jì)算機(jī)圖形學(xué)算法1（以掃描線為中心的邊緣填充算法）12/26/20224 1、將繪圖窗口的背景色置為； 2、對(duì)多邊形的每一條非水平邊做： 從該邊上的每個(gè)象素開始向右求余；算法2（以邊為中心的邊緣填充算法）1/4/2023104浙江大學(xué)計(jì)算機(jī)圖形學(xué)算法2（以邊為中心的邊緣填充算法）12/26/202242浙邊緣填充算法適合用于具有幀緩存的圖形系統(tǒng)。處理后，按掃描線順序讀出幀緩存的內(nèi)容，送入顯示設(shè)備。優(yōu)點(diǎn)：算法簡(jiǎn)單缺點(diǎn)：對(duì)于復(fù)雜圖形，每一象素可能被訪問(wèn)多次，輸入/輸出的量比有序邊表算法大得多。1/4/2023105浙江大學(xué)計(jì)算機(jī)圖形學(xué)邊緣填充算法適合用于具有幀緩存的圖形系統(tǒng)。處理后，按掃描線順引入柵欄，以減少填充算法訪問(wèn)象素的次數(shù)。柵欄：與掃描線垂直的直線，通常過(guò)一頂點(diǎn)，且把多邊形分為左右二半?；舅枷耄簰呙杈€與多邊形的邊求交，將交點(diǎn)與柵欄之間的象素取補(bǔ)。減少了象素重復(fù)訪問(wèn)數(shù)目，但不徹底。柵欄填充算法1/4/2023106浙江大學(xué)計(jì)算機(jī)圖形學(xué)引入柵欄，以減少填充算法訪問(wèn)象素的次數(shù)。柵欄填充算法12/21.對(duì)多邊形的每一條邊進(jìn)行掃描轉(zhuǎn)換，即對(duì)多邊形邊界所經(jīng)過(guò)的象素作一個(gè)邊界標(biāo)志。2.填充。對(duì)每條與多邊形相交的掃描線，按從左到右的順序，逐個(gè)訪問(wèn)該掃描線上的象素。取一個(gè)布爾變量inside來(lái)指示當(dāng)前點(diǎn)的狀態(tài)，若點(diǎn)在多邊形內(nèi)，則inside為真。若點(diǎn)在多邊形外，則inside為假。Inside的初始值為假，每當(dāng)當(dāng)前訪問(wèn)象素為被打上標(biāo)志的點(diǎn)，就把inside取反。對(duì)未打標(biāo)志的點(diǎn)，inside不變。邊界標(biāo)志算法1/4/2023107浙江大學(xué)計(jì)算機(jī)圖形學(xué)1.對(duì)多邊形的每一條邊進(jìn)行掃描轉(zhuǎn)換，即對(duì)多邊形邊界所經(jīng)過(guò)的邊界標(biāo)志算法:算法過(guò)程voidedgemark_fill(polydef,color)多邊形定義polydef；intcolor;{對(duì)多邊形polydef每條邊進(jìn)行直線掃描轉(zhuǎn)換；inside=FALSE;for(每條與多邊形polydef相交的掃描線y)for(掃描線上每個(gè)象素x){if(象素x被打上邊標(biāo)志)inside=!(inside);if(inside！=FALSE)drawpixel(x,y,color);elsedrawpixel(x,y,background); }}1/4/2023108浙江大學(xué)計(jì)算機(jī)圖形學(xué)邊界標(biāo)志算法:算法過(guò)程voidedgemark_fill(邊界標(biāo)志算法用軟件實(shí)現(xiàn)時(shí)，掃描線算法與邊界標(biāo)志算法的執(zhí)行速度幾乎相同，但由于邊界標(biāo)志算法不必建立維護(hù)邊表以及對(duì)它進(jìn)行排序，所以邊界標(biāo)志算法更適合硬件實(shí)現(xiàn)，這時(shí)它的執(zhí)行速度比有序邊表算法快一至兩個(gè)數(shù)量級(jí)。1/4/2023109浙江大學(xué)計(jì)算機(jī)圖形學(xué)邊界標(biāo)志算法用軟件實(shí)現(xiàn)時(shí)，掃描線算法與邊界標(biāo)志算法的執(zhí)行速度邊界標(biāo)志算法思考：如何處理邊界的交點(diǎn)個(gè)數(shù)使其成為偶數(shù)？1/4/2023110浙江大學(xué)計(jì)算機(jī)圖形學(xué)邊界標(biāo)志算法思考：如何處理邊界的交點(diǎn)個(gè)數(shù)使其成為偶數(shù)？12/區(qū)域填充算法區(qū)域指已經(jīng)表示成點(diǎn)陣形式的填充圖形，它是象素的集合。區(qū)域填充指先將區(qū)域的一點(diǎn)賦予指定的顏色，然后將該顏色擴(kuò)展到整個(gè)區(qū)域的過(guò)程。區(qū)域填充算法要求區(qū)域是連通的1/4/2023111浙江大學(xué)計(jì)算機(jī)圖形學(xué)區(qū)域填充算法區(qū)域指已經(jīng)表示成點(diǎn)陣形式的填充圖形，它是象素的集區(qū)域填充表示方法：內(nèi)點(diǎn)表示、邊界表示內(nèi)點(diǎn)表示枚舉處區(qū)域內(nèi)部的所有像素內(nèi)部的所有像素著同一個(gè)顏色邊界像素著與內(nèi)部像素不同的顏色邊界表示枚舉出邊界上所有的像素邊界上的所有像素著同一顏色內(nèi)部像素著與邊界像素不同的顏色1/4/2023112浙江大學(xué)計(jì)算機(jī)圖形學(xué)區(qū)域填充表示方法：內(nèi)點(diǎn)表示、邊界表示12/26/202250區(qū)域填充區(qū)域填充要求區(qū)域是連通的連通性

4連通、8連通4連通：8連通1/4/2023113浙江大學(xué)計(jì)算機(jī)圖形學(xué)區(qū)域填充區(qū)域填充要求區(qū)域是連通的12/26/202251浙江區(qū)域填充4連通與8連通區(qū)域的區(qū)別連通性：4連通可看作8連通區(qū)域，但對(duì)邊界有要求對(duì)邊界的要求1/4/2023114浙江大學(xué)計(jì)算機(jī)圖形學(xué)區(qū)域填充4連通與8連通區(qū)域的區(qū)別12/26/202252浙江A：適合于內(nèi)點(diǎn)表示區(qū)域的填充算法設(shè)G為一內(nèi)點(diǎn)表