第8章隱藏線及隱藏面消除

1、Computer Graphics第八章 隱藏線和隱藏面的消除Computer Graphics隱藏線和隱藏面的消除基于窗口的子分算法緩沖器算法和掃描線算法光線投射算法基于多邊形的子分算法優(yōu)先級排序表算法 曲面隱藏線的消除可見面判斷的有效技術(shù)多面體隱藏線消除算法Computer Graphics線框架結(jié)構(gòu)模型 它是將立體對象用輪廓線和小的元素面描述的模型，這種模型的對象立體數(shù)據(jù)輸入方式簡單，容易操作，可以實現(xiàn)描述的快速性，經(jīng)常被人們使用。 但是由于線框表示會出現(xiàn)錯誤理解。如下圖所示。 Computer Graphicsv 消隱的效果圖Computer Graphics隱藏線或隱藏面消除確定線或

2、面可見性相對于投影中心透視投影相對于投影方向平行投影Computer Graphics以構(gòu)成圖像的每一個像素為處理單元，對場景中的所有表面，確定相對于觀察點是可見的表面，用該表面的顏色填充該像素兩種基本算法以三維場景中的物體對象為處理單元，在所有對象之間進行比較，除去完全不可見的物體和物體上不可見的部分在和投影點到像素連線相交的表面中，找到離觀察點最近的表面；用該表面上交點處的顏色填充該像素；判定場景中的所有可見表面；用可見表面的顏色填充相應(yīng)的像素以構(gòu)成圖形；Computer Graphics假定假定1 1：垂直投影垂直投影如果不是這種情況，可對消隱的對象先作變換，變成這種情況，然后再作消隱計

3、算。下面討論消隱算法時，都假定投影平面是oxy平面，投影方向為負z軸方向的垂直投影。本章所討論的消隱算法的前提假定：本章所討論的消隱算法的前提假定：Computer Graphicsv 本章說明的各種消隱方法都假定構(gòu)成對象的不同面不不能相互貫穿能相互貫穿，如圖貫穿和循環(huán)遮擋例如用圖中的虛線便可把原來循環(huán)遮擋的三個平面，分割成不互相循環(huán)遮擋的四個面。 也不能有循環(huán)遮擋不能有循環(huán)遮擋的情況，如果有這種情況，可把它們剖分成互不貫串和不循環(huán)遮擋的情況。假定假定2 2：Computer Graphics8.1 可見面判斷的有效技術(shù)場景有N個面，所有的面兩兩求交判定可見面，O(N2)減少可見線和可見面判定

4、計算量的常用的技術(shù)非垂直投影轉(zhuǎn)換成垂直投影后向面消除邊界盒Computer Graphics8.1.1 邊界盒Computer Graphics一個好的包圍盒要具有兩個條件：一個好的包圍盒要具有兩個條件：v包圍和充分緊密包圍包圍和充分緊密包圍著形體著形體； 對其的測試比較簡單對其的測試比較簡單。Computer Graphicsmin12min12max12max12min( , ),min( ,)max( , ),max( ,)xx xyy yxx xyy yQ1Q2邊界盒Q5Q6的邊界盒1max2min1max2min2max1min2max1minyyxxyyxx或或 邊的邊界盒maxC

5、omputer Graphics8.1.2 后向面消除后向面總是看不見的，而且別的棱也不會由于后向面的遮擋而成為不可見，因此，把后向面全部去掉并不影響消隱結(jié)果IJFGH，F(xiàn)ABG，HCDI和IDEJ 前向面 其余為后相面多邊形表面后向面表面的法向指向與觀察者相背離前向面外法線方向指向觀察者Computer Graphics8.1.2 后向面消除頂點 ，頂點的坐標LVVV,21),(iiizyx多邊形F沿著頂點序列走時，其內(nèi)部始終在他的右側(cè)1V2V3VLV若構(gòu)成凸的多邊形 是F內(nèi)法線方向12 ,111Lkvvvvkka a 大于零，外法線和 z軸正向的夾角大于90度，后向面z)(a a前向面前向

6、面0SP 后向面0SPComputer Graphicsv 設(shè)多邊形設(shè)多邊形F F的頂點為的頂點為 ，頂點，頂點 的坐標為的坐標為 。( (次序如圖所示次序如圖所示) )v 如果是一凸多邊形，可只取一個三角形計算有向面積如果是一凸多邊形，可只取一個三角形計算有向面積v 凹多邊形的內(nèi)法線方向，可以計算多邊形在凹多邊形的內(nèi)法線方向，可以計算多邊形在oxyoxy平面上投影的有向面積平面上投影的有向面積。有向面積。有向面積spsp可如下計算可如下計算v 如果如果 ，說明其，說明其外法線外法線方向與方向與z z軸正向的夾角軸正向的夾角90,90,則則F F所在的面為后向面。所在的面為后向面。v 如果如果

7、 ，說明其，說明其外法線外法線方向與方向與z z軸正向的夾角軸正向的夾角90,90,則則F F所在的面為前向面。所在的面為前向面。11112111111121() ()21 ()() ()()2LkkKzLkkkkKspv vv vxxyyxxyy LVVV,21iV),(iiizyx頂點的排列次序，使觀察者在多頂點的排列次序，使觀察者在多 面體外沿著面體外沿著 走時，走時，多邊形的內(nèi)部始終在他的右側(cè)。多邊形的內(nèi)部始終在他的右側(cè)。1V2V3VLVLVVV210SP0SPComputer Graphics背面剔除背面剔除法向向量N 視線向量V法向向量N 法向向量N 90 90V VN N cos

8、Computer Graphics8.2 多面體隱藏線消除算法用線框方式來表示多面體，在這種表示方式下，多面體用棱邊來表示隱藏線便是不可見的棱邊或棱邊中不可見的部分找到各棱邊上可見和不可見部分的分界點多面體的各棱邊投影到oxy 平面上在oxy平面上求棱邊和棱邊之間的交點BC,BA,BG，EA為隱藏線Computer Graphics8.2.1 算法的基本思想v 隱藏線消除實際計算過程 ：Step1確定可能遮擋體A的那些體集合B (包括體A本身)。Step2A的每個多邊形G，要從B中找出可能遮擋它的所有多邊形的集合CStep3對多邊形G的每一條邊L，從集合C中找出可能遮擋它的所有多邊形EStep

9、4求L和多邊形E中的邊的交點，確定L的可見部分Computer Graphics設(shè)邊L的頂點是vi和vj，對邊vivj和每一個可能遮擋它的多邊形E，都要作下列計算和判斷，以確定其隱藏關(guān)系 如果如果v vi i和和v vj j都在都在多邊形多邊形E E所在平面靠近觀察者的一側(cè)，所在平面靠近觀察者的一側(cè)，則則E E不能遮擋直線段不能遮擋直線段v vi iv vj j 如果如果v vi i和和v vj j不都在多邊形不都在多邊形E E所在平面靠所在平面靠 近觀察者的一側(cè)，且近觀察者的一側(cè)，且v vi iv vj j和和E E在在OxyOxy平面平面 的投影相交，求出其交點。只的投影相交，求出其交點。

10、只保留在保留在v vi i v vj j 上的對應(yīng)點在多邊形上的對應(yīng)點在多邊形E E后邊的交點。后邊的交點。若無交點，這時要判斷若無交點，這時要判斷v vi i或或v vj j在在OxyOxy平平 面上的投影是否在面上的投影是否在E E的投影的內(nèi)部，的投影的內(nèi)部， 若是，則若是，則v vi iv vj j就會整個被就會整個被E E所遮擋。所遮擋。Step4的處理技術(shù)的處理技術(shù)Computer Graphics1.1.確定確定L L頂點處與遮擋多邊形的前后位置關(guān)系頂點處與遮擋多邊形的前后位置關(guān)系),(jjjzyxjjjzyxz),(jvjvjvl 設(shè)點設(shè)點 的坐標為的坐標為 ，若，若 ，則，則

11、在多邊形所在平面的前面，否則認為在多邊形所在平面的前面，否則認為 在多邊在多邊 形所在平面的后面。形所在平面的后面。1v2vLv3v4v5v),(iiizyx)(),(5343vvvvcbacyybxxazyxz/)()(),(333l 設(shè)多邊形的頂點為設(shè)多邊形的頂點為 , , , 其坐標為其坐標為 i i=1,2,=1,2,L L。 任取三個不在一直線上的頂點，設(shè)為任取三個不在一直線上的頂點，設(shè)為 , , , , , 記向量記向量 , ,則多邊形則多邊形E E所在的平所在的平 面方程為面方程為8.2.2 確定邊L和多邊形E關(guān)系的技術(shù)Computer Graphics( , )jjz x yj

12、viv(,)jjjz xyzjzComputer Graphics 上對應(yīng)的交點在多邊形所在平面的前面，否則在后面。v 判斷邊vivj和多邊形E在oxy平面的投影之間是否有交點，可通過求邊vivj和E的邊界在oxy平面上投影是否相交實現(xiàn)v 在 vivj平面的投影線段的參數(shù)方程為 (8.6) v 多邊形上任一邊vkvk+1在oxy平面上的投影為 (8.7)v 聯(lián)立(8.6)和(8.7)，解方程得2. 確定L與遮擋多邊形的交點和遮擋多邊形的前后位置關(guān)系(1)(1)ijijxxsx syysy s11(1)(1)kkkkxxtxtyytyt11()() ()()/()() ()()/kikkkikk

13、ikjijiiksyy xxxxyyRtxxyyxxyyR11()() ()()kkjikkjiRxxyyyyxx0, 1s t邊和線段vivj在oxy平面上的投影才有交點1(1)(1)ijkkzsz sztztjivv(1)ijzsz s 1(1 )kkztz t Computer Graphicsv 注意 ，其中 表示向量 在z軸上的投影。3. 確定交點和多邊形的關(guān)系：是進點還是出點1()kkij zRw www ( )zAA11,kkijkkijw ww w w ww w滿足右手系當 時， 由多邊形外進入多 邊形內(nèi)（該交點稱為進點）0R ijww當 時， 由多邊形內(nèi)離開多邊形到多邊形外（

14、該交點稱為出點）。0Rijwwwiwj進入或走出多邊形Wk+2Wk+1WkWiWjWjWiComputer Graphics4. 確定 點和多邊形的關(guān)系iwv 判斷 點在多邊形內(nèi)或外，可以從 點出發(fā)沿x軸的正向作一條射線v 若該射線和多邊形邊界的交點個數(shù)是奇數(shù)，則 在多邊形內(nèi)v 若該射線和多邊形邊界的交點個數(shù)是偶數(shù)，就在多邊形外v 由于舍入誤差，可得到完全不同的結(jié)果5w7w6w8w1w2w3w4wiwiwiw無交點奇交點單處理iw偶交點iwiwiw11()()/()kkkkkkyyyxxxxyiyy1kkw w把代入的方程11()()/()kkikkkkxxxyyyyx得1kkww說明ixx

15、Fwi若有一個交點。Computer Graphics8.2.3 確定L的可見部分v 不可見階 它是一個數(shù)字，代表了邊上從該點到下一個交點的部分被幾個多邊形遮擋 與所有多邊形的交點進行由小到大的順序排序jiww1, 01210nnsssss不可見階的確定1確定邊起始頂點處的不可見階。將階置為覆蓋該點的多邊形的個數(shù)。2確定邊 與遮擋多邊形各交點處的不可見階。交點為進點則 不可見階加1，交點為出點則 不可見階減1jiww原則：若 處不可見階為0，則由參數(shù) 和 所對應(yīng)的直線段是可見的，否則為不可見isis1isComputer Graphics8.3 基于窗口的子分算法Computer Graphi

16、cs多邊形與窗口的關(guān)系：Computer Graphics所有多邊形均和窗口分離，這時只要把窗口內(nèi)所有的像素填上背景色只有一個多邊形和窗口相交，或這個多邊形包含在窗口內(nèi)。這時，先對窗口內(nèi)每一像素填上背景顏色，再對窗口內(nèi)多邊形部分用掃描線算法填色只有一個包圍窗口的多邊形，則窗口用包圍多邊形的顏色填充。多個多邊形和窗口的關(guān)系分別是相交、內(nèi)含或包圍，但是有一個包圍窗口的多邊形在其他多邊形前面，整個窗口用該包圍多邊形的顏色填充窗口分割的結(jié)束條件不成立的窗口將再一分為四Computer Graphicsv 提高效率的有效的處理技術(shù)排序?qū)λ械亩噙呅伟雌漤旤c的z坐標最大值來排序細分每次細分窗口后，用邊界盒

17、的辦法判斷多邊形序列中的多邊形是否和四個子窗口相交，不相交的多邊形可從多邊形序列中排除若窗口被多邊形G包含，被G遮擋的多邊形要從窗口的多邊形序列中去掉 EA窗口zmaxzminB C D GHF圖8.12 確定被遮的擋多邊形izzmaxminCD被AB遮擋GHzzAB遮擋了EFComputer Graphics8.4 基于多邊形的子分算法v 算法描述：各多邊形在深度方向作初步的排序多邊形序列中的第一個多邊形(裁剪多邊形)作為裁剪窗口區(qū)域內(nèi)多邊形確定內(nèi)部表中多邊形的前后順序區(qū)域外多邊形外部表中同樣的工作裁剪過程要重復(fù)到外部表中不再有多邊形為止v 目的是盡量減少對窗口劃分的次數(shù)。 Computer

18、 Graphicszxy43212i3i4i4oa) ni為窗口內(nèi)的多邊形表，n=2,3,4； b) no為窗口外的多邊形表,n=3,4圖8.14 消隱多邊形的裁剪3o例子Computer Graphics具體步驟：具體步驟：v 對各多邊形在深度方向作初步 的排序v 把多邊形序列中的第一個多邊 形（裁剪多邊形）取為裁剪窗口。 多邊形序列中的其它的多邊形 都要被此窗口裁剪。v 裁剪結(jié)果要建立兩個多邊形序 列表 消隱多邊形的裁剪Ni為窗口內(nèi)的多邊形表；內(nèi)部表內(nèi)部表: :放入位于窗口內(nèi)的部分放入位于窗口內(nèi)的部分no為窗口外的多邊形表外部表外部表: :放入位于窗口外的部放入位于窗口外的部分分Compu

19、ter Graphicsv 確定裁剪多邊形（即取為窗口的那個多邊形）是否比內(nèi)部表中的多邊形更靠近觀察者v 如果是則內(nèi)部表中的其他多邊形都被其遮擋，可把該多邊形區(qū)域填上裁剪多邊形的顏色v 如果發(fā)現(xiàn)內(nèi)部表中某多邊形H比裁剪多邊形更靠近觀察者這時則只好把多邊形H的原始多邊形（即未被裁剪時的多邊形）代替原來的裁剪多邊形重復(fù)上述工作。Computer Graphicsv接著處理外部表中的各多邊形，把外部表中的第一多邊形作為裁剪窗口，重復(fù)上述工作v這一過程要重復(fù)到外部表中不再有多邊形為止要消隱的多邊形 消隱多邊形的裁剪Ni為窗口內(nèi)的多邊形表；no為窗口外的多邊形表Computer Graphicsv 算法

20、簡述：各多邊形在深度方向作初步的排序多邊形序列中的第一個多邊形(裁剪多邊形)作為裁剪窗口區(qū)域內(nèi)多邊形確定內(nèi)部表中多邊形的前后順序區(qū)域外多邊形外部表中同樣的工作裁剪過程要重復(fù)到外部表中不再有多邊形為止Computer Graphics8.5 z緩沖器算法和掃描線算法uvnumaxvmaxv 基本思想：基本思想：Computer Graphics具體實現(xiàn)此算法需要z緩沖器數(shù)組和幀緩沖器數(shù)組，分別設(shè)為Zdepth 與Frame ：對屏幕上每個點（x,y），令Zdepth xy 為z的極小值，F(xiàn)rame xy為背景顏色。對所有多邊形做如下工作：對多邊形上 每一點（x,y）,計算其z值。 若z Zdep

21、th xy， 則 Zdepth xyz，并將此點屬性值 賦給Framexy，否則 說明此點離觀察 者較遠，兩個數(shù)組的值都不用改變x,y（）Computer Graphics克服Computer Graphics掃描線z緩沖器算法v 算法思想Computer Graphicsv 每處理一條掃描線，都要檢查各多邊形是否和該線相交，還要計算多邊形所在平面上很多點的z值，需要花費很大的計算v 采取類似多邊形掃描轉(zhuǎn)換的掃描線算法處理，提高效率x,y（）Computer Graphics數(shù)據(jù)結(jié)構(gòu)1多邊形Y筒系數(shù)a，b，c和dy 屬性color編號IP2邊Y筒上端點x坐標的值y x 編號IP3多邊形活化表.

22、多邊形活化表中記錄了在 平面上的投影和當前考慮的掃描線相交的多邊形4邊活化表邊活化表中存放多邊形的邊和當前掃描線相交的邊對Computer Graphics367811101198713圖 8.15 要消隱的物體xo多邊形y筒邊y筒1/7107 28 2 1 2多邊形活化表1,; 3, 0, 7; 3, 1, 4111IPzzzyxxyxxyxlrrrlll2,; 5,71,7210; 5,65,656222IPzzzyxxyxxyxlrrrlll邊活化表Computer Graphics算法如下建立多邊形Y筒和邊Y筒，初始化多邊形和邊的活化表為空。1TEXT2以最上面的掃描線為當前掃描線。4

23、檢查多邊形Y筒若有新的多邊形涉及當前掃描線，則把它放入多邊形活化表中。若有新的多邊形加入多邊形活化表，則要把該多邊形在 平面上的投影和掃描線相交的邊對加入邊活化表中。對當前掃描線y，把幀緩沖器相應(yīng)行置成底色，z緩沖器的各單元放z的極小值3若所有掃描線都已經(jīng)處理完，則算法結(jié)束，否則選下一條掃描線為當前掃描線，轉(zhuǎn)步驟365對邊活化表中的每個邊對，令 ，對每一個滿足 的坐標為 的像素從左到右依次進行處理。lxzz rlxxx),(yxComputer Graphics對邊活化表和多邊形活化表修改1）、修改邊活化表，對每一邊做如下計算 若yl 或yr小于0，相應(yīng)的邊就要從一個邊對中去掉，并從y筒中找到

24、合適的邊來代替。若這兩條邊同時結(jié)束于某一點，則去掉這一邊對。若yl和yr都不小于0，則修改 為 修改后的表便是新掃描線的邊活話表。2）、修改多邊形活化表。令 ，若 ，則將該多邊形從多邊形活化表中刪除。 1 -y y1, -y yrrll算法步驟：算法步驟：-對邊活化表修改rrrlllxxx ,xxxylxllz xzz zllrzxx,1yy0 yComputer Graphics8.6 優(yōu)先級排序表算法v 模擬示例Computer Graphicsv 算法思想 優(yōu)先級排序表算法按多邊形離觀察者的遠近來建立一個多邊形排序表，距觀察者遠的優(yōu)先級低，近的優(yōu)先級高 從優(yōu)先級低的多邊形開始，依次把多邊

25、形的顏色填入幀緩沖存儲器中 表中距觀察者近的元素覆蓋幀緩沖存儲器中原有的內(nèi)容 當優(yōu)先級最高的多邊形的圖形送入幀緩沖器后，整幅圖形就形成了Computer Graphicsv 優(yōu)先級排序表算法的關(guān)鍵在于對多邊形做正確的排序優(yōu)先級排序表算法的關(guān)鍵在于對多邊形做正確的排序v 動態(tài)的算法： 根據(jù)每個多邊形頂點z坐標的極小值zmin的大小，按由小到大對它們做初步排序，并把它們組成一個鏈表 若鏈表中只有一個多邊形，則算法結(jié)束。否則取表頭多邊形為P。1. 設(shè)Q為鏈表中P之外的任一多邊形。若對所有Q都有 ,則P不會遮擋其它多邊形，為優(yōu)先級最低的多邊形，在鏈表中去除P，轉(zhuǎn)（2）；否則，若所有Q都滿足下面四項條件

26、中的一項，則在鏈表中去除P，轉(zhuǎn)（2）。若不滿足此四項條件中任何一個的Q，交換P和Q，轉(zhuǎn)（3）。minzQmaxzPComputer Graphics四項條件P和Q在平面 oxy上的投影不相交Q 的各頂點均在P的近視點的一側(cè)P 的各頂點均在Q的遠離視點的一側(cè)P和Q在oxy平面上投影的邊界盒在x或y方向上不相交Computer Graphics特殊情況v 解決：圖8.22，把多邊形序列中原多邊形P從序列中去掉，而把P分成的兩個多邊形加入鏈表中，這樣可避免使多邊形P和Q不斷地循環(huán)進行交換圖8.21 互相遮擋 圖8.22 用Q所在平面把P一分為二 Computer Graphicsv 對飛機駕駛員著陸

27、進行模擬訓(xùn)練時要顯示消隱后的跑道周圍情況，這時景物是不變的，僅視點發(fā)生變化。v 可對不同的視點位置把景物的優(yōu)先級排序表預(yù)先算好，然后再用油畫家算法顯示圖形，這樣便可使消隱過程加速，實現(xiàn)動態(tài)顯示圖8.23 視點在不同區(qū)域有不同的優(yōu)先級ABCD視點所在區(qū)域 優(yōu)先級表優(yōu)先級表Computer Graphics8.7 光線投射算法v原理：要處理的場景中有無限多條光線，從采樣的角度講我們僅對穿過像素的光線感興趣，因此，可考慮從像素出發(fā)，逆向追蹤射入場景的光線路徑Computer Graphics具體做法是：v 由視點出發(fā)穿過觀察平面上一像素向場景發(fā)射一條射線(如圖8.25)v 求出射線與場景中各物體表面

28、的交點v 離視點最近的交點的顏色即為像素要填的顏色。v 光線投射算法對于包含曲面，特別是包含球面的場景有很高的效率。圖8.25 一條由象素點射入場景的視線 Computer Graphicsz z緩沖器算法:每次處理一個面片,對面片上的每個投影點計算z值，計算出來的值與以前保存的z值進行比較，從而確定每個像素所對應(yīng)的可見面片光線投射算法可看作是z緩沖器算法的一種變形光線投射算法:每次處理一個像素，并沿光線的投射路徑計算出該像素所對應(yīng)的所有面片的z值。Computer Graphics8.8 曲面的隱藏線消除v 由方程 表示曲面v 曲面可以由 和 產(chǎn)生的 條曲線來表示 即由 和 兩組平面和曲面 的交線來表示v 隱藏線消除就是要去掉這兩 族交線中被遮擋的部分),(zxfy (a)未消隱的曲面表示(b)消隱的曲面表示( , ), 0,1,2,iyf x zin( , ), 0