【正文】 量大 掃描線算法 在多邊形填充算法中，活性邊表的使用取得了節(jié)省運(yùn)行空間的效果。 ⑶ 若 zij?ZB(i, j)， 則 ZB(i, j)=zij， CB(i, j)=多邊形 ?的顏色 。若是，將多邊形 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值 )。 X O Y Z 區(qū)域排序 ? 多邊形區(qū)域排序算法可簡(jiǎn)單描述如下： （ 1）初始化：將場(chǎng)景中的多邊形全部放入集合 M中，集合 N、 L置為空 （ 2）若集合 M中的多邊形的個(gè)數(shù)為 1，則從集合 M中取出該多邊形放入 N中，轉(zhuǎn)（ 6）。 ⑷ 比較裁剪多邊形與各個(gè)內(nèi)部多邊形的深度，檢查裁剪多邊形是否是離視點(diǎn)最近的多邊形。 – 對(duì)于后兩種情況需要進(jìn)一步判別線段的可見性 基本思想： 在圖像空間中，將待顯示的所有多邊形按深度值從小到大排序，用前面可見多邊形去切割后面的多邊形，最終使得每個(gè)多邊形要么是完全可見，要么是完全不可見。在同一投影點(diǎn)上，離視線近的對(duì)象會(huì)擋住離視線遠(yuǎn)的對(duì)象。那么多邊形的邊把線段投影的參數(shù)區(qū)間 [0, 1]分割成若干子區(qū)間，每個(gè)子區(qū)間對(duì)應(yīng)一條子線段 (如下圖所示 )，進(jìn)一步判斷各子線段的隱藏性 線段投影被分為若干子線段 可見子線段的確定 ? 把各個(gè)子線段與所有需要比較的多邊形依次進(jìn)行 隱藏性判別 ，記下各條隱藏子線段的位置。以上算法適合任何平面多邊形 計(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為朝后面，不可見，不畫出或用虛線表示。 執(zhí)行這種功能的算法 ， 稱為 消隱算法 例如： 基本概念 沒有消隱的圖形具有二義性： (a) 立方體的線框圖； (b) 頂點(diǎn) B離視點(diǎn)最近時(shí)的消隱； (c) 頂點(diǎn) C離視點(diǎn)最近時(shí)的消隱 B C ? 消隱的對(duì)象是三維物體 ? 消隱結(jié)果與觀察物體有關(guān)，也與視點(diǎn)有關(guān) 線框圖 消隱圖 真實(shí)感圖形 ? 如圖所示，由于視點(diǎn)的位置不同，物體的可見部分也不同： B C A D E1 E2 消隱與觀察者的位置關(guān)系 消隱的分類 ? 線消隱 (Hiddenline) 對(duì)象：線框模型 ?面消隱 (Hiddensurface) 對(duì)象：填色圖 線框模型 填色圖 ?線消隱 是以場(chǎng)景中的物體為處理單元，將一個(gè)物體與其余的 k－ 1 個(gè)物體 逐一比較 ，僅顯示它可見的表面以達(dá)到消隱的目的 此類算法通常用于 消除隱藏線 ? 假定場(chǎng)景中有 k 個(gè)物體，平均每個(gè)物體的表面由 h 個(gè)多邊形構(gòu)成，其計(jì)算復(fù)雜度為 O((kh)2) 算法描述如下： for (場(chǎng)景中的每一個(gè)物體 ) { 將該物體與場(chǎng)景中的其它物體進(jìn)行比較，確定其表面的可見部分； 顯示該物體表面的可見部分； } （示例如右圖） 線消隱示例 ?面消隱 是以窗口內(nèi)的每個(gè)像素為處理單元， 確定在每一個(gè)像素處，場(chǎng)景中的物體哪一個(gè)距離觀察點(diǎn)最近（可見的 )，從而用它的顏色來顯示該像素。此類算法通常用于 消除隱藏面 ?若顯示區(qū)域中有 m n 個(gè)像素，則其計(jì)算復(fù)雜度為O(mnk) 算法描述如下： for (窗口內(nèi)的每一個(gè)像素 ) {確定距觀察點(diǎn)最近的物體，以該物體表面的顏色來顯示像素； } 面消隱示例 平面多邊形的外法矢量 3221 pppp ??n為了判別物體上各表面是朝前面還是朝后面 ， 需求出各表面 (平面多邊形 )指向體外的法矢量 。 ? 視線方向與外法線的關(guān)系如圖 0cos ?i? 20 ?? ?? i0cos ?i? ??? ?? i2V N 平面 P θ X Y Z 視線方向與外法線的關(guān)系 ? 視線矢量平行于某一基本坐標(biāo)軸時(shí)夾角的計(jì)算 – 當(dāng)視線矢量 vi平行于某一基本坐標(biāo)軸時(shí)，那么平面的外法矢量 n{A， B， C}與視線矢量的夾角就是外法矢量 n與某一基本坐標(biāo)軸的夾角，分別用 α、 β、 γ表示視線矢量平行 X、 Y、 Z軸時(shí)平面的外法矢量 n{A， B， C}與坐標(biāo)軸的夾角 ? 當(dāng)視線矢量平行 Z軸時(shí)，有 ? 同理，若視線矢量平行 X軸時(shí)，某平面的可見性由該平面外法矢量 n在 X軸的方向分量 A所決定 ? 若視線矢量平行 y軸時(shí)，某平面的可見性由該平面外法矢量 n在 Y軸的方向分量 B所決定 222c osCBACnC????? 凹多面體的隱藏線消隱 ? 凹多面體的隱藏線消除比較復(fù)雜 ? 假設(shè)凹多面體用它的表面多邊形的集合表示 ，消除隱藏線的問題可歸結(jié)為： 對(duì)于一條空間線段 P1P2和一個(gè)多邊形 ?，判斷線段是否被多邊形遮擋 。最后，對(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è)試。為了減少比較和計(jì)算的工作量，檢驗(yàn)分兩步進(jìn)行：粗略檢驗(yàn)和精確檢驗(yàn) ? 粗略檢驗(yàn) – 設(shè)視點(diǎn)在 z軸正向無窮遠(yuǎn)處。用區(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è)多邊形；我們把其中落在裁剪多邊形外的多邊形叫作外部多邊形；把落在裁剪多