第7章-可見面的判定

1、XYZx1y1z1z2XpYp窗口坐標(biāo)系屏幕坐標(biāo)系模型坐標(biāo)系世界坐標(biāo)系視口窗口建建 模模顯顯 示示處處 理理幾幾 何何 變變 換換裁裁 剪剪確定可見面確定可見面光光 照照 明明投投 影影v 由于投影變換失去了深度信息，往往導(dǎo)致圖形的二義性。由于投影變換失去了深度信息，往往導(dǎo)致圖形的二義性。要消除二義性，就必須在繪制時消除被遮擋的不可見的線要消除二義性，就必須在繪制時消除被遮擋的不可見的線或面，習(xí)慣上稱作消除隱藏線和隱藏面或面，習(xí)慣上稱作消除隱藏線和隱藏面（或可見線判定、（或可見線判定、可見面判定），可見面判定），或簡稱為或簡稱為消隱。消隱。經(jīng)過消隱得到的投影圖稱經(jīng)過消隱得到的投影圖稱為物體的真

2、實圖形。為物體的真實圖形。v按消隱對象分類按消隱對象分類 (a)線消隱線消隱 消隱對象是物體上的邊，消除的是物體上不可見的邊。消隱對象是物體上的邊，消除的是物體上不可見的邊。 (b)面消隱面消隱 消隱對象是物體上的面，消除的是物體上不可見的面。消隱對象是物體上的面，消除的是物體上不可見的面。1以構(gòu)成圖像的每一個以構(gòu)成圖像的每一個像素像素為處理單元，確定場景中為處理單元，確定場景中的所有在該像素上有投影的所有在該像素上有投影的表面，相對于觀察點可的表面，相對于觀察點可見的表面。適于面消隱。見的表面。適于面消隱。2以三維場景中的以三維場景中的物體對象物體對象為處理單元，在所有對象為處理單元，在所有

3、對象之間進(jìn)行比較，除去完全之間進(jìn)行比較，除去完全不可見的物體和物體上不不可見的物體和物體上不可見的部分可見的部分。 適于面消隱適于面消隱也適于線消隱。也適于線消隱。窗口像素視點圖7.1 以像素為對象的消隱算法xz窗口平行投影y圖7.2 以物體為對象的消隱算法前提：把物體看成是由一個或多個多邊形（或更復(fù)雜的面片）組成前提：把物體看成是由一個或多個多邊形（或更復(fù)雜的面片）組成！假定構(gòu)成物體假定構(gòu)成物體的面不能相互的面不能相互貫穿，也不能貫穿，也不能有循環(huán)遮擋的有循環(huán)遮擋的情況。情況。(a)(b) 貫穿和循環(huán)遮擋貫穿和循環(huán)遮擋如果構(gòu)成物體的面不滿足該假如果構(gòu)成物體的面不滿足該假定，可以把它們定，可以

4、把它們剖分剖分成互不貫成互不貫穿和不循環(huán)遮擋的情況。穿和不循環(huán)遮擋的情況。例如，用上圖中的虛線便可把原來例如，用上圖中的虛線便可把原來循環(huán)遮擋的三個平面，分割成不存循環(huán)遮擋的三個平面，分割成不存在循環(huán)遮擋的四個面。在循環(huán)遮擋的四個面。 提提 醒醒7.1.1347.1.27.1.3后向面消除后向面消除邊界盒邊界盒投影規(guī)范化投影規(guī)范化物體的邊界盒是指能夠包含該物體的一個簡單的幾何形狀，物體的邊界盒是指能夠包含該物體的一個簡單的幾何形狀，如矩形、圓、長方體等。如矩形、圓、長方體等。 邊界盒邊界盒 ：采用邊界盒在消隱中的好處：采用邊界盒在消隱中的好處：可避免不必要的裁剪運算，避免在物體或它們的投影之間

5、進(jìn)可避免不必要的裁剪運算，避免在物體或它們的投影之間進(jìn)行不必要的比較運算。行不必要的比較運算。 xyz圖圖7.4 兩個物兩個物體投影在體投影在xy平面，包圍平面，包圍投影的邊界投影的邊界盒為矩形盒為矩形注意選取適當(dāng)?shù)倪吔绾校鹤⒁膺x取適當(dāng)?shù)倪吔绾校翰豢商?，也不可太大。不可太小，也不可太大。一種簡單的求邊界盒的方法：一種簡單的求邊界盒的方法：計算多邊形頂點坐標(biāo)的最大值和計算多邊形頂點坐標(biāo)的最大值和最小值得到（即采用矩形邊界盒）最小值得到（即采用矩形邊界盒） A邊界盒不相交邊界盒不相交：在在Oxy平面投影的邊界盒，兩個邊界盒不平面投影的邊界盒，兩個邊界盒不 相交，所以兩個多邊形不相交。相交，所以兩

6、個多邊形不相交。 B 邊界盒相交邊界盒相交：相交的情況可分為相交的情況可分為兩種兩種，投影相交或投影，投影相交或投影 不相交。無論哪種情況都需要做進(jìn)一步的不相交。無論哪種情況都需要做進(jìn)一步的 處理，以判斷兩物體的投影是否相交。處理，以判斷兩物體的投影是否相交。 邊界盒應(yīng)用原則邊界盒應(yīng)用原則xyzA 不相交不相交(a)(a)邊界盒和投影均重邊界盒和投影均重疊疊(b)(b)邊界盒重疊，投影不重疊邊界盒重疊，投影不重疊 用邊界盒技術(shù)判斷兩條直線是否相交。用邊界盒技術(shù)判斷兩條直線是否相交。 ),(iiiyxQ舉例：舉例：xminxmaxymaxyminxyQ1Q6Q5Q2Q4Q3記點記點vi在在oxy

7、面上的投影為面上的投影為 。直線段直線段 的邊界盒是包含該直線且的邊界盒是包含該直線且邊平行于坐標(biāo)軸的最小矩形，這個矩邊平行于坐標(biāo)軸的最小矩形，這個矩形由下面四個參數(shù)確定形由下面四個參數(shù)確定 21QQ)max()max()min()min(21max21max21min21min,yyy,xxx,yyy,xxx，設(shè)兩個邊界盒的參數(shù)為設(shè)兩個邊界盒的參數(shù)為: :21,maxmaxminmin, i , y, x, yxiiii當(dāng)它們滿足當(dāng)它們滿足: : )(2max1minxx)(2max1minyy)(1max2minxx)(1max2minyy或或或或或或 表明兩個邊界盒不相交，則邊界盒中的兩

8、條直線段也不相交。表明兩個邊界盒不相交，則邊界盒中的兩條直線段也不相交。v 用球代替長方體作為邊界盒可以簡化判斷直線同邊界盒是用球代替長方體作為邊界盒可以簡化判斷直線同邊界盒是否相交的計算過程，否相交的計算過程，即若邊界球的球心到直線的距離大于即若邊界球的球心到直線的距離大于球的半徑，那么直線與邊界球不相交，球的半徑，那么直線與邊界球不相交，也就與球內(nèi)的物體也就與球內(nèi)的物體不相交。一個有效的確定邊界球的方法是取球的不相交。一個有效的確定邊界球的方法是取球的中心為：中心為：2minmaxxxxc2minmaxyyyc2minmaxzzzc222lllzyxRmaxmin2lxxxmaxmin2l

9、yyymaxmin2lzzz取半徑為：取半徑為：其中：其中：進(jìn)一步簡化判斷進(jìn)一步簡化判斷v 1、后向面后向面v 多面體表面多變形的法向可分為兩種：一種是指向多面體多面體表面多變形的法向可分為兩種：一種是指向多面體的外部的外部外法向，一種指向多面體的內(nèi)部外法向，一種指向多面體的內(nèi)部內(nèi)法向。內(nèi)法向。v 必然有一些多邊形表面的必然有一些多邊形表面的外法向指向與觀察者相背離的方外法向指向與觀察者相背離的方向向，這些多邊形完全被多面體上其它，這些多邊形完全被多面體上其它 多邊形遮擋。這些多邊形遮擋。這些被遮擋的多邊形被遮擋的多邊形 稱為后向面。稱為后向面。v 首先消除掉這些面，去除后向面的過首先消除掉這

10、些面，去除后向面的過 程稱為程稱為后向面消除。后向面消除。 思路：把顯然不可見的面去掉，減少消隱過程中的思路：把顯然不可見的面去掉，減少消隱過程中的直線求交數(shù)目直線求交數(shù)目IJFGH，F(xiàn)ABG，HCDI，IDEJ 所在的面為前向面所在的面為前向面 JEAF，DEABC,HGBC所在的面為后向面所在的面為后向面如何判斷：根據(jù)定義尋找外（或內(nèi)）法向，則外法向背離觀如何判斷：根據(jù)定義尋找外（或內(nèi)）法向，則外法向背離觀 察者，或內(nèi)法向指向觀察者，則該面為后向面。察者，或內(nèi)法向指向觀察者，則該面為后向面。2、判斷后向面的方法、判斷后向面的方法1）首先對多邊形的頂點進(jìn)行排序：）首先對多邊形的頂點進(jìn)行排序：

11、設(shè)多邊形設(shè)多邊形F F的頂點為的頂點為 v1,v2,vL頂點頂點 的坐標(biāo)為的坐標(biāo)為 。次序要求如下排列：使觀察者在多面體外沿。次序要求如下排列：使觀察者在多面體外沿著著v1v2 vL走時，多邊形的內(nèi)部始終在它的右側(cè)。走時，多邊形的內(nèi)部始終在它的右側(cè)。iV),(iiizyx右設(shè)多邊形設(shè)多邊形F F的頂點為的頂點為 v1,v2,vL頂點頂點 的坐標(biāo)為的坐標(biāo)為 。次序如圖。次序如圖iV),(iiizyx2）判斷后向面：判斷后向面：如果如果v1,v2,vL構(gòu)成凸的多邊形，則向量構(gòu)成凸的多邊形，則向量 12 ,111Lkvvvvkka a是是F的的內(nèi)法線方向，內(nèi)法線方向，如果如果 a的的z分量分量0)(

12、za說明說明內(nèi)法向量內(nèi)法向量和和z軸正方向的夾角軸正方向的夾角大于大于9090度，度，F(xiàn)的的外法線方向外法線方向和和z z軸正方向的夾角小于軸正方向的夾角小于9090度，度，F(xiàn)為前向面。為前向面。否則，即否則，即a a的的z z分量大于分量大于0 0 即即 ，則，則F F的的內(nèi)法向內(nèi)法向和和z z軸正方向的夾角大于軸正方向的夾角大于9090度，度，外法線方向外法線方向和和z z軸正方向的夾角小于軸正方向的夾角小于9090度，度，F(xiàn) F為后向面。為后向面。2、判斷后向面的方法、判斷后向面的方法0)(zav1v2v3v4v5v6 ：可以看作是三角形：可以看作是三角形v1vk vk+1在平面在平面o

13、xy上投影的上投影的有向面積的二倍。有向面積的二倍。 )(21sin| |21*21npmqcitaACABACABSz)(a2、判斷后向面的方法、判斷后向面的方法頂點為頂點為A，B，C的三角形面積求解如下，設(shè)：的三角形面積求解如下，設(shè)：),(nmAB ),(qpAC 所以，三角形所以，三角形v1vk vk+1在平面在平面oxy上投影的上投影的有向面積為：有向面積為：1111111()()()()2kkkkxxyyxxyy恰好是恰好是是否可以這樣說，求一個多邊形的內(nèi)法向的是否可以這樣說，求一個多邊形的內(nèi)法向的z z分量等價于求其分量等價于求其任意一個三角形的有向面積？任意一個三角形的有向面積？

14、Zkkkkkkzzyyxxzzyyxxkji11111111z)(a a2、判斷后向面的方法、判斷后向面的方法111121() ()2LkkKzspv vv v 注意：如果多邊形是凸的，則可只取一個三角形計算有向面積注意：如果多邊形是凸的，則可只取一個三角形計算有向面積sp。如。如果多邊形不是凸的，只取一個三角形計算有向面積果多邊形不是凸的，只取一個三角形計算有向面積sp可能會出現(xiàn)錯誤，可能會出現(xiàn)錯誤，即即F所在的面為前向面也可能出現(xiàn)所在的面為前向面也可能出現(xiàn)sp0的情況的情況, ,因此，需按上式計算多因此，需按上式計算多邊形邊形F的有向面積。的有向面積。 v1v2v3v4v5v6v1v2v3

15、v4v5v6如果如果 ，則，則F所在的面為后向面。所在的面為后向面。如果如果 ，則，則F所在的面為前向面。所在的面為前向面。2、判斷后向面的方法、判斷后向面的方法3）可以通過計算可以通過計算多邊形多邊形在在Oxy平面上投影的平面上投影的有向面積有向面積判判斷斷F是否為后向面。是否為后向面。有向面積有向面積sp可如下計算：可如下計算：)()(21 )()(211111211111121yyxxyyxxvvvvspkkLKkkzkLKk0SP0SP 物體之間的遮擋關(guān)系與投影中心和投影方向有著密切的關(guān)系，對物體物體之間的遮擋關(guān)系與投影中心和投影方向有著密切的關(guān)系，對物體的可見性判定也和投影方式有密切

16、的關(guān)系。的可見性判定也和投影方式有密切的關(guān)系。注意：注意：垂直投影的優(yōu)點：進(jìn)行投影時可以忽略垂直投影的優(yōu)點：進(jìn)行投影時可以忽略z值，即實物的值，即實物的（x，y）即可直接做為投影后的二維平面上的坐標(biāo)即可直接做為投影后的二維平面上的坐標(biāo)（x，y）(x,y,z) (x,y)(x,y,z)(x,y) 所以，下面的工作就是將非垂直投影轉(zhuǎn)換成垂直投影。這樣可以降低所以，下面的工作就是將非垂直投影轉(zhuǎn)換成垂直投影。這樣可以降低算法的復(fù)雜性，提高運算速度。算法的復(fù)雜性，提高運算速度。 如何把透視投影變?yōu)榇怪蓖队?，如何把透視投影變?yōu)榇怪蓖队?，其本質(zhì)是把棱臺變成長方體。其本質(zhì)是把棱臺變成長方體。 AB) , (y

17、x),(AzAyAx投影平面投影平面由棱臺到長方體的變換由棱臺到長方體的變換(,)ccccxyzP把左邊的棱臺把左邊的棱臺A變換成右邊長方體變換成右邊長方體B。設(shè)。設(shè) (xA,yA,zA )是棱臺是棱臺A中任意一點，中任意一點，它在投影平面的投影為它在投影平面的投影為 (x,y,0) ，事實上透視投影是把線段，事實上透視投影是把線段 (xA,yA,zA)和和(x,y,0)之間的點都變換成之間的點都變換成 (x,y,0)，如果能把，如果能把 (xA,yA,zA)和和(x,y,0)之間的之間的點指定一個相應(yīng)的點指定一個相應(yīng)的Z值，值，且該值不改變原線段上點之間的前后關(guān)系，且該值不改變原線段上點之間

18、的前后關(guān)系，就可就可把棱臺把棱臺A變?yōu)殚L方體變?yōu)殚L方體B，即將透視投影變換成了正投影。，即將透視投影變換成了正投影。求求A的坐標(biāo)如何的坐標(biāo)如何變換到變換到B的坐標(biāo)，即（的坐標(biāo)，即（xA,yA,zA）到（）到（xB,yB,zB）的變換）的變換), , (Bzyx),(BzByBx同一圖形同一圖形垂直投影不改變垂直投影不改變x，y值值投影面投影面) , (yx如果對如果對z的射影變換是線的射影變換是線性的，則不改變視見體性的，則不改變視見體內(nèi)各表面的前后位置關(guān)內(nèi)各表面的前后位置關(guān)系可以通過不改變視見系可以通過不改變視見體的前后平面體的前后平面 z=zf和和zzb，的前后位置關(guān)系實現(xiàn)，的前后位置關(guān)系

19、實現(xiàn)，把這兩個條件代入左式，把這兩個條件代入左式，得：得： ()()fcffbcbbzzzAzBzzzAzB, cfbfbAzzzBz z投影公式投影公式則只剩下則只剩下zB沒有解，沒有解，則按照類似于則按照類似于xB和和yB的形式來找的形式來找zB與與ZA的關(guān)系的關(guān)系()/()()/()BcAcccABcAcccAxxxxx zzzyyyyy zzz()/()AcAzAzBzza,ba,b是系數(shù)，是我們假定的，是系數(shù)，是我們假定的，則，如何求解？則，如何求解？v 判斷哪個多邊形是可見判斷哪個多邊形是可見 ： 可在兩多邊形共同覆蓋的區(qū)域內(nèi)取一點可在兩多邊形共同覆蓋的區(qū)域內(nèi)取一點（x, y），）

20、，如果投如果投影為影為垂直投影垂直投影, ,把（把（x, y）分別代入兩個多邊形表達(dá)式，得）分別代入兩個多邊形表達(dá)式，得到兩個空間點到兩個空間點P1(x,y,z1)和和P2(x,y,z2)，當(dāng)，當(dāng)z1z2時，時，P1遮擋遮擋P2，當(dāng)，當(dāng)z2z1時，時，P2遮擋遮擋P1； 但但如果不是垂直投影，則需根據(jù)視點或投影方向計算兩個多如果不是垂直投影，則需根據(jù)視點或投影方向計算兩個多邊形在邊形在oxy平面的投影為平面的投影為P1(x1,y1,z1) 和和P2(x2,y2,z2)總結(jié)：總結(jié)： 在非垂直投影下計算在非垂直投影下計算P1和和P2要比在垂直投影下計要比在垂直投影下計算花費的計算量大許多。算花費的

21、計算量大許多。 射影變換之后射影變換之后 7.2.17.2.2基于多邊形的細(xì)分算法基于多邊形的細(xì)分算法基于窗口的細(xì)分算法基于窗口的細(xì)分算法概述概述區(qū)域細(xì)分算法區(qū)域細(xì)分算法是一種是一種分而治之分而治之(Divide-Conquer)的算法，它把投影區(qū)域作為考察對象，如果很容的算法，它把投影區(qū)域作為考察對象，如果很容易確定投影區(qū)域內(nèi)的多邊形是否可見，便顯示這易確定投影區(qū)域內(nèi)的多邊形是否可見，便顯示這些多邊形，否則將這些區(qū)域進(jìn)一步細(xì)分，隨著不些多邊形，否則將這些區(qū)域進(jìn)一步細(xì)分，隨著不斷細(xì)分，判斷多邊形的可見性將越來越簡單。斷細(xì)分，判斷多邊形的可見性將越來越簡單。本節(jié)介紹基于窗口的細(xì)分算法和基于多邊形

22、的細(xì)本節(jié)介紹基于窗口的細(xì)分算法和基于多邊形的細(xì)分算法。分算法?；舅枷牖舅枷胱臃值倪^程子分的過程 把物體投影到全屏幕窗口上，然后遞歸的將窗口把物體投影到全屏幕窗口上，然后遞歸的將窗口一分為一分為四，四，如果可以確定小窗口內(nèi)的多邊形是否可見，則顯示如果可以確定小窗口內(nèi)的多邊形是否可見，則顯示這些多邊形，否則，將小窗口細(xì)分為更小的窗口，遞歸這些多邊形，否則，將小窗口細(xì)分為更小的窗口，遞歸地執(zhí)行上述過程。每一次把矩形的窗口等分成四個相等地執(zhí)行上述過程。每一次把矩形的窗口等分成四個相等的小矩形。的小矩形。注意：分成的小矩形也稱為窗口。注意：分成的小矩形也稱為窗口。 具體分析關(guān)系判斷具體分析關(guān)系判斷

23、細(xì)分后都要對多邊形和窗口就下面四種關(guān)系作判斷：細(xì)分后都要對多邊形和窗口就下面四種關(guān)系作判斷：窗口和多邊形分離窗口和多邊形分離(圖中情況圖中情況1)1多邊形和窗口相交多邊形和窗口相交(圖中情況圖中情況2)2窗口包圍了多邊形窗口包圍了多邊形(圖中情況圖中情況3)3多邊形包圍了窗口多邊形包圍了窗口(圖中情況圖中情況4)41234 多邊形和窗口的關(guān)系多邊形和窗口的關(guān)系具體分析可見性判斷具體分析可見性判斷 對以下的三種情況，窗口中多邊形的可見性容易判定，不需要再對對以下的三種情況，窗口中多邊形的可見性容易判定，不需要再對窗口進(jìn)行分割：窗口進(jìn)行分割： 所有多邊形均和窗口分離，則窗口內(nèi)只需所有多邊形均和窗口

24、分離，則窗口內(nèi)只需顯示背景色；顯示背景色； 1只有一個多邊形和窗口相交，或這個多邊只有一個多邊形和窗口相交，或這個多邊形包含在窗口內(nèi)。這時，先對窗口內(nèi)每一形包含在窗口內(nèi)。這時，先對窗口內(nèi)每一像素填上背景顏色，再對窗口內(nèi)多邊形部像素填上背景顏色，再對窗口內(nèi)多邊形部分用掃描線算法填色。分用掃描線算法填色。 2一個多邊形包圍窗口，其他多邊形和窗口一個多邊形包圍窗口，其他多邊形和窗口分離，或有多個多邊形和窗口的關(guān)系分別分離，或有多個多邊形和窗口的關(guān)系分別是相交、內(nèi)含或包圍，但是有一個多邊形是相交、內(nèi)含或包圍，但是有一個多邊形包圍窗口并且在其他多邊形前面，則窗口包圍窗口并且在其他多邊形前面，則窗口用包圍

25、多邊形的顏色填充。用包圍多邊形的顏色填充。 3橙色橙色紫色紫色具體分析分割結(jié)束條件具體分析分割結(jié)束條件 對不滿足上述三種情況的窗口，重復(fù)細(xì)分過程，并對細(xì)分后對不滿足上述三種情況的窗口，重復(fù)細(xì)分過程，并對細(xì)分后的各子窗口重復(fù)做同樣的處理。細(xì)分若干次后，窗口的面積的各子窗口重復(fù)做同樣的處理。細(xì)分若干次后，窗口的面積就小于或等于一個像素的面積了，此時細(xì)分結(jié)束，該窗口對就小于或等于一個像素的面積了，此時細(xì)分結(jié)束，該窗口對應(yīng)的像素的顏色可取成最靠近觀察者的多邊形的顏色。應(yīng)的像素的顏色可取成最靠近觀察者的多邊形的顏色。 橙色橙色紫色紫色基本思想基本思想 用多邊形的邊界對區(qū)域作劃分，其目的是盡量減少對區(qū)域用

26、多邊形的邊界對區(qū)域作劃分，其目的是盡量減少對區(qū)域劃分的次數(shù)劃分的次數(shù)利用裁剪算法。利用裁剪算法。 該算法是對上節(jié)基于窗口細(xì)分算法的改進(jìn)。由于算法在景該算法是對上節(jié)基于窗口細(xì)分算法的改進(jìn)。由于算法在景物空間中以任意指定的精度進(jìn)行運算，其輸出結(jié)果仍為多物空間中以任意指定的精度進(jìn)行運算，其輸出結(jié)果仍為多邊形，所以算法不僅可用來處理隱藏面消除，也可用來處邊形，所以算法不僅可用來處理隱藏面消除，也可用來處理多面體隱藏線消除問題。理多面體隱藏線消除問題。 算法描述算法描述Step1：Step2：Step3：內(nèi)部表：放入位于窗口內(nèi)的部分內(nèi)部表：放入位于窗口內(nèi)的部分 外部表：放入位于窗口外的部分外部表：放入位

27、于窗口外的部分yx4321要消隱的多邊形要消隱的多邊形xyz43212i3i4i4oni為窗口內(nèi)的多邊形表；為窗口內(nèi)的多邊形表；no為窗口外的多邊形表為窗口外的多邊形表3o算法描述算法描述Step4：即取為窗口的那個多邊形即取為窗口的那個多邊形) ) yx4321要消隱的多邊形要消隱的多邊形xyz4321如何判斷窗口是如何判斷窗口是否遮擋其余的多否遮擋其余的多邊形邊形 求出裁減多邊形也就是內(nèi)部表中第一求出裁減多邊形也就是內(nèi)部表中第一個多邊形，各頂點坐標(biāo)的極小值個多邊形，各頂點坐標(biāo)的極小值Zmin； 求出內(nèi)部多邊形各頂點坐標(biāo)求出內(nèi)部多邊形各頂點坐標(biāo)z的極大值的極大值Zmaxi； 對那些滿足對那些

28、滿足ZminZmaxi的內(nèi)部表中的的內(nèi)部表中的多邊形，便可認(rèn)為它被裁減多邊形所多邊形，便可認(rèn)為它被裁減多邊形所遮擋；遮擋； 若某一內(nèi)部多邊形不滿足上式，則要若某一內(nèi)部多邊形不滿足上式，則要從該兩多邊形相交的區(qū)域上取一點，從該兩多邊形相交的區(qū)域上取一點，做和做和z軸平行的線，求出該線和兩個多軸平行的線，求出該線和兩個多邊形所在平面的交點，根據(jù)交點的位邊形所在平面的交點，根據(jù)交點的位置便可準(zhǔn)確地確定哪一個多邊形更靠置便可準(zhǔn)確地確定哪一個多邊形更靠近觀察者。近觀察者。如何判斷窗口是如何判斷窗口是否遮擋其余的多否遮擋其余的多邊形邊形EAzmaxzminBCDGHFxz算法描述算法描述Step5：如果內(nèi)

29、部表中有某多邊形如果內(nèi)部表中有某多邊形H比裁剪區(qū)域（多邊形）更比裁剪區(qū)域（多邊形）更靠近觀察者，說明原來的預(yù)排序不對，此時要用多邊形靠近觀察者，說明原來的預(yù)排序不對，此時要用多邊形H的原始多邊形（即未被裁剪時的多邊形）代替原來的裁剪的原始多邊形（即未被裁剪時的多邊形）代替原來的裁剪多邊形重復(fù)上述工作。多邊形重復(fù)上述工作。 yx4321要消隱的多邊形要消隱的多邊形xyz4321！如左圖如果對頂點排序如左圖如果對頂點排序的話，則的話，則1 1自然要排最自然要排最前面，首先會用前面，首先會用1 1做裁做裁剪多邊形，但實際情況剪多邊形，但實際情況是是2 2在在1 1的前面，所以應(yīng)的前面，所以應(yīng)該以該以

30、2 2做新的裁剪多邊做新的裁剪多邊形，重復(fù)上述工作形，重復(fù)上述工作算法描述算法描述Step6：內(nèi)部表中多邊形的按前后順序排好序后，接下來是內(nèi)部表中多邊形的按前后順序排好序后，接下來是對外部表對外部表中中的各多邊形進(jìn)行排序。對外部表中各多邊形的排序和對內(nèi)部表中各的各多邊形進(jìn)行排序。對外部表中各多邊形的排序和對內(nèi)部表中各多邊形的處理方法相同，即把外部表中第一個多邊形作為裁剪多邊多邊形的處理方法相同，即把外部表中第一個多邊形作為裁剪多邊形形(假定外部表中的多邊形也是按原來的多邊形次序排序假定外部表中的多邊形也是按原來的多邊形次序排序)，對外部，對外部表中的其它多邊形作裁剪并確定遮擋關(guān)系，這一過程又形

31、成新的外表中的其它多邊形作裁剪并確定遮擋關(guān)系，這一過程又形成新的外部表。裁剪過程要重復(fù)到外部表中不再有多邊形為止。部表。裁剪過程要重復(fù)到外部表中不再有多邊形為止。 yx4321要消隱的多邊形要消隱的多邊形xyz43214o 3o基本思想基本思想將能夠包含整個場景的立方體，即八叉樹的將能夠包含整個場景的立方體，即八叉樹的根結(jié)點根結(jié)點，按照，按照x，y，z三個方向中的剖面分割成八個子立方體，稱為根結(jié)三個方向中的剖面分割成八個子立方體，稱為根結(jié)點的點的八個子結(jié)點八個子結(jié)點。對每一個子立方體，如果它包含的表面。對每一個子立方體，如果它包含的表面片少于一個給定的值（例如片少于一個給定的值（例如3），則該

32、子立方體為八叉樹），則該子立方體為八叉樹的的終端結(jié)點終端結(jié)點，否則為非終端結(jié)點并將其進(jìn)一步分割成八個，否則為非終端結(jié)點并將其進(jìn)一步分割成八個子立方體；重復(fù)上述過程，直到每個小立方體所包含的表子立方體；重復(fù)上述過程，直到每個小立方體所包含的表面片少于一個給定的值，分割即告終止。面片少于一個給定的值，分割即告終止。 具體分析具體分析1）每一終端結(jié)點對應(yīng)一個求交面片表，該表中包含的是與終端結(jié)點對）每一終端結(jié)點對應(yīng)一個求交面片表，該表中包含的是與終端結(jié)點對應(yīng)的立方體中所包含的景物表面片。應(yīng)的立方體中所包含的景物表面片。2）八叉樹由于其不相交立方體之間的規(guī)則結(jié)構(gòu)，可以很方便的進(jìn)行空）八叉樹由于其不相交立

33、方體之間的規(guī)則結(jié)構(gòu)，可以很方便的進(jìn)行空間預(yù)排序，然后再根據(jù)列表優(yōu)先級算法便可以很容易對平行投影給間預(yù)排序，然后再根據(jù)列表優(yōu)先級算法便可以很容易對平行投影給出正確的顯示順序。出正確的顯示順序。122333314455556666777xyzv從后向前顯示的八叉樹排列從后向前顯示的八叉樹排列對從后向前排對從后向前排列算列算 法，先顯示最法，先顯示最遠(yuǎn)的八遠(yuǎn)的八 分體，然后分體，然后是與最是與最 遠(yuǎn)的八分遠(yuǎn)的八分 體體共享一共享一 個面的三個個面的三個相鄰八相鄰八 分體順序任分體順序任意），意）， 然后顯示最然后顯示最近八分近八分 體的三個相體的三個相鄰八分鄰八分 體（順序任體（順序任意），最后顯意

34、），最后顯示最近的八分示最近的八分體體 具體分析具體分析 對于過視點和像素的射線，根據(jù)空間網(wǎng)格之間的鄰接關(guān)系，能很快對于過視點和像素的射線，根據(jù)空間網(wǎng)格之間的鄰接關(guān)系，能很快地求得射線和景物的第一個交點，從而使計算量大大減少，見圖地求得射線和景物的第一個交點，從而使計算量大大減少，見圖7.15。具體地說，射線從起始點開始，跨越一個個它所經(jīng)過的網(wǎng)格。具體地說，射線從起始點開始，跨越一個個它所經(jīng)過的網(wǎng)格單元，直到遇到它與景物有交點的網(wǎng)格單元為止，此后射線無需再單元，直到遇到它與景物有交點的網(wǎng)格單元為止，此后射線無需再繼續(xù)跟蹤下去，從而避免了與后面景物表面的求交計算。繼續(xù)跟蹤下去，從而避免了與后面景

35、物表面的求交計算。對射線與對射線與景物有交點的第一個網(wǎng)格單元，如果射線與景物有多個交點，則需景物有交點的第一個網(wǎng)格單元，如果射線與景物有多個交點，則需選擇離視點最近的交點。選擇離視點最近的交點。 射線沿網(wǎng)格與表面片求交射線空間網(wǎng)格對屏幕上對屏幕上每一個像素點，每一個像素點，過像素中心做一條投影過像素中心做一條投影線，找到此投影線與所有多邊形交點中線，找到此投影線與所有多邊形交點中離觀察者離觀察者最近的點，最近的點，此點的屬性（顏色或灰度）值即為這此點的屬性（顏色或灰度）值即為這一屏幕像素點的屬性值。一屏幕像素點的屬性值。 基本思想：基本思想：Z緩沖器緩沖器v z緩沖器是一組緩沖器是一組存貯單元

36、存貯單元 其單元個數(shù)和屏幕上其單元個數(shù)和屏幕上像素像素的個數(shù)相同的個數(shù)相同 也和也和幀緩沖器幀緩沖器的單元個數(shù)相同，它們之間一一對應(yīng)。的單元個數(shù)相同，它們之間一一對應(yīng)。Z緩緩沖沖區(qū)區(qū)示示意意圖圖 具體實現(xiàn)具體實現(xiàn)需要兩個緩沖器數(shù)組，需要兩個緩沖器數(shù)組，z緩沖器數(shù)組緩沖器數(shù)組用于存儲投影線與所有用于存儲投影線與所有多邊形交點的多邊形交點的z值，值，幀緩沖器數(shù)組幀緩沖器數(shù)組用來存儲像素的顏色值。用來存儲像素的顏色值。分別設(shè)為分別設(shè)為Zdepth 與與Frame 對屏幕上每個點（對屏幕上每個點（x，y），令），令Zdepth xy為為z的極小的極小值，值，F(xiàn)rame xy為背景顏色。為背景顏色。 對

37、所有多邊形做如下工作：對多邊形上在像素中心有投對所有多邊形做如下工作：對多邊形上在像素中心有投影的每一點（影的每一點（x,y）計算其）計算其z值。若值。若zZdepth xy，則，則Zdepth xyz，并將此點屬性值賦給，并將此點屬性值賦給Framexy，否，否則說明此點離觀察者較遠(yuǎn)，兩個數(shù)組的值都不用改變。則說明此點離觀察者較遠(yuǎn)，兩個數(shù)組的值都不用改變。 12具體實現(xiàn)具體實現(xiàn)只有只有z坐標(biāo)值坐標(biāo)值大于大于z z緩沖器緩沖器時才改變時才改變幀緩幀緩沖器沖器的那一個單元的值，同時的那一個單元的值，同時z緩沖器中緩沖器中相應(yīng)單元的值也要改成這點的相應(yīng)單元的值也要改成這點的z坐標(biāo)值。坐標(biāo)值。如果這

38、點的如果這點的z坐標(biāo)值小于坐標(biāo)值小于z緩沖器緩沖器中相應(yīng)單元的值，則說中相應(yīng)單元的值，則說明對應(yīng)象素已顯示了物體上一個點的屬性，該點比要考慮明對應(yīng)象素已顯示了物體上一個點的屬性，該點比要考慮的點更接近觀察者。這樣，無論幀緩沖器或的點更接近觀察者。這樣，無論幀緩沖器或z z緩沖器相應(yīng)緩沖器相應(yīng)單元的值均不應(yīng)改變。單元的值均不應(yīng)改變。l 對顯示物體的對顯示物體的每一個面上每一個面上的的每一個點每一個點都做上述處理后，都做上述處理后，便可得到消除了隱藏面的圖。便可得到消除了隱藏面的圖。 Zdepth xyz1 Frame xygreenZdepth xyz2 Frame xyblue掃描線掃描線z緩

39、沖器算法緩沖器算法 將將z緩沖器的單元數(shù)置為和一條掃描線上的像素數(shù)目相同。緩沖器的單元數(shù)置為和一條掃描線上的像素數(shù)目相同。從最上面的一條掃描線開始工作，向下從最上面的一條掃描線開始工作，向下對每一條掃描線對每一條掃描線作作如下處理：如下處理： 把相應(yīng)的幀緩沖器單元置成底色，把相應(yīng)的幀緩沖器單元置成底色，z緩沖器中存放緩沖器中存放z的極小值。的極小值。 對每個多邊形檢查它在平面上的投影和當(dāng)前的掃描線是否相對每個多邊形檢查它在平面上的投影和當(dāng)前的掃描線是否相交。然后計算各重疊面片的深度值以確定離觀察者最近的面交。然后計算各重疊面片的深度值以確定離觀察者最近的面片。當(dāng)某像素點所對應(yīng)的可見面被確定后，

40、該點的顏色值置入片。當(dāng)某像素點所對應(yīng)的可見面被確定后，該點的顏色值置入幀緩沖器。幀緩沖器。 step1step2 掃描線算法也屬于圖像空間消隱算法。該算法可以看作是多邊形區(qū)域填掃描線算法也屬于圖像空間消隱算法。該算法可以看作是多邊形區(qū)域填充里介紹過的充里介紹過的邊相關(guān)掃描線填充算法邊相關(guān)掃描線填充算法的延伸。不同的是在的延伸。不同的是在消隱算法中處消隱算法中處理的是多個面片，理的是多個面片，而多邊形填充中是對單個多邊形面進(jìn)行填充。而多邊形填充中是對單個多邊形面進(jìn)行填充。 掃描線掃描線z緩沖器算法緩沖器算法 v 對每個多邊形，檢查它在對每個多邊形，檢查它在oxy平面上的平面上的投影和當(dāng)前掃描線投

41、影和當(dāng)前掃描線是否相交？是否相交？ 若不相交，則不考慮該多邊形。若不相交，則不考慮該多邊形。 如果相交，則掃描線和多邊形邊界的如果相交，則掃描線和多邊形邊界的交點是成對地交點是成對地出現(xiàn)出現(xiàn)v 對對每對交點中間的像素每對交點中間的像素計算多邊形所在平面對應(yīng)點的深度（計算多邊形所在平面對應(yīng)點的深度（即即z值值），并），并和和z緩沖器緩沖器中相應(yīng)單元存放的深度值中相應(yīng)單元存放的深度值進(jìn)行比較進(jìn)行比較。 若前者大于后者，則若前者大于后者，則z緩沖器的相應(yīng)單元內(nèi)容要被求得的平面深度代緩沖器的相應(yīng)單元內(nèi)容要被求得的平面深度代替，幀緩沖器相應(yīng)單元的內(nèi)容也要換成該平面的屬性。替，幀緩沖器相應(yīng)單元的內(nèi)容也要換

42、成該平面的屬性。v 對所有的多邊形都作上述處理后，幀緩沖器中這一行的值便反應(yīng)了消隱對所有的多邊形都作上述處理后，幀緩沖器中這一行的值便反應(yīng)了消隱后的圖形。后的圖形。v 對幀緩沖器每一行的單元都填上相應(yīng)內(nèi)容后就得到了整個消隱后的圖。對幀緩沖器每一行的單元都填上相應(yīng)內(nèi)容后就得到了整個消隱后的圖。step2相交的判斷相交的判斷數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 與多邊形掃描轉(zhuǎn)換中掃描線算法數(shù)據(jù)結(jié)構(gòu)和算法類似。與多邊形掃描轉(zhuǎn)換中掃描線算法數(shù)據(jù)結(jié)構(gòu)和算法類似。 多邊形多邊形Y表表1/7107282 1 2 邊邊表（表（ET）step2 多邊形所在平面方程多邊形所在平面方程ax+by+cz+d=0系數(shù)系數(shù)a，b，c和和d，

43、 記錄和該多邊形在記錄和該多邊形在oxy平面上的投影相交的掃描線的條數(shù)平面上的投影相交的掃描線的條數(shù)y， 多邊形的屬性多邊形的屬性color和編號和編號IP。9-1=89-1=811-3=811-3=836 7 81110118713要消隱的物體要消隱的物體xyostep2實際上是一個實際上是一個指針數(shù)組指針數(shù)組 ，每個表的深度和顯示屏幕每個表的深度和顯示屏幕行數(shù)相同。行數(shù)相同。將所有多邊形存在多邊形將所有多邊形存在多邊形Y表中，根據(jù)表中，根據(jù)多邊形頂點多邊形頂點中中Y坐標(biāo)最大值，坐標(biāo)最大值，插入多邊形插入多邊形Y表中的相應(yīng)位置，多表中的相應(yīng)位置，多邊形邊形Y表中保存多邊形的序號和其頂點的最大

44、表中保存多邊形的序號和其頂點的最大y坐坐標(biāo)。標(biāo)。step2v 根據(jù)邊兩端點較大的根據(jù)邊兩端點較大的y坐標(biāo)值決定放入邊表的哪一行。坐標(biāo)值決定放入邊表的哪一行。邊的上端點邊的上端點x坐標(biāo)的值坐標(biāo)的值；該投影和相鄰的兩條掃描線交點的該投影和相鄰的兩條掃描線交點的x坐標(biāo)的差坐標(biāo)的差x；和該邊在和該邊在oxy平面上的投影相交的掃描線條數(shù)平面上的投影相交的掃描線條數(shù)y；該邊所屬多邊形的編號該邊所屬多邊形的編號IPIP。367811101198713圖圖7.16 7.16 要消隱的物體要消隱的物體xo1/7107282 12step2相交的判斷相交的判斷數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 活化多邊形表活化多邊形表1,; 3,

45、 0, 7; 3, 1, 4111IPzzzyxxyxxyxlrrrlll2,; 5,71,7210; 5,65,656222IPzzzyxxyxxyxlrrrlll活化邊對表活化邊對表step2v 記錄在記錄在oxy平面上的投影和當(dāng)前考慮的掃描線相交的多邊形，如：平面上的投影和當(dāng)前考慮的掃描線相交的多邊形，如：當(dāng)掃描線對應(yīng)當(dāng)掃描線對應(yīng)y=10或或11時，活化多邊形表只有一個多邊形。當(dāng)時，活化多邊形表只有一個多邊形。當(dāng)y=8時活化多邊形表如圖。表中的時活化多邊形表如圖。表中的y值值( (掃描線的條數(shù)）掃描線的條數(shù)）是已經(jīng)過修改是已經(jīng)過修改的。的。（由上到下掃描，故（由上到下掃描，故y=5 和和

46、y=7）367811101198713 圖圖 7.16 7.16 要消隱的物體要消隱的物體xo8-3=58-3=58-1=78-1=7step2v活化邊對表中存放多邊形邊和掃描線相交的邊對?；罨厡Ρ碇写娣哦噙呅芜吅蛼呙杈€相交的邊對。 例如圖中例如圖中y=6的掃描線上的活化邊對表中有兩個邊對的掃描線上的活化邊對表中有兩個邊對 一是和多邊形一是和多邊形在在oxy平面上的投影相交的兩條邊平面上的投影相交的兩條邊 另一是和多邊形另一是和多邊形投影相交的兩條邊。投影相交的兩條邊。367811101198713 圖圖7.16 7.16 要消隱的物體要消隱的物體xo1,; 3, 0, 7; 3, 1, 4

47、111IPzzzyxxyxxyxlrrrlll2,; 5,71,7210; 5,65,656222IPzzzyxxyxxyxlrrrlllstep2xl左交點的左交點的x坐標(biāo)值坐標(biāo)值xl左交點所在邊和兩相鄰掃描線交點的左交點所在邊和兩相鄰掃描線交點的x坐標(biāo)之差坐標(biāo)之差yl以和左交點所在邊相交的掃描線條數(shù)為初值，以以和左交點所在邊相交的掃描線條數(shù)為初值，以后每處理一條掃描線減后每處理一條掃描線減1xr右交點的右交點的x坐標(biāo)值坐標(biāo)值xr右交點所在邊和兩相鄰掃描線交點的右交點所在邊和兩相鄰掃描線交點的x坐標(biāo)之差坐標(biāo)之差 以和右交點所在邊相交的掃描線條數(shù)為以和右交點所在邊相交的掃描線條數(shù)為初值，以后每

48、處理一條掃描線減初值，以后每處理一條掃描線減1yr1,; 3, 0, 7; 3, 1, 4111IPzzzyxxyxxyxlrrrlllstep2zl左交點處多邊形所在平面的深度值左交點處多邊形所在平面的深度值zx沿掃描線向右走過一個象素時，多邊形所在平面深度的增沿掃描線向右走過一個象素時，多邊形所在平面深度的增量。對方程為量。對方程為ax+by+cz+d=0的平面來說的平面來說zx=a/c（c0）zy沿沿y y方向向下移過一根掃描線時，多邊形所在平面深度的增量。方向向下移過一根掃描線時，多邊形所在平面深度的增量。對方程為對方程為ax+by+cz+d=0的平面來說的平面來說zy=b/c（c0）

49、IP所在多邊形的編號所在多邊形的編號1,; 3, 0, 7; 3, 1, 4111IPzzzyxxyxxyxlrrrlll2,; 5,71,7210; 5,65,656222IPzzzyxxyxxyxlrrrlll邊對邊對邊對邊對step2若已知多邊形的方程，則可用增量法計算掃描線每一個像素的深度。設(shè)平若已知多邊形的方程，則可用增量法計算掃描線每一個像素的深度。設(shè)平面方程為：面方程為： ax+by+cz+d=0則多邊形面上的點（則多邊形面上的點（x，y）所對應(yīng)的深度值為：）所對應(yīng)的深度值為：zl左交點處多邊形所在平面的深度值左交點處多邊形所在平面的深度值zx沿掃描線向右走過一個象素時，多邊形所

50、在平面深度的增沿掃描線向右走過一個象素時，多邊形所在平面深度的增量。對方程為量。對方程為ax+by+cz+d=0的平面來說的平面來說zx=a/c（c0）zy沿沿y y方向向下移過一根掃描線時，多邊形所在平面深度的增量。方向向下移過一根掃描線時，多邊形所在平面深度的增量。對方程為對方程為ax+by+cz+d=0的平面來說的平面來說zy=b/c（c0）step2zx沿掃描線向右走過一個像素時，多邊形所在平面深度的增沿掃描線向右走過一個像素時，多邊形所在平面深度的增量。對方程為量。對方程為ax+by+cz+d=0的平面來說的平面來說zx=a/c（c0）zy沿沿y y方向向下移過一根掃描線時，多邊形所

51、在平面深度的增量。方向向下移過一根掃描線時，多邊形所在平面深度的增量。對方程為對方程為ax+by+cz+d=0的平面來說的平面來說zy=b/c（c0）由于所有掃描線上相鄰點間的水平間距為由于所有掃描線上相鄰點間的水平間距為1個像素單位，掃描線行與行之間的個像素單位，掃描線行與行之間的垂直間距也為垂直間距也為1。因此可以利用這種連貫性來簡化計算過程，如圖所示。因此可以利用這種連貫性來簡化計算過程，如圖所示。step2若已計算出（若已計算出（x，y）點的深度值為）點的深度值為zi，沿，沿x方向相鄰連貫點方向相鄰連貫點（x+1，y）的深度值）的深度值zi+1可由下式計算：可由下式計算： 沿著沿著y方

52、向的計算應(yīng)先計算出方向的計算應(yīng)先計算出y坐標(biāo)的范圍，然后從上至下逐個處坐標(biāo)的范圍，然后從上至下逐個處理各個面片。由最上方的頂掃描線出發(fā)，沿多邊形左邊界遞歸計理各個面片。由最上方的頂掃描線出發(fā)，沿多邊形左邊界遞歸計算邊界上各點的坐標(biāo)：算邊界上各點的坐標(biāo)： 公式（公式（1 1）step2這里這里m為該邊的斜率，沿該邊的深度也可以遞歸計算出來，即：為該邊的斜率，沿該邊的深度也可以遞歸計算出來，即： 如果該邊是一條垂直邊界，則計算公式簡化為：如果該邊是一條垂直邊界，則計算公式簡化為： 公式（公式（2 2）對于每條掃描線，首先根據(jù)公式（對于每條掃描線，首先根據(jù)公式（2）計算出與其相交的多邊）計算出與其相

53、交的多邊形最左邊的交點所對應(yīng)的深度值，然后，該掃描線上所有的后形最左邊的交點所對應(yīng)的深度值，然后，該掃描線上所有的后續(xù)點由（續(xù)點由（1）式計算出來。）式計算出來。 v 對每一條掃描線，對每一條掃描線，檢查對每個多邊形檢查對每個多邊形的投影是否相交，如相交則交點成對的投影是否相交，如相交則交點成對出現(xiàn)，對出現(xiàn)，對每對交點中間的每個像素每對交點中間的每個像素計計算算多邊形所在平面對應(yīng)點的多邊形所在平面對應(yīng)點的深度深度（即（即z值），并值），并和和z緩沖器緩沖器中相應(yīng)單元存放的中相應(yīng)單元存放的深度值作比較深度值作比較，若前者大于后者，則，若前者大于后者，則z緩沖器的相應(yīng)單元內(nèi)容要被求得的平緩沖器的相

54、應(yīng)單元內(nèi)容要被求得的平面深度代替，幀緩沖器相應(yīng)單元的內(nèi)面深度代替，幀緩沖器相應(yīng)單元的內(nèi)容也要換成該平面的屬性。容也要換成該平面的屬性。 對所有的多邊形都作上述處理后，幀緩沖器中這一行對所有的多邊形都作上述處理后，幀緩沖器中這一行的值便反應(yīng)了消隱后的圖形，對幀緩沖器每一行的單的值便反應(yīng)了消隱后的圖形，對幀緩沖器每一行的單元都填上相應(yīng)內(nèi)容后也就得到了整個消隱后的圖。元都填上相應(yīng)內(nèi)容后也就得到了整個消隱后的圖。367811101198713xo多邊形多邊形y表表1/7107 28 2 1 2邊表邊表1) 建立多邊形建立多邊形y表和邊表，初始化表和邊表，初始化活化多邊形和活化邊對表為空活化多邊形和活化

55、邊對表為空2)2)以最上面的掃描線為當(dāng)前掃描線。以最上面的掃描線為當(dāng)前掃描線。3)3)對當(dāng)前掃描線對當(dāng)前掃描線y y，把幀緩沖器相應(yīng)，把幀緩沖器相應(yīng)行置成底色行置成底色z z緩沖器的各單元放緩沖器的各單元放z z的極小值。的極小值。算法步驟：算法步驟：多邊形多邊形Y Y表表 4)4) 檢查檢查多邊形多邊形y表，表，如果有新的多邊形涉及當(dāng)前掃描線，如果有新的多邊形涉及當(dāng)前掃描線，則把它放入則把它放入活化多邊形表中?；罨噙呅伪碇小?18 896 68 88 要消隱的物體要消隱的物體107 若有新的多邊形加入活化多邊形表，則要把該多邊形在若有新的多邊形加入活化多邊形表，則要把該多邊形在Oxy平面上

56、的投影和掃描線相交的平面上的投影和掃描線相交的邊對加入活化邊對表邊對加入活化邊對表。多邊形Y表1/7107 28 2 1 2邊表661,; 3, 0, 7; 3, 1, 4111IPzzzyxxyxxyxlrrrlll2,; 5,71,7210; 5,65,656222IPzzzyxxyxxyxlrrrlll5）對邊活化表中的對邊活化表中的每個邊對，每個邊對，令令 ，對每一個滿足，對每一個滿足 的坐標(biāo)為的坐標(biāo)為 的像素從的像素從左到右左到右依次進(jìn)行處依次進(jìn)行處理，求深度值理，求深度值z并與并與z緩沖器的值比較。緩沖器的值比較。zx=zx+zx6）若所有掃描線都已經(jīng)處理完，則算法結(jié)束，若所有掃描

57、線都已經(jīng)處理完，則算法結(jié)束，否則選下一否則選下一條掃描線為當(dāng)前掃描線，條掃描線為當(dāng)前掃描線，轉(zhuǎn)步驟轉(zhuǎn)步驟3），直到所有的掃描），直到所有的掃描線都處理完。線都處理完。lxzz rlxxx),(yx從上到下，從左到右從上到下，從左到右每條掃描線處理完后，處理下一條掃描線之前，需要每條掃描線處理完后，處理下一條掃描線之前，需要進(jìn)行以下處理：進(jìn)行以下處理：v 1）修改邊活化表，對每一邊對要做如下計算）修改邊活化表，對每一邊對要做如下計算 1,1llrry yy y lyrylyryrxlxlz若若或或小于小于0，則相應(yīng)的邊要從該邊對中去掉，并從，則相應(yīng)的邊要從該邊對中去掉，并從都不小于都不小于0，則修改，則修改邊表邊表中找合適的邊來代替。若這兩條邊同時結(jié)束于某一點，中找合適的邊來代替。若這兩條邊同時結(jié)束于某一點，則去掉這一邊對。若則去掉這一邊對。若公式（公式（2）,rrrlllxxx xxx又由于又由于ylxllz xz z z修改后的表便是新掃描線的