計算機圖形學第七章

1、第七章 消隱？基本概念 ？消隱算法的基本原則？畫家算法？Z緩沖器算法？掃描線Z緩沖器算法？光線投射算法 ？繪制基本概念產(chǎn)生真實感的方法之一： 反映三維場景中的相互遮擋關系面消隱與線消隱 表面模型與線框模型 物體表面：平面與曲面 面消隱對象： 由平面多邊形構成的多面體基本概念消隱算法的分類1）類：以窗口內的每個像素為處理單元； for (窗口內的每一個像素) 確定距視點最近的物體，以該物體表面的顏色來顯示像素 2）類：以場景中的物體為處理單元； for (場景中的每一個物體) 將其與場景中的其它物體比較，確定其表面的可見部分； 顯示該物體表面的可見部分；基本概念算法復雜度 假設場景中有k個物體，

2、平均每個物體表面由h個多邊形構成，顯示區(qū)域中有m x n個像素，則：第一種算法的復雜度為：O(mnkh) 第二種算法的復雜度為：O(kh)*(kh)消隱算法的基本原則 1排序 2連貫性物體連貫性面（邊）連貫性掃描線連貫性深度連貫性畫家算法由來：畫家的作畫順序暗示出所畫物體之間的相互遮擋關系算法的基本思想 基本思想： （1）先把屏幕置成背景色； （2）將物體的各個面按其距觀察點的遠近進行排序，結果放在一張深度優(yōu)先級表中；（深度優(yōu)先級表是一個線性表，距觀察點遠的多邊形優(yōu)先級低，將之放在表頭；距觀察點近的多邊形優(yōu)先級高，將之放在表尾。） （3）按照從表頭到表尾（從遠到近）的順序逐個取出多邊形，投影到

3、屏幕上并顯示。畫家算法本算法不能處理的情況：多邊形循環(huán)遮擋多邊形相互穿透 解決辦法：分割成兩個深度優(yōu)先級表的建立 當兩個多邊形P和Q交叉在一起時，要進行對多邊形的排序。 假設多邊形的z范圍是平面z=zmin和z=zmax之間的區(qū)域，所以，zmin是所有多邊形頂點的最小z值，zmax是所有多邊形頂點的最大z值。與此類似定義多邊形的x和y范圍，則將x、y和z范圍的交集稱為多邊形的范圍或包圍盒。在投影坐標系XYZ中，投影方向是Z軸的負方向，因此z值大者離觀察點更近。記zmin(P)、zmax(P)分別為多邊形P的各個頂點z坐標的最小值與最大值，排序算法如下： 第一步：將場景中所有多邊形存入一個線性表

4、（數(shù)組或鏈表）中，記為L；第二步：如果L中僅有一個多邊形，算法結束；否則，根據(jù)每個多邊形的zmin對它們預排序。不妨假定多邊形P落在表首，即zmin(P)為最小。再記Q為L P（表中其余多邊形）中任意一個；第三步：判別P，Q之間的關系，有如下二種：（1）如果對所有的Q，有zmax(P)zmin(Q)，則需進一步判別： 若P、Q的投影P、Q的包圍盒不相交，則P、Q在表中的次序不重要，令L = L P，返回第二步；否則進行下一步。 若P的所有頂點位于Q所在平面的不可見的一側，則當前的P、Q關系正確，令L = L P，返回第二步；否則進行下一步。 若Q的所有頂點位于P所在平面的可見的一側，則當前的P

5、、Q關系正確，令L = L P,返回第二步；否則進行下一步。 對P、Q的投影P、Q求交，若P、Q不相交，則P、Q在表中的次序不重要，令L = L P，返回第二步；否則，在它們所相交的區(qū)域中任取一點，計算P、Q在該點的深度值，如果P的深度小，則P、Q關系正確，令L = L P，返回第二步；否則，交換P、Q，返回第三步。Z緩沖區(qū)算法由來： 幀緩沖器 保存各像素顏色值 z緩沖器 -保存各像素處物體深度值 z緩沖器中的單元與幀緩沖器中的單元一一對應Z緩沖區(qū)(Z-Buffer)算法 算法的基本思想 基本思想：先將FB（幀緩沖區(qū)，用于存貯各像素點的顏色和亮度值）中全部存放背景色，ZB（深度緩沖區(qū)，用于存貯

6、對應于該像素點的z座標值）中所有單元的初始值置為最小值。在把顯示對象的每個面上每一點的屬性（顏色或灰度）值填入幀緩沖區(qū)相應單元前，要把這點的z坐標值和ZB中相應單元的值進行比較，檢查當前多邊形的深度值是否大于該像素原來的深度值。如果大于，說明當前多邊形更靠近觀察點，用它的顏色替換像素原來的顏色，同時ZB中相應單元的值也要改成這點的z坐標值；否則，說明在當前像素處，當前多邊形被前面所繪制的多邊形遮擋了，是不可見的，像素的顏色值不改變。對顯示對象的每個面上的每個點都做了上述處理后，便可得到消除了隱藏面的圖。 算法的描述for(x0;xxmax;x+) for (y0;yZB(x,y) 用z(x,y

7、)替換ZB(x,y)的值; 用多邊形在(x,y)處的顏色值替換FB(x,y)的值； Z緩沖區(qū)算法優(yōu)點：簡單穩(wěn)定，利于硬件實現(xiàn)缺點：1）需要一個額外的Z緩沖區(qū) 2）在每個多邊形占據(jù)的每個像素處都要計算深度值，計算量大掃描線Z緩沖區(qū)算法由來：Z緩沖器算法中所需要的Z緩沖器容量較大，為克服這個缺點可以將整個繪圖區(qū)域分割成若干個小區(qū)域，然后一個區(qū)域一個區(qū)域地顯示，這樣Z緩沖器的單元數(shù)只要等于一個區(qū)域內像素的個數(shù)就可以了。如果將小區(qū)域取成屏幕上的掃描線，就得到掃描線Z緩沖器算法。掃描線Z緩沖區(qū)算法算法的基本思想 基本思想：依順序處理每一條掃描線，在處理當前掃描線時，設計一個一維數(shù)組作為當前掃描線的深度緩

8、沖區(qū)（ZB）。首先找出掃描線與投影到屏幕上的所有多邊形的相交區(qū)間，對每一個相交區(qū)間上的各像素利用連貫性計算其深度z值，并與ZB中的值比較，以決定各區(qū)間點的像素顏色，并將之寫入幀緩沖區(qū)（FB）。算法的描述 y=yi； for(x0;xZB(x, yi) 用z(x,yi)替換ZB(x, yi)的值; 用 (x, yi)處的顏色值替換FB(x, yi)的值； 光線追蹤算法算法的基本思想 基本思想：從視點出發(fā)，沿投影方向（光線方向）發(fā)出射線，此射線穿過觀察屏幕的像素與場景中的物體相交。計算該射線與物體表面的交點，離像素最近的交點所在面的顏色即為該像素的顏色；如果沒有交點，說明沒有多邊形的投影覆蓋此像素

9、，則用背景色作為該像素的顏色。 算法的描述 for(x0;xxmax;x+) for (y0;yymax;y+) 形成通過該屏幕像素(x,y)的射線； for（每個多邊形） 將射線與該多邊形求交點； if (有交點） 以最近交點所屬多邊形的顏色顯示像素(x,y) else 以背景色顯示像素(x,y)； 繪 制 光照明模型模擬復雜逼真的光照明現(xiàn)象將生成真實圖形或圖像的過程稱為繪制簡單的光照模型光線在物體之間的傳播方式由光源發(fā)出的光到達物體表面后，產(chǎn)生反射和折射。由光源發(fā)出的光稱為直接光，物體對直接光的反射或折射稱為直接反射和直接折射，相對的，把物體表面間對光的反射和折射稱為間接光，間接反射，間接

10、折射光線跟蹤算法基礎最基本的光線跟蹤算法是跟蹤鏡面反射和折射。從光源發(fā)出的光遇到物體的表面，發(fā)生反射和折射，光就改變方向，沿著反射方向和折射方向繼續(xù)前進，直到遇到新的物體光源發(fā)出光線，經(jīng)反射與折射，只有很少部分可以進入人的眼睛實際光線跟蹤方向與光傳播的方向相反視線跟蹤-由視點與象素(x，y)發(fā)出一根射線，與第一個物體相交后，在其反射與折射方向上進行跟蹤四種光線定義在光線跟蹤算法中，有如下的四種光線視線是由視點與象素(x，y)發(fā)出的射線陰影測試線是物體表面上點與光源的連線反射光線，視線反射方向光線折射光線，視線折射方向光線光強計算光線V與物體表面交與點P時，光在點P對光線V方向的貢獻分為三部分由

11、光源產(chǎn)生的直接的光線照射光強，是交點出處的局部光強反射方向上由其他物體引起的間接光照光強，由 計算， 通過對反射光線的遞歸跟蹤得到折射方向上由其他物體引起的間接光照光強，由 計算， 通過對折射光線的遞歸跟蹤得到把上述三部分光強相加，就是該條光線V在P點處的總的光強光照模型公式：其中：N、L分別為沿表面法線和光源入射方向的單位矢量。 R 、S分別為沿反射方向和視線方向的單位矢量。 Ia為入射的泛光強。 Il為入射光強度。 Ka為泛光的漫反射常數(shù)（ 0Ka 1） Kd為入射光的漫反射常數(shù)（ 0Kd 1） Ks為反射率曲線。 d為透視點離物體的距離。 n為冪次，用來模擬反射光的空間分布。 k為任意常

12、數(shù)，當視點在無窮遠時。例 題反射光視線L入射光NRSL在右圖中，表面P點的法線和入射光線與視線矢量分別為：N=j L=-i+2j-k S=i+1.5j+0.5k R=i+2j+k設畫面中只有一個物體，d=0,k=1;點光源比泛光源亮10倍，Ia=1Il=10;物體表面同金屬表面一樣發(fā)亮，絕大多數(shù)光被鏡面反射。假設Ks=0.8,Kd=Ka=0.15,n=5,由于Ks+Kd=0.95，表明有5%的光被物體表面吸收。請計算光照模型是多少？光線跟蹤算法 光線跟蹤算法實際上是光照明物理過程的近似逆過程光線跟蹤基本過程可以跟蹤物體間的鏡面反射光線和規(guī)則透射，模擬了理想表面的光的傳播終止條件實際的算法進行過

13、程中，不可能進行無窮的光線跟蹤算法應用意義上的終止條件該光線未碰到任何物體該光線碰到了背景光線在經(jīng)過許多次反射和折射以后，就會產(chǎn)生衰減，光線對于視點的光強貢獻很小光線反射或折射次數(shù)即跟蹤深度大于一定值算法偽碼表示從視點出發(fā)，對于視屏上的每一個象素點，從視點作一條到該象素點的射線，調用下面的算法函數(shù)就可以確定這個象素點的顏色RayTracing(start, direction, weight, color)if ( weight MinWeight )color = black; else計算光線與所有物體的交點中離start最近的點；if ( 沒有交點 ) color = black;els

14、e = 在交點處用局部光照模型計算出的光強； 計算反射方向 R； RayTracing(最近的交點,R, weight* , ); 計算折射方向 T； RayTracing(最近的交點,T,weight* , );color = + + ;光線與物體求交對于反射光線與折射光線的方向計算問題Whitted光透射模型中的計算方法光線跟蹤算法中需要用到大量的求交運算，因而求交運算的效率對于整個算法的效率影響很大光線與物體的求交時光線跟蹤算法的核心光線與球的求交球是光線跟蹤算法中最常用的體素很容易進行光線與球的相交判斷，球又常常用來作為復雜物體的包圍盒 為光線的起點坐標， 為光線的方向，已經(jīng)單位化。

15、為球心坐標，R為球的半徑求交前提條件代數(shù)解法由起點發(fā)出的光線參數(shù)方程球面的隱式方程：代入合并有：解方程有 ，光線與球無交 ，光線與球相切，t=B/2 ，光線與球有兩個交點t0，交點無效t代入光線參數(shù)方程，可求得交點坐標交點的坐標交點處的法向量代數(shù)法求交點和法向量總共需要17次加減運算、17次乘法運算、1次開方運算和3次比較操作幾何解法幾何法求交示意基本步驟計算光線起點到球心的距離平方 光線的起點在球內，光線與球有且僅有一個交點 光線的起點在球外，光線與球有兩個交點或一個切點或沒有交點計算光線起點到光線離球心最近點A距離當光線的起點在球外，若 ，則球在光線的背面，光線與球無交點計算半弦長的平方，來判定交點的個數(shù) ，光線與球無交 ，光線與球相切 ，光線與球有兩個交點計算光線起點到光線與球交點的距離來計算交點的位置t代入光線的參數(shù)方程，可以得到交點的位置交點的坐標交點處的球面法向幾何法求交點和法向總共需要16次加減運算、13次乘法運