【正文】 z )( ????C≠0 深度值的計(jì)算 （ 41） （ 42） ? 若已計(jì)算出（ x， y）點(diǎn)的深度值為 zi，沿 x方向相鄰連貫點(diǎn)（ x+1， y）的深度值 zi+1可由下式計(jì)算： ? 沿多邊形左邊界遞歸計(jì)算邊界上各點(diǎn)的坐標(biāo)： ? m為該邊的斜率，沿該邊的深度也可以遞歸計(jì)算出來，即： CAzCDByxAzii ????????])1([1mxx ii11 ???CBmAzCDyBmxAz iiii??????????])1()1([1（ 43） （ 44） （ 45） ? 如果該邊是一條垂直邊界，則計(jì)算公式簡(jiǎn)化為： ? 對(duì)于每條掃描線，首先根據(jù)公式（ 45）計(jì)算出與其相交的多邊形最左邊的交點(diǎn)所對(duì)應(yīng)的深度值，然后，該掃描線上所有的后續(xù)點(diǎn)由（ 43）式計(jì)算出來 ? 所有的多邊形處理完畢，即得消隱后的圖形 CBzzii ???? 1（ 46） 缺點(diǎn)： (1) ZB和 CB兩個(gè)緩存數(shù)組占用的存儲(chǔ)單元太多 ，需要有一個(gè)較大容量的 Z—Buffer (2) 在每個(gè)多邊形占據(jù)的每個(gè)像素處都要計(jì)算深度值，計(jì)算量大 掃描線算法 在多邊形填充算法中，活性邊表的使用取得了節(jié)省運(yùn)行空間的效果。若是，將多邊形 PB從 M中去掉，將 PBout加入到 M中，轉(zhuǎn)（ 4）；否則，將多邊形 PAout放入 M中， L置空，轉(zhuǎn)（ 2） （ 6）掃描轉(zhuǎn)換集合 N中的多邊形 基本算法 觀察者 深度緩存 (Zbuffer)算法 深度緩存 (Zbuffer)算法 ?由來 ： 幀緩沖器 – 保存各像素顏色值 (CB) z緩沖器 –保存各像素處物體深度值 (ZB) z緩沖器中的單元與幀緩沖器中的單元一一對(duì)應(yīng) （創(chuàng)建一個(gè)數(shù)組， 數(shù)組的大小和屏幕的分辨率有關(guān)，等于橫向象素?cái)?shù) m和縱向象素?cái)?shù) n的乘積 ） ?思路 ： 先將 z緩沖器中個(gè)單元的初始值置為 +Zmax (大于場(chǎng)景中的所有 Z值 )。 ⑷ 比較裁剪多邊形與各個(gè)內(nèi)部多邊形的深度，檢查裁剪多邊形是否是離視點(diǎn)最近的多邊形。在同一投影點(diǎn)上，離視線近的對(duì)象會(huì)擋住離視線遠(yuǎn)的對(duì)象。以上算法適合任何平面多邊形 計(jì)算方法 : 凸多面體消隱的基本原理 – 表面外法線與其可見性的關(guān)系 – 設(shè)平面 Pi上任一點(diǎn)的外法矢 ni與該點(diǎn)的視線矢量 vi的數(shù)量積： – 從而有 – 其中 θi為 ni與 vi之間的夾角， i=1， 2， …， m，這里 m為平面數(shù) iiiii vnvn ???c o s? 當(dāng) ，即 時(shí)， Pi為朝前面，為可見的，應(yīng)該畫出； ? 當(dāng) ，即 時(shí)， Pi為朝后面，不可見，不畫出或用虛線表示。此類算法通常用于 消除隱藏面 ?若顯示區(qū)域中有 m n 個(gè)像素，則其計(jì)算復(fù)雜度為O(mnk) 算法描述如下： for (窗口內(nèi)的每一個(gè)像素 ) {確定距觀察點(diǎn)最近的物體，以該物體表面的顏色來顯示像素； } 面消隱示例 平面多邊形的外法矢量 3221 pppp ??n為了判別物體上各表面是朝前面還是朝后面 ， 需求出各表面 (平面多邊形 )指向體外的法矢量 。最后，對(duì)這些區(qū)間進(jìn)行求并集運(yùn)算，即可確定總的隱藏子線段的位置，余下的則是可見子線段 （右圖） ? 包圍盒 – 任意一個(gè)形體的能夠包圍它的最小簡(jiǎn)單外圍形體 ? 一個(gè)好的包圍盒要具有兩個(gè)條件 ? 包圍盒充分緊密包圍著形體 ? 包圍盒本身為簡(jiǎn)單形體，對(duì)其的測(cè)試比較簡(jiǎn)單 采用某些手段減少運(yùn)算復(fù)雜度 – 應(yīng)用 — 避免盲目求交 ? 例如：兩個(gè)空間多邊形 A、 B在投影平面上的投影分別為 A’， B’ ，因?yàn)?A’ 、 B’的矩形包圍盒不相交，則 A’、 B’不相交，無須進(jìn)行遮擋測(cè)試。用區(qū)域排序算法消隱，需要用到一個(gè)多邊形裁剪算法 區(qū)域排序算法（ 1） 面消隱 ? 當(dāng)對(duì)兩個(gè)形體相應(yīng)表面的多邊形進(jìn)行裁剪時(shí)，我們稱用來裁剪的多邊形為裁剪多邊形，另一個(gè)多邊形為被裁剪多邊形 ? 算法要求多邊形的邊都是有向的，不妨設(shè)多邊形的外環(huán)總是順時(shí)針方向的，并且沿著邊的走向，左側(cè)始終是多邊形的外部，右側(cè)是多邊形的內(nèi)部 ? 若兩多邊形相交，新的多邊形可以用“遇到交點(diǎn)后向右拐”的規(guī)則來生成 ? 于是被裁剪多邊形被分為兩個(gè)乃至多個(gè)多邊形；我們把其中落在裁剪多邊形外的多邊形叫作外部多邊形；把落在裁剪多邊形之內(nèi)的多邊形叫作內(nèi)部多邊形 區(qū)域排序算法（ 2） 算法的步驟： ⑴ 進(jìn)行初步深度排序，如可按各多邊形 z向坐標(biāo)最小值 (或最大值、平均值 )排序。否則對(duì) M中的所有多邊形按 Zmin(P)由小到大（由近到遠(yuǎn)）的順序進(jìn)行預(yù)排序，放入 L中 （ 3）從 L中取出當(dāng)前深度（ z值）最小的多邊形，即最近的多邊形作為裁剪多邊形 PA，求出該多邊形在 xoy面上的投影多邊形 A。 ⑷ 對(duì)每個(gè)多邊形重復(fù) ⑵ 、 ⑶ 兩步 。 2）從下到上依次對(duì)每一條掃描線進(jìn)行消隱處理，對(duì)每條掃描線上的點(diǎn)置初值， Z值 Z(x)取為最大，顏色 I(x)取為背景色。此時(shí)，物體表面會(huì)發(fā)生兩類反射，即 漫反射 和 鏡面反射 ? 在直射照明下，物體表面 P點(diǎn)的漫反射和鏡面反射的模型根據(jù) Lambert定律和 BuiTuong Phong的實(shí)驗(yàn)提出 (圖 )。則 V的法線 nV取做： nV = (a1+a2+…+ an)i+(b1+b2+…+ bn)j+(c1+c2+…+ )k Step2: 用光照模型求得 V點(diǎn)的亮度 Step3:由兩頂點(diǎn)的亮度，插值得出棱上各點(diǎn)的亮度。接著算法取視線方向?qū)拔镞M(jìn)行第二次消隱 方法 2：曲面細(xì)節(jié)多邊形方法 方法 3： z緩沖器方法 ? 為了方便地在光滑曲面片上生成陰影 ， Williams提出一種 z緩沖器方法 首先，利用 z緩沖器消隱算法取光源為視點(diǎn)對(duì)景物進(jìn)行消隱。這個(gè)過程可以表示為一棵光線跟蹤樹 ? 右圖示出與上圖對(duì)應(yīng)的一棵光線跟蹤樹 ,光強(qiáng)計(jì)算方法是以后序周游的算法遍歷這棵光線跟蹤樹 光線跟蹤樹 ? 對(duì)于樹上任意一結(jié)點(diǎn) Pi , Pi處沿視線方向 V射去的光強(qiáng) I為 I=IG+WP?Ir+TP?It Pi點(diǎn)所受到的光照 跟蹤光線結(jié)束 條件 ? 光線與光源相交 ? 光線未碰到任何物體 ? 光線與背景相交 ? 被跟蹤的光線對(duì)著交點(diǎn)處光強(qiáng)度作用趨近于 0 ? 光線反射或折射次數(shù)即跟蹤深度大于一定值 光線跟蹤方法 優(yōu)點(diǎn) ： 1) 各物體之間反射的影響 ， 因此顯示效果十分逼真 2) 有消隱功能 3) 有影子效果 4) 該算法具有并行性質(zhì) Witted繪制的光線跟蹤效果 光線與實(shí)體的求交 ? 光線跟蹤算法中 75%以上的工作量用于求交計(jì)算 ?進(jìn)行求交運(yùn)算之前，常用包圍球或包圍盒的方法對(duì)物體進(jìn)行是否與光線相交的預(yù)測(cè)。 表面圖案的描繪 將一幅平面圖案描繪到物體表面上的過程如下：