《计算机图形学》课件——第7章 消除隐藏线和隐藏面.pptVIP

区域经过分割变小以后，只需要考虑被包含的多边形和相交的多边形的变化。 因为分离的或包围的多边形，对变小的区域，仍然保持是分离的或包围的。分割达到显示设备的分辨能力之后就可以停止，即最小的区域可以是显示表面上的一个像素单位。如果在做了最大数目的分割之后，仍然不能确定该如何填充，那么，就计算所有相关的多边形在这个不可再分区域对应点的范围的中心z坐标值，取z坐标最小的多边形像素值填充这个区域。包围的相交的被包含的分离的（4）（2）（3）（1）如何判断包围的多边形位于其它多边形最前面：1.对所有的多边形，计算其所在平面在区域的四个角点的应有深度，即相应的z坐标，如果有一个包围的多边形的对应四个z坐标，都小于其它多边形的对应z坐标，那么这个包围的多边形就位于所有其它多边形的前面。2.判别相交的多边形是否在整个包围多边形的后面，将相交多边形的顶点坐标代入包围多边形的平面方程，判别符号。区域分割成子区域：1.子区域需考察的情况：只需考虑父区域被包含的或相交的多边形。对于分离的或包围的多边形，进行区域分割之后仍保持分离包围的关系。2.分割中止的条件：一个像素单位或最大数目的分割对于仍不能判断的，则找出中心点，计算中心点对应的所有多边形的z值，取z值最小的多边形像素值来填充该区域。3.分割方法（1）等分（2）按多边形顶点做分割（3）按多边形投影进行分割 Wanock首先提出的最初的区域分割算法是每次把区域分成四个正方形。 下图做了5次区域分割的情形，其中区域内标出的数字，表示前面所说的四种情形中的哪一种，可以作出决定。没有标出数字的区域是还不能做出决定。（1）等分：分割区域为正方形1．所有的多边形与区域分离。2．只有一个相交的多边形，或者只有一个被包含的多边形。3．只有一个包围的多边形，无其它的多边形。4．多个多边形与之相交、包围、或被包含，且有一个包围的多边形位于其它多边形最前面（2）按照顶点位置来做分割(先A后B)区域分割不一定总是等分，当区域内有多边形的顶点时，可以按照顶点位置来做分割，这样可以少做一些分割。围绕多边形顶点分割（先是A，后是B）1．所有的多边形与区域分离。2．只有一个相交的多边形，或者只有一个被包含的多边形。3．只有一个包围的多边形，无其它的多边形。4．多个多边形与之相交、包围、或被包含，且有一个包围的多边形位于其它多边形最前面（3）按照多边形投影选择区域做分割 区域分割还可以按照客体中多边形投影的范围进行，这可以少做很多分割。 Weiler和Atherton提出的算法，直接就用多边形的投影做为分割的区域。选择用做分割的区域时，可以按照多边形各顶点坐标最小值的递增次序按照多边形投影选择区域做分割（3）按照多边形投影选择区域做分割 按深度进行预排序。 用距视点最近的多边形对所有多边形进行裁剪和区域分类。 删去位于离视点最近的多边形之后的其他多边形。 必要时递归地进行分割。 最后用深度排序消除所有不确定性。按照多边形投影选择区域做分割第七节BSP树算法二叉空间剖分(BinarySpace-Partitioning,BSP)树算法是一种判别物体可见性的有效算法。它类似于深度排序算法,将表面由后往前地在屏幕上绘出。该算法特别适用于场景中位置固定不变,仅视点移动的情况。一、构造BSP树BSP树取场景中的一个多边形作为分割面,递归地将空间分为两个子空间。场景中的其他多边形中,完全位于剖分平面某一侧的多边形被归入相应的子空间,与剖分面相交的多边形沿剖分面被分割成两部分,分别放入相应的子空间。这两个子空间再分别选一个多边形作分割面递归地子分下去,直到每个子空间只剩一个多边形为止。上述划分过程可用二叉树方便地表示出来,二叉树的根为最初被选作分割面的多边形。BSP树的构造在景物空间内完成。为简单起见,这里假设每个多边形和分割面都垂直于纸面。先取多边形1作为分割面,分割面与多边形2相交,将其分为多边形2a和2b,多边形2a和3在分割面的前面,多边形2b、4和5在分割面的后面,见图7-27中BSP树生成的中间过程。然后从“树”枝中选取多边形3作为分割面,其“前”枝子空间包含多边形2a,“后”枝子空间为空。至此,树的这一分枝分割完毕,返回到根,处理树的“后”枝。取多边形5作为分割面,分割后,多边形4归入其前枝,多边形2b归入其后枝。因为每一子空间都仅包含了一个多边形,故这个分枝也分割完毕。实际上,多边形4和多边形5是共面的,在这种情况下,可放入任一分枝。因为初始分割面和后面每一子空间的分割面的选取是任意的,表示同一场景