计算机图形学消隐算法ppt课件

消隐算法 主要内容 一 概述二 消隐的基本技术三 凸多面体消除隐藏线四 消除隐藏面 1 用计算机生成三维形体的真实图形 是计算机图形学研究的重要内容之一 在使用显示设备描绘三维图形时 必须把三维信息作某种投影变换 在二维显示表面上绘制出来 由于投影变换失去了深度信息 往往导致图形的二义性 要消除二义性 必须在绘制时消隐实际不可见得线和面 即消隐 经过消隐的投影图称为物体的真实图形 一 概述 2 消隐不仅与消隐对象有关 还与观察者的位置有关 如图所示 由于视点的位置不同 物体的可见部分也不同 消隐与观察者的位置关系 3 按消隐的对象分类线消隐 Hidden line 面消隐 Hidden surface 按消隐空间分类物体空间消隐算法图像空间消隐算法 4 线消隐 Hidden line 消隐对象是物体上不可见的线 一般用于线框图 当用笔式绘图仪或其它画线设备绘制图形时 主要使用这种算法 面消隐 Hidden surface 消隐对象是物体上不可见的面 一般用于填色图 当用光栅扫描显示器绘制图形时 主要使用这种算法 早期图形显示器是用线条表示图形 消隐主要是消隐线问题 使用光栅显示器后 物体可用连续变化的色调来描述 消隐算法的研究渐渐转向消隐面的问题 5 第一种是物空间算法 它以三维场景中的物体对像作为处理单元的 在所有的对像之间进行比较 除去完全不可见的的物体和物体上不可见的部分 常用于线框表示立体的线隐藏 也用于面隐藏 for 场景中的每一个物体 将其与场景中的其它物体比较 确定其表面的可见部分 显示该物体表面的可见部分 隐藏线 面 的消除的两种基本算法 特点是 算法可以达到相当高的精度 6 第二种是像空间算法 它以构成图形的每一个像素为处理单元的 确定场景中哪些表面的像素相对于观察点而言是可见的 用该表面的颜色填充该像素 常用于隐藏面 特点是 算法精度低 只能达到屏幕精度为止 但速度往往更高 其算法是对每一个像素 在和投影点到像素的连线相交的表面中找到离观察点最近的表面用该表面上交点处的颜色填充该像素 for 窗口内的每一个像素 确定距视点最近的物体 以该物体表面的颜色来显示像素 7 算法复杂度 假设场景中有k个物体 平均每个物体表面由h个多边形构成 显示区域中有mxn个像素 则 第一种算法的复杂度为 O kh kh 第二种算法的复杂度为 O mnkh 8 物空间消隐算法 需对物体表面的h个多边形中的每个面与其余h 1个面进行比较 精确地求出物体上每个棱边或每个面的遮挡关系 算法的计算量正比于h2 即算法复杂度为 O h 2 则 k个物体的算法复杂度为 O kh 2 9 象空间消隐算法 这类算法对屏幕上的每个象素进行判断 以决定物体上哪个多边形在该象素点上是可见的 若屏幕上有m n个象素点 每个物体表面上有h个多边形 则该类消隐算法计算量正比于mnh 则 k个物体的算法复杂度为 O mnkh 10 各种消隐算法均采用一定形式的几何排序 通过排序 可搜查出位置上靠近观察者的几何元素 确定几何元素之间在位置上的遮挡关系 解决消隐计算的主要问题 各种算法都有各自的排序方法和排序次序 排序次序影响算法的效率 算法排序 11 二 消隐基本技术 为了提高消隐算法的效率 各种消隐算法常采用一些有效的消隐基本算法 利用连贯性将透视投影转换成平行投影包围盒技术背面剔除空间分割技术物体分层表示 12 物体连贯性面的连贯性区域连贯性扫描线的连贯性深度连贯性 利用连贯性 连贯性是指从一个事物到另一个事物 其属性值 如颜色值 空间位置 通常是平缓过渡的性质 例如 棱边的连贯性是指 棱边的可见性在它与其他棱边相交时才发生变换 面的连贯性是指 如果面的一部分是可见的 则一般情况下整个面都是可见的 13 物体连贯性若物体A与物体B是完全分离的 消隐时只需要比较两物体之间的遮挡关系即可 不需要对它们的表面多边形逐一进行测试 面的连贯性一张面内的各种属性值一般是缓慢变化的 可采用增量的形式对其进行计算 区域连贯性一个区域一般指屏幕上一组相邻的象素 他们通常为同一个可见面所占据 可见性相同 扫描线的连贯性在相邻两条扫描线上 可见面的分布情况相似 深度连贯性同一表面上的相邻部分深度是相近的 而占据屏幕上同一区域的不同表面的深度不同 这样只需取其上一点计算出深度值 比较该深度值便能得出结果 14 包围盒技术 一个形体的包围盒指的是包围它的简单形体 比如 2D的矩形 3D的立方块 长方体 球等 目的 避免盲目的求交测试 各物体间的比较等 一个好的包围盒要具有两个条件 包围和充分紧密包围着形体 对其的测试比较简单 例 矩形包围盒及长方体包围盒提高算法效率 15 包围盒不相交 线段和多边形也不相交 线段完全可见 无需就线段和多边形的遮挡关系进行进一步判断 可推广到面与面的遮挡快速判断 例如 两个空间多边形A B在投影平面上的投影分别为A B 因为A B 的矩形包围盒不相交 则A B 不相交 无须进行遮挡测试 右图 包围盒相交 投影也相交 包围盒相交 投影不相交 16 背面剔除 外法向外法向与投影方向 观察方向 的夹角判断 前向面与后向面 背面 剔除依据 物体表面是封闭的 背面总是被前向面所遮挡 从而始终是不可见的 17 视线 法线夹角法N面的法向量V面上一点指向观察点的向量 cos 1 0 时可见 时不可见 N V N V 19 空间分割技术 依据 场景中的物体 它们的投影在投影平面上是否有相互遮挡的重叠部分 对于根本不存在相互遮挡关系的物体 应避免这种不必要的测试 方法 将投影平面上的窗口分成若干小区域 为每个小区域建立相关物体表 表中物体的投影于该区域有相交部分 则在小区域中判断哪个物体可见时 只要对本区域的相关物体表中的物体进行比较即可 20 复杂度比较 假定每个小区域的相关物体表中平均有h个物体 场景中有k个物体 由于物体在场景中的分布是分散的 显然h远小于k 根据物空间消隐方法所述 其算法复杂度为O h2 远小于O k2 21 物体分层表示 表示形式 模型变换中的树形表示方式原理 减少场景中物体的个数 降低算法复杂度 方法 将父节点所代表的物体看成子节点物体的包围盒 当两个父节点之间不存在遮挡关系时 就勿对两者的子节点做进一步测试 父节点之间的遮挡关系可以用它们之间的包围盒进行预测试 22 将透视投影转换成平行投影 消隐与透视关系较密切 体现在 1 消隐必须在投影之前完成 因为消隐需要物体三维信息 投影后只有二维信息 2 物体之间的遮挡关系与投影中心 视点 的选取有关 3 物体之间的遮挡关系与投影方式有关 在平行投影时 其遮挡关系可通过深度值来确定 23 凸多面体的每个面要么可见 要么不可见 不可能出现一个面部分可见 部分不可见 三 凸多面体隐藏线的消除 凸多面体是由若干个平面围成的物体 假设这些平面方程为 aix biy ciz di 0 i 1 2 n 调整系数的符号 使每个平面的法向量 ai bi ci 指向多面体内部 如果投影方向为 Xp Yp Zp 那么 ai bi ci Xp Yp Zp 0时 此平面为不可见面 在作图时 此面不绘制 24 凸多面体消隐的基本原理表面外法线与其可见性的关系设平面Pi上任一点的外法矢ni与该点的视线矢量vi的数量积 从而有其中 i为ni与vi之间的夹角 i 1 2 m 这里m为平面数 当cos i 0 即0 i 2时 Pi为朝前面 为可见的 应该画出 当cos i 0 即 2 i 时 Pi为朝后面 不可见 不画出或用虚线表示 视线方向与外法线的关系如图7 7 视线方向与外法线的关系 26 视线矢量平行于某一基本坐标轴时夹角的计算 当视线矢量vi平行于某一基本坐标轴时 那么平面的外法矢量n A B C 与视线矢量的夹角就是外法矢量n与某一基本坐标轴的夹角 分别用 表示 视线矢量平行X Y Z轴时平面的外法矢量n A B C 与坐标轴的夹角 27 当视线矢量平行Z轴时 有同理 若视线矢量平行X轴时 某平面的可见性由该平面外法矢量n在X轴的方向分量A所决定 若视线矢量平行y轴时 某平面的可见性由该平面外法矢量n在Y轴的方向分量B所决定 28 平面多边形的外法矢量的计算为了判别物体上各表面是朝前面还是朝后面 需求出各表面 平面多边形 指向物体外侧的法矢量 如图所示 物体表面外法矢量 29 在图中 平面P1P2P3的外法矢量 任意多边形法矢量的算法方法如下 设法矢量 三个方向分量为 式中 m为顶点号 若i n 则j i 1 否则i m j 1 30 为避免在程序中出现两种计算外法矢量的方法 建议凸多边形也采用该算法进行计算 多边形所在的平面方程可写成 其中 为平面上任意一点 31 算法实现的一般步骤根据表面的数据结构 取顶点数据 计算表面的外法线矢量 计算外法线在投影方向上的分量的值 根据分量的值判断表面的可见性 若表面可见画出该表面 否则处理下一个表面 32 计算平面法向量 已知平面上三个点的坐标为 x1 y1 z1 x2 y2 z2 x3 y3 z3 其顺序符合右手规则 其大姆指所指方向为该平面的法向量 a b c 则 a y2 y1 z3 z1 y3 y1 z2 z1 b z2 z1 x3 x1 z3 z1 x2 x1 c x2 x1 y3 y1 x3 x1 y2 y1 33 如 投影面为XOY面 投影方向从 0 0 10 到 10 10 0 即 10 10 10 斜投影 0123面 0 0 1 10 10 10 10不可见4567面 0 0 1 10 10 10 10可见0145面 0 1 0 10 10 10 10不可见2367面 0 1 0 10 10 10 10可见0374面 1 0 0 10 10 10 10可见1256面 1 0 0 10 10 10 10不可见 34 实体模型数据结构之一 x array 0 100 100 0 0 100 100 0 y array 0 0 200 200 0 0 200 200 z array 0 0 0 0 300 300 300 300 line p array 0 1 2 3 0 7 6 5 4 7 1 5 6 2 1 0 3 7 4 0 6 7 3 2 6 4 5 1 0 4 face s array 0 5 10 15 20 25 face e array 4 9 14 19 24 29 面表 线表 顶点表 35 1 画家算法 深度排序算法 是同时运用物空间与像空间算法的操作 在物空间和像空间中完成排序 在像空间中完成扫描转换 画家的作画时 先涂背景色 然后由远及近的将景物画上 顺序暗示出所画物体之间的相互遮挡关系 所以称为画家算法 算法基本原理 1 先把屏幕置成背景色 2 将场景中的物体的各个面按其距观察点的远近进行排序 结果放在一张线性表中 线性表构造 距观察点远的优先级低 放在表头 距观察点近的优先级高 放在表尾 该表称为深度优先级表 3 然后按照从远到近 从表头到表尾 的顺序逐个绘制物体表面 也称 表优先级算法 四 消除隐藏面 36 深度优先级表的建立 多边形优先级的考虑首先对一个简单的画面 可以直接建立一个确定的深度优先表如图 a 所示 深度方向上无重叠 当画面略微复杂一点 却无法按简单的Z向排序建立确定的深度优先表 以确定每一个多边形的优先级 如图 b 所示 深度方向上有重叠 37 二 投影重叠判断 测试按照难度递增顺序排列 1 P和Q在oxy平面上投影的包围盒在x方向上不相交 2 P和Q在oxy平面上投影的包围盒在y方向上不相交 3 P在Q之后 P的各顶点均在Q的远离视点的一侧 4 Q在P之前 Q的各顶点均在P的靠近视点的一侧 5 P和Q在观察平面oxy上的投影不相交 上面5项只要有一项成立 P就不遮挡Q 不需要重新排序 38 对于1 2两种情况 可利用包围盒技术测试 对于3 4两种情况 可根据 内外法 测试 即将S面的顶点坐标代入R面的方程 AX BY CZ D 检查结果值的符号 一般使建立的平面方程的外法线方向正对着视点 如果结果值小于零 则表示S面在R面的内侧 即S面位于R面的后面 结果值大于零 则表示S面在R面的外侧 即S面位于R面的前面 测试1至4均为假 则需执行测试5 在XY平面上利用直线方程计算两表面边界的交点 但两表面在坐标范围x y z方向上均重叠 也有可能不相交 如图所示 39 对于某一重叠表面 上述五项测试均不成立 则需在有序表中调换两个面的位置 调换两个面的位置后 需要对调换过顺序的表面重复上述5项测试 40 对于两个或多个表面循环遮挡 该算法可能导致无限循环 此时 算法反复将重叠表面的位置进行组合 为避免死循环 可对调至更远处的表面进行标识 执行重排序后 若某个面的位置需再次交换 则表明存在交叉覆盖的情况 如图所示 将P沿Q所在平面分割成两部分P1和P2 从表中去掉原多边形P 而将P的这两个新的部分插入原表中的适当位置 使其仍保持按Zmin排序的性质 对新形成的表 重新执行第二步 41 无法直接建立正确的深度优先表 解决方法是沿多边形所在平面间的交线循环分割这些多边形 42 排序计算量大 多边形相交或循环重叠时 必须分割多边形 画家算法的不足 43 x Array 0 80 80 0 0 80 80 0 y Array 0 0 80 80 0 0 80 80 8个顶点的X Y Z坐标z Array 0 0 0 0 80 80 80 80 line p Array 0 1 2 3 0 7 6 5 4 7 1 5 6 2 1 0 3 7 4 0 6 7 3 2 6 4 5 1 0 4 face s Array 0 5 10 15 20 25 face e Array 4 9 14 19 24 29 Fori 0To7xx i x i Cos ry z i Sin ry yy i x i Sin ry Sin rx y i Cos rx z i Cos ry Sin rx zz i x i Sin ry Cos rx y i Sin rx z i Cos ry Cos rx Nexti 各顶点绕X轴和Y轴的旋转变换Fori 0To5face zmax i 0Forj face s i Toface e i 1Ifzz line p j face zmax i Thenface zmax i zz line p j NextjNexti 求各面最大Z坐标 44 Fori 0To5L iForm i 1To5If face zmax m i Thenk face s i face s i face s L face s L kk face e i face e i face e L face e L kk face zmax i face zmax i face zmax L face zmax L kEndIfNexti 对面表根据最大Z坐标从小到大排序 face s Array 0 5 10 15 20 25 face e Array 4 9 14 19 24 29 face zmax Array 68 90 54 90 90 22 face s Array 25 10 0 5 15 20 face e Array 29 14 4 9 19 24 face zmax Array 22 54 68 90 90 90 45 Fori 0To5 多边形面循环ymin 10000 ymax 0Forj face s i Toface e i 1If yy line p j ymax Thenymax yy line p j Next 计算面多边形顶点的最大最小值Forh yminToymax 扫描线循环k 0Forj face s i Toface e i 1 面多边形的边循环IfInt yy line p j 1 Int yy line p j Thent h yy line p j 0 5 yy line p j 1 yy line p j If t 0Andt 1 Thenxjd k xx line p j xx line p j 1 xx line p j tyjd k h k k 1 计算扫描线与边的交点EndIfEndIfNextPicture1 Line xjd 0 yjd 0 xjd 1 yjd 1 RGB face s i 10 50 100 NextNext 46 正轴测投影 一个面正投影 x Array 0 50 50 0 0 y Array 0 0 50 50 0 z Array 50 50 50 50 50 fori 0to3picture1 line x i y i x i 1 y i 1 next 47 xx i x i Cos ry z i Sin ry yy i x i Sin ry Sin rx y i Cos rx z i Cos ry Sin rx zz i x i Sin ry Cos rx y i Sin rx z i Cos ry Cos rx x Array 0 50 50 0 0 y Array 0 0 50 50 0 z Array 50 50 50 50 50 fori 0to4xx i x i Cos ry z i Sin ry yy i x i Sin ry Sin rx y i Cos rx z i Cos ry Sin rx zz i x i Sin ry Cos rx y i Sin rx z i Cos ry Cos rx nextfori 0to3picture1 line xx i yy i xx i 1 yy i 1 next 一个面正轴测投影 48 x Array 0 0 50 50 0 0 0 0 0 0 y Array 0 50 50 0 0 0 50 50 0 0 z Array 50 50 50 50 50 0 0 50 50 0 fs Array 0 5 fe Array 4 9 fori 0to9xx i x i Cos ry z i Sin ry yy i x i Sin ry Sin rx y i Cos rx z i Cos ry Sin rx zz i x i Sin ry Cos rx y i Sin rx z i Cos ry Cos rx nextforj 0to1fori fs j tofe j 1picture1 line xx i yy i xx i 1 yy i 1 nextendif 两个面正轴测投影 49 x Array 0 0 50 50 0 0 0 0 0 0 y Array 0 50 50 0 0 0 50 50 0 0 z Array 50 50 50 50 50 0 0 50 50 0 fs Array 0 5 fe Array 4 9 fori 0to9xx i x i Cos ry z i Sin ry yy i x i Sin ry Sin rx y i Cos rx z i Cos ry Sin rx zz i x i Sin ry Cos rx y i Sin rx z i Cos ry Cos rx nextforj 0to1c xx fs j 1 xx fs j yy fs j 2 yy fs j xx fs j 2 xx fs j yy fs j 1 yy fs j if c 0 thenfori fs j tofe j 1picture1 line xx i yy i xx i 1 yy i 1 nextendifendif 两个面正轴测投影 消隐 a y2 y1 z3 z1 y3 y1 z2 z1 b z2 z1 x3 x1 z3 z1 x2 x1 c x2 x1 y3 y1 x3 x1 y2 y1 50 2 深度缓冲器算法 Z buffer算法 Z缓冲器算法的基本思想是 将投影平面每个像素所对应的所有面片 平面或曲面 的深度进行比较 然后取离视线最近面片的属性值作为该像素的属性值 见图 Z缓冲器算法基本思想 一种典型的 也是最简单的像空间消隐算法 51 帧缓存来存放每个象素的颜色值初值可放对应背景颜色的值深度缓存来存放每个象素的深度值 初值取成z的极小值 屏幕 52 深度缓冲器算法 算法描述深度缓冲器所有单元均置为最小z值 帧缓冲器各单元均置为背景色 然后逐个处理多边形表中的各面片 每扫描一行 计算该行各像素点 x y 所对应的深度值z x y 并将结果与深度缓冲器中该像素单元所存储的深度值ZB x y 进行比较 若z ZB x y 则ZB x y z 同时将该像素的属性值I x y 写入帧缓冲器 即FB x y I x y 否则不变 53 算法描述 for v 0 v vmax v for u 0 u umax u 将帧缓冲器的第 u v 单元置为背景色 将Z缓冲器的第 u v 单元置为 1 可见的最小深度值 for 每个多边形 for 多边形在投影平面上的投影区域内的每个像素 u v 计算多边形在当前像素 u v 处的深度值d if d Z缓冲器的第 u v 单元的值 置帧缓冲器的第 u v 单元值为当前多边形颜色 置Z缓冲器的第 u v 单元值为d 54 深度缓冲器算法 深度值的计算若已知多边形的方程 则可用增量法计算扫描线每一个像素的深度 设平面方程为 则多边形面上的点 x y 所对应的深度值为 C 0 55 由于所有扫描线上相邻点间的水平间距为1个像素单位 扫描线行与行之间的垂直间距也为1 因此可以利用这种连贯性来简化计算过程 如图所示 深度计算 56 若已计算出 x y 点的深度值为zi 沿x方向相邻连贯点 x 1 y 的深度值zi 1可由下式计算 沿多边形左边界递归计算边界上各点的坐标 m为该边的斜率 沿该边的深度也可以递归计算出来 即 57 如果该边是一条垂直边界 则计算公式简化为 对于每条扫描线 首先根据公式计算出与其相交的多边形最左边的交点所对应的深度值 然后 利用图形连贯性将该扫描线上所有的后续点计算出来 所有的多边形处理完毕 即得消隐后的图形 58 优点 1 简单稳定 利于硬件实现2 Z缓冲器算法的最大优点 Z Buffer算法在象素级上以近物取代远物 形体在屏幕上的出现顺序是无关紧要的 可以轻而易举地处理隐藏面以及显示复杂曲面之间的交线 缺点 1 需要一个额外的Z缓冲器2 在每个多边形占据的每个像素处都要计算深度值 计算量大 59 3 扫描线算法 每个单元存放对应象素当前最近面的深度值 每一个扫描线用一个缓冲器 60 方程 z 100 Z 4x 12 0 4 10 10 10 10 10 12 16 20 10 10 10 10 10 12 16 20 16 20 20 61