《第3章二维图形裁剪.ppt》由会员分享，可在线阅读，更多相关《第3章二维图形裁剪.ppt（56页珍藏版）》请在第壹文秘上搜索。
1、本章主要内容本章主要内容3.1裁剪概述裁剪概述3.2线段裁剪线段裁剪直接求交算法；直接求交算法；Cohen-Sutherland算法；（重点，算法实现）算法；（重点，算法实现）中点算法3.3多边形裁剪多边形裁剪 Sutlerland_Hodgman算法算法（难点，算法实现）Weiler-Athenton算法 3.4字符裁剪字符裁剪裁 剪二维图形裁剪二维图形裁剪预备知识：求交（矩形窗口）（矩形窗口）裁剪裁剪三维裁剪长方体裁剪体棱锥体体裁剪体编码裁剪算法编码裁剪算法被裁剪对象：直线段、多边形直线段、多边形、三维实体1.裁剪：裁剪：是裁去窗口之外物体或物体部分的一种操作。是裁去窗口之外物体或物体部分
2、的一种操作。3.1裁剪概述裁剪概述“取景器”=窗口裁剪的目的裁剪的目的判断图形元素是否落在裁剪窗口之内并找出其位于内判断图形元素是否落在裁剪窗口之内并找出其位于内部的部分部的部分裁剪处理的基础裁剪处理的基础图元关于窗口内外关系的判别图元关于窗口内外关系的判别图元与窗口的求交图元与窗口的求交假定条件假定条件矩形裁剪窗口：矩形裁剪窗口：xmin,xmaxymin,ymax待裁剪点或线段：待裁剪点或线段：2.裁剪概述裁剪概述 点裁剪点裁剪 点点(x,y)在窗口内的充分必要条件是：在窗口内的充分必要条件是：问题：对于任何多边形窗口，如何判别？问题：对于任何多边形窗口，如何判别？xxxminmaxyyy
3、minmaxWytWybWxlWxrP1P2P3线段相对于该窗口的情况有情况有:线段全部全部位于窗口的内部窗口的内部（A）；线段全部全部位于窗口外部窗口外部（B、C）；线段的中间部分中间部分在窗口内窗口内，而二端点在窗口外部（D）；线段的一端在窗口内一端在窗口内，而另一端在窗口外另一端在窗口外（E）。x=xLx=xRy=yBy=yTABCDE3.2 线段裁剪线段裁剪待裁剪线段和窗口的关系待裁剪线段和窗口的关系 线段完全可见线段完全可见显然不可见显然不可见 线段至少有一端点在窗口之外，但非显然不可见线段至少有一端点在窗口之外，但非显然不可见 保留丢弃裁剪为提高效率，算法设计时应考虑：(一）快速判
4、断线段完全在窗口内或处的情形；(二)设法减少裁剪情形中求交次数和每次求交时所需的计算量。3.2.1直接求交算法基本思想基本思想是：判断直线与窗口的位置关系，确定该直线是完全可见、部分可见或完全不可见，然后输出处于窗口内线段的端点，并显示此线段。根据直线段和窗口的关系可知：（1）整条线在窗口之内。此时，不需剪裁，显示整条线段。（2）整条线在窗口之外，此时，不需剪裁，不显示整条线段。（3）部分线在窗口之内，部分线在窗口之外。此时，需要求出线段与窗口边界的交点，并将窗口外的线段部分剪裁掉，显示窗口内的部分。例1 设有直线段P0P1，有一个矩形裁剪窗口，写出对该线段裁剪的算法。1）判断线段端点的位置，
5、由图4-2（a）可知：P0不在窗口内，P1在窗口内。2）保持线段起始点在裁剪窗口内：交换两点，使P0在内，如图4-2（b）所示。3）求出直线与窗口的交点I，如图4-2（c）所示。4）取P0 I线段显示，擦除I P1线段，并将P1替换I，即得P0P1线段，裁剪结束。如图4-2（d）所示。P1P0P0P1P0P1IP0P1求线段与窗口交点求线段与窗口交点设线段两端点坐标为：和则过这两点的直线方程为：其中k为斜率。上述直线方程与窗口各边界的交点为：左：右：下：上：11111212)()(yxxkyxxxxyyykyxxkyxxLL11)(kyxxkyxxRR11)(0)(/1(11kyyyykxxB
6、B0)(/1(11kyyyykxxTT)(111yxP，)(222yxP，基本思想基本思想：对于每条待裁剪的线段P1P2分三种情况处理：若P1P2完全在窗口内，则显示该线段P1P2，简称“取取”之；若P1P2完全在窗口外，则丢弃该线段，简称“舍舍”之；若线段既不满足“取”的条件，也不满足“舍”的条件，则求线段与窗口边界的交点交点，在交点处把线段分为两段，其中一段完全在窗口外，可舍弃之，然后对另一段重复上述处理。核心思想：分区编码分区编码和线段分割线段分割。3.2.2Cohen-Sutherland 算法算法(编码算法)分区编码方法：图形区域划分成九个区域。四位编码 表示端点所处的位置：(-)上
7、上 下下 右右 左左第一一位为“1”时，表示点在y=yy=yT T的上方的上方；第二二位为“1”时，表示点在y=yy=yB B的下方的下方；第三三位为“1”时，表示点在x=xx=xR R的右方的右方；第四四位为“1”时，表示点在x=xx=xL L的左方的左方。000000010010100001001001101001010110 x=xLx=xRy=yBy=yT11111 1 1 1 1 1 1 1#define LEFT 1#define RIGHT 2#define BOTTOM 4#define TOP 8编码原则编码原则每个区域赋予一个四位编码，每个区域赋予一个四位编码，CtCbCr
8、Cl，上下右左；，上下右左；elseyyCt0max1当elsexxCr0max1当elsexxCl0min1当elseyyCb0min1当编码方法编码方法x=xLx=xRy=yBy=yTABCDE第一步第一步 判别线段两端点是否都落在窗口内，如果是，判别线段两端点是否都落在窗口内，如果是，则线段则线段完全可见完全可见；否则进入第二步；否则进入第二步；第二步第二步 判别线段是否为判别线段是否为显然不可见显然不可见，如果是，则裁，如果是，则裁 剪结束；否则进行第三步剪结束；否则进行第三步 ；第三步第三步 求线段与求线段与窗口边延长线窗口边延长线的交点，这个交点将的交点，这个交点将 线段分为两段，
9、其中一段显然不可见，丢弃。线段分为两段，其中一段显然不可见，丢弃。对余下的另一段重新进行第一步，第二步判断，对余下的另一段重新进行第一步，第二步判断，直至结束直至结束 Cohen-Sutherland 算法算法步骤编码判断编码判断对一条线段的可见性测试方法：对一条线段的可见性测试方法：（1）若线段两个端点的四位二进制编码全为）若线段两个端点的四位二进制编码全为0000，即两端，即两端点编码逻辑或运算为点编码逻辑或运算为0，那么该线段完全位于窗口内，可直，那么该线段完全位于窗口内，可直接保留；接保留；（2）对两端点的四位二进制编码进行逻辑与运算，若结果）对两端点的四位二进制编码进行逻辑与运算，若
10、结果不为零，那么整条线段必位于窗口外，可直接舍弃；不为零，那么整条线段必位于窗口外，可直接舍弃；（3）否则，这条线段既不能直接保留，也不能直接舍弃，）否则，这条线段既不能直接保留，也不能直接舍弃，它可能与窗口相交。此时，需要对线段进行再分割，即找它可能与窗口相交。此时，需要对线段进行再分割，即找到与窗口边线的一个交点，根据交点位置，赋予四位二进到与窗口边线的一个交点，根据交点位置，赋予四位二进制编码，并对分割后的线段按照一定的顺序（如左右下上）制编码，并对分割后的线段按照一定的顺序（如左右下上）进行检查，决定保留、舍弃或再次进行分割。重复这一过进行检查，决定保留、舍弃或再次进行分割。重复这一过
11、程，直到全部线段均被舍弃或保留为止。程，直到全部线段均被舍弃或保留为止。裁剪过程是递归的Cohen-Sutherland裁剪算法如何判定应该与窗口的哪条边求交呢？如何判定应该与窗口的哪条边求交呢？编码中对应位为1的边。计算线段P1(x1,y1)P2(x2,y2)与窗口边界的交点if(LEFT&code!=0)x=XL;y=y1+(y2-y1)*(XL-x1)/(x2-x1);else if(RIGHT&code!=0)x=XR;y=y1+(y2-y1)*(XR-x1)/(x2-x1);else if(BOTTOM&code!=0)y=YB;x=x1+(x2-x1)*(YB-y1)/(y2-y1
12、);else if(TOP&code!=0)y=YT;x=x1+(x2-x1)*(YT-y1)/(y2-y1);左交点右交点下交点上交点例：P1P2C1=0001C2=0000P1P2C1=0100C2=0101BCP1P2C1=0101C2=1010P1P2ADC1=0000C2=0000例：例：Cohen-SutherLand算法过程：过程：1）输入线段AB的两端点坐标A（x0,y0）、B（x1,y1），以及裁剪窗口的四条边界：yt,yb,xl,xr。2）对AB编码，A的编码codeA=0001，B的编码为codeB=0110。3）线段线段AB裁剪的基本过程（按左右下上的顺序）裁剪的基本过
13、程（按左右下上的顺序）：由于codeA|codeB0，对AB不能全部保留；又因为codeA&codeB=0，对AB不能全部舍弃，因此要对AB进行求交处理。由codeA=0001知A在窗口左边外侧，按左右下上的顺序求AB与窗口左边交点为P1，AP1必在窗口外，故裁剪掉，并用A替换P1。如图（b）所示。（交点替换是为了方便编程循环）。对P1B重复上述处理。A（原P1）编码为0000，B编码为0110；由于A（原P1）已在窗口内，交换A和B的坐标值与编码，则B编码为0000，A编码变为0110，按左右下上顺序求得右交点为P3；A（原B）P3必在窗口外，故裁剪掉，并用A替换P3。如图（c）所示。A的编
14、码还没有达到0000，再求得下边交点为P2，AP2必定在窗口外，故裁剪掉，并用A替换P2。如图（d）所示。对剩下的直线段AB再进行判断，现在A编码为0000，B编码为0000，由于codeA|codeB=0，全在窗口中，故全部保留。最后得到裁剪后的线段为AB，算法结束。求交测试顺序固定求交测试顺序固定(左上右下）左上右下）最坏情形，线段求交四次。最坏情形，线段求交四次。对于那些非完全可见、又非显然不可见的线段，需要求交求交（如线段AD)，求交前先测试与窗口哪条边所在直线有交？(按序判断端点编码中各位的值ClCtCrCb）1）特点：用编码方法可快速判断线段-完全可见和显然不可见。2）特别适用二种
15、场合：大窗口场合；窗口特别小的场合(如,光标拾取图形时,光标看作小的裁剪窗口。）编码算法特点算法的思路：算法的思路：采用与前相似的线段端点编码和相应的检查方法，采用与前相似的线段端点编码和相应的检查方法，先先判定完全可见线段和显然不可见线段判定完全可见线段和显然不可见线段。否则，将否则，将线段分割成相等的两段线段分割成相等的两段，然后对每一小段重，然后对每一小段重复上述的检查，复上述的检查，直至找到每段与窗口边界的交点或分割小直至找到每段与窗口边界的交点或分割小段的长度充分小段的长度充分小，可以视为一点时为止。，可以视为一点时为止。相当于：相当于：对分查找法求交，分割次数最多不超过线段端对分查
16、找法求交，分割次数最多不超过线段端点的表示精度点的表示精度。3.2.3 中点分割算法算法过程：1）输入线段AB的两端点坐标A（x0,y0）、B（x1,y1），以及裁剪窗口的四条边界：yt,yb,xl,xr。2）对AB编码，A的编码codeA=0001，B的编码为codeB=0110。3）线段AB裁剪的基本过程：例：中点例：中点算法裁剪过程：y=yTy=yBx=xLx=xRABBPm2Pm1Pm3y=yTy=yBx=xLx=xRBABPm2Pm1由于codeA|codeB0，对AB不能全部保留；又因为codeA&codeB=0，对AB不能全部舍弃，因此要对AB求中点处理；求AB中点。判断中点Pm1是否在窗口内，若不在窗口内，则将中点和离窗口最远点构成的线段去掉，以线段另一端点和该中点再构成线段，求其中点；若中点Pm1在窗口内，如上页左图所示。则以中点和最远点构成线段APm1，并求其中点Pm2，直至中点与窗口边界的坐标值在规定的误差范围内，则该中点就是线段落在窗口内的一个端点，用原线段端点A替代每一次保留的中点。若另一端点在窗口内，则经即可确定该线段在窗口内的部分；若不在窗口内，如右图，交
