消除隐藏线和隐藏面.PPTVIP

第七章 消除隐藏线和隐藏面的算法 图象空间算法对显示设备上每一个可分辨象素进行判断，看组成物体的多个多边形表面中哪一个在该象素上可见，即要对每一象素检查所有的表面。 客体空间算法把注意力集中在分析要显示形体各部分之间的关系上，这种算法对每一个组成形体的表面，都要与其它各表面进行比较，以便消去不可见的面或面的不可见部分。每步比较都可能涉及较多的计算。 第一节 线面比较法消除隐藏线 多面体的面可见性 凸多面体的可见面就是朝向观察位置的面。 设观察方向由指向观察位置的一个方向向量k给出，所考查的面的外法向量是n，则这两个向量的夹角为 ?。 若0? ? ? ?/2时，所考查面是可见的，否则就是不可见的。 设 则 利用外法线就可以判断凸多面体上各表面的可见性，由此就能解决对单个凸多面体的隐藏线和隐藏面的消除问题。 对于一个凸多面体，若某个面可见。则该面上所有线均可见，若某个面不可见,则该面轮廓线以外的线都不可见。于是判断出可见面，只显示可见面及与之有关的线段，就画出了消隐后的图形。这个方法只适用于单个凸多面体。 可能可见线和可能可见面的比较 范围检查 显然，如果不发生遮挡，就必定不是隐藏线。可以通过简单的范围检查发现这类情况，以避免往后不必要的Z方向的深度比较。 按xv方向对投影范围的检查，可分别计算出投影线段和多边形表面投影范围x坐标的最大值和最小值，设分别是 zv方向的范围检查（深度检验） 粗略的深度检验 在此范围检查中若线段的最大z坐标zmax1小于多边形表面最小的z坐标zmin2，则线段完全在表面前面，根本不发生遮挡现象，可以不必再往下做精确的深度检验。 精确深度检验 设空间一条线段P1P2和一个平面多边形表面如图所示，过线段两端P1，P2各做一条与zv轴平行的直线l1和l2，这两条直线与平面相交于点P1’，P2’ ，为直线两端点在平面上的投影点。显然两组对应点P1和P1’，P2 和P2’的xv坐标和yv坐标相同，比较zv 坐标： 若z1≤z1’ 且z2≤ z2’ ，则线段不会被遮挡； 若z1≥ z1’ 且z2≥ z2’ ，则线段有可能被遮挡，还需要做进一步检查。 第二节 曲面隐藏线消除的浮动水平线算法 这种曲面也可以由 和 两族曲线来表示。隐藏线消除就是要去掉这两族曲线中被遮挡的部分。 设 第三节 深度排序算法 深度排序算法的主要步骤： 1.?把所有的多边形按顶点最大z坐标值进行排序。 2. 解决当多边形z范围发生交迭时出现的不明确问题。 3. 按最大z坐标值逐渐减小的次序，对每个多边形进行扫描转换。 第四节 画家算法 画家算法又称深度优先级表法，它是深度排序算法的一种具体实现。 这种方法是先把屏幕置成背景色，再把物体的各个面按其离视点的远近进行排序。离视点远者在表头，离视点近者在表尾，构成深度优先级表。然后，从表头至表尾逐个取出多边形，投影到屏幕上，显示多边形所包含的实心区域。由于后显示的图形取代先显示的画面，而后显示的图形所代表的面离视点更近，所以，由远及近地绘制各面，就相当于清除隐藏面。这与油画家作画的过程类似，先画远景，再画中景，最后画近景。由于这个原因，此算法习惯上称作画家算法或油画算法。 首先介绍数据文件的格式，然后介绍程序所使用的数据结构，再接着介绍程序的算法流程图，最后对个别子程序功能作一些解释。 物体采用边界表示模式存储。数据文件由若干三元组和若干四元组组成。三元组表示物体顶点的坐标。四元组表示物体的某个面由那些顶点构成，每个面顶点个数都是4个。如图7.15所示，为一个立方体的数据文件。 边界表示： 三元组表示物体顶点的坐标。 四元组表示物体的某个面由哪些顶点构成，每个面顶点个数都是4个。 第六节 扫描线算法 扫描线算法是图像空间算法，它建立图像是通过每次处理一条扫描线来完成的。这个算法是第二章讨论的多边形填充的扫描线算法的推广。在多边形填充的扫描线算法中，只是对一个多边形做扫描转换，而这里是同时对多个多边形做扫描转换。 1 将实施扫描转换时遍查AET表中各“吊桶”的指针i初始置为1，扫描线正在多少个多边形内的累计数值s初始置为零，将活动多边形表，即扫描线正在通过的多边形按深度递增次序排列而