二维图形的裁剪讲稿.ppt

《二维图形的裁剪讲稿.ppt》由会员分享，可在线阅读，更多相关《二维图形的裁剪讲稿.ppt（93页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于二维图形的裁剪关于二维图形的裁剪第一页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院2 2二维裁剪二维裁剪识别图形在指定区域内和区域外的部分的过程称为裁剪算法，简称识别图形在指定区域内和区域外的部分的过程称为裁剪算法，简称裁剪（裁剪（clipping）二维窗口是投影平面上的一个矩形。一般来说，这个矩形的边和投二维窗口是投影平面上的一个矩形。一般来说，这个矩形的边和投影平面上的坐标轴平行，图形在窗口内的部分被显示出来，窗口外影平面上的坐标轴平行，图形在窗口内的部分被显示出来，窗口外的部分被裁剪掉了。平面上的图形受该矩形的裁剪称为二维裁剪。的部分

2、被裁剪掉了。平面上的图形受该矩形的裁剪称为二维裁剪。第二页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院3 3裁剪的应用裁剪的应用从定义的场景中抽取用于观察的部分从定义的场景中抽取用于观察的部分在三维视图中识别出可见面在三维视图中识别出可见面防止线段或对象的边界混淆防止线段或对象的边界混淆用实体造型来创建对象用实体造型来创建对象显示多窗口的环境显示多窗口的环境允许选择图形的一部分来进行拷贝、移动或删除等绘图操作允许选择图形的一部分来进行拷贝、移动或删除等绘图操作裁剪算法类型裁剪算法类型图形裁剪与窗口图形裁剪与窗口视图变换的先后视图变换的先后窗口边

3、界裁剪窗口边界裁剪视区边界裁剪视区边界裁剪图形生成与裁剪先后图形生成与裁剪先后先生成后裁剪先生成后裁剪先裁剪后生成先裁剪后生成第三页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院4 4点的裁剪点的裁剪图形裁剪中的最基本的问题。图形裁剪中的最基本的问题。假设裁剪窗口为一个在标准位置的矩形，即边与坐标轴平行的矩形，由上假设裁剪窗口为一个在标准位置的矩形，即边与坐标轴平行的矩形，由上（y=ymin）、下（）、下（y=ymax）、左（）、左（x=xmin）、右（）、右（x=xmax）四条边描）四条边描述。述。点点(x,y)在窗口内的充分必要条件是：在窗口

4、内的充分必要条件是：裁剪窗口（裁剪窗口（Xmin，Xmax，Ymin，Ymax）是世界坐标系的窗口边界或视区边界是世界坐标系的窗口边界或视区边界应用举例应用举例爆炸场景或海面泡沫的显示爆炸场景或海面泡沫的显示问题：对于任何多边形窗口，如何判别？问题：对于任何多边形窗口，如何判别？(xmin,ymin)(xmax,ymax)第四页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院5 5直线段裁剪直线段裁剪直线段裁剪算法是复杂图形裁剪的基础。复杂的曲线可以通过折直线段裁剪算法是复杂图形裁剪的基础。复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线

5、段的裁剪问题。线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。裁剪的目的裁剪的目的判断图形元素是否落在裁剪窗口之内并找出其位于内部的部分判断图形元素是否落在裁剪窗口之内并找出其位于内部的部分裁剪处理的基础裁剪处理的基础图元关于窗口内外关系的判别图元关于窗口内外关系的判别图元与窗口的求交图元与窗口的求交假定条件假定条件矩形裁剪窗口：矩形裁剪窗口：xmin,xmaxXymin,ymax待裁剪线段：待裁剪线段：第五页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院6 6直线段裁剪直线段裁剪待裁剪线段和窗口的关系待裁剪线段和窗口的关系（1）完全落在窗口

6、内，线段完全可见）完全落在窗口内，线段完全可见（2）完全落在窗口外，显然不可见）完全落在窗口外，显然不可见（3）与与窗窗口口边边界界相相交交，线线段段至至少少有有一一端端点点在在窗窗口口之之外外，但但非非显显然然不不可见可见第六页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院7 7要确定一条直线段上位于窗口内的可见段，只须要确定一条直线段上位于窗口内的可见段，只须求出它的两个位于窗口内的可见端点即可。求出它的两个位于窗口内的可见端点即可。算法的基本思想算法的基本思想把所有的直线按照它和窗口的关系分类，不同的直把所有的直线按照它和窗口的关系分类，不

7、同的直线使用不同的处理方法确定其可见部分。线使用不同的处理方法确定其可见部分。第七页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院8 8为提高效率，算法设计时应考虑：为提高效率，算法设计时应考虑：(一）快速判断情形一）快速判断情形(1)(2)；(二二)设法减少情形设法减少情形(3)求交次数和每次求交时所需的计算求交次数和每次求交时所需的计算量。量。直线裁剪算法的主要步骤：直线裁剪算法的主要步骤：首先将不需要裁剪的直线挑出，并删去其中在窗外的直线；首先将不需要裁剪的直线挑出，并删去其中在窗外的直线；其次，对其余直线，逐条与窗框求交点，并将窗外部分删

8、去其次，对其余直线，逐条与窗框求交点，并将窗外部分删去第八页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院9 9实交点实交点是直线段与窗口矩形边界的交点。是直线段与窗口矩形边界的交点。虚虚交交点点则则是是直直线线段段与与窗窗口口矩矩形形边边界界延延长长线线或或直直线线段段的的延长线与窗口矩形边界的交点。延长线与窗口矩形边界的交点。第九页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院1010直线的剪裁算法直线的剪裁算法直接求交算法直接求交算法矢量裁剪法矢量裁剪法Cohen-Sutherland算法算法

9、中点分割算法中点分割算法梁友栋梁友栋Barsky算法算法Nicholl-Lee-Nicholl算法算法第十页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院1111直接求交算法直接求交算法直线与窗口边直线与窗口边都写成参数形都写成参数形式，求参数值。式，求参数值。第十一页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院1212矢量裁剪法矢量裁剪法算法思想算法思想先从线段的一个端点出发进行判断或进行求交运算，所得交点坐标先从线段的一个端点出发进行判断或进行求交运算，所得交点坐标保存在（保存在（xs，ys）

10、中，然后再从线段的另一个端点出发用前面的）中，然后再从线段的另一个端点出发用前面的判断及其求交运算求得交点坐标（判断及其求交运算求得交点坐标（x，y），最后只输出两个交点），最后只输出两个交点间的线段。间的线段。用窗口的四条边界的直线将窗口分为用窗口的四条边界的直线将窗口分为9个区。个区。012345678(x2,y2)ybytxlxr(x1,y1)第十二页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院1313排斥性测试排斥性测试若线段满足下述四个条件之一时：若线段满足下述四个条件之一时：max(x1,x2)xlmin(x1,x2)xrmax(y

11、1,y2)ybmin(y1,y2)yt则线段必定位于窗口之外，无输出线段。则线段必定位于窗口之外，无输出线段。包含性测试包含性测试 若线段满足：若线段满足：xlx1 xr,yby1 yt,则线段的始点在则线段的始点在0区，区，也即线段可见段的起点为：也即线段可见段的起点为：xs=x1 ,ys=y1第十三页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院1414求交点，并判断求交点，并判断I.若若x1xl,则：则：线段的起点坐标可能线段的起点坐标可能位于位于3区、区、4区、区、5区。区。而新起点的坐标可能在而新起点的坐标可能在直线直线y=yb和线段的

12、交点上和线段的交点上直线直线y=yt和线段的交点上和线段的交点上直线直线x=xl和线段的交点上和线段的交点上012345678(x1,y1)(x2,y2)ybytxlxr第十四页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院1515第一种情况：第一种情况：此时，若此时，若xlxsxr则则(xsys)为有效新起点。为有效新起点。第二种情况：第二种情况：此时，若此时，若xlxsxr则则(xsys)为有效新起点。为有效新起点。第三种情况：第三种情况：此时，若此时，若ybys yt 则则(xs ys)为有效新起点。为有效新起点。三种情况都不满足，则此线段

13、不在窗口区内。三种情况都不满足，则此线段不在窗口区内。第十五页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院1616II.若若x1xr线段的起点坐标可能线段的起点坐标可能位于位于6区、区、7区、区、8区。区。而新起点的坐标可能在而新起点的坐标可能在直线直线y=yb和线段的交点上和线段的交点上直线直线y=yt和线段的交点上和线段的交点上直线直线x=xr和线段的交点上和线段的交点上012345678(x1,y1)ybytxlxr第十六页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院1717第一种情况：第

14、一种情况：此时，若此时，若xlxsxr则则(xsys)为有效新起点。为有效新起点。第二种情况：第二种情况：此时，若此时，若xlxsxr则则(xsys)为有效新起点。为有效新起点。第三种情况：第三种情况：此时，若此时，若ybysyt则则(xsys)为有效新起点。为有效新起点。若此三种情况都不满足，则此线段不在窗口区内。若此三种情况都不满足，则此线段不在窗口区内。第十七页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院1818III 若若Xl=X=Xr线段的起点坐标可能位于线段的起点坐标可能位于1区区和和2区。区。而新起点的坐标可能在而新起点的坐标可能

15、在直线直线y=yb和线段的交点上和线段的交点上直线直线y=yt和线段的交点上和线段的交点上012345678(x1,y1)ybytxlxr第十八页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院1919第一种情况：第一种情况：此时，若此时，若xlxs xr 则则(xs ys)为有效新起点。为有效新起点。第二种情况：第二种情况：此时，若此时，若xlxs xr 则则(xs ys)为有效新起点。为有效新起点。若此二种情况都不满足，则此线段不在窗口区内。若此二种情况都不满足，则此线段不在窗口区内。使用同样的方法，可得到直线在窗口的另一个可见端使用同样的方法

16、，可得到直线在窗口的另一个可见端点。点。第十九页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院2020Cohen-Sutherland 算法算法(编码算法编码算法)基本思想：基本思想：Cohen-Sutherland直线剪裁算法以区域编码为基础，将窗口及其周围直线剪裁算法以区域编码为基础，将窗口及其周围的八个方向以的八个方向以4 bit的二进制数进行编码。对每条直线段的二进制数进行编码。对每条直线段p0(x0,y0)p1(x1,y1)分三种情况处理：分三种情况处理：(1)直线段完全可见，直线段完全可见，“简取简取”之。之。(2)直线段完全不可见，

17、直线段完全不可见，“简弃简弃”之。之。(3)直线段既不满足直线段既不满足“简取简取”的条件，的条件，也不满足也不满足“简弃简弃”的条件，需要对的条件，需要对直线段按交点进行分段，分段后重复上述处理。直线段按交点进行分段，分段后重复上述处理。第二十页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院2121算法步骤：算法步骤：第一步第一步判别线段两端点是否都落在窗口内，判别线段两端点是否都落在窗口内，如果是，则线段完全可见；否则进入第二步；如果是，则线段完全可见；否则进入第二步；第二步第二步判别线段是否为显然不可见，判别线段是否为显然不可见，如果是，则

18、裁剪结束；否则进行第三步；如果是，则裁剪结束；否则进行第三步；第三步第三步求线段与窗口边延长线的交点，求线段与窗口边延长线的交点，这个交点将线段分为两段，其中一段显然不可见，丢弃。对余下的这个交点将线段分为两段，其中一段显然不可见，丢弃。对余下的另一段重新进行第一步，第二步判断，直至结束另一段重新进行第一步，第二步判断，直至结束裁剪过程是递归的。裁剪过程是递归的。第二十一页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院2222第二十二页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院2323Cohen

19、-SutherLand算法算法(编码算法编码算法)特点：对显然不可见线段的快速判别特点：对显然不可见线段的快速判别编码方法：延长窗口的四条边线，由窗口四条边所在直线编码方法：延长窗口的四条边线，由窗口四条边所在直线把二维平面分成把二维平面分成9个区域，每个区域赋予一个四位编码，个区域，每个区域赋予一个四位编码，CtCbCrCl，上下右左；，上下右左；左域左域右域右域上上域域下下域域内域内域第二十三页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院2424第一位第一位1：点处于上边框线的上边；：点处于上边框线的上边；第二位第二位1：点处于下边框线的下

20、边；：点处于下边框线的下边；第三位第三位1：点处于右边框线的右边；：点处于右边框线的右边；第四位第四位1：点处于左边框线的左边；：点处于左边框线的左边；显然：显然：如果某线段的两端点的两个四位代码全为零时那么该线段完全位于窗口内，如果某线段的两端点的两个四位代码全为零时那么该线段完全位于窗口内，即全为即全为“0000”，可直接保留；，可直接保留；如果两端点的标识码的逻辑与（按位乘）运算，结果不为零，那么该线段必位于如果两端点的标识码的逻辑与（按位乘）运算，结果不为零，那么该线段必位于窗口外，可直接舍弃。窗口外，可直接舍弃。否则，这一线段可能与窗口相交。此时，需要对线段进行再分割，即找到与否则，

21、这一线段可能与窗口相交。此时，需要对线段进行再分割，即找到与窗口边线的一个交点，根据交点位置，赋予四位二进制编码，然后再进行上窗口边线的一个交点，根据交点位置，赋予四位二进制编码，然后再进行上述测试，测试结果是必有一段在窗口之外，可被排除，另一段再重复上述处述测试，测试结果是必有一段在窗口之外，可被排除，另一段再重复上述处理过程。理过程。直到全部线段均被舍弃或被保留为止。直到全部线段均被舍弃或被保留为止。第二十四页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院2525Cohen-SutherLand算法算法(编码算法编码算法)端点编码：定义为它所

22、在区域的编码端点编码：定义为它所在区域的编码结论：当线段的两个端点的编码的结论：当线段的两个端点的编码的逻辑逻辑“与与”非零非零时时 ，线，线段为显然不可见的段为显然不可见的 第二十五页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院2626求交测试顺序固定求交测试顺序固定(左上右下）左上右下）最坏情形，线段求交四次。最坏情形，线段求交四次。Cohen-SutherLand算法算法(编码算法编码算法)对于那些非完全可见、又非显然不可见的线段，需要对于那些非完全可见、又非显然不可见的线段，需要求交求交（如，线段（如，线段AD)AD)，求交前，求交前先

23、测试先测试与窗口哪条边所在与窗口哪条边所在直线有交？直线有交？(按序判断端点编码中各位的值按序判断端点编码中各位的值ClCtCrCbClCtCrCb）第二十六页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院27271）特点：）特点：容易将不需要裁剪的直线挑出。容易将不需要裁剪的直线挑出。规则是：如果一条直线的两端在同一区域，则该直线不需要裁剪，否则该直规则是：如果一条直线的两端在同一区域，则该直线不需要裁剪，否则该直线为可能裁剪直线。线为可能裁剪直线。对可能裁剪的直线缩小了与之求交的边框范围。对可能裁剪的直线缩小了与之求交的边框范围。规则是：如果

24、直线的一个端点在上（下、左、右）域，则此直线与上边框求规则是：如果直线的一个端点在上（下、左、右）域，则此直线与上边框求交，然后删去上边框以上的部分。该规则对直线的另一端点也适用。一条直交，然后删去上边框以上的部分。该规则对直线的另一端点也适用。一条直线至多只需要与两条边框求交。线至多只需要与两条边框求交。用编码方法可快速判断线段用编码方法可快速判断线段-完全可见和显然不可见。完全可见和显然不可见。2）特别适用二种场合：）特别适用二种场合：大窗口场合；大窗口场合；窗口特别小的场合，如光标拾取图形时窗口特别小的场合，如光标拾取图形时,光标看作小的裁剪窗口。光标看作小的裁剪窗口。第二十七页，讲稿共

25、九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院2828例题：例题：例题：例题：P P1 1P P2 2P1：(-3/2,1/6)；编码；编码(0001)P2：(1/2,3/2)；编码；编码(1000)(2)求右边交点，得求右边交点，得 P1(1,11/6)P2(-1,1/2)；并编码，并编码，判别之不可见判别之不可见(1)求左边交点，得求左边交点，得P1P2;P1:(-1,1/2);编码编码(0000)判别知非完全可见，且判别知非完全可见，且P1在窗口内，在窗口内，因此交换因此交换P1P2得新线段得新线段P1P2；P1：(1/2,3/2)；编码；编码(1

26、000)P2：(-1,1/2)；编码编码(0000)(3)求上边交点，得求上边交点，得 P1(-1/4,1)P2(-1,1/2)；并编；并编码，两端点编码全部为码，两端点编码全部为0，线段完全可见，程序结束线段完全可见，程序结束P1P1P1第二十八页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院2929Cohen-SutherLand算法算法(编码算法编码算法)如何判定该与窗口的哪条边求交呢？如何判定该与窗口的哪条边求交呢？编码中对应位为编码中对应位为1的边。的边。2）if(ai=bi=ci=di=0)则显示整条直线，取出下一条直线，返回则显示整

27、条直线，取出下一条直线，返回1）；）；否则否则if(a1&a2)or(b1&b2)or(c1&c2)or(d1&b2)=1)则取出下一条直线，返回则取出下一条直线，返回1）；）；否则否则例子：依次对每条直线例子：依次对每条直线P1P2作如下处理作如下处理1）对直线两端点）对直线两端点P1、P2按各自所在的区域编码，按各自所在的区域编码，P1、P2的编码分别记为：的编码分别记为：C1(P1)=a1,b1,c1,d1，C2(P2)=a2,b2,c2,d2其中其中ai，bi，ci，di取值域为取值域为0，1，i=1,2第二十九页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学

28、院计算机科学与技术学院30303）if(a1&a2=1)，则求直线与窗上边（，则求直线与窗上边（yyw_max)之交点，并之交点，并删去交点以上部分；删去交点以上部分；if(b1&b2=1)，则求直线与窗下边（，则求直线与窗下边（yyw_min)之交点，并删去之交点，并删去交点以下部分；交点以下部分；if(c1&c2=1)，则求直线与窗右边（，则求直线与窗右边（xxw_max)之交点，并删去交点以右部分；之交点，并删去交点以右部分；if(d1&d2=1)，则，则求直线与窗左边（求直线与窗左边（xxw_max)之交点，并删去交点以左部分；之交点，并删去交点以左部分；4）返回）返回1）。）。第三十

29、页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院3131第三十一页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院3232中点分割算法中点分割算法基本思想：基本思想：从从P P0 0点出发找出离点出发找出离P P0 0最近的可见点，和从最近的可见点，和从P P1 1点出发找出离点出发找出离P P1 1最近的可最近的可见点。这两个可见点的连线就是原线段的可见部分。见点。这两个可见点的连线就是原线段的可见部分。定义：定义：线段端点的最近可见点是指任一线段被窗口裁剪后所得两个新端点中离线段端点的最近可见点是

30、指任一线段被窗口裁剪后所得两个新端点中离该端点较近的一个点。该端点较近的一个点。从从P0点出发找出点出发找出距距P0最近的可见点（图中为最近的可见点（图中为A点），点），从从P1点出发找出距点出发找出距P1最近的可见点（图中为最近的可见点（图中为B）。）。取中点取中点Pm=(P1+P2)/2。第三十二页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院3333中点分割法中点分割法与前一种与前一种Cohen-Sutherland算法一样首先对线段端点进行编码，并算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况把线段与窗口的关系分为三种情

31、况:全在全在、完全不在完全不在和和线段与窗口线段与窗口有交有交。对前两种情况，进行一样的处理。对前两种情况，进行一样的处理。对第三类线段的处理对第三类线段的处理当对直线段不能简取也不能简弃时，不断地用对分方法，舍去线段的不可见当对直线段不能简取也不能简弃时，不断地用对分方法，舍去线段的不可见部分，用中点去逼近线段与窗口边界的交点。部分，用中点去逼近线段与窗口边界的交点。简单地简单地用中点分割的方法求出线段与用中点分割的方法求出线段与窗口的交点，窗口的交点，把线段等分为二段，对把线段等分为二段，对两段重复上述测试处理，直至每条线两段重复上述测试处理，直至每条线段完全在窗口内或完全在窗口外。段完全

32、在窗口内或完全在窗口外。第三十三页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院3434实现算法：（实现算法：（以以P0点为例说明）点为例说明）1)排斥性测试排斥性测试测试线段是否完全被排斥在窗口之外，若测试线段是否完全被排斥在窗口之外，若是，则无线段输出，算法结束。否则执行是，则无线段输出，算法结束。否则执行下一步；下一步；2)包含性测试包含性测试测试测试P1点是否包含在窗口内，如果是，则点是否包含在窗口内，如果是，则P1点点即为即为P0的最远可选点，算法结束，否则，执行下的最远可选点，算法结束，否则，执行下一步；一步；3)将直线段将直线段P0

33、P1于中点于中点Pm处分割，则分如下几处分割，则分如下几种情况处理：种情况处理：第三十四页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院3535线段线段MP1完全在窗口之外，那么便以线段完全在窗口之外，那么便以线段P0M为新的线为新的线段段P0P1，然后返回算法的第一步重新开始测试；，然后返回算法的第一步重新开始测试；如果线段如果线段MP1没有被完全排斥在窗口之外，那么便以线段没有被完全排斥在窗口之外，那么便以线段MP1作为新线段作为新线段P0P1，然后返回算法的第一步。，然后返回算法的第一步。P0P1MP0P1MP0P1MP0P1M第三十五页，

34、讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院3636中点分割算法中点分割算法-求线段与窗口的交点求线段与窗口的交点从从P0出发找距离出发找距离P0最近可见点采用中点分割方法最近可见点采用中点分割方法先求出先求出P0P1的中点的中点Pm,若若P0Pm不是显然不可见的，不是显然不可见的，并且并且P0P1在窗口中有可见部分，在窗口中有可见部分，则距则距P0最近的可见点一定落在最近的可见点一定落在P0Pm上，所以用上，所以用P0Pm代替代替P0P1；否则取否则取PmP1代替代替P0P1。再对新的再对新的P0P1求中点求中点Pm。重复上述过程，直到。重复上

35、述过程，直到PmP1长度小于给定的控制常数为止，此时长度小于给定的控制常数为止，此时Pm收敛于交点。收敛于交点。从从P1出发找距离出发找距离P1最近可见点采用上面类似方法。最近可见点采用上面类似方法。第三十六页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院3737中点分割算法框图中点分割算法框图第三十七页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院3838算法步骤：算法步骤：(1)输输入入直直线线段段的的两两端端点点坐坐标标：p0(x0,y0)、p1(x1,y1)，以以及及窗窗口口的的四四条条边边

36、界坐标：界坐标：ymin、ymax、xmin和和xmax。(2)对对p0、p1进行编码：点进行编码：点p0的编码为的编码为code1，点，点p1的编码为的编码为code2。(3)若若code1|code2=0，对对直直线线段段应应简简取取之之，保保留留当当前前直直线线段段的的端端点点坐坐标标，转转(5)；否否则则，若若code1&code20，对对直直线线段段可可简简弃弃之之，转转(5)；当当上上述述两条均不满足时，进行步骤两条均不满足时，进行步骤(4)。(4)求出直线段的中点求出直线段的中点M，将，将p1M、p2M入栈。入栈。(5)当当栈栈不不空空时时，从从栈栈中中弹弹出出一一条条直直线线段

37、段，取取为为p0p1，转转(2)进进行行处处理理。否否则则，继续继续(6)。(6)当当栈栈为为空空时时，合合并并保保留留的的直直线线段段端端点点，得得到到窗窗口口内内的的直直线线段段p0p1。用用直直线线扫描转换算法画出当前的直线段扫描转换算法画出当前的直线段p0p1，算法结束。，算法结束。第三十八页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院3939中点分割算法的中点分割算法的核心思想是是通过二分逼近来确定直线段与通过二分逼近来确定直线段与窗口的交点窗口的交点。第三十九页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学

38、院计算机科学与技术学院4040第四十页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院4141重新构造重新构造算法步骤算法步骤：(1)若若code1|code2=0，对对 直直 线线 段段 应应 简简 取取 之之，结结 束束；否否 则则，若若code1&code20，对对直直线线段段可可简简弃弃之之，结结束束；当当这这两两条条均均不不满满足足时时，进行步骤进行步骤(2)。(2)找找出出该该直直线线段段离离窗窗口口边边界界最最远远的的点点和和该该直直线线段段的的中中点点。判判中中点点是是否否在在窗窗口口内内：若若中中点点不不在在窗窗口口内内，则则把把

39、中中点点和和离离窗窗口口边边界界最最远远点点构构成成的的线线段段丢丢掉掉，以以线线段段上上的的另另一一点点和和该该中中点点再再构构成成线线段段求求其其中中点点；如如中中点点在在窗窗口口内内，则则又又以以中中点点和和最最远远点点构构成成线线段段，并并求求其其中中点点，直直到到中中点点与与窗窗口口边边界界的的坐坐标标值值在在规规定定的的误误差差范范围围内内相相等等，则则该该中中点就是该线段落在窗口内的一个端点坐标。点就是该线段落在窗口内的一个端点坐标。(3)如如另另一一点点在在窗窗口口内内，则则经经(2)即即确确定定了了该该线线段段在在窗窗口口内内的的部部分分。如如另另一一点点不不在在窗窗口口内内

40、，则则该该点点和和所所求求出出的的在在窗窗口口上上的的那那一一点点构构成成一一条条线线段，重复步骤段，重复步骤(2)，即可求出落在窗口内的另一点。，即可求出落在窗口内的另一点。第四十一页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院4242第四十二页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院4343#defineTRUE1#defineFALSE0intmid_trim(p1,p2,xmin,ymin,xmax,ymax,a)floatp13,p23,xmin,ymin,xmax,ymax,a3

41、;floatA3,B3,M3;set_point(p1,A);set_point(p2,B);while(TRUE)if(Identify_line_out(A,B,xmin,ymin,xmax,ymax)=TRUE)retuenFALSE;if(Identify_pt_in(B,xmin,ymin,xmax,ymax)=TRUE)set_point(B,a);returnTRUE;第四十三页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院4444elseget_midpoint(A,B,M);if(Identify_line_out(M,B,xm

42、in,ymin,xmax,ymax)=TRUE)set_point(M,B);elseset_point(M,A);第四十四页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院4545第四十五页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院4646对分辩率为对分辩率为2N*2N的显示器，上述二分过程的显示器，上述二分过程至多进行至多进行N次。次。主要过程只用到加法和除法运算，适合硬件主要过程只用到加法和除法运算，适合硬件实现，实现，它可以用左右移位来代替乘除法，这它可以用左右移位来代替乘除法，这样就大大

43、加快了速度样就大大加快了速度。中点分割裁剪算法中点分割裁剪算法第四十六页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院4747梁友栋梁友栋Barsky算法算法算法基本思想：算法基本思想：设要裁剪的线段为设要裁剪的线段为P0P1P0P1 ，和窗口边界交于和窗口边界交于A,B,C,DA,B,C,D四点。四点。首先从首先从D、A和和P0三点三点中找出最靠近中找出最靠近P1的点。的点。图中显然为图中显然为A其次从其次从C、B和和P1中找中找出最靠近出最靠近P0的点，图的点，图中显然为中显然为B那么那么AB就是就是P0P1线段线段上的可见部分上的可见部分第

44、四十七页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院4848梁友栋梁友栋Barsky算法算法具体计算时将具体计算时将P0P1写成参数方程写成参数方程其中：其中：0=t=1第四十八页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院4949梁友栋梁友栋Barsky算法算法窗口边界分类：始边和终边窗口边界分类：始边和终边第四十九页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院5050梁友栋梁友栋Barsky算法算法交点计算交点计算xyyTyBxLxBABCD

45、P1P0第五十页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院5151梁友栋梁友栋Barsky算法算法为了确定始边和终边，以及求为了确定始边和终边，以及求P0P1与它们的交点，令与它们的交点，令易知交点的参数为易知交点的参数为第五十一页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院5252梁友栋梁友栋Barsky算法算法EFAB分析另外一个分析另外一个D第五十二页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院5353梁友栋梁友栋-Barsky-Bars

46、ky算法算法当当Qi=0时时 若若Di 0 时，线段不可见时，线段不可见（如图中（如图中AB，有，有QR=0，DR0 时时,分析另一分析另一D,（如图中的（如图中的EF就是这种情况，它使就是这种情况，它使QL=0，DL0和和QR=0，DR0。这时由于。这时由于EF和和x=xL及及x=xR平行，故平行，故不必去求出不必去求出EF和和x=xL及及x=xR的交点，而让的交点，而让EF和和y=yT及及y=yB的交点决定直线段上的可见部分。）的交点决定直线段上的可见部分。）EFAB第五十三页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院5454P1yxyT

47、yBxLxBABCDP0t0t0t1t1lP0lP1第五十四页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院5555第五十五页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院5656Nicholl-Lee-Nicholl算法算法NLN算法在求交计算前进行更多的区域测试来减少求交计算法在求交计算前进行更多的区域测试来减少求交计算，消除算，消除C-S算法中多次求交的情况。算法中多次求交的情况。基本想法：通过在裁剪窗口周围创立多个区域来对一条基本想法：通过在裁剪窗口周围创立多个区域来对一条直线段的多次裁剪。

48、也即对直线段的多次裁剪。也即对2D平面的更细的划分。平面的更细的划分。第五十六页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院5757Nicholl-Lee-Nicholl算法算法假定待裁剪线段假定待裁剪线段P0P1为非完全可见且非显然不可见。为非完全可见且非显然不可见。步骤：步骤：第一步，窗口四边所在的直线将二维平面划分成第一步，窗口四边所在的直线将二维平面划分成9个个区域，假定区域，假定落在区域落在区域0、4、5第五十七页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院5858Nicholl-Le

49、e-Nicholl算法算法第二步：从第二步：从P P0 0点向窗口的四个角点发出射线，这四条射线和窗口的四条点向窗口的四个角点发出射线，这四条射线和窗口的四条边所在的直线一起将二维平面划分为更多的小区域边所在的直线一起将二维平面划分为更多的小区域 。此时。此时P1P1的位置的位置决定了决定了P0P1P0P1和窗口边的相交关系。和窗口边的相交关系。第五十八页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院5959Nicholl-Lee-Nicholl算法算法第三步，确定第三步，确定P P1 1所在的区域所在的区域（判断（判断P P1 1所在区域位置，

50、所在区域位置，可判定可判定P P0 0、P P1 1与窗口哪条边求交与窗口哪条边求交)。根据窗口四边的坐标值及根据窗口四边的坐标值及P P0 0P P1 1和各射线的斜率可确和各射线的斜率可确定定P1P1所在的区域。所在的区域。第四步，求交点，确定第四步，求交点，确定P P0 0P P1 1的可见部分的可见部分特点特点：效率较高，但仅适合二维矩形窗口。：效率较高，但仅适合二维矩形窗口。第五十九页，讲稿共九十三页哦2022/9/252022/9/25计算机科学与技术学院计算机科学与技术学院6060非矩形窗口的线段裁剪非矩形窗口的线段裁剪思考：思考：凹多边形窗口的线段裁剪凹多边形窗口的线段裁剪圆和