隐藏线和隐藏面的消除.ppt

第七章 隐藏线和隐藏面的消除 消隐的几个效果图 线框架结构模型它是将立体对象用轮廓线和小的元素面描述的模型 这种模型的对象立体数据输入方式简单 容易操作 可以实现描述的快速性 经常被人们使用 但是由于线框表示会出现错误理解 如下图所示 隐藏线消除或隐藏面消除 用计算机生成三维图形 首先要确定三维场景中的物体哪些部分是可见的 即确定哪些线或面是可见的 生成三维图形时只绘制可见的部分 场景中可见部分的判断过程称为可见线或面的判定 也称为隐藏线或面的消除 三维场景中物体的可见性对透视投影是相对于投影中心 对平行投影则是相对于投影方向 基于图像空间的方法 隐藏面和隐藏线的消除有两种基本的算法 用该表面上交点处的颜色填充该像素 在和投影点到像素连线相交的表面中 找到离观察点最近的表面 算法简单描述为 以构成图像的每一个像素为处理单元侧重于向屏幕投影后形成的图像 对于图像空间中的每一个像素 基于物体空间的方法 用可见表面的颜色填充相应的像素以构成图形 判定场景中的所有可见表面 对于三维场景中的每一个物体 是以三维场景中的物体对象为处理单元侧重于景中各物体之间的几何关系 假定1 垂直投影 如果不是这种情况 可对消隐的对象先作变换 变成这种情况 然后再作消隐计算 下面讨论消隐算法时 都假定投影平面是oxy平面 投影方向为负z轴方向的垂直投影 本章所讨论的消隐算法的前提假定 本章说明的各种消隐方法都假定构成对象的不同面不能相互贯穿 如图 贯穿和循环遮挡 例如用图中的虚线便可把原来循环遮挡的三个平面 分割成不互相循环遮挡的四个面 也不能有循环遮挡的情况 如果有这种情况 可把它们剖分成互不贯串和不循环遮挡的情况 假定2 7 1可见面判断的有效技术 减少求交计算的常用技术 用边界盒排除不相交的线段求交 非垂直投影转换成垂直投影 把后向面全部去掉 用边界盒排除不相交的线段求交 边界盒 一个物体的边界盒是指能够包含该物体的一个几何形状 该形状有较简单的边界 边界盒的形状可以是长方形 体 状或是圆 球 形状的 边界盒可用于投影边界盒 可用于物体本身边界盒 还可用于某一维方向上的边界盒 包围物体投影的边界盒不相交的情况 图7 3两个物体投影在 x y 平面 包围投影的边界盒 包围物体投影的边界盒相交的情况 一个好的包围盒要具有两个条件 包围和充分紧密包围着形体 对其的测试比较简单 边界盒可用于包围物体本身而不只是他们的投影 在此情况下 边界盒是三维的 边界盒也可用于在某一维方向上进行包围 以判断两个物体在该方向上是否相交 1 zmin1 zmax1 2 zmin2 zmax2 生成边界盒的一个较简单的方法 P136 判断两条直线是否相交 多边形的判定 把内法线方向背向视点的面称为前向面内法线方向指向视点的面 即外法线方向背离视点 称为后向面多面体面的顶点排序 IJFGH FABG HCDI IDEJ所在的面为前向面JEAF DEABC HGBC所在的面为后向面 去掉后向面 设多边形F的顶点为 顶点的坐标为 次序如图所示 如果是一凸多边形 可只取一个三角形计算有向面积凹多边形的内法线方向 可以计算多边形在oxy平面上投影的有向面积 有向面积sp可如下计算如果 说明其外法线方向与z轴正向的夹角 90 则F所在的面为后向面 如果 说明其外法线方向与z轴正向的夹角 90 则F所在的面为前向面 判断后向面的方法P137 背面剔除 非垂直投影转换成垂直投影 物体之间的遮挡关系与投影中心和投影方向有着密切的关系 对物体的可见性判定也和投影方式有密切的关系 如果投影为垂直投影 则多边形在oxy平面上的投影可由忽略了z坐标的顶点得到 从而可大大减少计算量 7 2多面体的隐藏线消除 讨论隐藏线消除问题 总假定它们是用线框方式来表示的 在这种方式下多面体用棱来表示 如果能把各棱上可见和不可见部分的分界点找到 消隐问题也就迎刃而解了 这些分界点都是多面体的各棱在oxy平面上投影间的交点 如图 这样 问题就转化成了在oxy平面上求很多直线的交点的计算 如果消隐对象有N条棱 用两两求交的方法求所有交点的工作量为 实际上交点个数远小于 如图的多面体有15条边 棱在oxy平面上的投影相互间只有5个交点 问题在于如何能预先知道它们是不相交的 从而把它们排挤在求交计算之外 可用7 1中方法求棱边投影的包围盒 剔除后向面技术 棱间交点只有五个 在oxy平面上求很多直线的交点的计算 要对物体一个一个来考虑 如考虑体A的显示时 对Step1 3可采用边界盒方法进行处理 下面讨论对Step4的处理技术 Step4求L和多边形E中的边的交点 确定L的可见部分 Step3对多边形G的每一条边L 从集合C中找出可能遮挡它的所有多边形E Step2对体A的每个多边形G 要从B中找出可能遮挡它的所有多边形的集合C step1确定可能遮挡体A的那些体集合B 包括体A本身 隐藏线消除 物体用线框图表示 实际计算过程 设边L的顶点是vi和vj 对边vivj和每一个可能遮挡它的多边形E 都要作下列计算和判断 以确定其隐藏关系 如果vi和vj都在多边形E所在平面靠近观察者的一侧 则E不能遮挡直线段vivj 如果vi和vj不都在多边形E所在平面靠近观察者的一侧 且vivj和E在Oxy平面的投影相交 求出其交点 只保留在vivj上的对应点在多边形E后边的交点 若无交点 这时要判断vi或vj在Oxy平面上的投影是否在E的投影的内部 若是 则vivj就会整个被E所遮挡 确定L的可见部分的具体计算过程 1 确定L顶点处与遮挡多边形的前后位置关系 设点的坐标为 若 则在多边形所在平面的前面 否则认为在多边形所在平面的后面 设多边形的顶点为 其坐标为i 1 2 L 任取三个不在一直线上的顶点 设为 记向量 则多边形E所在的平面方程为 2 确定L与遮挡多边形的交点同遮挡多边形的前后位置关系 为了判断边vivj和多边形在oxy平面的投影之间是否有交点 可首先计算求边vivj和多边形的边界在oxy平面上投影的交点 我们可以把vivj的投影线段用参数方程表示 多边形上任一边的投影用用参数方程表示 求交点时解方程 可得 只有当0 l 1和0 t 1时线段和线段vivj在oxy平面上的投影才有交点 为了判断vIvj上对应交点的点是在多边形所在平面的前面还是后面 则要去比较和 若前者大于后者 则vivj上交点的对应点在多边形所在平面的前面 否则在后面 这个信息也要和交点的信息一起保存起来 3 确定交点和多边形的关系 是进点还是出点P140 由式 7 9 可知 其中 z是指向量在z轴上的投影 判断Qi点在多边形内或外 若该射线和多边形边界的交点个数是奇数 则Qi在多边形内 否则就在多边形外 但正确地找到交点的个数并不容易 如图点Q6处 由于舍入误差 计算时可能认为Q5Q6 Q6Q7和QiF均有交点 也可能算出一个交点或没有求出交点 不同的交点数可得到完全不同的结果 需要特殊处理 4 确定Qi起点和多边形的关系 不可见阶ivord 这里要分两步来做 P140 141 Step2 确定边QiQj与遮挡多边形交点处的不可见阶 Step1 确定边QiQj顶点处的不可见阶 它是一个数字 是某个确定的点的属性 代表了边上从该点到下一个交点的部分被几个多边形遮挡 5 确定L的可见部分 首先对直线段QiQj与所有多边形交点按参数S由小到大排序确定起点Qi处的不可见阶 就是遮挡他的多边形的个数 即S0处的不可见阶Si处的不可见阶是 当其为进点时 为Si 1处的加1 为出点时 Si 1处的减1L的可见部分为SiSi 1 其中Si的不可见阶为0时 7 3区域子分算法 区域子分算法 warnock 是一种所谓分而治之的算法 整个屏幕称为窗口 分而治之算法是一个递推的四等分过程 每一次把矩形的窗口等分成四个相等的小矩形 分成的矩形也称为窗口 每一次子分 均要把要显示的多边形和窗口的关系作一判断 子分的过程 这种关系可有以下四种 即 在窗口和每个多边形的关系确定之后 有些窗口内的图形便可显示了 它们属于下列四种情况之一 所有多边形都和窗口分离这时只要把窗口内所有的象素填上背景颜色 只有一个多边形和窗口相交 或这个多边形包含在窗口内 这时先对窗口内每一象素填上背景颜色 再对窗口内多边形部分用扫描线算法填色 只有一个包围窗口的多边形窗口用包围多边形的颜色填充 如果有多个多边形和窗口的关系分别是相交 内含或包围 但是有一个包围窗口的多边形在其它多边形前面整个窗口用该包围多边形的颜色填充 对上述四种情况不成立的窗口再一分为四 分得的窗口重复上述的处理 窗口的边长越分越短 分了若干次后 窗口的边长就和一个象素的宽度一样了 这时这个窗口对应的象素的颜色可取成最靠近观察者的多边形的颜色 或和这个窗口相交的多边形颜色的平均值 7 4基于多边形的子分算法 目的是尽量减少对窗口划分的次数 用多边形的边界来对窗口作划分的方法 是对基于窗口子分算法的改进 要消隐的多边形 算法思想 对各多边形在深度方向作初步的排序把多边形序列中的第一个多边形 裁剪多边形 取为裁减窗口 多边形序列中的其它的多边形都要被此窗口裁剪 裁剪结果要建立两个多边形序列表 消隐多边形的裁剪 确定裁剪多边形 即取为窗口的那个多边形 是否比内部表中的多边形更靠近观察者如果是则内部表中的其他多边形都被其遮挡 可把该多边形区域填上裁剪多边形的颜色如果发现内部表中某多边形H比裁剪多边形更靠近观察者 这时则只好把多边形H的原始多边形 即未被裁剪时的多边形 代替原来的裁剪多边形重复上述工作 接着处理外部表中的各多边形 把外部表中的第一多边形作为裁剪窗口 重复上述工作这一过程要重复到外部表中不再有多边形为止 要消隐的多边形 消隐多边形的裁剪Ni为窗口内的多边形表 no为窗口外的多边形表 7 5Z缓冲器算法和扫描线算法 z缓冲器算法是最简单的消除隐藏面算法之一基本思想 对屏幕上每一个像素点 找到此像素投影线与所有多边形交点中离观察者最近的点 此点的属性值即为这一屏幕像素点的属性值z缓冲器是一组存贮单元其单元个数和屏幕上象素的个数相同也和帧缓冲器的单元个数相同 它们之间一一对应 算法步骤 在把显示物体的每个面上每一点的属性 颜色或灰度 值填入帧缓冲器相应单元前 要把这点的z坐标值和z缓冲器中相应单元内的值作比较 只有前者大于后者时才改变帧缓冲器的那一个单元的值 同时z缓冲器中相应单元的值也要改成这点的z坐标值 如果这点的z坐标值小于z缓冲器中相应单元的值 则说明对应象素已显示了物体上一个点的属性 该点比要考虑的点更接近观察者 这样 无论帧缓冲器或z缓冲器相应单元的值均不应改变 对显示物体的每一个面上的每一个点都做上述处理后 便可得到消除了隐藏面的图 图形消隐和生成的过程就是给帧缓冲器和z缓冲器中相应单元填值的过程 设置两个缓冲器数组 即z缓冲器和帧缓冲器 Zdepth Frame 流程 for 场景中的每一个多边形 扫描转换该多边形 for 多边形所覆盖的每一个像素点 x y 计算多边形在该像素点的深度值z x y if z x y Z buf中对应此像素点 x y 的z值 把多边形在 x y 处的深度值z x y 存入Z buf中的 x y 处 把多边形在 x y 处的亮度值存入f buf中的 x y 处 当所有的多边形都处理完后 帧缓冲器中的内容即为消除隐藏面后的图像 为了克服这个缺点 如果把这个区域取成屏幕上一行 就得到了扫描线z缓冲器算法 可把整个平面分成若干区域 一区一区来显示 这样z缓冲器的单元数只要等于屏幕上一个区域的象素个数 算法的缺点 工作量较大 显示物体的表面和象素对应的每一个点处都要计算它的z值 要很大的z缓冲器 不需要对显示物体的面预先进行排序 简单 可靠 算法的优点 扫描线z缓冲器 算法思想 对每一条扫描线来说 把相应的帧缓冲器单元置成底色 在z缓冲器中存放z的极小值 从最上面的一条扫描线开始工作 向下对每一条扫描线作处理 z缓冲器的单元数可以取成和一行上的象素数目相同 对每个多边形检查它在oxy平面上的投影和当前的扫描是否相交 若不相交 则不考虑该多边形 如果相交 则扫描线和多边形边界的交点事实上是成对地出现对每对交点中间的象素计算多边形所在平面对应点的深度 即z值 并和z缓冲器中相应单元存放的深度值作比较 若前者大于后者 则z缓冲器的相应单元内容要被求得的平面深度代替 帧缓冲器相应单元的内容也要换成该平面的属性 对所有的多边形都作上述处理后 帧缓冲器中这一行的值便反应了消隐后的图形 对帧缓冲器每一行的单元都填上相应内容后也就得到了整个消隐后的图 流程 for 每条扫描线 将扫描线帧缓冲器f buf置成背景色 将扫描线深度缓冲器Z buf置成最小值 for 每个多边形 求出该多边形与当前扫描线的相交区间 for 相交区间内每个象素点 x y 计算多边形在该处的深度值z if 多边形在该处的深度值z Z buf在该处的值 用多边形在该处的深度值z取代Z buf在该处的值 用多边形在该处的亮度值取代f buf在该处的值 用f buf的内容显示当前扫描线 上述算法要花费很多时间去计算在处理每一条扫描线时 要检查各多边形是否和该线相交还要计算多边形所在平面上很多点的z值为了使这些工作能高效率地进行 可采取类似多边形扫描转换的扫描线算法处理 扫描线z缓冲器 算法分析 数据结构 y 扫描线算法 算法数据结构 每个筒的深度和显示屏幕行数相同 根据多边形顶点Y坐标最大值来决定放入多边形Y筒的相应行数 多边形Y筒要记录多边形所在平面方程ax by cz d 0系数a b c和d 还要记录和该多边形在oxy平面上的投影相交的扫描线的条数 y 以及多边形的属性color和编号IP 建立一个多边形Y筒 每个筒的深度和显示屏幕行数相同 根据边两端点较大的Y坐标值为决定放入边Y筒的相应行数 边Y筒中记录的每一条边要保存下列信息 和该边在oxy平面上的投影相交的扫描线条数 y 该投影和相邻的两条扫描线交点的x坐标的差 x 由上到下扫描 该边所属多边形的编号IP及边的上端点x坐标的值x 建立一个边Y筒 记录在oxy平面上的投影和当前考虑的扫描线相交的多边形 例 当扫描线对应y 10或11时 多边形活化表只有一个多边形 当y 8时多边形活化表如图 表中的 y值是已经过修改的 由上到下扫描 故 y 5 和 y 7 建立一个多边形活化表 边活化表中存放多边形边界和扫描线相交的边对 例如图中y 6的扫描线上的边活化表中应有两个对边 一是和多边形 在oxy平面上的投影相交的两条边另一是和多边形 投影相交的两条边 建立一个边活化表 边活化表中每一边对要保存下列信息 1 建立多边形y筒和边y筒 初始化多边形和边的活化表为空 2 以最上面的扫描线为当前扫描线 3 对当前扫描线y 把帧缓冲器相应行置成底色 z缓冲器的各单元放z的极小值 4 检查多边形的y筒 如果有新的多边形涉及当前扫描线 则把它放入多边形活化表中 若有新的多边形加入多边形活化表 则要把该多边形在Oxy平面上的投影和扫描线相交的边对加入边活化表中 算法步骤 扫描线z缓冲器 算法步骤 5 对边活化表中的每个边对 令 对每一个满足的坐标为的像素从左到右依次进行处理 P164具体处理 6 若所有扫描线都已经处理完 则算法结束 否则选下一条扫描线为当前扫描线 转步骤3 直到所有的扫描线都处理完 7 6优先级表算法 算法思想 按多边形离观察者的远近来建立一张表距观察者远的优先级低 近的优先级高 如果这张表能正确地建立好 那么只要从优先级低的多边形开始 依次把多边形的颜色填入帧缓冲存储器中以形成该多边形的图形直到优先级最高的多边形的图形送入帧缓冲器后 整幅图就显示好了 这种算法也称为油画家算法因为油画家绘画时常先画底色 然后再一层层往上画 算法的关键 对多边形做正确的排序 下面给出一个动态的算法 1 根据每个多边形顶点z坐标的极小值zmin的大小 按由小到大对它们做初步排序 并把它们组成一个链表 2 若链表中只有一个多边形 则算法结束 否则取表头多边形为P 3 设Q为链表中P之外的任一多边形 若对所有Q都有 则P不会遮挡其它多边形 在链表中去除P 转 2 否则 若所有Q都满足下面四项中的一项 则在链表中去除P 转 2 否则 对不满足此四项条件之一的Q 交换P和Q 转 3 图7 21互相遮挡 虽然P并不遮挡Q 但它也不能使上述四项检查成立 对这样的特殊情况 需要把P沿Q平面一分为二 见图7 22 把多边形序列中原多边形P从序列中去掉 而把P分成的两个多边形加入链表中 这样可避免使多边形P和Q不断地循环进行交换 某些特殊情况 图7 22用Q所在平面把P一分为二 互相遮挡 优点 可以较好地解决透明或半透明物体的存在可采用反走样算法改善多边形边界的显示效果 用来解决动态显示问题时 可大大提高效率 图7 23视点在不同区域有不同的优先级 用来解决动态显示问题时 可大大提高效率 对飞机驾驶员着陆进行模拟训练时要显示消隐后的跑道周围情况 这时景物是不变的 仅视点发生变化 可对不同的视点位置把景物的优先级排序表预先算好 然后再用油画家算法显示图形 这样便可使消隐过程加速 实现动态显示 有了这个优先级表 不论视点在哪一个区域 均可很容易地用油画家算法得到消除隐藏面的图 优先级表 RayCastingAppel提出建立在几何光学基础之上对于包含曲面 特别是球面的场景效率高 7 7光线投射算法 基本思想观察者之所以能看见景物光源发出的光照射到物体上的结果其中一部分光到达人的眼睛引起视觉到达观察者眼中的光由物体表面反射通过表面折射或透射若从光源出发跟踪光线则只有极少量的光能到达观察者的眼睛效率低从视点或像素出发 仅对穿过像素的光线反向跟踪当光线路径到达一个可见的不透明物体的表面时停止追踪 将景物通过透视投影变换到图像空间反向跟踪一条穿过像素点的光线决定它与场景中的哪一景物表面相交交点按深度排序需求出该光线与景物表面的所有可能的交点具有最大z值的交点对应的面就是屏幕上该像素对应的可见面离视点最近该像素处的显示值由相应物体的属性决定对屏幕上所有像素都进行如上处理后 算法结束 假设视点位于z轴正向投影平面 屏幕 垂直于z轴 反向跟踪一条穿过像素点的光线 光线投射算法 for y 0 y ymax y for x 0 x xmax x 形成通过像素 x y 的投影线 for 场景中的每一个多边形 将投影线与多边形求交 if 有交点 以最近交点所属多边形的颜色显示像素 x y else以背景颜色显示像素 x y 7 8曲面的隐藏线消除 曲面方程y f x z 在表示这个曲面的线框式立体图中 也存在隐藏线的消除问题 这种曲面可由x xi constz zi const两族曲线来表示 隐藏线消除就是要去掉这两族曲线中被遮挡的部分 a 未消隐的曲面表示 b 消隐的曲面表示 消隐算法先考虑对应z zi const的一族曲线的消隐算法 如果图形显示器在水平方向有M个象素 则建立M个内存单元yu j 在这些单元是先放上初值 初值应取成小于minf x z 消隐算法 对应z zi const的一族曲线的消隐算法设zi z0 ih i 1 2 n h 0 平面z zn是最靠近观察者的从平面z zn上的曲线y f x zn 开始 对水平方向每个象素的对应x坐标值xj 计算yjn f xjn zn 若yjn yu j 则点 xj yjn zn 是可见点 并把yu j 内容换成yjn 消隐算法 对应z zi const的一族曲线的消隐算法若yjn yu j 则点 xj yjn zn 为不可见 不要改变yu j 的内容 对z zn平面上的曲线完成上述工作后 再对平面z zn 1上的曲线重复上述工作 这样按z值递减方向一条一条曲线处理过去 就得到一组消除隐藏线的曲线族了 结束