计算机软件及应用二维图形裁剪课件

1、二维图形裁剪裁剪概述 线段裁剪直接求交算法； Cohen-Sutherland算法；（重点，算法实现） 梁友栋-Barsky算法 多边形裁剪 Sutlerland_Hodgman算法（难点，算法实现） Weiler-Athenton算法 字符裁剪裁 剪二维图形裁剪预备知识：求交（矩形窗口）裁剪三维裁剪长方体裁剪体棱锥体体裁剪体直接求交算法编码裁剪算法中点分割算法被裁剪对象：直线段、多边形、三维实体一、裁剪概述 裁剪：是裁去窗口之外物体或物体部分的一种操作。剪裁的应用1、从定义的场景中抽取出用于观察的部分；2、在三维视图中标识出可见面；3、防止线段或对象的边界混淆；4、用实体造型来创建对象；5、

2、显示多窗口的环境；6、允许选择图形的一部分来进行拷贝，移动和删除。 “取景器”=窗口视区1 视区2（viewport） 裁剪的目的判断图形元素是否落在裁剪窗口之内并找出其位于内部的部分裁剪处理的基础图元关于窗口内外关系的判别图元与窗口的求交假定条件矩形裁剪窗口：xmin,xmaxymin,ymax待裁剪点或线段：点裁剪 点(x, y)在窗口内的充分必要条件是： 问题：对于任何多边形窗口，如何判别？WytWybWxlWxrP1P2P3线段相对于该窗口的情况有:线段全部位于窗口的内部（A）；线段全部位于窗口外部（B、C）；线段的中间部分在窗口内，而二端点在窗口外部（D）；线段的一端在窗口内，而另一

3、端在窗口外（E）。x=xLx=xRy=yBy=yTABCDE二、线段裁剪待裁剪线段和窗口的关系 线段完全可见显然不可见 线段至少有一端点在窗口之外，但非显然不可见 保留丢弃裁剪为提高效率，算法设计时应考虑：(一）快速判断线段完全在窗口内或外的情形；(二) 设法减少裁剪情形中求交次数和每次求交时所需的计算量。直接求交算法基本思想是：判断直线与窗口的位置关系，确定该直线是完全可见、部分可见或完全不可见，然后输出处于窗口内线段的端点，并显示此线段。根据直线段和窗口的关系可知：（1）整条线在窗口之内。此时，不需剪裁，显示整条线段。（2）整条线在窗口之外，此时，不需剪裁，不显示整条线段。（3）部分线在窗

4、口之内，部分线在窗口之外。此时，需要求出线段与窗口边界的交点，并将窗口外的线段部分剪裁掉，显示窗口内的部分。例1 设有直线段P0P1，有一个矩形裁剪窗口，写出对该线段裁剪的算法。1）求出直线P0P1与窗口的交点I，如图（a）所示。2）取P0 I线段显示，擦除I P1线段，并将P1替换I，即得P0P1线段，裁剪结束。如图（b）所示。 P0P1IP0P1（a）（b）求线段与窗口交点设线段两端点坐标为：和则过这两点的直线方程为：其中k为斜率。上述直线方程与窗口各边界的交点为：左：右：下：上：基本思想：对于每条待裁剪的线段P1P2分三种情况处理：若P1P2完全在窗口内，则显示该线段P1P2，简称“取”

5、之；若P1P2完全在窗口外，则丢弃该线段，简称“舍”之；若线段既不满足“取”的条件，也不满足“舍”的条件，则求线段与窗口边界的交点，在交点处把线段分为两段，其中一段完全在窗口外，可舍弃之，然后对另一段重复上述处理。 核心思想：分区编码和线段分割。 Cohen-Sutherland 算法 (编码算法) 分区编码方法：图形区域划分成九个区域。四位编码 表示端点所处的位置： (-) 上 下 右 左第一位为“1”时，表示点在y=yT的上方；第二位为“1”时，表示点在y=yB的下方；第三位为“1”时，表示点在x=xR的右方；第四位为“1”时，表示点在x=xL的左方。0000000100101000010

6、01001101001010110 x=xLx=xRy=yBy=yT11111 1 1 1#define LEFT 1#define RIGHT 2#define BOTTOM 4#define TOP 8编码原则每个区域赋予一个四位编码，CtCbCrCl，上下右左；编码方法练习：请给出右图的线段端点编码（端点编码：定义为它所在区域的编码）x=xLx=xRy=yBy=yTABCDE第一步 判别线段两端点是否都落在窗口内，如果是， 则线段完全可见；否则进入第二步；第二步 判别线段是否为显然不可见，如果是，则裁 剪结束；否则进行第三步 ；第三步 求线段与窗口边延长线的交点，这个交点将 线段分为两段

7、，其中一段显然不可见，丢弃。 对余下的另一段重新进行第一步，第二步判断， 直至结束 Cohen-Sutherland 算法步骤当线段的两个端点的编码的逻辑“与”非零时 ，线段为显然不可见的。也可以进行“按位与”运算，可知这两个端点是否同在视区的上、下、左、右；如code1=0101,code2=0110，则code1&code2=0100,表示在窗口下方。问题：显然可见的编码如何判断？编码判断当线段的两个端点的编码的逻辑“与”非零时 ，线段为显然不可见的。也可以进行“按位于”运算，可知这两个端点是否同在视区的上、下、左、右；如code1=0101,code2=0110，则code1&code2

8、=0100,表示在窗口下方。问题：显然可见的编码如何判断？编码判断对一条线段的可见性测试方法：（1）若线段两个端点的四位二进制编码全为0000，即两端点编码逻辑或运算为0，那么该线段完全位于窗口内，可直接保留；（2）对两端点的四位二进制编码进行逻辑与运算，若结果不为零，那么整条线段必位于窗口外，可直接舍弃；（3）否则，这条线段既不能直接保留，也不能直接舍弃，它可能与窗口相交。此时，需要对线段进行再分割，即找到与窗口边线的一个交点，根据交点位置，赋予四位二进制编码，并对分割后的线段按照一定的顺序（如左右下上）进行检查，决定保留、舍弃或再次进行分割。重复这一过程，直到全部线段均被舍弃或保留为止。例

9、：分别给下列直线段编码，并判断是否需要剪裁。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裁剪的基本过程（按左右下上的顺序）： 由于codeA | codeB0，对AB不能全部保留；又因为codeA & codeB=0，对AB不能全部舍

10、弃，因此要对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的编码还没有达到0000，再求得下边交点为P2，AP2必定在窗口外，故裁剪掉，并用A替换P2。如图（d）所示。 对剩下的直

11、线段AB再进行判断，现在A编码为0000，B编码为0000，由于codeA | codeB=0，全在窗口中，故全部保留。最后得到裁剪后的线段为AB，算法结束。 求交测试顺序固定(左上右下）最坏情形，线段求交四次。对于那些非完全可见、又非显然不可见的线段，需要求交（如线段AD)，求交前先测试与窗口哪条边所在直线有交？(按序判断端点编码中各位的值ClCtCrCb） 1）特点：用编码方法可快速判断线段- 完全可见和显然不可见。 2）特别适用二种场合： 大窗口场合； 窗口特别小的场合(如, 光标拾取图形时, 光标看作小的裁剪窗口。）编码算法特点设要裁剪的线段是P0P1。 P0P1和窗口边界交于A,B,

12、C,D四点，见图。算法的基本思想是从A,B和P0三点中找出最靠近的P1点，图中要找的点是P0。从C,D和P1中找出最靠近P0的点。图中要找的点是C点。那么P0C就是P0P1线段上的可见部分。梁友栋-Barsky算法 线段的参数表示x=x0+txy=y0+ty 0=t tl,则可见线段区间 tl , tut0t1t2t3P01交点计算P13.始边和终边的确定及交点计算：令 QL= x DL= x0-xL QR= x DR= xR-x0 QB= y DB= y0-yB QT= y DT= yT-y0参数交点为: ti= Di / Qi i=L,R,B,TQi 0 ti为与终边交点参数当Qi =0时

13、 若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的交点决定直线段上的可见部分。） ABEFAB三、多边形裁剪错觉：直线段裁剪的组合？ 关键：要保持窗口内多边形的边界部分，而且要将窗框的有关部分按一定次序插入多边形的保留边界之间，从而使剪裁后的多边形的边仍然保持封闭状态。新的问题： 1）边界不再封闭，需要用窗口边界的恰当部分来封闭它，如何确定其边界？2）一个凹多边形可能被裁剪成几个小的多

14、边形，如何确定这些小多边形的边界？Sutherland-Hodgman算法思路：将多边形边界作为一个整体，分而治之。将多边形的各边先相对于窗口的某一条边界进行裁剪，然后将裁剪结果再与另一条边界进行裁剪，如此重复多次，便可得到最终结果。流水线过程(左上右下)：左边的结果是上边的开始。亦称逐边裁剪算法内侧空间与外侧空间多边形的边与半空间的关系PIS 可 见 侧PS 可 见 侧PIS 可 见 侧PS 可 见 侧(a)从外到内 (b)从内到内 (c)从内到外(d)从外到外输出P和I 输出P 输出I 不输出p1p2p3p4p5q1q2q3q4需要设置二个表： 输入顶点表(向量)存放被裁剪多边形的顶点p1

15、-pm。 输出顶点表(线性链表)存放裁剪过程中及结果的顶点 q1-qn。q5q6q7q8q1q2p3q7q8q5q6q4q3裁剪前： 裁剪后：输入顶点表：p1p2p3p4p5 输入顶点表: 不变输出顶点表： 空 输出顶点表: q1q2p3q7q8q5q6q4q3需要设置二个表： 输入顶点表(向量)存放被裁剪多边形的顶点p1- pm。 输出顶点表(线性链表)存放裁剪过程中及结果的顶点 q1- qn。实现方法：设置二个表 输入顶点表(向量)存放被裁剪多边形的顶点p1-pm。 输出顶点表(线性链表)存放裁剪过程中及结果的顶点 q1-qn。输入顶点表中各顶点要求按一定顺序排列，一般可采用顺时针或逆时针

16、方向。相对于裁剪窗口的各条边界，按顶点表中的顺序，逐边进行裁剪。算法中相对于各窗口边界的裁剪过程相同，且每次都是相对于前一次的结果进行处理。裁剪结果的顶点构成：裁剪边内侧的原顶点； 多边形的边与裁剪边的交点。顺序连接。特点：裁剪算法采用流水线方式， 适合硬件实现。可推广到任意凸多边形裁剪 窗口问题：一个凹多边形可能被裁剪成几个小的多边形，如何确定这些小多边形的边界？AFEDCBV1V2V3V4AFEDCBV1V2V3V4AED Sutherland-Hodgman多边形裁剪：输入顶点BAFEDC，输出顶点：V1 A V2 V3 E D V4Sutherland-Hodgman算法Weiler-

17、Athenton算法裁剪窗口为任意多边形（凸、凹、带内环）的情况：主多边形：被裁剪多边形，记为A 裁剪多边形：裁剪窗口，记为B 主多边形和裁剪多边形把二维平面分成两部分。内裁剪：AB外裁剪：A-B裁剪结果区域的边界由A的部分边界和B的部分边界两部分构成，并且在交点处边界发生交替，即由A的边界转至B的边界，或由B的边界转至A的边界 Weiler-Athenton算法如果主多边形与裁剪多边形有交点，则交点成对出现，它们被分为如下两类：进点：主多边形边界由此进入裁剪多边形内 如，I1,I3, I5, I7, I9, I11出点：主多边形边界由此离开裁剪多边形区域. 如， I0,I2, I4, I6,

18、 I8, I10 Weiler-Atherton（W-A）算法（双边裁剪法） 可以用一个有内孔的凹多边形去裁剪另一个也有内孔的凹多边形。 被裁剪的多边形主多边形 裁剪区域裁剪多边形 各多边形的外部边界取顺时针方向，而其内部边界或孔取逆时针方向。思路：主多边形和裁剪多边形均用它们的顶点表来定义。 这两类交点分别用进点表和出点表来存放。主多边形和裁剪多边形的边界若相交，交点必定成对地出现，其中一个交点为主多边形边进入裁剪多边形内部时的交点（称进点），另一个交点则为离开时的交点（称出点）。c1c2c3c4s1s2s3s4s5s6s7I1I2I3I4I5I6I7I8裁剪窗口多边形主多边形主多边形 裁剪

19、窗口 顶点表 顶点表 s1 c1 I1 I8 I2 I1 s2 c2 I3 I2 s3 I3 I4 c3 s4 I4 I5 I5 I6 c4 s5 I6 I7 I7 s6 c1 I8 s7 s1起点简单例4 : W-A算法进行多边形裁剪进点出点算法： 1.分别建立主多边形和裁剪多边形的顶点表； 2.求出主多边形与裁剪多边形的交点（进点和出点）并分别建立进点表和出点表； 3.将交点加入各顶点表中； 4. if 进点表为空 then finish（1）取一进点作为始点；（2）跟踪主多边形顶点表，直至发现下一交点，复制这一段主多边形顶点到内表中； 根据交点处指针，转到裁剪多边形顶点表中的相应位置跟踪裁剪多边形顶点表，直至发现下一交点，复制这一段裁剪多边形顶点到内表中； if 该交点不是起始点 then （2） if 进点表中还有未遍历到的交点 then （1）（3）finish复杂例5，分析裁剪过程，分别写出主多边形、裁剪多边形的顶点表，以及最终裁剪结果。Weiler-Athenton算法交点的奇异情况处理 1.与裁剪多边形边重