《[计算机软件及应用]二维图形裁剪》由会员分享，可在线阅读，更多相关《[计算机软件及应用]二维图形裁剪（47页珍藏版）》请在金锄头文库上搜索。
1、二维图形裁剪,裁剪概述 线段裁剪 直接求交算法； Cohen-Sutherland算法；（重点，算法实现） 梁友栋-Barsky算法 多边形裁剪 Sutlerland_Hodgman算法（难点，算法实现） Weiler-Athenton算法 字符裁剪,三维裁剪,被裁剪对象：直线段、多边形、三维实体,一、裁剪概述 裁剪：是裁去窗口之外物体或物体部分的一种操作。,剪裁的应用,1、从定义的场景中抽取出用于观察的部分； 2、在三维视图中标识出可见面； 3、防止线段或对象的边界混淆； 4、用实体造型来创建对象； 5、显示多窗口的环境； 6、允许选择图形的一部分来进行拷贝，移动和删除。,“取景器”=窗口,
2、视区1 视区2 （viewport）,裁剪的目的 判断图形元素是否落在裁剪窗口之内并找出其位于内部的部分 裁剪处理的基础 图元关于窗口内外关系的判别 图元与窗口的求交 假定条件 矩形裁剪窗口：xmin,xmaxymin,ymax 待裁剪点或线段：,点裁剪 点(x, y)在窗口内的充分必要条件是： 问题：对于任何多边形窗口，如何判别？,线段相对于该窗口的情况有: 线段全部位于窗口的内部（A）； 线段全部位于窗口外部（B、C）； 线段的中间部分在窗口内，而二端点在窗口外部（D）； 线段的一端在窗口内，而另一端在窗口外（E）。,二、线段裁剪,待裁剪线段和窗口的关系 线段完全可见 显然不可见 线段至少
3、有一端点在窗口之外，但非显然不可见,保留,为提高效率，算法设计时应考虑： (一）快速判断线段完全在窗口内或外的情形； (二) 设法减少裁剪情形中求交次数和每次求交时所需的计算量。,直接求交算法,基本思想是：判断直线与窗口的位置关系，确定该直线是完全可见、部分可见或完全不可见，然后输出处于窗口内线段的端点，并显示此线段。 根据直线段和窗口的关系可知： （1）整条线在窗口之内。此时，不需剪裁，显示整条线段。 （2）整条线在窗口之外，此时，不需剪裁，不显示整条线段。 （3）部分线在窗口之内，部分线在窗口之外。 此时，需要求出线段与窗口边界的交点，并将窗口外的线段部分剪裁掉，显示窗口内的部分。,例1
4、设有直线段P0P1，有一个矩形裁剪窗口，写出对该线段裁剪的算法。,1）求出直线P0P1与窗口的交点I，如图（a）所示。 2）取P0 I线段显示，擦除I P1线段，并将P1替换I，即得P0P1线段，裁剪结束。如图（b）所示。,（a）,（b）,求线段与窗口交点,设线段两端点坐标为： 和 则过这两点的直线方程为： 其中k为斜率。上述直线方程与窗口各边界的交点为： 左： 右： 下： 上：,基本思想：对于每条待裁剪的线段P1P2分三种情况处理： 若P1P2完全在窗口内，则显示该线段P1P2，简称“取”之； 若P1P2完全在窗口外，则丢弃该线段，简称“舍”之； 若线段既不满足“取”的条件，也不满足“舍”的
5、条件，则求线段与窗口边界的交点，在交点处把线段分为两段，其中一段完全在窗口外，可舍弃之，然后对另一段重复上述处理。 核心思想：分区编码和线段分割。,Cohen-Sutherland 算法 (编码算法),分区编码方法：图形区域划分成九个区域。 四位编码 表示端点所处的位置： (-) 上 下 右 左 第一位为“1”时，表示点在y=yT的上方； 第二位为“1”时，表示点在y=yB的下方； 第三位为“1”时，表示点在x=xR的右方； 第四位为“1”时，表示点在x=xL的左方。,1111,编码原则,每个区域赋予一个四位编码，CtCbCrCl，上下右左；,编码方法,练习：请给出右图的线段端点编码（端点编码
6、：定义为它所在区域的编码）,第一步 判别线段两端点是否都落在窗口内，如果是， 则线段完全可见；否则进入第二步； 第二步 判别线段是否为显然不可见，如果是，则裁 剪结束；否则进行第三步 ； 第三步 求线段与窗口边延长线的交点，这个交点将 线段分为两段，其中一段显然不可见，丢弃。 对余下的另一段重新进行第一步，第二步判断， 直至结束,Cohen-Sutherland 算法步骤,当线段的两个端点的编码的逻辑“与”非零时 ，线段为显然不可见的。也可以进行“按位与”运算，可知这两个端点是否同在视区的上、下、左、右； 如code1=0101,code2=0110，则code1&code2=0100,表示在
7、窗口下方。 问题：显然可见的编码如何判断？,编码判断,当线段的两个端点的编码的逻辑“与”非零时 ，线段为显然不可见的。也可以进行“按位于”运算，可知这两个端点是否同在视区的上、下、左、右； 如code1=0101,code2=0110，则code1&code2=0100,表示在窗口下方。 问题：显然可见的编码如何判断？,编码判断,对一条线段的可见性测试方法： （1）若线段两个端点的四位二进制编码全为0000，即两端点编码逻辑或运算为0，那么该线段完全位于窗口内，可直接保留； （2）对两端点的四位二进制编码进行逻辑与运算，若结果不为零，那么整条线段必位于窗口外，可直接舍弃； （3）否则，这条线段
8、既不能直接保留，也不能直接舍弃，它可能与窗口相交。 此时，需要对线段进行再分割，即找到与窗口边线的一个交点，根据交点位置，赋予四位二进制编码，并对分割后的线段按照一定的顺序（如左右下上）进行检查，决定保留、舍弃或再次进行分割。重复这一过程，直到全部线段均被舍弃或保留为止。,例：分别给下列直线段编码，并判断是否需要剪裁。,例：Cohen-SutherLand算法过程：,过程： 1）输入线段AB的两端点坐标A（x0,y0）、B（x1,y1），以及裁剪窗口的四条边界：yt,yb,xl,xr。 2）对AB编码，A的编码codeA=0001，B的编码为codeB=0110。 3）线段AB裁剪的基本过程（
9、按左右下上的顺序）： 由于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）所
10、示。 A的编码还没有达到0000，再求得下边交点为P2，AP2必定在窗口外，故裁剪掉，并用A替换P2。如图（d）所示。 对剩下的直线段AB再进行判断，现在A编码为0000，B编码为0000，由于codeA | codeB=0，全在窗口中，故全部保留。 最后得到裁剪后的线段为AB，算法结束。,求交测试顺序固定(左上右下） 最坏情形，线段求交四次。,对于那些非完全可见、又非显然不可见的线段，需要 求交（如线段AD)，求交前先测试与窗口哪条边所在 直线有交？(按序判断端点编码中各位的值ClCtCrCb）,1）特点：用编码方法可快速判断线段- 完全可见和显然不可见。 2）特别适用二种场合： 大窗口场合
11、； 窗口特别小的场合(如, 光标拾取图形时, 光标看作小的裁剪窗口。）,编码算法特点,设要裁剪的线段是P0P1。 P0P1和窗口边界交于A,B,C,D四点，见图。 算法的基本思想是从A,B和P0三点中找出最靠近的P1点，图中要找的点是P0。从C,D和P1中找出最靠近P0的点。图中要找的点是C点。那么P0C就是P0P1线段上的可见部分。,梁友栋-Barsky算法,线段的参数表示 x=x0+tx y=y0+ty 0=t=1 x=x1-x0 y=y1-y0 窗口边界的四条边分为两类：始边和终边。,1.求出P0P1与两条始边的交点参数t0, t1 , 令tl=max(t0 ,t1, P0)，则tL即为
12、三者中离p1最近的点的参数 2.求出p0p1与两条终边的交点参数t2, t3, 令tu=min(t2,t3, P1) ，则tU即为三者中离p0最近的点的参数 若tu tl,则可见线段区间 tl , tu,t0,t1,t2,t3,P0,1,交点计算,P1,3.始边和终边的确定及交点计算： 令 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,T Qi 0 ti为与终边交点参数,当Qi =0时 若Di 0 时, 分析另一D, （如图中的EF就是这种情况，它使QL=0，
13、DL0和QR=0，DR0。这时由于EF和x=xL及x=xR平行，故不必去求出EF和x=xL及x=xR的交点，而让EF和y=yT及y=yB的交点决定直线段上的可见部分。）,A,B,E,F,A,B,三、多边形裁剪,错觉：直线段裁剪的组合？ 关键：要保持窗口内多边形的边界部分，而且要将窗框的有关部分按一定次序插入多边形的保留边界之间，从而使剪裁后的多边形的边仍然保持封闭状态。 新的问题： 1）边界不再封闭，需要用窗口边界的恰当部分来封闭它，如何确定其边界？,2）一个凹多边形可能被裁剪成几个小的多边形，如何 确定这些小多边形的边界？,Sutherland-Hodgman算法,思路：将多边形边界作为一个
14、整体，分而治之。将多边形的各边先相对于窗口的某一条边界进行裁剪，然后将裁剪结果再与另一条边界进行裁剪，如此重复多次，便可得到最终结果。 流水线过程(左上右下)：左边的结果是上边的开始。,亦称逐边裁剪算法,内侧空间与外侧空间 多边形的边与半空间的关系,(a)从外到内 (b)从内到内 (c)从内到外 (d)从外到外 输出P和I 输出P 输出I 不输出,需要设置二个表： 输入顶点表(向量)存放被裁剪多边形的顶点p1-pm。 输出顶点表(线性链表)存放裁剪过程中及结果的顶点 q1-qn。,裁剪前： 裁剪后： 输入顶点表：p1p2p3p4p5 输入顶点表: 不变 输出顶点表： 空 输出顶点表: q1q2
15、p3q7q8q5q6q4q3,需要设置二个表： 输入顶点表(向量)存放被裁剪多边形的顶点p1- pm。 输出顶点表(线性链表)存放裁剪过程中及结果的顶点 q1- qn。,实现方法： 设置二个表 输入顶点表(向量)存放被裁剪多边形的顶点p1-pm。 输出顶点表(线性链表)存放裁剪过程中及结果的顶点 q1-qn。 输入顶点表中各顶点要求按一定顺序排列，一般可采用顺时针或逆时针方向。 相对于裁剪窗口的各条边界，按顶点表中的顺序，逐边进行裁剪。,算法中相对于各窗口边界的裁剪过程相同，且每次都是相对于前一次的结果进行处理。,裁剪结果的顶点构成：裁剪边内侧的原顶点； 多边形的边与裁剪边的交点。 顺序连接。
16、,特点： 裁剪算法采用流水线方式， 适合硬件实现。 可推广到任意凸多边形裁剪 窗口,问题：一个凹多边形可能被裁剪成几个小的多边形，如何确定这些小多边形的边界？,Sutherland-Hodgman多边形裁剪：输入顶点BAFEDC， 输出顶点：V1 A V2 V3 E D V4,Sutherland-Hodgman算法,Weiler-Athenton算法,裁剪窗口为任意多边形（凸、凹、带内环）的情况： 主多边形：被裁剪多边形，记为A 裁剪多边形：裁剪窗口，记为B,主多边形和裁剪多边形把二维平面分成两部分。 内裁剪：AB 外裁剪：A-B,裁剪结果区域的边界由A的部分边界和B的部分边界两部分构成，并且在交点处边界发生交替，即由A的边界转至B的边界，或由
