消除隱藏線和隱藏面的算法

消除隱藏線和隱藏面的算法第一頁，共六十二頁，2022年，8月28日圖象空間算法對顯示設備上每一個可分辨象素進行判斷，看組成物體的多個多邊形表面中哪一個在該象素上可見，即要對每一象素檢查所有的表面。客體空間算法把注意力集中在分析要顯示形體各部分之間的關系上，這種算法對每一個組成形體的表面，都要與其它各表面進行比較，以便消去不可見的面或面的不可見部分。第二頁，共六十二頁，2022年，8月28日第一節(jié)線面比較法消除隱藏線

多面體的面可見性

對象：凸多面體可見面：朝向觀察位置的面觀察方向：由指向觀察位置的一個方向向量k給出，面的外法向量是n，則這兩個向量的夾角滿足0

/2時，所考查面是可見的，否則就是不可見的第三頁，共六十二頁，2022年，8月28日把n和k記作則面為可見面不可見面退化為線。第四頁，共六十二頁，2022年，8月28日第五頁，共六十二頁，2022年，8月28日

設空間有一個四面體，頂點A，B，C，D的坐標依次是（0，0，0），（2，0，1），（4，0,0）,(3,2,1)從z軸正向無窮遠處觀察,求各面的可見性

觀察方向向量是k=(0,0,1),第六頁，共六十二頁，2022年，8月28日因此,，面DAB為可見面.類似計算可知，面DBC是可見面,面ADC是不可見面,面ACB退化為線。三角面DAB的法向量是:第七頁，共六十二頁，2022年，8月28日單個凸多面體－－可見面上的線是可見線，多個凸多面體或非凸多面體－－用上面的方法預處理，剩下可能可見面可能可見的棱線:在可見面上或與可見面有邊界

線面比較法：(觀察位置位于Z軸負方向無窮遠處）0：預處理，用外法線法判斷出所有可能可見面思想：求出所有可能可見面，可能可見面上的線段是可能可見線。每一條可能可見線和每一個可能可見面比較，第八頁，共六十二頁，2022年，8月28日1.范圍檢查（xv,yv方向）①求出線段的投影xmin1,xmax1,ymin1,ymax1②求出多邊形表面的投影范圍（zv平面上包含多邊形投影的最小矩形）xmin2,xmax2,ymin2,ymax2

第九頁，共六十二頁，2022年，8月28日③比較投影范圍：在xv方向:若xmax1<=xmin2或xmax2<=xmin1,則無遮擋關系Yv方向：若ymax1<=ymin2或ymax2<=ymin1,則無遮擋關系第十頁，共六十二頁，2022年，8月28日2.zv方向粗略的深度檢查。若線段投影的最大z坐標小于多邊形表面投影范圍最小的z坐標，則線段完全在表面前面，根不發(fā)生遮擋現(xiàn)象，可以不必再往下做精確的深度檢驗。3.精確的深度檢驗

第十一頁，共六十二頁，2022年，8月28日若，則線段不被遮擋若，有可能遮擋需要進一步檢查若非以上兩種情況，必然相交，求出交點，交點將原線段分成兩段，分別屬于上面兩種情況求出z1,z1’設平面方程為直線L1的參數(shù)方程X=x1，Y=y1，Z=z1+t，代入平面方程得：第十二頁，共六十二頁，2022年，8月28日若t≥0,則z1≤z1’，靠近視點可見若t＜0,則z1>z1’，遠離視點4.進一步檢查對平面遮擋了線段的哪些部分做精確計算求線段投影與多邊形邊框投影的交點（第五章第一節(jié)）設交點已經(jīng)求出，設其對應的參數(shù)λ，按從小到大依次排序后是λ1，λ2。。。，則這些交點將投影線段分成的各子線段的可見性應是可見，不可見交替出現(xiàn)。判斷子線段的可見性：(第五章第四節(jié)）

第十三頁，共六十二頁，2022年，8月28日

需要檢查出某一段子線段是否可見。為此可以取子線段上任意一點，若這點在多邊形表面各邊線的投影所形成的封閉多邊形內(nèi)，這子線段就不可見，否則就可見。

第十四頁，共六十二頁，2022年，8月28日第三節(jié)深度排序算法

深度排序算法：先畫最遠的，再畫最近的（優(yōu)先級算法，畫家算法）深度排序算法的主要步驟：1.

把所有的多邊形按頂點最大z坐標值進行排序。（客體空間）2.解決當多邊形z范圍發(fā)生交迭時出現(xiàn)的不明確問題。3.按最大z坐標值逐漸減小的次序，對每個多邊形進行掃描轉(zhuǎn)換。（圖像空間）

第十五頁，共六十二頁，2022年，8月28日不明確問題檢驗方法

所有多邊形按頂點最大z坐標值排序后得到一個排序表，設P是排在表中最后的那個多邊形。

設Q是排在P前面并且z坐標范圍與其發(fā)生交迭的一個多邊形，對Q與P的次序關系進行檢查。

QP第十六頁，共六十二頁，2022年，8月28日第十七頁，共六十二頁，2022年，8月28日檢查可以按下面列出的五個步驟進行，每個步驟判斷一種情況。

1．多邊形的x坐標范圍不相交迭，所以多邊形不相交迭。QP2．多邊形的y坐標范圍不相交迭，所以多邊形不相交迭。QP3.P整個在Q遠離觀察點的一側(cè)。QP第十八頁，共六十二頁，2022年，8月28日4.Q整個在P的靠近觀察點的一側(cè)。QP5.多邊形在z=0平面上的投影本身不相交迭。QP以上五步中任何一步成立，都可以說明當前排序正確第十九頁，共六十二頁，2022年，8月28日

如果五步檢查都為假，就假定P是遮擋了Q，交換P和Q在排序表中的位置。（QPPQ)

如果仍做交換，算法會永遠循環(huán)下去而沒有結(jié)果。

為了避免循環(huán)，可以做一個限制。當做過首次五步檢查后，發(fā)生某個多邊形被移到排序表的末尾時，就立即加上一個標記，以后就不能再做移動。出現(xiàn)再次應該移動時，用一個多邊形所在的平面，把另一個多邊形裁剪分為兩個。第二十頁，共六十二頁，2022年，8月28日PQ第二十一頁，共六十二頁，2022年，8月28日第五節(jié)z緩沖算法

z緩沖算法:(深度緩沖算法)是一種最簡單的圖象空間算法。幀緩沖存儲器:存儲各點的象素值，初始化為背景值。z緩沖存儲器:存儲相應的z值。初始化最大z值。對每一個多邊形，不必進行深度排序算法要求的初始排序，立即就可以逐個進行掃描轉(zhuǎn)換。第二十二頁，共六十二頁，2022年，8月28日第二十三頁，共六十二頁，2022年，8月28日掃描轉(zhuǎn)換時，對每個多邊形內(nèi)部的任意點（x,y）,實施如下步驟：1.計算在點（x，y）處多邊形的深度值z（x，y）。2.如果計算所得的z（x，y）值，小于在z緩沖存儲器中點xy處記錄的深度值，那么就做：（1）把值zxy送入z緩沖存儲器的點(x,y)處。（2）把多邊形在深度z(xy處應有的象素值，送入幀緩沖存儲器的點xy處。

第二十四頁，共六十二頁，2022年，8月28日

算法中深度計算，可通過多邊形的頂點坐標求出所在平面的方程，然后再使用平面方程，對每個點xy，解出相應的z。

對面方程，

解出是：

第二十五頁，共六十二頁，2022年，8月28日設在點（x,y）處的深度值是z1:則在點（x+△x,y）處的深度值就是第二十六頁，共六十二頁，2022年，8月28日z緩沖算法的工作流程：幀緩沖區(qū)置成背景色；z緩沖區(qū)置成最大z值；for(各個多邊形){掃描轉(zhuǎn)換該多邊形；for(計算多邊形所覆蓋的每個象素（x,y）){計算多邊形在該象素的深度值Z(x,y)；if(Z(x,y)小于Z緩沖區(qū)中的(x,y)處的值){把Z(x,y)存入Z緩沖區(qū)中的(x,y)處；把多邊形在(x,y)處的亮度值存入幀緩存區(qū)的(x,y)處；}}}第二十七頁，共六十二頁，2022年，8月28日Z-Buffer算法優(yōu)點：在象素級上以近物取代遠物。形體在屏幕上的出現(xiàn)順序是無關緊要的。這種取代方法實現(xiàn)起來遠比總體排序靈活簡單，有利于硬件實現(xiàn)。Z-Buffer算法缺點：占用空間大，沒有利用圖形的相關性與連續(xù)性。需要開一個與圖象大小相等的緩存數(shù)組ZB。改進算法:只用一個深度緩存變量zb。第二十八頁，共六十二頁，2022年，8月28日Z-Buffer(){幀緩存全置為背景色

for(屏幕上的每個象素(i,j))//掃描整個屏幕{深度緩存變量zb置最大值MaxValue

for(多面體上的每個多邊形Pk)

{

if(象素點(i,j)在pk的投影多邊形之內(nèi))

{計算Pk在(i,j)處的深度值depth;

if(depth小于zb)

{zb=depth;

indexp=k;}}}

If(zb!=MaxValue)計算多邊形Pindexp在交點(i,j)處的光照顏色并顯示

}}第二十九頁，共六十二頁，2022年，8月28日第六節(jié)掃描線算法

消除隱藏面的掃描線算法：圖象空間算法第二章第三節(jié)多邊形掃描轉(zhuǎn)換算法＝》推廣

填充算法：針對一個多邊形做掃描轉(zhuǎn)換消隱算法：同時對多個多邊形做掃描轉(zhuǎn)換。第三十頁，共六十二頁，2022年，8月28日ET表（邊表）中吊桶的內(nèi)容：1．與較小的y坐標對應的端點的x坐標xmin。2．邊的另一端點的較大的y坐標ymax。3．

x的增量Δx，它實際上是邊的斜率的倒數(shù)，是從一條掃描線走到下一條掃描線時，按x方向遞增的步長。4.邊所屬多邊形的標記。5.指針指向下一條邊第三十一頁，共六十二頁，2022年，8月28日PT表（多邊形表）：記錄多邊形信息，一個記錄對應一個多邊形。一個記錄的內(nèi)容：1．多邊形所在平面方程的系數(shù)A,B,C,D2．多邊形的顏色或亮度值3．進入/退出標志，標記當前掃描線對該多邊形是“進入”還是“退出

”

第三十二頁，共六十二頁，2022年，8月28日AET表（活躍邊表）：存儲與當前掃描線相交的各邊的信息。APT表（活躍多邊形表）：與當前掃描線相交的所有多邊形，按深度遞增排序。第三十三頁，共六十二頁，2022年，8月28日第三十四頁，共六十二頁，2022年，8月28日掃描線y=α:AET表中有AB,AC,到AB時，F(xiàn)lagABC=1,AB到AC一段用ABC的顏色填充到AC時，F(xiàn)lagABC=0,掃描線y=β：AET表中有四項AB,AC,FD,FEF,到AB時，F(xiàn)lagABC=1,AB到AC一段用ABC的顏色填充到AC時，F(xiàn)lagABC=0,AC到FD之間填充背景色到FD時,FlagDEF=1,FD到FE之間填充DEF顏色到FE時,FlagDEF=0掃描線y=γ：AET表中有四項AB,DE,CB,FE到AB時，F(xiàn)lagABC=1，AB到DE之間填ABC的顏色到DE時，F(xiàn)lagDEF=1，做深度比較，求（x’,γ）的深度

若ZDEF<ZABC，則DE到CB之間填DEF的顏色到CB時，F(xiàn)lagABC=0，BC到EF之間填DEF顏色到FE時，F(xiàn)lagDEF=0

第三十五頁，共六十二頁，2022年，8月28日

例子：設有兩個空間的三角形ABC、DEF,各頂點的坐標依次是（1，1，10），（2，5，10），（5，3，10），（3，4，5），（4，6，5），（6，2，5）。

第三十六頁，共六十二頁，2022年，8月28日第三十七頁，共六十二頁，2022年，8月28日第三十八頁，共六十二頁，2022年，8月28日算法步驟：第二章第三節(jié)多邊形掃描轉(zhuǎn)換算法3.2:在掃描線y上，按照AET表提供的x坐標對，用color實施填充修改加細如下：

3.2.1掃描線指向的“吊桶”的指針i1，掃描線在多少個多邊形內(nèi)的計數(shù)器s0活躍多邊形表P，初始為空。第三十九頁，共六十二頁，2022年，8月28日3.2.2設第i個“吊桶”記錄的相應多邊形是A。ifFlagA=FALSE

，then{FlagA=TRUE

，將A加到表P中，ss+1}else{FlagA=FALSE將P中刪除A，ss-1}第四十頁，共六十二頁，2022年，8月28日3.2.3ifs=0，goto3.2.5（這時掃描線不在任何多邊形內(nèi)，正通過背景，不必做掃描轉(zhuǎn)換)ifs=1，goto3.2.4（這時掃描線只在一個多邊形內(nèi)，不必做深度比較，去做掃描轉(zhuǎn)換。）若前面兩個判斷都為“假”，掃描線至少在兩個多邊形內(nèi)，應做深度比較。對表P前面兩個多邊形做深度比較，比較后排序應保證P表中的多邊形按深度遞增的次序。第四十一頁，共六十二頁，2022年，8月28日3.2.4對第i個和第i+1個“吊桶”存有的x坐標指示的掃描線上的一段，按照P表最前面多邊形指示的亮度或顏色，實施掃描轉(zhuǎn)換。

3.2.5i增加1，若i所指已無“吊桶”，步驟結(jié)束，去下一步驟3.3（刪除y=ymax的邊）。否則，回到步驟3.2.2。第四十二頁，共六十二頁，2022年，8月28日isPPT表FABCFDEF說明11(ABC)true

1到3填ABC的亮度或顏色值22(DEF,ABC)

true在步驟3發(fā)生深度比較，比較結(jié)果DEF更靠近觀察者，它仍在P表前面，3到3填DEF的亮度或顏色值31(DEF)false

3到5填DEF的亮度或顏色值40()false

第四十三頁，共六十二頁，2022年，8月28日

3.2.3深度比較條件太寬松，實際很多不必要的的比較改進1：假定沒有多邊形穿透另一個多邊形的情況下，如果掃描線從一個被遮擋的多邊形中走出，深度比較將是不必要的；掃描線從一個遮擋了其它多邊形的多邊形中走出，深度比較才可能必要。第四十四頁，共六十二頁，2022年，8月28日改進2：利用深度相關性，對于一組相鄰的掃描線來說，多邊形之間的深度關系常常是不發(fā)生變化的。

第四十五頁，共六十二頁，2022年，8月28日

改進3：對于穿透情況的處理，將一個多邊形分成兩個子多邊形第四十六頁，共六十二頁，2022年，8月28日改進4：背景顏色處理（1）幀緩存初始為某個特定的值（2）定義一個包含了客體中所有的多邊形，位于比其它多邊形都更遠離觀察者的平行于投影平面的一個平面上，并具有某個合適的亮度或顏色值。

（3）修改算法。當掃描線不在任何多邊形內(nèi)時，就往幀緩沖存儲器中送入背景的象素值。

第四十七頁，共六十二頁，2022年，8月28日第七節(jié)區(qū)域分割算法

區(qū)域分割算法：

將投影平面分割成區(qū)域，考察區(qū)域內(nèi)的圖象。如果容易決定在這個區(qū)域內(nèi)某些多邊形是可見的，那么就可以顯示那些可見的多邊形，完成對這一區(qū)域的顯示任務。否則，就將區(qū)域再分割成小的區(qū)域，對小的區(qū)域遞歸地進行判斷。由于區(qū)域逐漸變小，在每個區(qū)域內(nèi)的多邊形逐漸變小，最終總可以判定哪些多邊形是可見的。這個算法利用的區(qū)域的相關性，這種相關性是指位于適當大小的區(qū)域內(nèi)的所有象素，表示的其實是同一個表面。區(qū)域分割算法：圖像空間算法第四十八頁，共六十二頁，2022年，8月28日

形體中多邊形的投影多邊形與所考察區(qū)域之間的關系：1.包圍的多邊形，即多邊形包圍了所考察的區(qū)域。2.

相交的多邊形，即多邊形所考察的區(qū)域相交。3.被包含的多邊形,即多邊形全部在所考察的區(qū)域之內(nèi)。4.分離的多邊形，即多邊形與所考察的區(qū)域完全分離。

第四十九頁，共六十二頁，2022年，8月28日

區(qū)域不必再進行分割的情況：1．所有的多邊形與區(qū)域分離，所以在區(qū)域內(nèi)只需顯示背景值。2.只有一個相交的多邊形，或者只有一個被包含的多邊形。這時可以對區(qū)域首先填充背景值，然后對多邊形進行掃描轉(zhuǎn)換。（相交的多邊形，只對被包含的部分做掃描轉(zhuǎn)換）3.

只有一個包圍的多邊形，無其它的多邊形。整個區(qū)域填充該多邊形的象素值。（1,2,3用范圍檢查）多個多邊形與之相交、包圍、或被包含，且有一個包圍的多邊形位于其它多邊形最前面，區(qū)域填充為該多邊形的顏色。（深度檢查）第五十頁，共六十二頁，2022年，8月28日情形4的兩種情形

第五十一頁，共六十二頁，2022年，8月28日對不能做出判斷的情形的處理方法：（1）按照原算法將該區(qū)域分割（2）修改判斷是否在最前面的算法判別相交的多邊形是否在整個包圍多邊形的后面，將相交多邊形的頂點坐標代入包圍多邊形的平面方程，判別符號。第五十二頁，共六十二頁，2022年，8月28日

區(qū)域分割成子區(qū)域：1.子區(qū)域需考察的情況：只需考慮父區(qū)域包含的或相交的多邊形。對于分離的或包圍的多邊形，進行區(qū)域分割之后仍保持分離包圍的關系。

2.分割中止的條件：一個象素單位或最大數(shù)目的分割對于仍不能判斷的，則找出中心點，計算中心點對應的所有多邊形的z值，取z值最小的多邊形象素值來填充