第7章-可见面的判定

第七章可见面的判定XYZx1y1z1z2XpYp窗口坐标系屏幕坐标系模型坐标系世界坐标系视口窗口建模显示处理几何变换裁剪确定可见面光照明投影概述由于投影变换失去了深度信息，往往导致图形的二义性。要消除二义性，就必须在绘制时消除被遮挡的不可见的线或面，习惯上称作消除隐藏线和隐藏面（或可见线判定、可见面判定），或简称为消隐。经过消隐得到的投影图称为物体的真实图形。概述消隐的分类按消隐对象分类(a)线消隐消隐对象是物体上的边，消除的是物体上不可见的边。(b)面消隐消隐对象是物体上的面，消除的是物体上不可见的面。1以构成图像的每一个像素为处理单元，确定场景中的所有在该像素上有投影的表面，相对于观察点可见的表面。适于面消隐。2以三维场景中的物体对象为处理单元，在所有对象之间进行比较，除去完全不可见的物体和物体上不可见的部分。

适于面消隐也适于线消隐。窗口像素视点图7.1以像素为对象的消隐算法xz窗口平行投影y图7.2以物体为对象的消隐算法前提：把物体看成是由一个或多个多边形（或更复杂的面片）组成消除隐藏线和隐藏面的两种算法！假定构成物体的面不能相互贯穿，也不能有循环遮挡的情况。(a)(b)贯穿和循环遮挡如果构成物体的面不满足该假定，可以把它们剖分成互不贯穿和不循环遮挡的情况。例如，用上图中的虚线便可把原来循环遮挡的三个平面，分割成不存在循环遮挡的四个面。

提醒7.1.1347.1可见面判断的有效技术7.1.27.1.3后向面消除边界盒投影规范化物体的边界盒是指能够包含该物体的一个简单的几何形状，如矩形、圆、长方体等。7.1.1边界盒边界盒：采用边界盒在消隐中的好处：可避免不必要的裁剪运算，避免在物体或它们的投影之间进行不必要的比较运算。xyz图7.4

两个物体投影在xy平面，包围投影的边界盒为矩形注意选取适当的边界盒：不可太小，也不可太大。一种简单的求边界盒的方法：计算多边形顶点坐标的最大值和最小值得到（即采用矩形边界盒）

A边界盒不相交：在Oxy平面投影的边界盒，两个边界盒不相交，所以两个多边形不相交。

B边界盒相交：相交的情况可分为两种，投影相交或投影不相交。无论哪种情况都需要做进一步的处理，以判断两物体的投影是否相交。7.1.1边界盒边界盒应用原则xyzA不相交(a)边界盒和投影均重叠(b)边界盒重叠，投影不重叠

用边界盒技术判断两条直线是否相交。7.1.1边界盒举例：xminxmaxymaxyminxyQ1Q6Q5Q2Q4Q3记点vi在oxy面上的投影为。直线段的边界盒是包含该直线且边平行于坐标轴的最小矩形，这个矩形由下面四个参数确定

设两个边界盒的参数为:当它们满足:或或或

表明两个边界盒不相交，则边界盒中的两条直线段也不相交。用球代替长方体作为边界盒可以简化判断直线同边界盒是否相交的计算过程，即若边界球的球心到直线的距离大于球的半径，那么直线与边界球不相交，也就与球内的物体不相交。一个有效的确定边界球的方法是取球的中心为：取半径为：其中：7.1.1边界盒进一步简化判断1、后向面多面体表面多变形的法向可分为两种：一种是指向多面体的外部——外法向，一种指向多面体的内部——内法向。必然有一些多边形表面的外法向指向与观察者相背离的方向，这些多边形完全被多面体上其它多边形遮挡。这些被遮挡的多边形称为后向面。首先消除掉这些面，去除后向面的过程称为后向面消除。

7.1.2后向面消除思路：把显然不可见的面去掉，减少消隐过程中的直线求交数目IJFGH，FABG，HCDI，IDEJ所在的面为前向面JEAF，DEABC,HGBC所在的面为后向面如何判断：根据定义寻找外（或内）法向，则外法向背离观察者，或内法向指向观察者，则该面为后向面。2、判断后向面的方法7.1.2后向面消除1）首先对多边形的顶点进行排序：设多边形F的顶点为v1,v2,…,vL顶点的坐标为。次序要求如下排列：使观察者在多面体外沿着v1－>v2－>…－>vL走时，多边形的内部始终在它的右侧。右设多边形F的顶点为v1,v2,…,vL顶点的坐标为。次序如图2）判断后向面：如果v1,v2,…,vL构成凸的多边形，则向量

是F的内法线方向，如果

的z分量说明内法向量和z轴正方向的夹角大于90度，F的外法线方向和z轴正方向的夹角小于90度，F为前向面。否则，即a的z分量大于0

即，则F的内法向和z轴正方向的夹角大于90度，外法线方向和z轴正方向的夹角小于90度，F为后向面。2、判断后向面的方法7.1.2后向面消除v1v2v3v4v5v6：可以看作是三角形v1vk

vk+1在平面oxy上投影的有向面积的二倍。7.1.2后向面消除2、判断后向面的方法顶点为A，B，C的三角形面积求解如下，设：所以，三角形v1vk

vk+1在平面oxy上投影的有向面积为：恰好是是否可以这样说，求一个多边形的内法向的z分量等价于求其任意一个三角形的有向面积？7.1.2后向面消除2、判断后向面的方法注意：如果多边形是凸的，则可只取一个三角形计算有向面积sp。如果多边形不是凸的，只取一个三角形计算有向面积sp可能会出现错误，即F所在的面为前向面也可能出现sp≥0的情况,因此，需按上式计算多边形F的有向面积。v1v2v3v4v5v6v1v2v3v4v5v6如果

，则F所在的面为后向面。如果

，则F所在的面为前向面。7.1.2后向面消除2、判断后向面的方法3）可以通过计算多边形在Oxy平面上投影的有向面积判断F是否为后向面。有向面积sp可如下计算：7.1.2投影规范化物体之间的遮挡关系与投影中心和投影方向有着密切的关系，对物体的可见性判定也和投影方式有密切的关系。注意：垂直投影的优点：进行投影时可以忽略z值，即实物的（x，y）即可直接做为投影后的二维平面上的坐标（x，y）(x,y,z)(x,y)(x,y,z)(x’,y’)所以，下面的工作就是将非垂直投影转换成垂直投影。这样可以降低算法的复杂性，提高运算速度。7.1.2投影规范化如何把透视投影变为垂直投影，其本质是把棱台变成长方体。

AB投影平面由棱台到长方体的变换把左边的棱台A变换成右边长方体B。设(xA,yA,zA

)是棱台A中任意一点，它在投影平面的投影为(x’,y’,0)，事实上透视投影是把线段(xA,yA,zA)和(x’,y’,0)之间的点都变换成(x’,y’,0)，如果能把(xA,yA,zA)和(x’,y’,0)之间的点指定一个相应的Z值，且该值不改变原线段上点之间的前后关系，就可把棱台A变为长方体B，即将透视投影变换成了正投影。求A的坐标如何变换到B的坐标，即（xA,yA,zA）到（xB,yB,zB）的变换同一图形垂直投影不改变x，y值投影面7.1.2投影规范化如果对z的射影变换是线性的，则不改变视见体内各表面的前后位置关系可以通过不改变视见体的前后平面z=zf和z＝zb，的前后位置关系实现，把这两个条件代入左式，得：投影公式则只剩下zB没有解，则按照类似于xB和yB的形式来找zB与ZA的关系a,b是系数，是我们假定的，则，如何求解？？判断哪个多边形是可见：可在两多边形共同覆盖的区域内取一点（x,y），如果投影为垂直投影,把（x,y）分别代入两个多边形表达式，得到两个空间点P1(x,y,z1)和P2(x,y,z2)，当z1>z2时，P1遮挡P2，当z2>z1时，P2遮挡P1；但如果不是垂直投影，则需根据视点或投影方向计算两个多边形在oxy平面的投影为P1(x1,y1,z1)和P2(x2,y2,z2)总结：在非垂直投影下计算P1和P2要比在垂直投影下计算花费的计算量大许多。

7.1.3非垂直投影转换成垂直投影射影变换之后－－

7.2.17.2区域细分算法7.2.2基于多边形的细分算法基于窗口的细分算法7.2区域细分算法概述区域细分算法是一种分而治之(Divide-Conquer)的算法，它把投影区域作为考察对象，如果很容易确定投影区域内的多边形是否可见，便显示这些多边形，否则将这些区域进一步细分，随着不断细分，判断多边形的可见性将越来越简单。本节介绍基于窗口的细分算法和基于多边形的细分算法。7.2.1基于窗口的细分算法基本思想子分的过程把物体投影到全屏幕窗口上，然后递归的将窗口一分为四，如果可以确定小窗口内的多边形是否可见，则显示这些多边形，否则，将小窗口细分为更小的窗口，递归地执行上述过程。每一次把矩形的窗口等分成四个相等的小矩形。注意：分成的小矩形也称为窗口。7.3基于窗口的子分算法具体分析－关系判断细分后都要对多边形和窗口就下面四种关系作判断：窗口和多边形分离(图中情况1)1多边形和窗口相交(图中情况2)2窗口包围了多边形(图中情况3)3多边形包围了窗口(图中情况4)41234多边形和窗口的关系7.2.1基于窗口的细分算法具体分析－可见性判断对以下的三种情况，窗口中多边形的可见性容易判定，不需要再对窗口进行分割：所有多边形均和窗口分离，则窗口内只需显示背景色；

1只有一个多边形和窗口相交，或这个多边形包含在窗口内。这时，先对窗口内每一像素填上背景颜色，再对窗口内多边形部分用扫描线算法填色。2一个多边形包围窗口，其他多边形和窗口分离，或有多个多边形和窗口的关系分别是相交、内含或包围，但是有一个多边形包围窗口并且在其他多边形前面，则窗口用包围多边形的颜色填充。3橙色紫色7.2.1基于窗口的细分算法具体分析－分割结束条件对不满足上述三种情况的窗口，重复细分过程，并对细分后的各子窗口重复做同样的处理。细分若干次后，窗口的面积就小于或等于一个像素的面积了，此时细分结束，该窗口对应的像素的颜色可取成最靠近观察者的多边形的颜色。橙色紫色7.2.2基于多边形的细分算法基本思想用多边形的边界对区域作划分，其目的是尽量减少对区域划分的次数－－利用裁剪算法。该算法是对上节基于窗口细分算法的改进。由于算法在景物空间中以任意指定的精度进行运算，其输出结果仍为多边形，所以算法不仅可用来处理隐藏面消除，也可用来处理多面体隐藏线消除问题。算法描述Step1：对各多边形在深度方向作初步的排序：按多边形顶点z坐标值的最大值zmaxi做预排序，zmaxi大的排在前面。Step2：把多边形序列中的第一个多边形（裁剪多边形）取为窗口。多边形序列中的其它的多边形都要被此窗口裁剪。Step3：裁剪结果要建立两个多边形序列表－内部表：放入位于窗口内的部分－外部表：放入位于窗口外的部分yx4321要消隐的多边形xyz43212i3i4i4oni为窗口内的多边形表；no为窗口外的多边形表3o7.2.2基于多边形的细分算法算法描述Step4：将内部表中每一个其它多边形的深度值与裁剪多边形(即取为窗口的那个多边形)的深度值进行比较，如果内部表中每一个其它多边形均被裁剪多边形遮挡，则裁剪多边形是完全可见的，可把该多边形区域填上裁剪多边形的颜色。

yx4321要消隐的多边形xyz4321如何判断窗口是否遮挡其余的多边形7.2.2基于多边形的细分算法求出裁减多边形也就是内部表中第一个多边形，各顶点坐标的极小值Zmin；求出内部多边形各顶点坐标z的极大值Zmaxi；对那些满足Zmin>Zmaxi的内部表中的多边形，便可认为它被裁减多边形所遮挡；若某一内部多边形不满足上式，则要从该两多边形相交的区域上取一点，做和z轴平行的线，求出该线和两个多边形所在平面的交点，根据交点的位置便可准确地确定哪一个多边形更靠近观察者。7.2.2基于多边形的细分算法如何判断窗口是否遮挡其余的多边形EAzmaxzminBCDGHFxz算法描述Step5：如果内部表中有某多边形H比裁剪区域（多边形）更靠近观察者，说明原来的预排序不对，此时要用多边形H的原始多边形（即未被裁剪时的多边形）代替原来的裁剪多边形重复上述工作。

yx4321要消隐的多边形xyz4321！如左图如果对顶点排序的话，则1自然要排最前面，首先会用1做裁剪多边形，但实际情况是2在1的前面，所以应该以2做新的裁剪多边形，重复上述工作7.2.2基于多边形的细分算法算法描述Step6：内部表中多边形的按前后顺序排好序后，接下来是对外部表中的各多边形进行排序。对外部表中各多边形的排序和对内部表中各多边形的处理方法相同，即把外部表中第一个多边形作为裁剪多边形(假定外部表中的多边形也是按原来的多边形次序排序)，对外部表中的其它多边形作裁剪并确定遮挡关系，这一过程又形成新的外部表。裁剪过程要重复到外部表中不再有多边形为止。yx4321要消隐的多边形xyz43214o3o7.2.2基于多边形的细分算法7.3八叉树算法基本思想将能够包含整个场景的立方体，即八叉树的根结点，按照x，y，z三个方向中的剖面分割成八个子立方体，称为根结点的八个子结点。对每一个子立方体，如果它包含的表面片少于一个给定的值（例如3），则该子立方体为八叉树的终端结点，否则为非终端结点并将其进一步分割成八个子立方体；重复上述过程，直到每个小立方体所包含的表面片少于一个给定的值，分割即告终止。

7.3八叉树算法具体分析1）每一终端结点对应一个求交面片表，该表中包含的是与终端结点对应的立方体中所包含的景物表面片。2）八叉树由于其不相交立方体之间的规则结构，可以很方便的进行空间预排序，然后再根据列表优先级算法便可以很容易对平行投影给出正确的显示顺序。122333314455556666777xyzv从后向前显示的八叉树排列对从后向前排列算法，先显示最远的八分体，然后是与最远的八分体共享一个面的三个相邻八分体顺序任意），然后显示最近八分体的三个相邻八分体（顺序任意），最后显示最近的八分体7.3八叉树算法具体分析

对于过视点和像素的射线，根据空间网格之间的邻接关系，能很快地求得射线和景物的第一个交点，从而使计算量大大减少，见图7.15。具体地说，射线从起始点开始，跨越一个个它所经过的网格单元，直到遇到它与景物有交点的网格单元为止，此后射线无需再继续跟踪下去，从而避免了与后面景物表面的求交计算。对射线与景物有交点的第一个网格单元，如果射线与景物有多个交点，则需选择离视点最近的交点。

射线沿网格与表面片求交射线空间网格7.4z缓冲器算法和扫描线算法对屏幕上每一个像素点，过像素中心做一条投影线，找到此投影线与所有多边形交点中离观察者最近的点，此点的属性（颜色或灰度）值即为这一屏幕像素点的属性值。基本思想：7.4z缓冲器算法和扫描线算法Z缓冲器z缓冲器是一组存贮单元其单元个数和屏幕上像素的个数相同也和帧缓冲器的单元个数相同，它们之间一一对应。Z缓冲区示意图7.4z缓冲器算法和扫描线算法具体实现需要两个缓冲器数组，z缓冲器数组用于存储投影线与所有多边形交点的z值，帧缓冲器数组用来存储像素的颜色值。分别设为Zdepth[][]与Frame[][]

对屏幕上每个点（x，y），令Zdepth[x][y]为z的极小值，Frame[x][y]为背景颜色。对所有多边形做如下工作：对多边形上在像素中心有投影的每一点（x,y）计算其z值。若z>Zdepth[x][y]，则Zdepth[x][y]＝z，并将此点属性值赋给Frame[x][y]，否则说明此点离观察者较远，两个数组的值都不用改变。127.4z缓冲器算法和扫描线算法具体实现只有z坐标值大于z缓冲器时才改变帧缓冲器的那一个单元的值，同时z缓冲器中相应单元的值也要改成这点的z坐标值。如果这点的z坐标值小于z缓冲器中相应单元的值，则说明对应象素已显示了物体上一个点的属性，该点比要考虑的点更接近观察者。这样，无论帧缓冲器或z缓冲器相应单元的值均不应改变。对显示物体的每一个面上的每一个点都做上述处理后，便可得到消除了隐藏面的图。

Zdepth[x][y]＝z1Frame[x][y]＝greenZdepth[x][y]＝z2Frame[x][y]＝blue7.4z缓冲器算法和扫描线算法扫描线z缓冲器算法

将z缓冲器的单元数置为和一条扫描线上的像素数目相同。从最上面的一条扫描线开始工作，向下对每一条扫描线作如下处理：把相应的帧缓冲器单元置成底色，z缓冲器中存放z的极小值。对每个多边形检查它在平面上的投影和当前的扫描线是否相交。然后计算各重叠面片的深度值以确定离观察者最近的面片。当某像素点所对应的可见面被确定后，该点的颜色值置入帧缓冲器。step1step2扫描线算法也属于图像空间消隐算法。该算法可以看作是多边形区域填充里介绍过的边相关扫描线填充算法的延伸。不同的是在消隐算法中处理的是多个面片，而多边形填充中是对单个多边形面进行填充。7.4z缓冲器算法和扫描线算法扫描线z缓冲器算法

对每个多边形，检查它在oxy平面上的投影和当前扫描线是否相交？若不相交，则不考虑该多边形。如果相交，则扫描线和多边形边界的交点是成对地出现对每对交点中间的像素计算多边形所在平面对应点的深度（即z值），并和z缓冲器中相应单元存放的深度值进行比较。若前者大于后者，则z缓冲器的相应单元内容要被求得的平面深度代替，帧缓冲器相应单元的内容也要换成该平面的属性。对所有的多边形都作上述处理后，帧缓冲器中这一行的值便反应了消隐后的图形。对帧缓冲器每一行的单元都填上相应内容后就得到了整个消隐后的图。7.4z缓冲器算法和扫描线算法step2相交的判断－数据结构

与多边形扫描转换中扫描线算法数据结构和算法类似。多边形Y表1/710728212边表（ET）7.4z缓冲器算法和扫描线算法step2数据结构的具体实现——建立一个多边形Y表多边形所在平面方程ax+by+cz+d=0系数a，b，c和d，记录和该多边形在oxy平面上的投影相交的扫描线的条数Δy，多边形的属性color和编号IP。9-1=811-3=836781110118713ⅠⅡ要消隐的物体xyo7.4z缓冲器算法和扫描线算法step2数据结构的具体实现——建立一个多边形Y表实际上是一个指针数组，每个表的深度和显示屏幕行数相同。将所有多边形存在多边形Y表中，根据多边形顶点中Y坐标最大值，插入多边形Y表中的相应位置，多边形Y表中保存多边形的序号和其顶点的最大y坐标。7.4z缓冲器算法和扫描线算法step2数据结构的具体实现——建立一个边表根据边两端点较大的y坐标值决定放入边表的哪一行。边的上端点x坐标的值；该投影和相邻的两条扫描线交点的x坐标的差Δx；和该边在oxy平面上的投影相交的扫描线条数Δy；该边所属多边形的编号IP。367811101198713ⅠⅡ图7.16要消隐的物体xo1/7107282127.4z缓冲器算法和扫描线算法step2相交的判断－数据结构活化多边形表活化边对表7.4z缓冲器算法和扫描线算法step2数据结构的具体实现——建立一个活化多边形表记录在oxy平面上的投影和当前考虑的扫描线相交的多边形，如：当扫描线对应y=10或11时，活化多边形表只有一个多边形。当y=8时活化多边形表如图。表中的Δy值(扫描线的条数）是已经过修改的。（由上到下扫描，故△y=5和△y=7）367811101198713ⅠⅡ

图7.16要消隐的物体xo8-3=58-1=77.4z缓冲器算法和扫描线算法step2数据结构的具体实现——建立一个活化边对表活化边对表中存放多边形边和扫描线相交的边对。例如图中y=6的扫描线上的活化边对表中有两个边对一是和多边形Ⅰ在oxy平面上的投影相交的两条边另一是和多边形Ⅱ投影相交的两条边。367811101198713ⅠⅡ图7.16要消隐的物体xo7.4z缓冲器算法和扫描线算法step2xl左交点的x坐标值Δxl左交点所在边和两相邻扫描线交点的x坐标之差Δyl以和左交点所在边相交的扫描线条数为初值，以后每处理一条扫描线减1xr右交点的x坐标值Δxr右交点所在边和两相邻扫描线交点的x坐标之差以和右交点所在边相交的扫描线条数为初值，以后每处理一条扫描线减1Δyr数据结构的具体实现——建立一个活化边对表7.4z缓冲器算法和扫描线算法step2zl左交点处多边形所在平面的深度值Δzx沿扫描线向右走过一个象素时，多边形所在平面深度的增量。对方程为ax+by+cz+d=0的平面来说Δzx=–a/c（c≠0）Δzy沿y方向向下移过一根扫描线时，多边形所在平面深度的增量。对方程为ax+by+cz+d=0的平面来说Δzy=b/c（c≠0）IP所在多边形的编号边对边对数据结构的具体实现——建立一个活化边对表7.4z缓冲器算法和扫描线算法step2若已知多边形的方程，则可用增量法计算扫描线每一个像素的深度。设平面方程为：

ax+by+cz+d=0

则多边形面上的点（x，y）所对应的深度值为：zl左交点处多边形所在平面的深度值Δzx沿扫描线向右走过一个象素时，多边形所在平面深度的增量。对方程为ax+by+cz+d=0的平面来说Δzx=–a/c（c≠0）Δzy沿y方向向下移过一根扫描线时，多边形所在平面深度的增量。对方程为ax+by+cz+d=0的平面来说Δzy=b/c（c≠0）数据结构的具体实现——建立一个活化边对表7.4z缓冲器算法和扫描线算法step2Δzx沿扫描线向右走过一个像素时，多边形所在平面深度的增量。对方程为ax+by+cz+d=0的平面来说Δzx=–a/c（c≠0）Δzy沿y方向向下移过一根扫描线时，多边形所在平面深度的增量。对方程为ax+by+cz+d=0的平面来说Δzy=b/c（c≠0）由于所有扫描线上相邻点间的水平间距为1个像素单位，扫描线行与行之间的垂直间距也为1。因此可以利用这种连贯性来简化计算过程，如图所示。数据结构的具体实现——建立一个活化边对表7.4z缓冲器算法和扫描线算法step2若已计算出（x，y）点的深度值为zi，沿x方向相邻连贯点（x+1，y）的深度值zi+1可由下式计算：沿着y方向的计算应先计算出y坐标的范围，然后从上至下逐个处理各个面片。由最上方的顶扫描线出发，沿多边形左边界递归计算边界上各点的坐标：公式（1）数据结构的具体实现——建立一个活化边对表7.4z缓冲器算法和扫描线算法step2这里m为该边的斜率，沿该边的深度也可以递归计算出来，即：

如果该边是一条垂直边界，则计算公式简化为：

公式（2）对于每条扫描线，首先根据公式（2）计算出与其相交的多边形最左边的交点所对应的深度值，然后，该扫描线上所有的后续点由（1）式计算出来。数据结构的具体实现——建立一个活化边对表7.4z缓冲器算法和扫描线算法重温算法目标对每一条扫描线，检查对每个多边形的投影是否相交，如相交则交点成对出现，对每对交点中间的每个像素计算多边形所在平面对应点的深度（即z值），并和z缓冲器中相应单元存放的深度值作比较，若前者大于后者，则z缓冲器的相应单元内容要被求得的平面深度代替，帧缓冲器相应单元的内容也要换成该平面的属性。对所有的多边形都作上述处理后，帧缓冲器中这一行的值便反应了消隐后的图形，对帧缓冲器每一行的单元都填上相应内容后也就得到了整个消隐后的图。367811101198713ⅠⅡxo多边形y表1/710728212边表1)建立多边形y表和边表，初始化活化多边形和活化边对表为空2)以最上面的扫描线为当前扫描线。3)对当前扫描线y，把帧缓冲器相应行置成底色z缓冲器的各单元放z的极小值。算法步骤：多边形Y表

4)检查多边形y表，如果有新的多边形涉及当前扫描线，则把它放入活化多边形表中。1189688

要消隐的物体107若有新的多边形加入活化多边形表，则要把该多边形在Oxy平面上的投影和扫描线相交的边对加入活化边对表。多边形Y表1/710728212边表665）对边活化表中的每个边对，令，对每一个满足的坐标为的像素从左到右依次进行处理，求深度值z并与z缓冲器的值比较。zx=zx+△zx6）若所有扫描线都已经处理完，则算法结束，否则选下一条扫描线为当前扫描线，转步骤3），直到所有的扫描线都处理完。从上到下，从左到右每条扫描线处理完后，处理下一条扫描线之前，需要进行以下处理：1）修改边活化表，对每一边对要做如下计算若或小于0，则相应的边要从该边对中去掉，并从都不小于0，则修改边表中找合适的边来代替。若这两条边同时结束于某一点，则去掉这一边对。若公式（2）又由于修改后的表便是新扫描线的活化边对表。2）修改活化多边形表。若，则将该多边形从活化多边形表中删除。7.5深度排序算法基本思想