計(jì)算機(jī)圖形學(xué) 第2章 實(shí)面積圖形的生成.ppt

1、第2章 實(shí)面積圖形的生成,第2章 實(shí)面積圖形的生成,實(shí)面積圖形即封閉圖形(或有界表面)，在其封閉的面積上(輪廓內(nèi))具有相同的亮度或色彩，這意味著要讓計(jì)算機(jī)填充光柵掃描圖形顯示器(點(diǎn)陣圖形顯示器)中封閉面積上的每一個(gè)顯示點(diǎn)(像素點(diǎn))。實(shí)面積圖形既能描述物體的幾何輪廊，還能表現(xiàn)物體的表面色彩，這與人們觀察物體表面的習(xí)慣相一致，易為人們接受。更為重要的是實(shí)面積圖形還是描述三維物體、三維真實(shí)感圖形的顯示基礎(chǔ)，它對(duì)今后學(xué)習(xí)三維圖形學(xué)幫助極大。 根據(jù)表示實(shí)面積圖形的方法不同，實(shí)面積圖形的生成可分為兩大類(lèi)。第一類(lèi)叫多邊形的填充，即實(shí)面積圖形的輪廓用其封閉多邊形的頂點(diǎn)坐標(biāo)數(shù)據(jù)來(lái)描述定義(簡(jiǎn)稱(chēng)實(shí)面積圖形的圖形表

2、示法)，在其封閉的多邊形內(nèi)部填充用戶指定的顏色；第二類(lèi)叫種子填充，即用點(diǎn)陣方式描述定義實(shí)面積圖形，這個(gè)圖形的實(shí)面積由用戶指定的點(diǎn)陣顏色包圍或組成(簡(jiǎn)稱(chēng)實(shí)面積圖形的圖像表示法)，在圖形的實(shí)面積上填充用戶指定的顏色，其中這個(gè)指定的第一個(gè)填充點(diǎn)又稱(chēng)為種子。,21 多邊形的填充,一、多邊形的定義與性質(zhì) 1多邊形 多邊形是一個(gè)由折線段組成的封閉圖形，它由有序頂點(diǎn)的點(diǎn)集Vi(i=1n)及有向邊的線集Ei定義。n為多邊形的頂點(diǎn)數(shù)或邊數(shù)，且Ei=ViVi+1，i=1，2，n。這里Vn+1=V1，用以保證多邊形的封閉性。應(yīng)注意，當(dāng)用多邊形來(lái)表示有界平面或?qū)嵜娣e圖形的邊界時(shí)，規(guī)定多邊形每條有向邊的左側(cè)為實(shí)面積圖形

3、的實(shí)面積區(qū)域(或內(nèi)部區(qū)域)，因此它不允許多邊形的邊線自相交叉(見(jiàn)圖)。,V1,V3,V4,V2,V7,V6,V5,V4,V3,V2,V1,V8,2. 環(huán),因?yàn)槎噙呅蔚挠邢蜻吘€左側(cè)為其實(shí)面積區(qū)域，故沿實(shí)面積圖形外輪廓線多邊形的頂點(diǎn)方向順序環(huán)行時(shí)，要求該多邊形頂點(diǎn)的整個(gè)環(huán)行方向逆時(shí)針旋轉(zhuǎn)；而沿其內(nèi)輪廓線多邊形的頂點(diǎn)方向順序環(huán)行時(shí)，要求該多邊形頂點(diǎn)的整個(gè)環(huán)行方向順時(shí)針旋轉(zhuǎn)。這種定義了環(huán)行方向的多邊形稱(chēng)為環(huán)。前者為外環(huán)、后者為內(nèi)環(huán)(見(jiàn)圖)。 判斷一個(gè)多邊形環(huán)行方向的方法 ： 對(duì)于一個(gè)給定多邊形所對(duì)應(yīng)的n個(gè)頂點(diǎn)，總能找到一個(gè)點(diǎn)Vi，它位于該多邊形的最高處(或最低、最左、最右處等)以及與它相鄰的兩個(gè)點(diǎn)Vi

4、-1與Vi+1，若這三個(gè)點(diǎn)不在一條直線上(否則可合并它們?yōu)橐粭l直線)，那么當(dāng)這三點(diǎn)所形成的向量叉乘Vi-1 ViVi Vi+1的數(shù)值為正，該多邊形逆時(shí)針?lè)较蛐D(zhuǎn)，否則順時(shí)針?lè)较蛐D(zhuǎn)。,多邊形的外環(huán)、內(nèi)環(huán)定義方向示意圖,3帶孔多邊形,由一個(gè)外環(huán)和數(shù)個(gè)內(nèi)環(huán)組成的多邊形稱(chēng)為帶孔多邊形，若多邊形沒(méi)有內(nèi)環(huán)即為不帶孔多邊形。,4凹、凸多邊形的判別方法,定義：Vi-1Vi ViVi+1=ak 其中，a為實(shí)值，向量k與Vi-1Vi，ViVi+1符合右手螺旋法則。 若數(shù)值a0，則Vi點(diǎn)為凹點(diǎn)，否則為凸點(diǎn)。具有凹點(diǎn)的多邊形為凹多邊形，只具有凸點(diǎn)的多邊形為凸多邊形。外環(huán)的凹點(diǎn)對(duì)應(yīng)的內(nèi)角一定大于180，凸點(diǎn)的內(nèi)角小于

5、180。并且任何一個(gè)多邊形，其外形上凸點(diǎn)的個(gè)數(shù)總是多于其凹點(diǎn)的個(gè)數(shù)。,V9,V3,V8,V7,V6,V5,V4,V2,V2,V1,二、多邊形的填充原理,多邊形圖形的填充原理：找出所有位于封閉圖形內(nèi)的像素點(diǎn)，把這些點(diǎn)置換成所要求的像素值。 一般方法：如果在顯示屏中，采用從上到下、從左到右找出每一個(gè)顯示點(diǎn)，然后通過(guò)多邊形的邊界函數(shù)(凸多邊形有邊界函數(shù)且表達(dá)方式簡(jiǎn)單)等方法，判斷其是否位于封閉圖形之內(nèi)后再填充。 評(píng)價(jià)：這種方法原理雖然簡(jiǎn)單，但速度太慢，特別不適合凹多邊形與帶孔多邊形的填充需要。 因此有必要尋找一種通用的(適用于凸、凹、帶孔的多邊形)快速判斷像素點(diǎn)位于封閉圖形之內(nèi)的計(jì)算方法，這是多邊形

6、圖形填充的關(guān)鍵。,利用射線的交點(diǎn)計(jì)數(shù)法判斷像素點(diǎn)位于封閉圖形內(nèi)外的方法,從封閉圖形外找一點(diǎn)，引一水平射線(稱(chēng)為掃描線)與封閉圖形相交。當(dāng)交點(diǎn)計(jì)數(shù)為奇數(shù)時(shí)，掃描線在封閉圖形內(nèi)(射線穿人封閉圖形)；當(dāng)交點(diǎn)計(jì)數(shù)為偶數(shù)時(shí)，掃描線在封閉圖形外，該方法簡(jiǎn)稱(chēng)交點(diǎn)計(jì)數(shù)法則。,缺點(diǎn)：這種計(jì)算交點(diǎn)的方法不能正確處理如y=7時(shí)的情況 。必須提出補(bǔ)充規(guī)則以完善交點(diǎn)計(jì)數(shù)法則 。,改進(jìn)方法(1),1.當(dāng)掃描線與封閉多邊形的水平邊相交時(shí)，不計(jì)算其交點(diǎn)個(gè)數(shù)； 2.當(dāng)掃描線與封閉多邊形的奇異點(diǎn)相交時(shí)，其交點(diǎn)個(gè)數(shù)計(jì)算兩次；而對(duì)于掃描線與多邊形的其余每條斜邊相交，其交點(diǎn)個(gè)數(shù)僅計(jì)算一次。,所謂奇異點(diǎn)即封閉圖形的極值點(diǎn)，圖中共有(7，

7、7)，(7，1)，(2，9)，(13，11)等4個(gè)奇異點(diǎn).,這樣保證了任何一條掃描線與多邊形相交，其交點(diǎn)個(gè)數(shù)總是偶數(shù)。由此能正確地判斷出每一條掃描線中哪一部分位于封閉圖形之內(nèi)，哪一部分位于其外。,改進(jìn)方法(2),由于奇異點(diǎn)的交點(diǎn)個(gè)數(shù)要計(jì)算兩次，這對(duì)于實(shí)際操作來(lái)講還不夠簡(jiǎn)練，因此對(duì)于多邊形填充又提出另一種對(duì)奇異點(diǎn)的簡(jiǎn)單近似的處理方法： 在計(jì)算掃描線與多邊形的每一斜邊的交點(diǎn)之前，將斜邊中最低的端點(diǎn)在y方向上縮短一個(gè)屏坐標(biāo)刻度單位(注意，這將忽略近似水平斜邊)，然后再計(jì)算水平掃描線與多邊形各斜邊的所有交點(diǎn)。經(jīng)過(guò)這樣處理后，對(duì)多邊形的極大值奇異點(diǎn)計(jì)算兩次交點(diǎn)，而忽略了極小值奇異點(diǎn)的存在。,缺點(diǎn)：嚴(yán)重時(shí)

8、，實(shí)面積圖形的下部分缺少一條掃描填充線 。,總評(píng),經(jīng)過(guò)上述約定與處理之后，使得同一掃描線與封閉多邊形的交點(diǎn)總是成對(duì)出現(xiàn)，因此在正確計(jì)算掃描線與封閉多邊形的所有交點(diǎn)之后，圖形的填充就成了畫(huà)直線的過(guò)程。這種逐個(gè)計(jì)算要顯示的各點(diǎn)并顯示的過(guò)程又稱(chēng)掃描轉(zhuǎn)換。根據(jù)組織上述掃描線與封閉多邊形的交點(diǎn)方法不同，其多邊形的填充又有(YX)，Y-X與多邊形優(yōu)先級(jí)等多種算法。,三、多邊形的(YX)填充算法,(YX)填充算法根據(jù)多邊形填充算法的原理，先求出多邊形各斜邊與掃描線的所有交點(diǎn)并記錄；然后按從上到下、從左到右的次序?qū)λ械慕稽c(diǎn)進(jìn)行排序；最后利用這些交點(diǎn)總是成對(duì)出現(xiàn)并從上到下、從左到右排列的規(guī)律畫(huà)直線，畫(huà)完所有的

9、直線即完成填充任務(wù)。,多邊形,交叉點(diǎn)表,(YX)填充算法雖然簡(jiǎn)單，但當(dāng)多邊形的形狀復(fù)雜時(shí)，其交點(diǎn)表的容量非常大，而且對(duì)交點(diǎn)進(jìn)行排序很費(fèi)時(shí)，這極大地影響了該算法的使用效果。,四、多邊形的Y-X填充算法,為了克服（YX）算法兩個(gè)缺點(diǎn)，可對(duì)該算法進(jìn)行如下 改進(jìn)： 改進(jìn)存儲(chǔ)方式。不存儲(chǔ)多邊形上每個(gè)交點(diǎn)的坐標(biāo)，而是存儲(chǔ)其每條斜邊。如果一條斜邊用其2個(gè)頂點(diǎn)坐標(biāo)變量(x1，y1)，(x2，y2)來(lái)代替的話，這將比存儲(chǔ)斜邊上的每個(gè)交點(diǎn)坐標(biāo)所需的存儲(chǔ)容量要少得多； 改進(jìn)交點(diǎn)的計(jì)算方法，并要求斜邊上的每一交點(diǎn)與填充掃描線同步出現(xiàn)，以便畫(huà)線填充多邊形； 因多邊形的斜邊總量遠(yuǎn)比其交點(diǎn)總量小，故對(duì)斜邊的排序相對(duì)較快。

10、基于上述三點(diǎn)要求，可重新安排斜邊上交點(diǎn)的計(jì)算方法。 由于填充過(guò)程是從上到下逐行進(jìn)行，故有: yi+l=yi-1 利用這一遞推關(guān)系可求得斜邊上對(duì)應(yīng)交點(diǎn)的x坐標(biāo)為: xi+1=xi+ x 其中 x=-(x2-x1+ )/(y2-y1) (y1y2即為斜邊),顯然當(dāng)填充掃描線的高度， y=ymax=maxy1,y2時(shí)，開(kāi)始計(jì)算該斜邊上的第一個(gè)交點(diǎn)，此時(shí)該斜邊又稱(chēng)為激活斜邊；當(dāng)填充掃描線的高度y=ymin=miny1,y2時(shí)，停止計(jì)算該斜邊上的最后一個(gè)交點(diǎn)(即忽略斜邊最低的交點(diǎn)坐標(biāo))。,這一遞推計(jì)算交點(diǎn)公式的疊加分量，初始、結(jié)束條件為 :,不難發(fā)現(xiàn)，這4個(gè)遞推參數(shù)(xs,ys， x,ye)既能明確無(wú)誤

11、地表示一條斜邊，又能非常方便地遞推出該斜邊與掃描線的所有交點(diǎn)，因此Y-X填充算法就主要存儲(chǔ)這4個(gè)遞推參數(shù)而不用存儲(chǔ)其每條斜邊的兩個(gè)頂點(diǎn)。,多邊形總的填充過(guò)程是:從上到下、從左到右逐行逐點(diǎn)地填充多邊形內(nèi)的每一個(gè)顯示點(diǎn)。 因此無(wú)論多邊形的各斜邊等參數(shù)如何存儲(chǔ)，最后要求各斜邊上交點(diǎn)出現(xiàn)的次序是：排在上面的交點(diǎn)先出現(xiàn)，排在下面的交點(diǎn)后出現(xiàn)；對(duì)于同一高度的掃描線而言，排在左側(cè)的交點(diǎn)先出現(xiàn)，排在右側(cè)的交點(diǎn)后出現(xiàn)；且最好僅當(dāng)填充哪一掃描行時(shí)，才要求遞推出該行上的所有斜邊上的交點(diǎn)以利于填充。,由于此時(shí)該算法存儲(chǔ)的是每一條斜邊而非交點(diǎn)，故在具體地填充之前，對(duì)這些斜邊應(yīng)按從上到下、從左到右的次序排序。雖然如此，這

12、種排序并不能保證在填充過(guò)程中，其交點(diǎn)出現(xiàn)的次序一定滿足從左到右這一要求。 例如：,引發(fā)的問(wèn)題,填充前，斜邊排序后的結(jié)果為： AB，AC，DE，DF，F(xiàn)E 在填充yi+1行掃描線時(shí)，由于出現(xiàn)了新的斜邊DE，DF，即有4條斜邊被掃描填充，這些斜邊的次序?yàn)椋?AB，DE，DF，AC，F(xiàn)E,結(jié)論：填充前對(duì)斜邊進(jìn)行的排序，只能保證其交點(diǎn)是從上到下的出現(xiàn)次序；而在動(dòng)態(tài)填充過(guò)程中，每當(dāng)出現(xiàn)新的斜邊時(shí)，都要對(duì)斜邊進(jìn)行從左到右的排序，才能保證其交點(diǎn)是從左到右這一出現(xiàn)次序，這樣才能保證多邊形的填充過(guò)程順利進(jìn)行。,實(shí)現(xiàn)算法的數(shù)據(jù)結(jié)構(gòu)-初始邊表(EOT),由于算法需要進(jìn)行上述兩種排序，為了保存這兩種排序結(jié)果，特設(shè)計(jì)了

13、如下相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。 構(gòu)造初始邊表(EOT) 求出多邊形各斜邊的上述4個(gè)遞推參數(shù)，然后對(duì)各斜邊按 ymax 值從上到下排序。對(duì)具有同一高度的各斜邊(見(jiàn)圖2-8)，用一指針的指向表示其從左到右的排序結(jié)果。另外，把所有斜邊的高度 ymax 值集中存放于一個(gè)高度表(術(shù)語(yǔ)為y桶表)中，此刻高度表的索引值為各斜邊的高度，高度表的內(nèi)容為指向各斜邊的指針。為使高度表的操作簡(jiǎn)單，通常令高度表的大小等于顯示器的縱向分辨率，如圖2-9所示。各斜邊從左到右排序的方法是：若兩斜邊的 ys 與 xs 兩參數(shù)分別相同，則把x 值小的斜邊排在前，反之排在后；若兩斜邊的 ys 值相同，則把 xs 值小的斜邊排在前，反之排在后

14、。此時(shí) y 桶表與所鏈接的斜邊結(jié)點(diǎn)并稱(chēng)為多邊形的初始邊表(EOT)。,實(shí)現(xiàn)算法的數(shù)據(jù)結(jié)構(gòu)-活動(dòng)邊表(AET),活動(dòng)邊表(AET) 當(dāng)構(gòu)造完初始邊表(EOT)之后，就可以用遞推的方法，從上到下地計(jì)算出每條掃描線與多邊形各斜邊的交點(diǎn)，這些交點(diǎn)用活動(dòng)邊表(AET)來(lái)保存。活動(dòng)邊表具有與初始邊表相同的結(jié)點(diǎn)結(jié)構(gòu)，并用指針的指向?qū)崿F(xiàn)其斜邊即交點(diǎn)從左到右的排列次序，見(jiàn)圖。應(yīng)注意的是，在活動(dòng)邊表中，僅僅記錄當(dāng)前掃描線與各斜邊交點(diǎn)的x值以及所需的遞推參數(shù)x與ymin，以便填充畫(huà)線并不斷地遞推出下一掃描線與各斜邊的交點(diǎn)。對(duì)于已填充過(guò)的交點(diǎn)，不用保存其x值，該x值不斷被以后新出現(xiàn)的交點(diǎn)值所置換。因該表如此變化，故稱(chēng)

15、其為活動(dòng)邊表(AET)。,在活動(dòng)邊表中： AET表初始指針指示該行掃描線交點(diǎn)的最小x值； x值為當(dāng)前掃描線與斜邊交點(diǎn)的橫坐標(biāo)； ymin ,x遞推參數(shù)意義與上同。,活動(dòng)邊表的主要操作過(guò)程,活動(dòng)邊表的主要操作過(guò)程如下： 令A(yù)ET表為空。 y=TOP(顯示設(shè)備坐標(biāo)最大值)；y=y-1運(yùn)算；直至指向EOT表中第一個(gè)非空單元。 反復(fù)做以下各步，直至y=0。 第一步，將EOT表中的結(jié)點(diǎn)加入AET表中，并按從左到右的次序?qū)ET表中的結(jié)點(diǎn)排序。 第二步，根據(jù)AET表中成對(duì)結(jié)點(diǎn)所形成的區(qū)域，用相應(yīng)像素值填充畫(huà)直線。 第三步， y=y-1運(yùn)算，如果y0，轉(zhuǎn)第四步，否則結(jié)束。 第四步，當(dāng)ymin=y時(shí)，將AET

16、表中相應(yīng)結(jié)點(diǎn)刪除(用簡(jiǎn)單近似方法處理奇異點(diǎn))。 第五步，AET表中保留的結(jié)點(diǎn)執(zhí)行x=x+ x運(yùn)算。 第六步，如果此時(shí)EOT表中項(xiàng)ymax對(duì)應(yīng)值為，則轉(zhuǎn)第二步，否則轉(zhuǎn)第一步。,在Y-X填充算法中，由于它利用了多邊形的邊線相關(guān)特性，即它們?cè)谕桓叨壬?，其邊線的X方向的順序(左右關(guān)系)是很少改變的，因此在AET表的動(dòng)態(tài)變化過(guò)程中，對(duì)其結(jié)點(diǎn)進(jìn)行排序相對(duì)較少。 Y-X填充算法經(jīng)過(guò)上述優(yōu)化處理之后，雖然節(jié)省了存儲(chǔ)空間，減少了排序量，提高了多邊形的填充速度，但卻大大增加了算法過(guò)程本身的難度，這是不盡人意的地方。但該算法仍不失為目前實(shí)面積圖形生成的一們艮重要的算法，它擴(kuò)展至三維圖形的表面模型輸出顯示時(shí)，有很重

17、要的地位。,填充例子,該多邊形的各邊數(shù)據(jù)分別是 E1: (2,6), (ll,1);E2: (11,1), (17,5) ;E3:(17,10), (15,10); E4: (15,10), (10,8);E5: (10,8), (6,16);E6: (6,16), (2,16); E7: (2,16), (2,6);Es: (4,7), (8,8);E9: (8,8), (6,1.2); E10: (6,12),)(4,12);E11: (8,8), (6,12),在本算法的執(zhí)行過(guò)程中，AET表中的結(jié)點(diǎn)要不斷地進(jìn)行插入、排序、刪除。圖2-1-3表示了在算法執(zhí)行過(guò)程中掃描線的高度即y值、EOT

18、表與AET表的動(dòng)態(tài)變化等過(guò)程。,五、多邊形的優(yōu)先級(jí)填充算法,在一個(gè)顯示屏幕上顯示多個(gè)實(shí)面積圖形時(shí)，如果這些實(shí)面積圖形相互重疊，則它們之間會(huì)發(fā)生相互遮擋的情況。為了明確地區(qū)分一個(gè)多邊形遮擋另一個(gè)多邊形，有必要給每一個(gè)多邊形一個(gè)優(yōu)先級(jí)編號(hào)，而且各多邊形的優(yōu)先級(jí)編號(hào)互不相同。 規(guī)定如下：編號(hào)大的多邊形，其優(yōu)先級(jí)低，該多邊形應(yīng)先生成顯示；而編號(hào)小的多邊形，其優(yōu)先級(jí)高，該多邊形應(yīng)后生成顯示。那么在光柵掃描圖形顯示器中，后生成的多邊形自然地就覆蓋了先生成的多邊形。這一處理實(shí)面積圖形之間相互遮擋關(guān)系的過(guò)程與畫(huà)家在畫(huà)布上處理多個(gè)不透明圖畫(huà)的具體過(guò)程非常相似，故用這種方法生成各個(gè)多邊形的算法稱(chēng)為畫(huà)家算法。,顯然

19、在畫(huà)家算法中，需先對(duì)各多邊形的優(yōu)先級(jí)編號(hào)(用戶表示)進(jìn)行從大到小的排序，然后再逐次生成各個(gè)多邊形。此時(shí)當(dāng)每個(gè)多邊形用(YX)算法填充生成時(shí)，該畫(huà)家算法又記為P-(YX)填充算法；當(dāng)每個(gè)多邊形用Y-X算法填充生成時(shí)，該畫(huà)家算法又記為P-(Y-X)填充算法(或記為P-Y-X填充算法)。,畫(huà)家算法的缺點(diǎn)和改進(jìn),畫(huà)家算法原理雖然簡(jiǎn)單，但仍有不足之處。這是因?yàn)樗膱D形輸出直觀效果不明顯，往往是那些重要的多邊形因具有較高的優(yōu)先級(jí)而在最后出現(xiàn)，這會(huì)分散用戶的注意力，使用戶感到非常不方便或產(chǎn)生混亂。如果屏幕中的多個(gè)多邊形是整個(gè)的從上到下平穩(wěn)地進(jìn)行填充生成(如圖所示)，就不會(huì)分散用戶的注意力了。這種情況可以通過(guò)

20、先一次畫(huà)完同一高度的所有多邊形的填充線(按優(yōu)先級(jí)的次序逐一畫(huà)各多邊形的填充線)，再畫(huà)下一高度的所有多邊形的各填充線，直到畫(huà)完所有的多邊形。這樣就不會(huì)像畫(huà)家算法那樣，生成一個(gè)多邊形之后再生成另一個(gè)多邊形，而是緩慢地一次生成用戶希望最終產(chǎn)生的結(jié)果。,1. (YPX)填充算法,1(YPX)填充算法 該算法的主要步驟如下： (1)對(duì)于每個(gè)多邊形，計(jì)算其斜邊與掃描線的全部交點(diǎn)，把(x,y,p)3個(gè)量作為一組數(shù)據(jù)輸入到交點(diǎn)表中(即所有多邊形的全部交點(diǎn)都保存在這個(gè)交點(diǎn)表中)。其中(x，y)為交點(diǎn)坐標(biāo)，p為各多邊形的優(yōu)先級(jí)。 (2)交點(diǎn)表中的交點(diǎn)按x，y，p進(jìn)行分類(lèi)排序。就是說(shuō)，僅當(dāng)(y1y2)或(y1=y2

21、而p1p2)或(y1=y2，p1=p2而x1x2)的交點(diǎn)(x1，y1，p1)才排在交點(diǎn)(x2，y2，p2)之前。-上-下 高-低 左-右 (3)檢索其交點(diǎn)表，對(duì)于一條掃描線，利用每個(gè)多邊形中其交點(diǎn)成對(duì)出現(xiàn)這一規(guī)律，填充每一多邊形的直線段，填充后的交點(diǎn)從交點(diǎn)表中刪除。不斷循環(huán)這一過(guò)程直至處理完所有交點(diǎn)。 (YPX)填充算法的缺點(diǎn)在于交點(diǎn)表很大，這會(huì)使得其分類(lèi)排序非常緩慢，利用Y(PX)填充算法能改善這一點(diǎn)。,2Y-(PX)填充算法,Y-(PX)填充算法與Y-X填充算法非常類(lèi)似，但這兩者主要在分類(lèi)排序方法與結(jié)點(diǎn)結(jié)構(gòu)上有區(qū)別。Y-(PX)填充算法主要按Y，P，X的次序排序，而它的結(jié)點(diǎn)結(jié)構(gòu)如圖216所示。 Y-(PX)填充算法的主要步驟如下： (1)所有多邊形的各斜邊按Y，P，X的次序排序，其排序結(jié)果用一個(gè)初始邊表保存。 (2)活動(dòng)邊表動(dòng)態(tài)記錄與當(dāng)前掃描線相交的所有多邊形各斜邊的當(dāng)前交點(diǎn)。 (3)每當(dāng)活動(dòng)邊表中出現(xiàn)新的斜邊結(jié)點(diǎn)時(shí)，這些斜邊都要進(jìn)行優(yōu)先級(jí)編號(hào)從大到小、斜邊從左到右的排序。 (4)利用活動(dòng)邊表中成對(duì)的交點(diǎn)所形成的區(qū)域畫(huà)填充線，直至結(jié)束。