计算机图形学-cg lesson hierarchical z-buffer and region subdivision algorithms消隐算法图像景物空间

浙江大学CAD&CG国 图像空间消 景物空间消 CAD&CG国 l消隐的基本概念(隐藏线或面消除)：相对l消隐是图形学中非常重要的一个基本问l根据算法实现时所在的坐标系，消隐算法ll CAD&CG国 for(图像中每一个像素} CAD&CG国 for(世界坐标系中的每一个物体)} CAD&CG国 l理论上，景物空间算法的计算量O(n2)小于图像空间算法O(nN)(在场景中物体个l实际应用中通常会考虑画面的连贯性，所 景物空间和图 CAD&CG国 图像空间消 景物空间消 CAD&CG国 扫描线z-buffer算法 CAD&CG国 xz CAD&CG国 xz CAD&CG国 CAD&CG国 CAD&CG国 “外部”扫描线段：直接着背景颜 “内部”扫描线段：位于一个或多个多边形内 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多条扫描线间的深度连贯性：从一条扫描 实现：通 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国 充分发 扫描线上的(深度)连贯性：逐点深度判断‡区 改进后的算法可以处理贯穿情 CAD&CG国 图像空间消 景物空间消 CAD&CG国 原则：不绘制“看不见”和“被遮挡” 方法：“快 景物深度排序：八叉树 CAD&CG国

CAD&CG国 z-buffer：记录每个像素的深度 逐像素地快 判断效率 场景：森林中树 CAD&CG国 进一步发掘各 CAD&CG国 l上一层：每一个像素是 树：MIP-Mapz-buffer

hierarchical CAD&CG国 l场景：八叉树ll层次化处理光栅化l当遇到被遮挡的物 CAD&CG国 在光栅化一个多 CAD&CG国 选择场景物体的包围盒作为根立方 递归剖分立方 CAD&CG国 光栅化该节点所属的多边形，更新层次z-按照从前向后的顺序，对八个子 CAD&CG国 层次z-buffer CAD&CG国 硬件实现层次z-buffer算法更高 硬件开 CAD&CG国 图像空间消 景物空间消 CAD&CG国 区域细分算法(图像空间算法 分而治之(DivideandConquer)：把一个 CAD&CG国 CAD&CG国 CAD&CG国 窗口内目标足够简单 CAD&CG国 分 相 包 包 CAD&CG国 x

CAD&CG国 利用包围盒技术判断分离关 P不与窗口相交，P不与其子窗口相 P包含窗口，P包含 二维多边形裁 CAD&CG国 区域细分法 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外的裁剪多边删除内列中所有位于多边