第7章 消除隐藏线和隐藏面.pptVIP

第七章 消除隐藏线和隐藏面的算法 第一节 线面比较法消除隐藏线 第二节 曲面隐藏线消除的浮动水平线算法 第三节 深度排序算法 第四节 画家算法 第五节 z-缓冲算法 第六节 扫描线算法 第七节 区域分割算法 第八节 BSP树算法 第九节 八叉树算法 第十节 光线投影算法 图象空间算法对显示设备上每一个可分辨象素进行判断，看组成物体的多个多边形表面中哪一个在该象素上可见，即要对每一象素检查所有的表面。 客体空间算法把注意力集中在分析要显示形体各部分之间的关系上，这种算法对每一个组成形体的表面，都要与其它各表面进行比较，以便消去不可见的面或面的不可见部分。 第一节 线面比较法消除隐藏线 多面体的面可见性 对象：凸多面体 可见面：朝向观察位置的面 观察方向：由指向观察位置的一个方向向量k给出， 考查面的外法向量是n，则这两个向量的夹角 ? 满足0? ? ? ?/2时，所考查面是可见的，否则就是不可见的 把n和k记作 则 设空间有一个四面体，顶点A，B，C，D的坐标依次是(0,0,0) ,( 2,0,1) ,( 4,0,0),(3,2,1)从z轴正向无穷远处观察,求各面的可见性 观察方向向量是k=(0,0,1) 三角面DAB的法向量是: 因此,n·k=4 0，面DAB为可见面.类似计算可知，面DBC是可见面,面ADC是不可见面,面ACB退化为线。 利用外法线就可以判断凸多面体上各表面的可见性，由此就能解决对单个凸多面体的隐藏线和隐藏面的消除问题。 单个凸多面体──可见面上的线是可见线， 多个凸多面体或非凸多面体──用上面的方法预处理，剩下可能可见面 可能可见的棱线:在可见面上或与可见面有边 线面比较法：(观察位置位于Z轴负方向无穷远处) 0.预处理，用外法线法判断出所有可能可见面 思想：求出所有可能可见面，可能可见面上的线段是可能可见线。 每一条可能可见线和每一个可能可见面比较， 从而确定出可见线、隐藏线及可见线上的隐藏部分。 可能可见线和可能可见面 空间任一线段，只有其投影与多边形表面的投影范围发生交迭时，才可能与多边形表面有遮档关系 2. zv方向粗略的深度检查。 若线段投影的最大z坐标zmax1小于多边形表面投影范 围最小的z坐标zmin2，则线段完全在表面前面，根不 发生遮挡现象，可以不必再往下做精确的深度检验。 空间一条线段可能被一个多边形表面遮挡的消除隐藏线的算法的步骤如下： xv方向和yv方向的范围检查； 若不能判断，则接着做zv方向的范围检查即粗略的深度比较； 若还不能判断就再进行精确的深度比较，比较时应计算线段两端点在可能遮挡它的平面上的投影点，比较相应的坐标。这时可能出现线段与平面相交需要用交点，这些交点把线段的投影分成两部分考虑的情况。 判断得知线段确实被平面遮挡了哪些部分做精确计算，计算是求出线段的投影与遮挡平面上多边形表面边框投影的所有交点，这些交点把线段的投影分成可见和不可见的一些子线段。对子线段的可见性，先取上面一点做点的包含性检验来进行判断。 第二节 曲面隐藏线消除的浮动水平线算法 曲面方程 y=f(x,z) 建立M个象素，则建立M个内存单元yu(j)称之为上浮水平线数组，在这些单元中先放上初值，初值应取成小于minf(x,z)。 第三节 深度排序算法 深度排序算法：先画最远的，再画最近的 （优先级算法，画家算法） 深度排序算法的主要步骤： 1.?把所有的多边形按顶点最大z坐标值进行排序。（客体空间） 2. 解决当多边形z范围发生交迭时出现的不明确问题。 3. 按最大z坐标值逐渐减小的次序，对每个多边形进 行扫描转换。（图像空间） 算法的基本思想是按多边形离开观察位置的距离进行排序，然后按照距离减少的次序，把每个多边形内部点应有的象素值送入帧缓存存贮器中。 算法考查多边形的深度次序是在客体空间中进行，图形显示时覆盖步骤是在图象空间中实现，所以可以说是一个客体空间和图象空间的混合算法。 第四节 画家算法 画家算法又称深度优先级表法，它是深度排序算法的一种具体实现。 先画远景，再画中景，最后画近景。 扫描转换时，对每个多边形内部的任意点（x,y）,实施如下步骤： 1.计算在点（x，y）处多边形的深度值z（x，y）。 2.如果计算所得的z（x，y）值，小于在z?缓冲存储器中点?x?y?处记录的深度值，那么就做： （1）把值z?x? y?送入z?缓冲存储器的点(x,y)处。 （2）把多边形在深度z(x?y?处应有的象素值，送入帧缓冲存储器的点?x? y?处。 第六节 扫描线算法 消除隐藏面的扫描线算法：图象空间算法 它建立图