第7章-可見(jiàn)面的判定

第七章可見(jiàn)面的判定XYZx1y1z1z2XpYp窗口坐標(biāo)系屏幕坐標(biāo)系模型坐標(biāo)系世界坐標(biāo)系視口窗口建模顯示處理幾何變換裁剪確定可見(jiàn)面光照明投影概述由于投影變換失去了深度信息，往往導(dǎo)致圖形的二義性。要消除二義性，就必須在繪制時(shí)消除被遮擋的不可見(jiàn)的線或面，習(xí)慣上稱作消除隱藏線和隱藏面（或可見(jiàn)線判定、可見(jiàn)面判定），或簡(jiǎn)稱為消隱。經(jīng)過(guò)消隱得到的投影圖稱為物體的真實(shí)圖形。概述消隱的分類(lèi)按消隱對(duì)象分類(lèi)(a)線消隱消隱對(duì)象是物體上的邊，消除的是物體上不可見(jiàn)的邊。(b)面消隱消隱對(duì)象是物體上的面，消除的是物體上不可見(jiàn)的面。1以構(gòu)成圖像的每一個(gè)像素為處理單元，確定場(chǎng)景中的所有在該像素上有投影的表面，相對(duì)于觀察點(diǎn)可見(jiàn)的表面。適于面消隱。2以三維場(chǎng)景中的物體對(duì)象為處理單元，在所有對(duì)象之間進(jìn)行比較，除去完全不可見(jiàn)的物體和物體上不可見(jiàn)的部分。

適于面消隱也適于線消隱。窗口像素視點(diǎn)圖7.1以像素為對(duì)象的消隱算法xz窗口平行投影y圖7.2以物體為對(duì)象的消隱算法前提：把物體看成是由一個(gè)或多個(gè)多邊形（或更復(fù)雜的面片）組成消除隱藏線和隱藏面的兩種算法！假定構(gòu)成物體的面不能相互貫穿，也不能有循環(huán)遮擋的情況。(a)(b)貫穿和循環(huán)遮擋如果構(gòu)成物體的面不滿足該假定，可以把它們剖分成互不貫穿和不循環(huán)遮擋的情況。例如，用上圖中的虛線便可把原來(lái)循環(huán)遮擋的三個(gè)平面，分割成不存在循環(huán)遮擋的四個(gè)面。

提醒7.1.1347.1可見(jiàn)面判斷的有效技術(shù)7.1.27.1.3后向面消除邊界盒投影規(guī)范化物體的邊界盒是指能夠包含該物體的一個(gè)簡(jiǎn)單的幾何形狀，如矩形、圓、長(zhǎng)方體等。7.1.1邊界盒邊界盒：采用邊界盒在消隱中的好處：可避免不必要的裁剪運(yùn)算，避免在物體或它們的投影之間進(jìn)行不必要的比較運(yùn)算。xyz圖7.4

兩個(gè)物體投影在xy平面，包圍投影的邊界盒為矩形注意選取適當(dāng)?shù)倪吔绾校翰豢商?，也不可太大。一種簡(jiǎn)單的求邊界盒的方法：計(jì)算多邊形頂點(diǎn)坐標(biāo)的最大值和最小值得到（即采用矩形邊界盒）

A邊界盒不相交：在Oxy平面投影的邊界盒，兩個(gè)邊界盒不相交，所以兩個(gè)多邊形不相交。

B邊界盒相交：相交的情況可分為兩種，投影相交或投影不相交。無(wú)論哪種情況都需要做進(jìn)一步的處理，以判斷兩物體的投影是否相交。7.1.1邊界盒邊界盒應(yīng)用原則xyzA不相交(a)邊界盒和投影均重疊(b)邊界盒重疊，投影不重疊

用邊界盒技術(shù)判斷兩條直線是否相交。7.1.1邊界盒舉例：xminxmaxymaxyminxyQ1Q6Q5Q2Q4Q3記點(diǎn)vi在oxy面上的投影為。直線段的邊界盒是包含該直線且邊平行于坐標(biāo)軸的最小矩形，這個(gè)矩形由下面四個(gè)參數(shù)確定

設(shè)兩個(gè)邊界盒的參數(shù)為:當(dāng)它們滿足:或或或

表明兩個(gè)邊界盒不相交，則邊界盒中的兩條直線段也不相交。用球代替長(zhǎng)方體作為邊界盒可以簡(jiǎn)化判斷直線同邊界盒是否相交的計(jì)算過(guò)程，即若邊界球的球心到直線的距離大于球的半徑，那么直線與邊界球不相交，也就與球內(nèi)的物體不相交。一個(gè)有效的確定邊界球的方法是取球的中心為：取半徑為：其中：7.1.1邊界盒進(jìn)一步簡(jiǎn)化判斷1、后向面多面體表面多變形的法向可分為兩種：一種是指向多面體的外部——外法向，一種指向多面體的內(nèi)部——內(nèi)法向。必然有一些多邊形表面的外法向指向與觀察者相背離的方向，這些多邊形完全被多面體上其它多邊形遮擋。這些被遮擋的多邊形稱為后向面。首先消除掉這些面，去除后向面的過(guò)程稱為后向面消除。

7.1.2后向面消除思路：把顯然不可見(jiàn)的面去掉，減少消隱過(guò)程中的直線求交數(shù)目IJFGH，F(xiàn)ABG，HCDI，IDEJ所在的面為前向面JEAF，DEABC,HGBC所在的面為后向面如何判斷：根據(jù)定義尋找外（或內(nèi)）法向，則外法向背離觀察者，或內(nèi)法向指向觀察者，則該面為后向面。2、判斷后向面的方法7.1.2后向面消除1）首先對(duì)多邊形的頂點(diǎn)進(jìn)行排序：設(shè)多邊形F的頂點(diǎn)為v1,v2,…,vL頂點(diǎn)的坐標(biāo)為。次序要求如下排列：使觀察者在多面體外沿著v1－>v2－>…－>vL走時(shí)，多邊形的內(nèi)部始終在它的右側(cè)。右設(shè)多邊形F的頂點(diǎn)為v1,v2,…,vL頂點(diǎn)的坐標(biāo)為。次序如圖2）判斷后向面：如果v1,v2,…,vL構(gòu)成凸的多邊形，則向量

是F的內(nèi)法線方向，如果

的z分量說(shuō)明內(nèi)法向量和z軸正方向的夾角大于90度，F(xiàn)的外法線方向和z軸正方向的夾角小于90度，F(xiàn)為前向面。否則，即a的z分量大于0

即，則F的內(nèi)法向和z軸正方向的夾角大于90度，外法線方向和z軸正方向的夾角小于90度，F(xiàn)為后向面。2、判斷后向面的方法7.1.2后向面消除v1v2v3v4v5v6：可以看作是三角形v1vk

vk+1在平面oxy上投影的有向面積的二倍。7.1.2后向面消除2、判斷后向面的方法頂點(diǎn)為A，B，C的三角形面積求解如下，設(shè)：所以，三角形v1vk

vk+1在平面oxy上投影的有向面積為：恰好是是否可以這樣說(shuō)，求一個(gè)多邊形的內(nèi)法向的z分量等價(jià)于求其任意一個(gè)三角形的有向面積？7.1.2后向面消除2、判斷后向面的方法注意：如果多邊形是凸的，則可只取一個(gè)三角形計(jì)算有向面積sp。如果多邊形不是凸的，只取一個(gè)三角形計(jì)算有向面積sp可能會(huì)出現(xiàn)錯(cuò)誤，即F所在的面為前向面也可能出現(xiàn)sp≥0的情況,因此，需按上式計(jì)算多邊形F的有向面積。v1v2v3v4v5v6v1v2v3v4v5v6如果

，則F所在的面為后向面。如果

，則F所在的面為前向面。7.1.2后向面消除2、判斷后向面的方法3）可以通過(guò)計(jì)算多邊形在Oxy平面上投影的有向面積判斷F是否為后向面。有向面積sp可如下計(jì)算：7.1.2投影規(guī)范化物體之間的遮擋關(guān)系與投影中心和投影方向有著密切的關(guān)系，對(duì)物體的可見(jiàn)性判定也和投影方式有密切的關(guān)系。注意：垂直投影的優(yōu)點(diǎn)：進(jìn)行投影時(shí)可以忽略z值，即實(shí)物的（x，y）即可直接做為投影后的二維平面上的坐標(biāo)（x，y）(x,y,z)(x,y)(x,y,z)(x’,y’)所以，下面的工作就是將非垂直投影轉(zhuǎn)換成垂直投影。這樣可以降低算法的復(fù)雜性，提高運(yùn)算速度。7.1.2投影規(guī)范化如何把透視投影變?yōu)榇怪蓖队?，其本質(zhì)是把棱臺(tái)變成長(zhǎng)方體。

AB投影平面由棱臺(tái)到長(zhǎng)方體的變換把左邊的棱臺(tái)A變換成右邊長(zhǎng)方體B。設(shè)(xA,yA,zA

)是棱臺(tái)A中任意一點(diǎn)，它在投影平面的投影為(x’,y’,0)，事實(shí)上透視投影是把線段(xA,yA,zA)和(x’,y’,0)之間的點(diǎn)都變換成(x’,y’,0)，如果能把(xA,yA,zA)和(x’,y’,0)之間的點(diǎn)指定一個(gè)相應(yīng)的Z值，且該值不改變?cè)€段上點(diǎn)之間的前后關(guān)系，就可把棱臺(tái)A變?yōu)殚L(zhǎng)方體B，即將透視投影變換成了正投影。求A的坐標(biāo)如何變換到B的坐標(biāo)，即（xA,yA,zA）到（xB,yB,zB）的變換同一圖形垂直投影不改變x，y值投影面7.1.2投影規(guī)范化如果對(duì)z的射影變換是線性的，則不改變視見(jiàn)體內(nèi)各表面的前后位置關(guān)系可以通過(guò)不改變視見(jiàn)體的前后平面z=zf和z＝zb，的前后位置關(guān)系實(shí)現(xiàn)，把這兩個(gè)條件代入左式，得：投影公式則只剩下zB沒(méi)有解，則按照類(lèi)似于xB和yB的形式來(lái)找zB與ZA的關(guān)系a,b是系數(shù)，是我們假定的，則，如何求解？？判斷哪個(gè)多邊形是可見(jiàn)：可在兩多邊形共同覆蓋的區(qū)域內(nèi)取一點(diǎn)（x,y），如果投影為垂直投影,把（x,y）分別代入兩個(gè)多邊形表達(dá)式，得到兩個(gè)空間點(diǎn)P1(x,y,z1)和P2(x,y,z2)，當(dāng)z1>z2時(shí)，P1遮擋P2，當(dāng)z2>z1時(shí)，P2遮擋P1；但如果不是垂直投影，則需根據(jù)視點(diǎn)或投影方向計(jì)算兩個(gè)多邊形在oxy平面的投影為P1(x1,y1,z1)和P2(x2,y2,z2)總結(jié)：在非垂直投影下計(jì)算P1和P2要比在垂直投影下計(jì)算花費(fèi)的計(jì)算量大許多。

7.1.3非垂直投影轉(zhuǎn)換成垂直投影射影變換之后－－

7.2.17.2區(qū)域細(xì)分算法7.2.2基于多邊形的細(xì)分算法基于窗口的細(xì)分算法7.2區(qū)域細(xì)分算法概述區(qū)域細(xì)分算法是一種分而治之(Divide-Conquer)的算法，它把投影區(qū)域作為考察對(duì)象，如果很容易確定投影區(qū)域內(nèi)的多邊形是否可見(jiàn)，便顯示這些多邊形，否則將這些區(qū)域進(jìn)一步細(xì)分，隨著不斷細(xì)分，判斷多邊形的可見(jiàn)性將越來(lái)越簡(jiǎn)單。本節(jié)介紹基于窗口的細(xì)分算法和基于多邊形的細(xì)分算法。7.2.1基于窗口的細(xì)分算法基本思想子分的過(guò)程把物體投影到全屏幕窗口上，然后遞歸的將窗口一分為四，如果可以確定小窗口內(nèi)的多邊形是否可見(jiàn)，則顯示這些多邊形，否則，將小窗口細(xì)分為更小的窗口，遞歸地執(zhí)行上述過(guò)程。每一次把矩形的窗口等分成四個(gè)相等的小矩形。注意：分成的小矩形也稱為窗口。7.3基于窗口的子分算法具體分析－關(guān)系判斷細(xì)分后都要對(duì)多邊形和窗口就下面四種關(guān)系作判斷：窗口和多邊形分離(圖中情況1)1多邊形和窗口相交(圖中情況2)2窗口包圍了多邊形(圖中情況3)3多邊形包圍了窗口(圖中情況4)41234多邊形和窗口的關(guān)系7.2.1基于窗口的細(xì)分算法具體分析－可見(jiàn)性判斷對(duì)以下的三種情況，窗口中多邊形的可見(jiàn)性容易判定，不需要再對(duì)窗口進(jìn)行分割：所有多邊形均和窗口分離，則窗口內(nèi)只需顯示背景色；

1只有一個(gè)多邊形和窗口相交，或這個(gè)多邊形包含在窗口內(nèi)。這時(shí)，先對(duì)窗口內(nèi)每一像素填上背景顏色，再對(duì)窗口內(nèi)多邊形部分用掃描線算法填色。2一個(gè)多邊形包圍窗口，其他多邊形和窗口分離，或有多個(gè)多邊形和窗口的關(guān)系分別是相交、內(nèi)含或包圍，但是有一個(gè)多邊形包圍窗口并且在其他多邊形前面，則窗口用包圍多邊形的顏色填充。3橙色紫色7.2.1基于窗口的細(xì)分算法具體分析－分割結(jié)束條件對(duì)不滿足上述三種情況的窗口，重復(fù)細(xì)分過(guò)程，并對(duì)細(xì)分后的各子窗口重復(fù)做同樣的處理。細(xì)分若干次后，窗口的面積就小于或等于一個(gè)像素的面積了，此時(shí)細(xì)分結(jié)束，該窗口對(duì)應(yīng)的像素的顏色可取成最靠近觀察者的多邊形的顏色。橙色紫色7.2.2基于多邊形的細(xì)分算法基本思想用多邊形的邊界對(duì)區(qū)域作劃分，其目的是盡量減少對(duì)區(qū)域劃分的次數(shù)－－利用裁剪算法。該算法是對(duì)上節(jié)基于窗口細(xì)分算法的改進(jìn)。由于算法在景物空間中以任意指定的精度進(jìn)行運(yùn)算，其輸出結(jié)果仍為多邊形，所以算法不僅可用來(lái)處理隱藏面消除，也可用來(lái)處理多面體隱藏線消除問(wèn)題。算法描述Step1：對(duì)各多邊形在深度方向作初步的排序：按多邊形頂點(diǎn)z坐標(biāo)值的最大值z(mì)maxi做預(yù)排序，zmaxi大的排在前面。Step2：把多邊形序列中的第一個(gè)多邊形（裁剪多邊形）取為窗口。多邊形序列中的其它的多邊形都要被此窗口裁剪。Step3：裁剪結(jié)果要建立兩個(gè)多邊形序列表－內(nèi)部表：放入位于窗口內(nèi)的部分－外部表：放入位于窗口外的部分yx4321要消隱的多邊形xyz43212i3i4i4oni為窗口內(nèi)的多邊形表；no為窗口外的多邊形表3o7.2.2基于多邊形的細(xì)分算法算法描述Step4：將內(nèi)部表中每一個(gè)其它多邊形的深度值與裁剪多邊形(即取為窗口的那個(gè)多邊形)的深度值進(jìn)行比較，如果內(nèi)部表中每一個(gè)其它多邊形均被裁剪多邊形遮擋，則裁剪多邊形是完全可見(jiàn)的，可把該多邊形區(qū)域填上裁剪多邊形的顏色。

yx4321要消隱的多邊形xyz4321如何判斷窗口是否遮擋其余的多邊形7.2.2基于多邊形的細(xì)分算法求出裁減多邊形也就是內(nèi)部表中第一個(gè)多邊形，各頂點(diǎn)坐標(biāo)的極小值Zmin；求出內(nèi)部多邊形各頂點(diǎn)坐標(biāo)z的極大值Zmaxi；對(duì)那些滿足Zmin>Zmaxi的內(nèi)部表中的多邊形，便可認(rèn)為它被裁減多邊形所遮擋；若某一內(nèi)部多邊形不滿足上式，則要從該兩多邊形相交的區(qū)域上取一點(diǎn)，做和z軸平行的線，求出該線和兩個(gè)多邊形所在平面的交點(diǎn)，根據(jù)交點(diǎn)的位置便可準(zhǔn)確地確定哪一個(gè)多邊形更靠近觀察者。7.2.2基于多邊形的細(xì)分算法如何判斷窗口是否遮擋其余的多邊形EAzmaxzminBCDGHFxz算法描述Step5：如果內(nèi)部表中有某多邊形H比裁剪區(qū)域（多邊形）更靠近觀察者，說(shuō)明原來(lái)的預(yù)排序不對(duì)，此時(shí)要用多邊形H的原始多邊形（即未被裁剪時(shí)的多邊形）代替原來(lái)的裁剪多邊形重復(fù)上述工作。

yx4321要消隱的多邊形xyz4321！如左圖如果對(duì)頂點(diǎn)排序的話，則1自然要排最前面，首先會(huì)用1做裁剪多邊形，但實(shí)際情況是2在1的前面，所以應(yīng)該以2做新的裁剪多邊形，重復(fù)上述工作7.2.2基于多邊形的細(xì)分算法算法描述Step6：內(nèi)部表中多邊形的按前后順序排好序后，接下來(lái)是對(duì)外部表中的各多邊形進(jìn)行排序。對(duì)外部表中各多邊形的排序和對(duì)內(nèi)部表中各多邊形的處理方法相同，即把外部表中第一個(gè)多邊形作為裁剪多邊形(假定外部表中的多邊形也是按原來(lái)的多邊形次序排序)，對(duì)外部表中的其它多邊形作裁剪并確定遮擋關(guān)系，這一過(guò)程又形成新的外部表。裁剪過(guò)程要重復(fù)到外部表中不再有多邊形為止。yx4321要消隱的多邊形xyz43214o3o7.2.2基于多邊形的細(xì)分算法7.3八叉樹(shù)算法基本思想將能夠包含整個(gè)場(chǎng)景的立方體，即八叉樹(shù)的根結(jié)點(diǎn)，按照x，y，z三個(gè)方向中的剖面分割成八個(gè)子立方體，稱為根結(jié)點(diǎn)的八個(gè)子結(jié)點(diǎn)。對(duì)每一個(gè)子立方體，如果它包含的表面片少于一個(gè)給定的值（例如3），則該子立方體為八叉樹(shù)的終端結(jié)點(diǎn)，否則為非終端結(jié)點(diǎn)并將其進(jìn)一步分割成八個(gè)子立方體；重復(fù)上述過(guò)程，直到每個(gè)小立方體所包含的表面片少于一個(gè)給定的值，分割即告終止。

7.3八叉樹(shù)算法具體分析1）每一終端結(jié)點(diǎn)對(duì)應(yīng)一個(gè)求交面片表，該表中包含的是與終端結(jié)點(diǎn)對(duì)應(yīng)的立方體中所包含的景物表面片。2）八叉樹(shù)由于其不相交立方體之間的規(guī)則結(jié)構(gòu)，可以很方便的進(jìn)行空間預(yù)排序，然后再根據(jù)列表優(yōu)先級(jí)算法便可以很容易對(duì)平行投影給出正確的顯示順序。122333314455556666777xyzv從后向前顯示的八叉樹(shù)排列對(duì)從后向前排列算法，先顯示最遠(yuǎn)的八分體，然后是與最遠(yuǎn)的八分體共享一個(gè)面的三個(gè)相鄰八分體順序任意），然后顯示最近八分體的三個(gè)相鄰八分體（順序任意），最后顯示最近的八分體7.3八叉樹(shù)算法具體分析

對(duì)于過(guò)視點(diǎn)和像素的射線，根據(jù)空間網(wǎng)格之間的鄰接關(guān)系，能很快地求得射線和景物的第一個(gè)交點(diǎn)，從而使計(jì)算量大大減少，見(jiàn)圖7.15。具體地說(shuō)，射線從起始點(diǎn)開(kāi)始，跨越一個(gè)個(gè)它所經(jīng)過(guò)的網(wǎng)格單元，直到遇到它與景物有交點(diǎn)的網(wǎng)格單元為止，此后射線無(wú)需再繼續(xù)跟蹤下去，從而避免了與后面景物表面的求交計(jì)算。對(duì)射線與景物有交點(diǎn)的第一個(gè)網(wǎng)格單元，如果射線與景物有多個(gè)交點(diǎn)，則需選擇離視點(diǎn)最近的交點(diǎn)。

射線沿網(wǎng)格與表面片求交射線空間網(wǎng)格7.4z緩沖器算法和掃描線算法對(duì)屏幕上每一個(gè)像素點(diǎn)，過(guò)像素中心做一條投影線，找到此投影線與所有多邊形交點(diǎn)中離觀察者最近的點(diǎn)，此點(diǎn)的屬性（顏色或灰度）值即為這一屏幕像素點(diǎn)的屬性值?；舅枷耄?.4z緩沖器算法和掃描線算法Z緩沖器z緩沖器是一組存貯單元其單元個(gè)數(shù)和屏幕上像素的個(gè)數(shù)相同也和幀緩沖器的單元個(gè)數(shù)相同，它們之間一一對(duì)應(yīng)。Z緩沖區(qū)示意圖7.4z緩沖器算法和掃描線算法具體實(shí)現(xiàn)需要兩個(gè)緩沖器數(shù)組，z緩沖器數(shù)組用于存儲(chǔ)投影線與所有多邊形交點(diǎn)的z值，幀緩沖器數(shù)組用來(lái)存儲(chǔ)像素的顏色值。分別設(shè)為Zdepth[][]與Frame[][]

對(duì)屏幕上每個(gè)點(diǎn)（x，y），令Zdepth[x][y]為z的極小值，F(xiàn)rame[x][y]為背景顏色。對(duì)所有多邊形做如下工作：對(duì)多邊形上在像素中心有投影的每一點(diǎn)（x,y）計(jì)算其z值。若z>Zdepth[x][y]，則Zdepth[x][y]＝z，并將此點(diǎn)屬性值賦給Frame[x][y]，否則說(shuō)明此點(diǎn)離觀察者較遠(yuǎn)，兩個(gè)數(shù)組的值都不用改變。127.4z緩沖器算法和掃描線算法具體實(shí)現(xiàn)只有z坐標(biāo)值大于z緩沖器時(shí)才改變幀緩沖器的那一個(gè)單元的值，同時(shí)z緩沖器中相應(yīng)單元的值也要改成這點(diǎn)的z坐標(biāo)值。如果這點(diǎn)的z坐標(biāo)值小于z緩沖器中相應(yīng)單元的值，則說(shuō)明對(duì)應(yīng)象素已顯示了物體上一個(gè)點(diǎn)的屬性，該點(diǎn)比要考慮的點(diǎn)更接近觀察者。這樣，無(wú)論幀緩沖器或z緩沖器相應(yīng)單元的值均不應(yīng)改變。對(duì)顯示物體的每一個(gè)面上的每一個(gè)點(diǎn)都做上述處理后，便可得到消除了隱藏面的圖。

Zdepth[x][y]＝z1Frame[x][y]＝greenZdepth[x][y]＝z2Frame[x][y]＝blue7.4z緩沖器算法和掃描線算法掃描線z緩沖器算法

將z緩沖器的單元數(shù)置為和一條掃描線上的像素?cái)?shù)目相同。從最上面的一條掃描線開(kāi)始工作，向下對(duì)每一條掃描線作如下處理：把相應(yīng)的幀緩沖器單元置成底色，z緩沖器中存放z的極小值。對(duì)每個(gè)多邊形檢查它在平面上的投影和當(dāng)前的掃描線是否相交。然后計(jì)算各重疊面片的深度值以確定離觀察者最近的面片。當(dāng)某像素點(diǎn)所對(duì)應(yīng)的可見(jiàn)面被確定后，該點(diǎn)的顏色值置入幀緩沖器。step1step2掃描線算法也屬于圖像空間消隱算法。該算法可以看作是多邊形區(qū)域填充里介紹過(guò)的邊相關(guān)掃描線填充算法的延伸。不同的是在消隱算法中處理的是多個(gè)面片，而多邊形填充中是對(duì)單個(gè)多邊形面進(jìn)行填充。7.4z緩沖器算法和掃描線算法掃描線z緩沖器算法

對(duì)每個(gè)多邊形，檢查它在oxy平面上的投影和當(dāng)前掃描線是否相交？若不相交，則不考慮該多邊形。如果相交，則掃描線和多邊形邊界的交點(diǎn)是成對(duì)地出現(xiàn)對(duì)每對(duì)交點(diǎn)中間的像素計(jì)算多邊形所在平面對(duì)應(yīng)點(diǎn)的深度（即z值），并和z緩沖器中相應(yīng)單元存放的深度值進(jìn)行比較。若前者大于后者，則z緩沖器的相應(yīng)單元內(nèi)容要被求得的平面深度代替，幀緩沖器相應(yīng)單元的內(nèi)容也要換成該平面的屬性。對(duì)所有的多邊形都作上述處理后，幀緩沖器中這一行的值便反應(yīng)了消隱后的圖形。對(duì)幀緩沖器每一行的單元都填上相應(yīng)內(nèi)容后就得到了整個(gè)消隱后的圖。7.4z緩沖器算法和掃描線算法step2相交的判斷－數(shù)據(jù)結(jié)構(gòu)

與多邊形掃描轉(zhuǎn)換中掃描線算法數(shù)據(jù)結(jié)構(gòu)和算法類(lèi)似。多邊形Y表1/710728212邊表（ET）7.4z緩沖器算法和掃描線算法step2數(shù)據(jù)結(jié)構(gòu)的具體實(shí)現(xiàn)——建立一個(gè)多邊形Y表多邊形所在平面方程ax+by+cz+d=0系數(shù)a，b，c和d，記錄和該多邊形在oxy平面上的投影相交的掃描線的條數(shù)Δy，多邊形的屬性color和編號(hào)IP。9-1=811-3=836781110118713ⅠⅡ要消隱的物體xyo7.4z緩沖器算法和掃描線算法step2數(shù)據(jù)結(jié)構(gòu)的具體實(shí)現(xiàn)——建立一個(gè)多邊形Y表實(shí)際上是一個(gè)指針數(shù)組，每個(gè)表的深度和顯示屏幕行數(shù)相同。將所有多邊形存在多邊形Y表中，根據(jù)多邊形頂點(diǎn)中Y坐標(biāo)最大值，插入多邊形Y表中的相應(yīng)位置，多邊形Y表中保存多邊形的序號(hào)和其頂點(diǎn)的最大y坐標(biāo)。7.4z緩沖器算法和掃描線算法step2數(shù)據(jù)結(jié)構(gòu)的具體實(shí)現(xiàn)——建立一個(gè)邊表根據(jù)邊兩端點(diǎn)較大的y坐標(biāo)值決定放入邊表的哪一行。邊的上端點(diǎn)x坐標(biāo)的值；該投影和相鄰的兩條掃描線交點(diǎn)的x坐標(biāo)的差Δx；和該邊在oxy平面上的投影相交的掃描線條數(shù)Δy；該邊所屬多邊形的編號(hào)IP。367811101198713ⅠⅡ圖7.16要消隱的物體xo1/7107282127.4z緩沖器算法和掃描線算法step2相交的判斷－數(shù)據(jù)結(jié)構(gòu)活化多邊形表活化邊對(duì)表7.4z緩沖器算法和掃描線算法step2數(shù)據(jù)結(jié)構(gòu)的具體實(shí)現(xiàn)——建立一個(gè)活化多邊形表記錄在oxy平面上的投影和當(dāng)前考慮的掃描線相交的多邊形，如：當(dāng)掃描線對(duì)應(yīng)y=10或11時(shí)，活化多邊形表只有一個(gè)多邊形。當(dāng)y=8時(shí)活化多邊形表如圖。表中的Δy值(掃描線的條數(shù)）是已經(jīng)過(guò)修改的。（由上到下掃描，故△y=5和△y=7）367811101198713ⅠⅡ

圖7.16要消隱的物體xo8-3=58-1=77.4z緩沖器算法和掃描線算法step2數(shù)據(jù)結(jié)構(gòu)的具體實(shí)現(xiàn)——建立一個(gè)活化邊對(duì)表活化邊對(duì)表中存放多邊形邊和掃描線相交的邊對(duì)。例如圖中y=6的掃描線上的活化邊對(duì)表中有兩個(gè)邊對(duì)一是和多邊形Ⅰ在oxy平面上的投影相交的兩條邊另一是和多邊形Ⅱ投影相交的兩條邊。367811101198713ⅠⅡ圖7.16要消隱的物體xo7.4z緩沖器算法和掃描線算法step2xl左交點(diǎn)的x坐標(biāo)值Δxl左交點(diǎn)所在邊和兩相鄰掃描線交點(diǎn)的x坐標(biāo)之差Δyl以和左交點(diǎn)所在邊相交的掃描線條數(shù)為初值，以后每處理一條掃描線減1xr右交點(diǎn)的x坐標(biāo)值Δxr右交點(diǎn)所在邊和兩相鄰掃描線交點(diǎn)的x坐標(biāo)之差以和右交點(diǎn)所在邊相交的掃描線條數(shù)為初值，以后每處理一條掃描線減1Δyr數(shù)據(jù)結(jié)構(gòu)的具體實(shí)現(xiàn)——建立一個(gè)活化邊對(duì)表7.4z緩沖器算法和掃描線算法step2zl左交點(diǎn)處多邊形所在平面的深度值Δzx沿掃描線向右走過(guò)一個(gè)象素時(shí)，多邊形所在平面深度的增量。對(duì)方程為ax+by+cz+d=0的平面來(lái)說(shuō)Δzx=–a/c（c≠0）Δzy沿y方向向下移過(guò)一根掃描線時(shí)，多邊形所在平面深度的增量。對(duì)方程為ax+by+cz+d=0的平面來(lái)說(shuō)Δzy=b/c（c≠0）IP所在多邊形的編號(hào)邊對(duì)邊對(duì)數(shù)據(jù)結(jié)構(gòu)的具體實(shí)現(xiàn)——建立一個(gè)活化邊對(duì)表7.4z緩沖器算法和掃描線算法step2若已知多邊形的方程，則可用增量法計(jì)算掃描線每一個(gè)像素的深度。設(shè)平面方程為：

ax+by+cz+d=0

則多邊形面上的點(diǎn)（x，y）所對(duì)應(yīng)的深度值為：zl左交點(diǎn)處多邊形所在平面的深度值Δzx沿掃描線向右走過(guò)一個(gè)象素時(shí)，多邊形所在平面深度的增量。對(duì)方程為ax+by+cz+d=0的平面來(lái)說(shuō)Δzx=–a/c（c≠0）Δzy沿y方向向下移過(guò)一根掃描線時(shí)，多邊形所在平面深度的增量。對(duì)方程為ax+by+cz+d=0的平面來(lái)說(shuō)Δzy=b/c（c≠0）數(shù)據(jù)結(jié)構(gòu)的具體實(shí)現(xiàn)——建立一個(gè)活化邊對(duì)表7.4z緩沖器算法和掃描線算法step2Δzx沿掃描線向右走過(guò)一個(gè)像素時(shí)，多邊形所在平面深度的增量。對(duì)方程為ax+by+cz+d=0的平面來(lái)說(shuō)Δzx=–a/c（c≠0）Δzy沿y方向向下移過(guò)一根掃描線時(shí)，多邊形所在平面深度的增量。對(duì)方程為ax+by+cz+d=0的平面來(lái)說(shuō)Δzy=b/c（c≠0）由于所有掃描線上相鄰點(diǎn)間的水平間距為1個(gè)像素單位，掃描線行與行之間的垂直間距也為1。因此可以利用這種連貫性來(lái)簡(jiǎn)化計(jì)算過(guò)程，如圖所示。數(shù)據(jù)結(jié)構(gòu)的具體實(shí)現(xiàn)——建立一個(gè)活化邊對(duì)表7.4z緩沖器算法和掃描線算法step2若已計(jì)算出（x，y）點(diǎn)的深度值為zi，沿x方向相鄰連貫點(diǎn)（x+1，y）的深度值z(mì)i+1可由下式計(jì)算：沿著y方向的計(jì)算應(yīng)先計(jì)算出y坐標(biāo)的范圍，然后從上至下逐個(gè)處理各個(gè)面片。由最上方的頂掃描線出發(fā)，沿多邊形左邊界遞歸計(jì)算邊界上各點(diǎn)的坐標(biāo)：公式（1）數(shù)據(jù)結(jié)構(gòu)的具體實(shí)現(xiàn)——建立一個(gè)活化邊對(duì)表7.4z緩沖器算法和掃描線算法step2這里m為該邊的斜率，沿該邊的深度也可以遞歸計(jì)算出來(lái)，即：

如果該邊是一條垂直邊界，則計(jì)算公式簡(jiǎn)化為：

公式（2）對(duì)于每條掃描線，首先根據(jù)公式（2）計(jì)算出與其相交的多邊形最左邊的交點(diǎn)所對(duì)應(yīng)的深度值，然后，該掃描線上所有的后續(xù)點(diǎn)由（1）式計(jì)算出來(lái)。數(shù)據(jù)結(jié)構(gòu)的具體實(shí)現(xiàn)——建立一個(gè)活化邊對(duì)表7.4z緩沖器算法和掃描線算法重溫算法目標(biāo)對(duì)每一條掃描線，檢查對(duì)每個(gè)多邊形的投影是否相交，如相交則交點(diǎn)成對(duì)出現(xiàn)，對(duì)每對(duì)交點(diǎn)中間的每個(gè)像素計(jì)算多邊形所在平面對(duì)應(yīng)點(diǎn)的深度（即z值），并和z緩沖器中相應(yīng)單元存放的深度值作比較，若前者大于后者，則z緩沖器的相應(yīng)單元內(nèi)容要被求得的平面深度代替，幀緩沖器相應(yīng)單元的內(nèi)容也要換成該平面的屬性。對(duì)所有的多邊形都作上述處理后，幀緩沖器中這一行的值便反應(yīng)了消隱后的圖形，對(duì)幀緩沖器每一行的單元都填上相應(yīng)內(nèi)容后也就得到了整個(gè)消隱后的圖。367811101198713ⅠⅡxo多邊形y表1/710728212邊表1)建立多邊形y表和邊表，初始化活化多邊形和活化邊對(duì)表為空2)以最上面的掃描線為當(dāng)前掃描線。3)對(duì)當(dāng)前掃描線y，把幀緩沖器相應(yīng)行置成底色z緩沖器的各單元放z的極小值。算法步驟：多邊形Y表

4)檢查多邊形y表，如果有新的多邊形涉及當(dāng)前掃描線，則把它放入活化多邊形表中。1189688

要消隱的物體107若有新的多邊形加入活化多邊形表，則要把該多邊形在Oxy平面上的投影和掃描線相交的邊對(duì)加入活化邊對(duì)表。多邊形Y表1/710728212邊表665）對(duì)邊活化表中的每個(gè)邊對(duì)，令，對(duì)每一個(gè)滿足的坐標(biāo)為的像素從左到右依次進(jìn)行處理，求深度值z(mì)并與z緩沖器的值比較。zx=zx+△zx6）若所有掃描線都已經(jīng)處理完，則算法結(jié)束，否則選下一條掃描線為當(dāng)前掃描線，轉(zhuǎn)步驟3），直到所有的掃描線都處理完。從上到下，從左到右每條掃描線處理完后，處理下一條掃描線之前，需要進(jìn)行以下處理：1）修改邊活化表，對(duì)每一邊對(duì)要做如下計(jì)算若或小于0，則相應(yīng)的邊要從該邊對(duì)中去掉，并從都不小于0，則修改邊表中找合適的邊來(lái)代替。若這兩條邊同時(shí)結(jié)束于某一點(diǎn)，則去掉這一邊對(duì)。若公式（2）又由于修改后的表便是新掃描線的活化邊對(duì)表。2）修改活化多邊形表。若，則將該多邊形從活化多邊形表中刪除。7.5深度排序算法基本思想