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

第8章隐藏面和隐藏线的消除 隐藏面和隐藏线的消除是计算机图形学中的一个基本问题 由于存在不透光的物体 因此阻挡了来自某些物体部分的光线到达观察者 这些物体部分成为隐藏部分 隐藏部分是不可见的 为了使计算机生成的图能真实地反映这一情况 必须把隐藏的部分从图中消除 如果不把隐藏的线或面消除 还可能发生对图的错误理解 图8 1两种理解 基于图像空间的方法以构成图像的每一个像素为处理单元 对场景中的所有表面 确定相对于观察点是可见的表面 用该表面的颜色填充该像素 该算法多用于面消隐 算法的简单描述如下 对于图像中的每一个像素 在和投影点到像素连线相交的表面中 找到离观察点最近的表面 用该表面上交点处的颜色填充该像素 隐藏面和隐藏线的消除有两种基本的算法 基于物体空间的方法是以三维场景中的物体对象为处理单元 在所有对象之间进行比较 除去完全不可见的物体和物体上不可见的部分 该算法多用于线消隐 也用于面消隐 算法的简单描述如下 对于三维场景中的每一个物体 判定场景中的所有可见表面 用可见表面的颜色填充相应的像素以构成图形 隐藏面和隐藏线的消除有两种基本的算法 假定1 隐藏线和隐藏面消除所讨论的对象是一个三维图形 消隐后要在二维空间中表示出来 因此消隐后显示的图形将和三维空间至二维空间的投影方式有关 下面讨论消隐算法时 都假定投影平面就是oxy平面 投影方向为负z轴方向的垂直投影 如果不是这种情况 可对消隐的对象先作变换 变成这种情况 然后再作消隐计算 在投影平面就是oxy平面以及投影是透视时 可用变换 4 14 4 16 式 投影是平行投影 但投影方向不是负z轴方向 则可用变换 4 21 4 23 式 如果投影平面不是oxy平面 平行投影时则先要用变换 4 36 式 透视时先要用变换 4 33 式 式 4 33 中的常数A和B应满足式 4 17 假定2 本章说明的各种消隐方法都假定构成对象的不同面不能相互贯穿 见图8 1 也不能有循环遮挡的情况 如果有这种情况 可把它们剖分成互不贯串和不循环遮挡的情况 例如用图8 2 b 中的虚线便可把原来循环遮挡的三个平面 分割成不互相循环遮挡的四个面 图8 2贯穿和循环遮挡 8 1多面体的隐藏线消除 设有多个互不相交的多面体 对它们的消隐问题 和他们的显示方式有关 讨论隐藏线消除问题 总假定它们是用线框方式来表示的 在这种方式下多面体用棱来表示 这时隐藏线便是某些不可见的棱或棱的一部分 如果能把各棱上可见和不可见部分的分界点找到 消隐问题也就迎刃而解了 这些分界点都是多面体的各棱在oxy平面上投影间的交点 见图8 3 这样 问题就转化成了在oxy平面上求很多直线的交点的计算 图8 3 8 1多面体的隐藏线消除 在oxy平面上求很多直线的交点的计算 如果消隐对象有N条棱 用两两求交的方法求所有交点的工作量为O N2 当N很大时 这个工作量是可观的 要提高算法的效率 就要设法减少求交的工作量 实际上交点个数远小于O N2 例如图8 3的多面体有15条边 如果不计棱端点处的交点 棱在oxy平面上的投影相互间只有5个交点 这说明有很多棱在oxy平面上的投影相互间并不相交 问题在于如何能预先知道它们是不相交的 从而把它们排挤在求交计算之外 8 1多面体的隐藏线消除 减少求交计算的若干方法 把后向面全部去掉用边界盒排除不相交的线段求交 在后向面被删除后 如果两个相邻的多边形的公共边都在两个多边形的凸包上 则这两个多边形不会发生一个遮挡另一个的现象 因而在考虑一个多边形的边的显示时 可以不考虑另一个多边形对它的影响 8 1多面体的隐藏线消除 去掉后向面把内法线方向背向视点的面称为前向面 如图8 3中的IJFGH FABG HCDI和IDEJ所在的面均为前向面 其余的面称为后向面 例如图8 3中JEAF和DEABC所在的面均为后向面 后向面总是看不见的 不会仅由于后向面的遮挡 而使别的棱成为不可见 因此可把后向面全部去掉 这不影响消隐结果 8 1多面体的隐藏线消除 设多边形F的顶点为v1 v2 vL 顶点vi的坐标为 xiyizi 顶点的次序要求这样排列 使观察者在多面体外沿着v1 v2 v3 vL走时 多边形的内部始终在它的右侧 为了确定多边形的内法线方向 可以计算多边形在oxy平面上投影的有向面积 有向面积sp可如下计算如果sp 0 则F所在的面为后向面 如果sp 0 则F所在的面为前向面 8 1多面体的隐藏线消除 用边界盒排除不相交的线段求交 8 1多面体的隐藏线消除 在后向面被删除后 如果两个相邻的多边形的公共边都在两个多边形的凸包上 则这两个多边形不会发生一个遮挡另一个的现象 这时 在考虑一个多边形的边的显示时 可以不考虑另一个多边形对它的影响 8 1多面体的隐藏线消除 隐藏线消除实际计算过程 要对体一个一个来考虑 如考虑体A的显示时 先确定可能遮挡A的那些体 包括体A本身 对体A的每个多边形G 要找出可能遮挡它的所有多边形 这些多边形要从可能遮挡A的所有体的表面多边形中去找 然后对多边形G的每一条边L找出可能遮挡它的所有多边形 这些多边形要从可能遮挡多边形G的所有多边形中去找 以上各步均采用边界盒方法 找到所有可能遮挡边L的多边形后 便可求L和这些多边形的交点 并决定L的可见部分 L 8 1多面体的隐藏线消除 设边L的二端点顶点是vi和vj 对边vivj 即L 和每一个可能遮挡它的多边形 都要作下列计算和判断 以确定其隐藏关系 如果vi和vj都在多边形所在平面靠近观察者的一侧则这个多边形不能遮挡直线段vivj 这时没有必要再考虑vivj和这个多边形的关系 如果vi和vj不都在多边形所在平面靠近观察者的一侧 且vivj和多边形在oxy平面的投影之间有交点 那么把vivj和多边形的边界投影到oxy平面上 求出它们的投影之间的交点 对每一个交点还要判断它在vivj上的对应点是在多边形前面还是后面 只有在多边形后面 交点才要保留 如图8 6中边v1v2和多边形ABCD在oxy平面上的投影虽然有交点Q 但它在v1v2上的对应点v却在多边形的前方 这种交点可不考虑 如果vivj和多边形在oxy平面的投影之间没有交点 那么 这时要判断vi或vj在oxy平面上的投影是否在多边形投影的内部 如果在内部 则vivj就会整个被这个多边形所遮挡住了 图8 6 现在来说明确定L的可见部分的具体计算过程 1 确定L顶点处的与遮挡多边形的前后位置关系设多边形的顶点为 其坐标为 i 1 2 L 任取三个不在一直线上的顶点 设为 则这多边形所在的平面方程为或 8 1多面体的隐藏线消除 设点vj的坐标为 xj yj zj 若z xj yj zj则vj在多边形所在平面的前面 否则认为vj在多边形所在平面的后面 其中 8 1多面体的隐藏线消除 2 确定L与遮挡多边形的交点同遮挡多边形的前后位置关系 为了判断边vivj和多边形在oxy平面的投影之间是否有交点 可首先计算求边vivj和多边形的边界在oxy平面上投影的交点 我们可以把vivj的投影线段用参数方程表示 多边形上任一边的投影用用参数方程表示 求交点时解方程可得其中 8 9 只有当0 l 1和0 t 1时线段和线段vivj在oxy平面上的投影才有交点为了判断vIvj上对应交点的点是在多边形所在平面的前面还是后面 则要去比较和 若前者大于后者 则vivj上交点的对应点在多边形所在平面的前面 否则在后面 8 1多面体的隐藏线消除 3 确定交点和多边形的关系 是内点还是出点 由式 8 9 可知 其中 z是指向量在z轴上的投影 当0时 QiQj由多边形内离开多边形到多边形外 该交点称为出点 这个信息也要和交点的信息一起保存起来 8 1多面体的隐藏线消除 4 确定Qi起点和多边形的关系判断Qi点在多边形内或外 可以从Qi点出发沿x轴的正向作一射线 见图8 8 若该射线和多边形边界的交点个数是奇数 则Qi在多边形内 否则就在多边形外 但正确地找到交点的个数并不容易 如图8 8中点Q6处 由于舍入误差 计算时可能认为Q5Q6 Q6Q7和QiF均有交点 也可能算出一个交点或没有求出交点 不同的交点数可得到完全不同的结果 需要特殊处理 图8 8 8 1多面体的隐藏线消除 5 确定L的可见部分这里引入不可见阶ivord的概念它是一个数字 是某个确定的点的属性 代表了边上从该点到下一个交点的部分被几个多边形遮挡 这里要分两步来做 Step1 确定边QiQj顶点处的不可见阶Step2 确定边QiQj与遮挡多边形交点处的不可见阶 8 1多面体的隐藏线消除 5 确定L的可见部分 Step1 确定边QiQj顶点处的不可见阶首先将Qi处的ivord设置为0 对每一个和QiQj有交点的多边形 从与该多边形相交的交点中找出距离Qi最近的交点 交点参数最小 如图8 9中所示QiQj和多边形H1的交点B 若这个交点为QiQj的出点 则在ivord上加1 交点为进点 则ivord不变 事实上Qi处的ivord反映了有几个多边形遮挡由Qi到QiQj与所有多边形的所有交点中距离Qi最近的交点形成的线段 若Qi处不可见阶为0 则QiQj从l 0至l l1段为可见 否则为不可见 图8 9 8 1多面体的隐藏线消除 5 确定L的可见部分 Step2 确定边QiQj与遮挡多边形交点处的不可见阶 假设直线QiQj和所有的多边形共有n个的交点 将直线与所有多边形的交点按着交点参数的大小排序 形成统一的交点序列下面我们计算的不可见阶ivord 注意这里L0不可见阶就是Qi的不可见阶 首先将Li的不可见阶ivord设置Li 1的不可见阶如果Li处的交点为进点 说明该交点所在的多边形不遮挡由参数Li 1和Li所决定的直线段 而遮挡由参数Li和Li 1所决定的直线段 因此Li的不可见阶加1如果Li处的交点为出点 说明该交点所在的多边形遮挡由参数Li 1和Li所决定的直线段 而不遮挡由参数参数Li和Li 1所决定的直线段 因此Li的不可见阶减1若Li处不可见阶为0 则由参数Li和Li 1所决定的直线段是可见的 否则为不可见 8 3区域子分算法 讨论一个面或面的一部分可见与否 为了减少计算量 可先去掉所有的后向面 区域子分算法 warnock 是一种所谓分而治之的算法 整个屏幕称为窗口 分而治之算法是一个递推的四等分过程 每一次把矩形的窗口等分成四个相等的小矩形 分成的矩形也称为窗口 每一次子分 均要把要显示的多边形和窗口的关系作一判断 8 3区域子分算法 这种关系可有以下四种 即多边形包围了窗口多边形和窗口相交窗口包围了多边形窗口和多边形分离 8 3区域子分算法 在窗口和每个多边形的关系确定之后 有些窗口内的图形便可显示了 它们属于下列三种情况之一 所有多边形都和窗口分离 这时只要把窗口内所有的象素填上背景颜色 只有一个多边形和窗口相交 或这个多边形包含在窗口内 这时先对窗口内每一象素填上背景颜色 再对窗口内多边形部分用扫描线算法填色只有一个多边形和窗口相交 这个多边形把窗口整个包围在内 或虽有几个多边形和窗口相交 但离观察者最近的一个多边形包围了整个窗口 这时把整个窗口填上离观察者最近的那个多边形的颜色 对上述三种情况的窗口来说 图已可画出 因而不必再分细了 8 3区域子分算法 对上述三种情况不成立的窗口再一分为四 见图8 18 分得的窗口重复上述的处理 对不能处理的窗口再一分为四 窗口的边长越分越短 分了若干次后 窗口的边长就和一个象素的宽度一样了 这时这个窗口对应的象素的颜色可取成最靠近观察者的多边形的颜色 或和这个窗口相交的多边形颜色的平均值 图8 18 8 3区域子分算法 Divide Conqer算法的思想虽然简单 具体实现时的细节要处理好 才能提高效率 下面介绍一些有效的处理方法 对所有的多边形按其顶点的z坐标最大值 即最靠近观察者的一个顶点的z坐标值 来排序 对一个具体窗口来说 随着窗口不断地被细分 这个多边形序列的元素将越来越少 窗口变小了 用边界盒的办法就可能判定一些多边形和这个窗口是无交的 这些多边形也不会和这个窗口的子窗口相交 因此对这个窗口来说这些多边形可从多边形序列中排除 此外窗口变小了 就可能被一个多边形包含在内 这样在这个窗口内 比这个多边形远离观察者的多边形都会被这个多边形所遮挡 对这个窗口的子窗口来说这些多边形也被遮挡了 因此对这个窗口来说 这些被遮挡的多边形可从序列中去掉 8 3区域子分算法 对于不能用边界盒办法判断和窗口不相交的多边形 则要经过计算去确定它们之间的关系 这时可以采用与第四章中多边形裁剪算法类似的方法去确定多边形的窗口的边界是否有交点 有交点时 说明多边形和窗口有交 无交点时还要去确定它们是分离还是有包含关系 8 3区域子分算法 在找到了一个多边形包围所考虑的窗口后 就要把它和多边形序列中其它多边形离观察者的远近进行比较 把被它遮挡的多边形从序列中去掉 为此可把窗口四个顶点坐标的x y值代入那个包围窗口的多边形所在的平面方程 以求出对应四个顶点处该平面的z坐标值 以zmin记这四个z坐标值的最小值 对序列中第i个多边形 把它各顶点z坐标值的最大值记为zmaxi 若满足zmin zmaxi 则序列中第i个多边形便被遮挡了 如图8 19所示 多边形AB包含了窗口 多边形CD便可用此法证实是被遮挡的 但多边形EF则不能用此方法证实被多边形AB所遮挡 遇见这种情况可在窗口内多边形EF上任找一点G xG yG zG 把xG yG代入多边形AB所在的平面方程 求出H点处的坐标z值zH 若zH zG 则AB在窗口内遮挡了多边形EF Divide Conqer算法的具体实现 图8 19 8 3区域子分算法 区域子分法提出来后 有不少文章提出了一些改进 参考文章 88 中提出的方法是用多边形的边界来对窗口作划分 这样做的目的是尽量减少对窗口划分的次数 用多边形的边界来对窗口作划分的方法 8 3区域子分算法 用多边形的边界来对窗口作划分的方法 算法思想 先用某种方法对各多边形在深度方向作初步的排序 例如可按多边形顶点z坐标值的最大值zmaxi来排序 zmaxi大的排在前面 现把多边形序列中的第一个多边形 裁剪多边形 取为窗口 多边形序列中的其它的多边形都要被这窗口裁剪 裁剪的结果要建立两个多边形序列表 一个是窗口内的多边形表 一个是窗口外的多边形表 每一个被裁剪的多边形裁剪后位于窗口内的部分放入内部表中位于窗口外的部分放在外部表中 图8 21 a 和图8 21 b 分别为图8 20中多边形的内部表和外部表 图8 20中多边形1作为窗口 图8 20 图8 21 a b 8 3区域子分算法 下面要来确定裁剪多边形 即取为窗口的那个多边形 是否比内部表中的多边形更靠近观察者求出裁剪多边形各顶点坐标z的极小值zminc 求出内部多边形各顶点坐标z的极大值zmaxi对那些满足zminc zmaxi的内部表中的多边形 便可确认它被裁剪多边形所遮挡若某一内部多边形不满足上式 则要从该多边形上取一点 作一和z轴平行的线 求出该线和两个多边形所在平面的交点 根据交点的位置便可准确地确定哪一个多边形更靠近观察者 用多边形的边界来对窗口作划分的方法 算法思想 8 3区域子分算法 如果发现内部表中某多边形H比裁剪多边形更靠近观察者 这时则只好把多边形H的原始多边形 即未被裁剪时的多边形 代替原来的裁剪多边形重复上述工作 若裁剪多边形确实比内部表中的多边形都靠近观察者 则裁剪多边形便是完全可见的 可把它全部显示出来 用多边形的边界来对窗口作划分的方法 算法思想 8 3区域子分算法 下面则要去处理外部表中的各多边型把外部表中第一个多边形作为窗口 假定外部表中多边形也是按原来的多边形次序排序 对外部表中的其它多边形作裁剪并确定遮挡关系在这过程中又形成新的外部表 每一个新的外部表中多边形的个数均比原来的外部表中多边形的个数少 这一过程要重复到外部表中不再有多边形为止 用多边形的边界来对窗口作划分的方法 算法思想 8 4Z缓冲器算法 z缓冲器算法是最简单的消除隐藏面算法之一z缓冲器是一组存贮单元其单元个数和屏幕上象素的个数相同也和帧缓冲器的单元个数相同 它们之间一一对应 8 4Z缓冲器算法 z缓冲器的设置z缓冲器中每个单元的位数取决于图形在z方向的变化范围 一般取20bits就可以了 z缓冲器中每单元的值是对应象素点所反应的物体上点的z坐标值 z缓冲器中每个单元的初值取成z的极小值 帧缓冲器每个单元的初值可放对应颜色的值 8 4Z缓冲器算法 图形消隐和生成的过程就是给帧缓冲器和z缓冲器中相应单元填值的过程在把显示物体的每个面上每一点的属性 颜色或灰度 值填入帧缓冲器相应单元前 要把这点的z坐标值和z缓冲器中相应单元内的值作比较 只有前者大于后者时才改变帧缓冲器的那一个单元的值 同时z缓冲器中相应单元的值也要改成这点的z坐标值 如果这点的z坐标值小于z缓冲器中相应单元的值 则说明对应象素已显示了物体上一个点的属性 该点比要考虑的点更接近观察者 这样 无论帧缓冲器或z缓冲器相应单元的值均不应改变 对显示物体的每一个面上的每一个点都做上述处理后 便可得到消除了隐藏面的图 8 4Z缓冲器算法 算法的优点简单 可靠不需要对显示物体的面预先进行排序算法的缺点要很大的z缓冲器工作量较大 显示物体的表面和象素对应的每一个点处都要计算它的z值为了克服第一个缺点 可把整个平面分成若干区域 一区一区来显示 这样z缓冲器的单元数只要等于屏幕上一个区域的象素个数 如果把这个区域取成屏幕上一行 就得到了扫描线z缓冲器算法 8 4扫描线Z缓冲器算法 扫描线z缓冲器 算法思想z缓冲器的单元数可以取成和一行上的象素数目相同 从最上面的一条扫描线开始工作 向下对每一条扫描线作处理 对每一条扫描线来说 把相应的帧缓冲器单元置成底色 在z缓冲器中存放z的极小值 8 4扫描线Z缓冲器算法 扫描线z缓冲器 算法思想对每个多边形检查它在oxy平面上的投影和当前的扫描是否相交 若不相交 则不考虑该多边形 如果相交 则扫描线和多边形边界的交点一事实上是成对地出现对每对交点中间的象素计算多边形所在平面对应点的深度 即z值 并和z缓冲器中相应单元存放的深度值作比较 若前者大于后者 则z缓冲器的相应单元内容要被求得的平面深度代替 帧缓冲器相应单元的内容也要换成该平面的属性 对所有的多边形都作上述处理后 帧缓冲器中这一行的值便反应了消隐后的图形 对帧缓冲器每一行的单元都填上相应内容后也就得到了整个消隐后的图 8 4扫描线Z缓冲器算法 上述算法要花费很多时间去计算在处理每一条扫描线时 要检查各多边形是否和该线相交还要计算多边形所在平面上很多点的z值为了使这些工作能高效率地进行 可采取类似多边形扫描转换的扫描线算法处理 8 4扫描线Z缓冲器算法 数据结构一个多边形Y筒一个边Y筒一个多边形活化表一个边活化表 8 4扫描线Z缓冲器算法 建立一个多边形Y筒 图8 23是图8 22的多边形Y筒每个筒的深度和显示屏幕行数相同 根据多边形顶点Y坐标最大值来决定放入多边形Y筒的相应行数 多边形Y筒要记录多边形所在平面方程ax by cz d 0系数a b c和d 还要记录和该多边形在oxy平面上的投影相交的扫描线的条数 y 以及多边形的属性colour和编号IP 图8 22 图8 23 8 4扫描线Z缓冲器算法 建立一个边Y筒 图8 24是图8 22的边Y筒每个筒的深度和显示屏幕行数相同 根据边两端点较大的Y坐标值为决定放入边Y筒的相应行数 边Y筒中记录的每一条边要保存下列信息 和该边在oxy平面上的投影相交的扫描线条数 y 该投影和相邻的两条扫描线交点的x坐标的差 x 由上到下扫描 该边所属多边形的编号IP及边的上端点x坐标的值x 图8 24 图8 22 8 4扫描线Z缓冲器算法 建立一个多边形活化表记录在oxy平面上的投影和当前考虑的扫描线相交的多边形 以图8 22为例 当扫描线对应y 10或11时 多边形活化表只有一个多边形 当y 8时多边形活化表如图8 25 表中的 y值是已经过修改的 由上到下扫描 故 y 5 和 y 7 图8 22 图8 25 8 4扫描线Z缓冲器算法 建立一个边活化表边活化表中存放多边形边界和扫描线相交的边对 例如图8 22中y 6的扫描线上的边活化表中应有两个对边 一是和多边形 在oxy平面上的投影相交的两条边另一是和多边形 投影相交的两条边 图8 22 8 4扫描线Z缓冲器算法 边活化表中每一边对要保存下列信息 8 4扫描线Z缓冲器算法 一开始处理最上面的一条扫描线在处理前边和多边形的活化表均是空的 已建立图8 23和图8 24的两个Y筒后在处理每条扫描线时要做下列工作 1 把帧缓冲器相应行置成底色 2 z缓冲器的各单元放z的极小值 3 检查多边形的Y筒 如果有新的多边形涉及该扫描线 则把它放入多边形活化表中 4 如果有新的多边形加入多边形活化表 则要把该多边形在oxy平面上的投影和扫描线相交的边对加入边活化表中 5 如果有些边在这条扫描线处结束了 而其所在的多边形仍在多边形活化表内 则可从边的Y筒中找到该多边形在oxy平面上的投影和扫描线相交的新的边或边对 修改或加到边的活化表中去 边对在边活化表中的次序是不重要的 算法步骤 扫描 8 4扫描线Z缓冲器算法 下面从形成的活化边表中取出一个边对 令zx zl 对每一个满足xl x xr的坐标为 x y 的象素 y是当前考虑的扫描线高度 从左到右依次作下列处理 先计算这就是对应象素处多边形所在平面的深度 如果此值比z缓冲器相应单元中存放的值大 则要用它代替z缓冲器相应单元中原来的值 并把帧缓存中相应单元改成这个多边形的属性 这项工作要对活化表中的每个边对都做到 这项工作完成后 帧缓冲器相应行便存放了消隐后的结果 算法步骤 消隐 8 4扫描线Z缓冲器算法 修改后的表便是下一条扫描线的边活化表 对每一边对可先计算若 yl或 yr小于0 相应的边就要从一个边对中去掉 从边活化表中找合适的边来代替 也有可能这两条边同时结束于某一点 这说明这一边对可取消了 边和下一条扫描线交点的x值可由下式求得多边形所在平面对应下一条扫描线在x xl处的深度 算法步骤 下面来说明对边活化表修改的方法 8 4扫描线Z缓冲器算法 对多边形活化表中每一个多边形的 y要做如下修改当 y 0时 该多边形则要从多边形活化表中删除 做完这些工作后便可开始下一条扫描线的消隐工作 当把每一条扫描线的消隐工作都完成后 整个消隐工作也就完成了 算法步骤 下面来说明对多边形活化表修改的方法 8 5区间 跨距 扫描线算法 上节讲的扫描线z缓冲器算法将消隐问题分散到每一条扫描线上去解决 这样 问题变得较简单了 但在每个象素处计算多边形z值的工作量仍是很大的 实际上每条扫描线被各多边形边界在oxy平面上的投影分割成为数不多的区间 每一个区间上只显示一个面 因此 只要在区间上任一点处 找出在该处z值最大的一个面 这个区间上的每个象素就用这个面的颜色来显示 这种做法就是所谓跨距扫描线算法 8 5区间 跨距 扫描线算法 设多边形的边界在oxy平面上的投影和扫描线交点的横坐标为xi 这些交点把扫描线分成一个小区间 xi i 1 每个小区间称为一个跨距 在每个区间上最靠近观察者的那个面就是这个区间上的可见面 为了在区间上找到离观察者最近的面 只要去求出各多边形 限于那些在oxy平面上的投影和所考虑的扫描线相交的多边形 所在平面在区间左端点的z值 找出z值最大的一个面 如果两个面恰好在左端点相交时 可计算这两个面在右端点的z值并做比较 8 7优先级表算法 优先级表算法按多边形离观察者的远近来建立一张表距观察者远的优先级低 近的优先级高 如果这张表能正确地建立好 那么只要从优先级低的多边形开始 依次把多边形的颜色填入帧缓冲存储器中以形成该多边形的图形直到优先级最高的多边形的图形送入帧缓冲器后 整幅图就显示好了 这种算法也称为油画家算法因为油画家绘画时常先画底色 然后再一层层往上画 8 7优先级表算法 上述算法的困难在于怎样对多边形做一个正确的排序 下面给出了一个动态的方法先根据每个多边形顶点z坐标的极小值zmin的大小把多边形做一个初步的排序 设zmin最小的多边形是P 它暂时成为优先级最低的一个多边形