計算機圖形學 第2章 實面積圖形的生成.ppt

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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í)行過程中，AET表中的結(jié)點要不斷地進行插入、排序、刪除。圖2-1-3表示了在算法執(zhí)行過程中掃描線的高度即y值、EOT

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

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

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

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