第7章-可見面的判定

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

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

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

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

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

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

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

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

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

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

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

的z分量說明內(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、判斷后向面的方法頂點為A，B，C的三角形面積求解如下，設(shè)：所以，三角形v1vk

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ax+by+cz+d=0

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

如果該邊是一條垂直邊界，則計算公式簡化為：

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

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

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