《可见面判别算法剖析》由会员分享，可在线阅读，更多相关《可见面判别算法剖析（33页珍藏版）》请在金锄头文库上搜索。
1、第第9 9章章 可见面判别算法可见面判别算法 Computer Graphics 电子科技大学计算机学院 Designed by Lgs .UESTC CHP9 visible surface detection nvisible surface detection nAlgorithm type n表面定向理论 n后向面消除法（back-faces method） n深度缓冲法（depth-buffer method） nA缓冲器算法（A-buffer method） n扫描线算法（scan-line method） n深度排序算法（depth-sorting method） Designe
2、d by Lgs .UESTC n消隐的考虑： n用计算机生成三维形体的真实图形，是计算机图形学研究的重要内 容之一。在使用显示设备描绘三维图形时，必须把三维信息作某种 投影变换，在二显示表面上绘制出来。 n由于投影变换失去了深度信息，往往导致图形的二义性： n要消除二义性，必须在绘制时隐藏实际不可见的线和面，即消隐。 经过消隐的投影图称为物体的真实图形。 CHP9 visible surface detection Designed by Lgs .UESTC n不同消隐算法考虑的因素 n速度问题实时模拟，如飞行模拟 n真实度问题计算机动画，有连续色调，能产生阴影、 透明、表面纹理及反射、折
3、射等视觉效果 n在进行消隐算法的设计时，应在计算速度和图形细节之间 进行权衡，同一种算法无法兼顾 CHP9 visible surface detection Designed by Lgs .UESTC n消隐算法的实现空间（两种方法） n形体空间法(object-space method) n直接对形体定义进行处理（把形体和形体的某些 部分彼此比较，以确定哪些表面和线作为一个整 体是不可见的） n图像空间法(image-space method) n对形体投影图像进行处理（对投影平面上的每一 个象素位置逐点检测其可见性） CHP9 visible surface detection Des
4、igned by Lgs .UESTC n n 形体空间法是在定义对象的坐标系中实现的，而图像空形体空间法是在定义对象的坐标系中实现的，而图像空 间法是在对象显示的屏幕坐标系中实现的。间法是在对象显示的屏幕坐标系中实现的。 n n 形体空间法以尽可能高的精度完成几何计算，所以可以形体空间法以尽可能高的精度完成几何计算，所以可以 把图像放大许多倍而不致损害其准确性，但是图像空间把图像放大许多倍而不致损害其准确性，但是图像空间 法只能以与显示屏的分辨率相适应的精度来完成计算，法只能以与显示屏的分辨率相适应的精度来完成计算， 所以其图像的放大效果较差。所以其图像的放大效果较差。 n n 这两类算法的
5、性能特性也是不同的。形体空间法所需的这两类算法的性能特性也是不同的。形体空间法所需的 计算时间随场量中物体的个数而增加，而图像空间法的计算时间随场量中物体的个数而增加，而图像空间法的 计算时间则随图像中可见部分的复杂程度而增加。计算时间则随图像中可见部分的复杂程度而增加。 difference Designed by Lgs .UESTC nIdea（物空间算法） n表面法矢量 指向表面外部法线方向 n视线矢量 物体表面任一点指向 视点的方向 n视角 法矢量和视线矢量的夹角。 nw u v p1 p2p2 p3 p4 表面定向理论与定向法 Designed by Lgs .UESTC n判断原
6、则： n计算方法 n计算sign（cos） 表面定向理论与定向法 nw u v p1 p2p2 p3 p4 Designed by Lgs .UESTC 计算公式： 表面定向理论与定向法 Designed by Lgs .UESTC 后向面(back faces)消除法（物空间算法 ） Designed by Lgs .UESTC nEg: 左手系，view directionZ_axis X ZY Zv N(A,B,C) 容易得知： If C0back faces invisible Else visible 所谓的back face取决于 观察的方向和观察系统 的坐标系(右手和左手) 后向
7、面(back faces)消除法 Designed by Lgs .UESTC nIDEA: Depth-buffer method 像空间算法 深度缓冲器算法（Z-Buffer） Xv Zv Yv view direction (x,y) s1 s2 s3 n如图，s1平面 距离投影平面 最近，所以投 影点（x，y） 将保存s1平面 上相应点的属 性信息。 Designed by Lgs .UESTC nIDEA: Depth-buffer method n刷新缓冲器用来存储图像空间中每一个象素的属性，Z缓冲 器是用来存储图像空间中每一个可见象素相应的深度(或Z 坐标)，是一个独立的深度缓冲
8、器。 n计算将要写入刷新缓冲器象素的深度(或Z值)，并与已存储 在Z缓冲器中该象素的原来深度进行比较 ：若新象素点位于 刷新缓冲器中原象素点的前面，则将新象素点的属性写入刷 新缓冲器，并将相应的深度(Z值)也写入Z缓冲器；否则， 刷新缓冲器和Z缓冲器中的内容不变。 n本算法的实质是对给定的实质是对给定的x,y,x,y,寻找最小的寻找最小的z(x,y)z(x,y)值值。 深度缓冲器算法（Z-Buffer） Designed by Lgs .UESTC lAlgorithm description： 设置刷新缓冲器为背景颜色(或光强度) 设置Z缓冲器为最大Z值（深度最深，规范化后为1） while
9、 对每一个多边形 do begin while 对多边形中的每一个元素 do begin 计算该象素的深度z(x,y) 深度缓冲器算法（Z-Buffer） Designed by Lgs .UESTC /*比较z(x,y)与存储在Z缓冲其中该位置处的深度Z(x,y)*/ if z(x,y)Z(x,y) then 将此多边形的颜色(或光强度) 写入帧缓冲器且Z(x,y)z(x,y) end end end of algorithm *最终，Z-buffer 中保存的是可见面的深度值，而 Refresh-Buffer中保存的是这些表面的对应属性值。 深度缓冲器算法（Z-Buffer） Design
10、ed by Lgs .UESTC nProblem:计算采样点(x,y)的深度z(x,y) n设平面方程为：ax+by+cz+d=0 则 z=-(ax+by+d)/c c0 由于同一条扫描线上的y分量为常量，所以沿扫描线上的象素 x1=x+x，y1=y 处的深度为：z1 =-(ax1+by+d)/c =-(ax+by+d)/c-(a/c)x =z-(a/c)x 若x=1，则 z=z-a/c n n 所以，根据扫描向上各点前后相关性，运用增量方所以，根据扫描向上各点前后相关性，运用增量方 法计算法计算Z Z值是极为方便的值是极为方便的。 深度缓冲器算法（Z-Buffer） Designed by
11、 Lgs .UESTC n优点：简单，易于处理隐藏面以及显示曲面之间的交 贯线。被显示的画面可以任意复杂，因为图像空间的大 小是固定的，最坏情况下，计算量随画面复杂程度线性 增长。由于被显示的元素可按任意顺序写入帧缓冲器和Z 缓冲器，所以不需要进行深度排序，节省了排序时间。 n缺点：Z缓冲器需要占用大量存储空间。若被显示的画 面经变换和剪取后，Z值在一定范围内变化，则可采用固 定精度的Z缓冲器。 深度缓冲器算法（Z-Buffer） Designed by Lgs .UESTC nIdea（像空间算法） nz-buffer每个象素点只能对应一个可见面，只能处理 不透明表面。不能处理多个面的累计强
12、度值。 n对z-buffer进行扩展，使每个单元位置对应一个表面 链表。 nA的含义： nantialiased：反走样；（主要应用于物体边界） naccumulation-buffer：累计缓冲器； narea-averaged：区域平均； A缓冲器法 Designed by Lgs .UESTC n单元的深度域和强度域： n深度域：存储一个正或负的实数。为正，表示该象素具有唯一的 表面深度；为负，表示多个面共同对该象素点产生影响。 n强度域：存储表面的强度信息（深度域为正）或指针（深度域为 负）。 A缓冲器法 Id0 d0 surf 1 surf 2 surf 3 Designed by
13、Lgs .UESTC nSurf(i)中含有的数据项： nRGB强度分量 n表面的标识名 n透明性参数 n其他表面绘制参数 n深度 n覆盖度 n指向下一表面的指针 A缓冲器法 Designed by Lgs .UESTC 扫描线算法（像空间算法） nidea：判别与各条扫 描线相交的所有表面 的可见性，记算各重 叠表面的深度以找出 距离观察平面最近的 表面，将其相应属性 写入刷新缓冲器。 n避免对被遮挡区域的 采样是进一步提高扫 描线算法计算效率的 关键。 扫描线算法原理图 0x y 扫描线2 A2 A3 B1 B2 B3B4 扫描线1 扫描线3 C1 C2 C3 C4 AB C Design
14、ed by Lgs .UESTC 扫描线算法 nAlgorithm: n数据结构：三张表 n边表:保存线段端点坐标、线段斜率的倒数、和指向多边形表中对应 多边形的指针； n多边形表：包含各多边形面的平面方程系数、表面属性信息以及指向 边表的指针； n有效边表：也称活化边表，包含与当前扫描线相交的边，并将这些边 按x升序排列； n面标志Flag：on（开始，左边界）或者off（结束，右边界）； n算法关键：分割子区间，确定子区间上的唯一可见面。 n特殊情形：贯穿情形、循环遮挡情形。 Designed by Lgs .UESTC 扫描线算法 A1 扫描线算法原理图 0x y 扫描线2 A2 A3
15、B1 B2 B3B4 扫描线1 扫描线3 C1 C2 C3 C4 AB C Designed by Lgs .UESTC 扫描线算法 n贯穿情况的处理: n为了使算法能处理互相贯 穿的多边形，扫描线上的 分割点不仅应包含各多边 形的边与扫描线的交点， 而且应包含这些贯穿边界 与扫描线的交点(图中红色 为贯穿边界) (a)贯穿 Designed by Lgs .UESTC 扫描线算法 n循环遮挡情况的处理: n将多边形进行划分以消除 循环遮挡 n图中红色为划分边界 (b)循环遮挡 Designed by Lgs .UESTC 深度排序算法（画家算法） nDepth-sorting method,
16、 同时运用物空间和象空间操作。 nIdea：若场景中任何多边形在深度上均不贯穿或循环遮挡，则各多 边形的优先级顺序可完全确定。 n深度排序算法： n将多边形按深度进行排序：距视点近的优先级高，距视点远的优先级低 。 n由优先级低的多边形开始逐个对多边形进行扫描转换。 n其中的关键是将多边形按深度进行排序！ Designed by Lgs .UESTC 深度排序算法（画家算法） n深度的重叠问题 n无重叠情况：按深度 优先级顺序处理各个 表面S1 S2 Z1min Z1max Z2min Z2max s1和s2无深度重叠 Designed by Lgs .UESTC 深度排序算法（画家算法） n n 有重叠情况：对与有重叠情况：对与s s平面重叠的表面平面重叠的表面ss分别作如下测试分别作如下测试 n n 两表面在两表面在xyxy平面上投影的包围矩形无重叠；平面上投影的包围矩形无重叠； n n 相对于观察位置，面相对于观察位置，面s s完全位于重叠表面之后；完全位于重叠表面之后； n n 相对于观察位置，重叠表面完全位
