計算機圖形學-cg lesson hierarchical z-buffer and region subdivision algorithms消隱算法圖像景物空間

浙江大學CAD&CG國 圖像空間消 景物空間消 CAD&CG國 l消隱的基本概念(隱藏線或面消除)：相對l消隱是圖形學中非常重要的一個基本問l根據(jù)算法實現(xiàn)時所在的坐標系，消隱算法ll CAD&CG國 for(圖像中每一個像素} CAD&CG國 for(世界坐標系中的每一個物體)} CAD&CG國 l理論上，景物空間算法的計算量O(n2)小于圖像空間算法O(nN)(在場景中物體個l實際應(yīng)用中通常會考慮畫面的連貫性，所 景物空間和圖 CAD&CG國 圖像空間消 景物空間消 CAD&CG國 掃描線z-buffer算法 CAD&CG國 xz CAD&CG國 xz CAD&CG國 CAD&CG國 CAD&CG國 “外部”掃描線段：直接著背景顏 “內(nèi)部”掃描線段：位于一個或多個多邊形內(nèi) CAD&CG國 CAD&CG國 當掃描線與多邊形的一條邊相交 對每一個多邊形，用一個“in/out”標記 記錄當 CAD&CG國 每一個多邊形有其“in/out”標記符 CAD&CG國 掃描線與一條邊相交并且離開一個多邊 l如果離開的多邊形為被遮擋多邊形，則l如果如果離開的多邊形為非遮擋多邊形，且 CAD&CG國 CAD&CG國 poly-IDET poly-IDPT poly- A,B,C,D color in/out CAD&CG國 poly-IDET poly-IDPT poly- A,B,C,D color in/out CAD&CG國 Sb

CAD&CG國 S的標識符 III:S和T的flag值均為true，掃描線b 與掃描線II情形相

YYIx0,ba,bc,BG,BG+S,x0,ba,bc,32,13,x0,ba,32,ca,13,BG,BG+S,BG+S+T,BG+T,x0,ba,ac,12,13,a 2 CAD&CG國 AET:=IPL:=fory:=ymintoymax

--allpolys+BGe1:=first_item(AET);IPL:=while(e1.x<>MaxX)e2:=next_itempoly:=closestpolyinIPLat[(e1.x+e2.x)/2,y]draw_line(e1.x,e2.x,poly-color);updateIPL(flags);e1:=end-IPL:=NIL;updateend- CAD&CG國 l多條掃描線間的深度連貫性：從一條掃描 實現(xiàn)：通 AET和PT表實 CAD&CG國 x0,ba,23,ad,13, x0,ba,23,ec,ad,13, BG,BG+S,BG+S+T,BG+T,

SI CAD&CG國 記兩個掃描線段的深度值分別為(z1l,和(z2l,z2r)Sign(z1lz2l)和Sign(z1r CAD&CG國 充分發(fā) 掃描線上的(深度)連貫性：逐點深度判斷?區(qū) 改進后的算法可以處理貫穿情 CAD&CG國 圖像空間消 景物空間消 CAD&CG國 原則：不繪制“看不見”和“被遮擋” 方法：“快 景物深度排序：八叉樹 CAD&CG國

CAD&CG國 z-buffer：記錄每個像素的深度 逐像素地快 判斷效率 場景：森林中樹 CAD&CG國 進一步發(fā)掘各 CAD&CG國 l上一層：每一個像素是 樹：MIP-Mapz-buffer

hierarchical CAD&CG國 l場景：八叉樹ll層次化處理光柵化l當遇到被遮擋的物 CAD&CG國 在光柵化一個多 CAD&CG國 選擇場景物體的包圍盒作為根立方 遞歸剖分立方 CAD&CG國 光柵化該節(jié)點所屬的多邊形，更新層次z-按照從前向后的順序，對八個子 CAD&CG國 層次z-buffer CAD&CG國 硬件實現(xiàn)層次z-buffer算法更高 硬件開 CAD&CG國 圖像空間消 景物空間消 CAD&CG國 區(qū)域細分算法(圖像空間算法 分而治之(DivideandConquer)：把一個 CAD&CG國 CAD&CG國 CAD&CG國 窗口內(nèi)目標足夠簡單 CAD&CG國 分 相 包 包 CAD&CG國 x

CAD&CG國 利用包圍盒技術(shù)判斷分離關(guān) P不與窗口相交，P不與其子窗口相 P包含窗口，P包含 二維多邊形裁 CAD&CG國 區(qū)域細分法 CAD&CG國 圖像空間消 景物空間消 CAD&CG國 類似于Warnock算 輸出：具有任 對比Warnock CAD&CG國 -Atherton 更為一般的多邊 CAD&CG國 -Atherton 首先計算兩個多DB4 4a

S:ATA eE CAD&CG國 -Atherton DB4b4C S:Cc TA

eE CAD&CG國 -Atherton DB4b4a

S:A A Clip:eE CAD&CG國 -Atherton B4b4a

S:A Clip:A eE CAD&CG國 列：位于P外的裁剪多邊刪除內(nèi)列中所有位于多邊