CG-4-3图形裁剪.

1第六章图形的裁剪6.1二维裁剪的概念6.2直线段的裁剪算法6.3多边形的裁剪算法6.4文本裁剪26.1二维裁剪的概念6.1.1裁剪裁剪的原因在现实或想像的空间中，图形可以有任意，甚至无限大的尺寸但显示器的尺寸是有限的，被显示的图形有的部分落在窗口之内，有的部分落在窗口之外落在窗口之外的图形的部分不应该被显示，需要舍弃36.1二维裁剪的概念裁剪的概念确定图形中哪些部分落在显示区之内，哪些部分落在显示区之外,以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪46.1二维裁剪的概念裁剪的过程逐个判断构成图形的点、线段、文字等，是否包含在指定窗口区域内裁剪算法的效率裁剪的运算量非常大,算法的效率很重要裁剪方法的选择根据实际情况来选择裁剪方法,或考虑用硬件来实现56.1二维裁剪的概念6.1.2点的裁剪对于给定点P(x,y),则P点在窗口内的条件是：x1≤x≤x2y1≤y≤y2否则，P点就在窗口外等号成立时，表明点在窗口边界上，也认为是可见的(x1,y1)(x2,y2)66.1二维裁剪的概念6.1.3直线段的裁剪直线和窗口的关系分为三类：⑴整条直线在窗口内，完全显示,例如直线a⑵整条直线在窗口外，不显示,例如直线b⑶直线的一部分在窗口内，一部分在窗口外,例如直线c,dacbd76.1二维裁剪的概念直线段AB两端点(A,B)的位置关系：⑴两个端点都窗口内：整条直线在窗口内⑵两个端点一内一外：直线的一部分在窗口内⑶两个端点都窗口外：一部分在窗口外，如直线d整条直线在窗口外,如直线bacbd86.1二维裁剪的概念直线裁剪的传统法直接求交点法求直线与窗口边框的交点，然后对交点的性质作分析,显示交点与窗口内端点（或另一交点）之间的可见部分96.1二维裁剪的概念主要步骤：通过端点位置关系,直接判断出完全在窗口内的直线对其余直线，逐条与边框求交点，对交点进行分析，并将窗口外的部分删去算法特点该算法清楚解释了二维裁剪的含义，但效率较低10第六章图形的裁剪6.1二维裁剪的概念6.2直线段的裁剪算法6.4多边形的裁剪算法6.4文本裁剪116.2直线段的裁剪直线的裁剪算法直线段裁剪算法是复杂图形裁剪的基础复杂的曲线可以通过折线段来近似常用的直线段裁剪算法：Cohen-Sutherland算法中点分割算法梁友栋－barskey算法126.2.1Cohen-Sutherland算法基本思想：对于每条直线段P1P2分为三种情况处理:（1）若P1P2完全在窗口内，则显示该线段P1P2（2）若P1P2明显在窗口外，则丢弃该线段（3）若线段不满足（1）或（2）的条件：在直线与边框的交点处把线段分为两段其中一段完全在窗口外，可弃之，然后对另一段重复上述处理。13Cohen-Sutherland算法编码算法：将窗口边线两边沿长，得到九个区域，每一个区域都用一个四位二进制数（0或1）编码来表示编码方法：四位数分别按其区域相对于上、下、右、左四条边框线的位置编码为0（位于窗口侧）或1（位于非窗口侧）直线的端点都按其所处区域赋予相应的区域码14Cohen-Sutherland算法四位区域码的确定：按照上、下、右、左四条边框线的顺序位于窗口侧编码为0，位于非窗口侧编码为1100100010101100000000100101000100110x=xRx=xLy=yTy=yB窗口15Cohen-Sutherland裁剪判断规则：若code1=0,且code2=0,则P1P2完全在窗口内，“取”；若code1&code2≠0，则P1P2完全在窗口外，“弃”；否则，求直线与边框的交点，在交点处把线段分为两段其中一段完全在窗口外，可弃之对另一段重复上述处理。100110001010000100000010010101000110P1P2P3P416说明：1.当两个端点在窗口边线外的同侧位置，则它们的四位代码中，有一相同位，同时为“1”，显然两个端点代码的逻辑与不等于零。即：code1&code2≠0。此检查判断直线在窗口外，应全部舍弃。2.如果直线两端点不符合上述两种情况，不能简单地全部保留或全部舍弃直线时，则需计算出直线与窗口边线的交点，将直线分段后继续进行检查判断。这样可以逐段地舍弃位于窗口外的线段，保留剩在窗口内的线段。173.用编码裁剪算法对P1P2线段裁剪，可以在C点分割，对P2C，CP1进行判别，舍弃P2C；再分割CP1于D点，对CD，DP1作判别，舍弃CD，而DP1全部位于窗口内，算法结束。应该指出的是，分割线段是从C点还是D点开始，这是难以确定的，因此只能随机的，但是最后结果是相同的18ABCDEFGHIJ例题:写出图中线段端点的区域编码，并将线段分类（可见、不可见、需裁剪）。【解】（上、下、右、左）A(0001)B(1000)C(0000)D(1010)E（0000）F（0000）G（0100）H（0010）I（1001）J（1000）000110011000101000100110010001010000191、可见线段EF：E(0000),F(0000)2、不可见线段:IJ:(1001)and(1000)=(1000)3、待裁剪线段:AB:(0001)and(1000)=(0000)CD:(0000)and(1010)=(0000)AB的裁剪过程：求AB与上边框的交点B’（0000），删除B’点以上部分求AB’与左边框的交点A’（0000），删除A’点以下部分显示A’B’A(0001)B(1000）C(0000)D(1010)E(0000)F(0000)I(1001)J(1000)B’（0000）线段分类：20Cohen-Sutherland算法Cohen-Sutherland算法小结特点：可快速判断线段的完全可见和显然不可见优点：本算法的优点在于简单，易于实现。局限：本算法对于其它形状的窗口未必同样有效在这个算法中求交点计算量较大216.2.2中点分割裁剪算法中点分割裁剪算法基本思想：与Cohen-Sutherland算法一样，首先对线段端点进行编码，并把线段与窗口的关系分为三种情况，对前两种情况的处理，与Cohen-Sutherland算法相同；对于第三种情况，求线段与窗口的交点时采用中点分割的方法。22（3）分割直线段P1P2于中点Pm。如果Pm在窗口之外，那么以线段P1Pm作为新的P1P2线段，从算法的第一步重新开始执行。反之，以线段PmP2为新的线段P1P2（如图的线段c）开始执行。分割直线段P1P2于中点PmPm在窗口之外,以线段P1Pm作为新的P1P2再取中点Pm在窗口之内,以线段PmP2作为新的P1P2再取中点23中点分割裁剪算法中点分割法求交点（以求靠近P0的交点为例）求P0P1的中点Pm选择新的P0P1若Pm在窗口外，用PmP1代替P0P1若Pm在窗口内，用P0Pm代替P0P1对新的P0P1求中点Pm，重复上述过程直到PmP1长度小于给定的控制常数为止，此时Pm收敛于交点P0P1PmAB24中点分割法算法分析中点算法的执行时间决定于图中所含直线的数量、长度和点阵图形的分辨率对分辩率为2N*2N的显示器，上述二分过程至多进行N次可以用左右移位来代替乘除法，适合硬件实现，大大加快了速度。中点分割裁剪算法25第六章图形的裁剪6.1二维裁剪的概念6.2直线段的裁剪算法6.3多边形的裁剪算法6.4文本裁剪266.3多边形裁剪多边形裁剪多边形的剪裁不是直线段裁剪的组合多边形的剪裁要保持窗口内多边形的边界部分，使剪裁后的多边形仍然保持封闭状态276.3多边形裁剪边界不再封闭，需要用窗口边界的恰当部分来封闭它286.3多边形裁剪一个凹多边形可能被裁剪成几个小的、互不相连多边形，需要用窗口边界的恰当部分来来连接它296.3多边形的裁剪常用的多边形裁剪算法：多边形逐边裁剪法Sutherland-Hodgman算法多边形窗口的双边裁剪法Weiler-Athenton算法306.3.1多边形逐边裁剪法逐边裁剪法（Sutherland-Hodgman法）将多边形关于矩形窗口的裁剪，分解为关于窗口四条边所在直线的裁剪用窗口的某一条边界裁剪多边形把多边形分成两部分:可见一侧；不可见一侧然后将裁剪结果再用另一条边界进行裁剪如此重复多次，便可得到最终结果。重复进行，完成四条边的裁剪适用于裁剪窗口为规则四边形状（矩形）31流水线过程(左、上、右、下)前边的结果是后边的输入6.3.1多边形逐边裁剪法32（a）裁剪前图形（b）以AB边裁剪（c）以BC边裁剪剪图形（d）以CD边裁剪剪图形（e）以DA边裁剪先用窗口的第一条边界对要裁剪的多边形进行裁剪，去掉窗口外的图形，保留窗口内的图形再用窗口的第二条边界对要裁剪的多边形进行裁剪，去掉窗口外的图形，保留窗口内的图形33起点终点边P4P5完全可见，则输点P5边P6P7完全不可见，则无输出边部分可见，则需计算此边与窗口边界的交点假设以P4作为起点，最终输出的结果为：P5-S1-S2-P1-S3-S4-S5-S6-P4S1S2S3S4S5S6346.3.2多边形窗口的双边的裁剪法双边的裁剪法（Weiler-Athenton法）适用于裁剪窗口为任意多边形（凸、凹、带内环）主多边形：被裁剪多边形，记为A裁剪多边形：裁剪窗口，记为B如果主多边形与裁剪多边形有交点，则交点成对出现，它们被分为如下两类：进点：主多边形边界由此进入裁剪多边形内出点：主多边形边界由此离开裁剪多边形区域35多边形顶点的排序多边形的外部边界取顺时针方向内部边界或内空取逆时针方向以使多边形内部总是位于前进方向的右侧裁剪结果结果区域的边界由A的部分边界和B的部分边界两部分构成，并且在交点处边界发生交替，即由A的边界转至B的边界，或由B的边界转至A的边界6.3.2多边形窗口的双边的裁剪法36算法步骤1、建立物体多边形和裁剪多边形的顶点表2、求物体多边形和裁剪多边形的交点将这些交点按顺序插入两多边形的顶点表中在两顶点表中的相同交点间建立双向指针3、建立空的裁剪结果顶点表4、裁剪取一个交点，执行以下步骤。6.3.2多边形窗口的双边的裁剪法37裁剪过程：(1)沿着物体多边形顶点表顺序查找，直到发现下一个交点，将到该点为止的部分输出到结果顶点表中(2)把连接指针转到裁剪多边形表中；(3)沿着裁剪多边形顶点表顺序查找，直到发现下一个交点，将到该点为止的部分输出到结果顶点表中(4)把连接指针转到物体多边形表中；(5)重复(1)～(4)直至回到起始点。6.3.2多边形窗口的双边的裁剪法38例：用双边裁剪法的应用用双边边裁剪法裁剪下图红多边形表示裁剪窗口ABCDEFGeabcd12345639用双边裁剪法的应用物体顶点表裁剪顶点表A12B3CD4EF5G6Aa2b3c4d5e61a裁剪结果顶点表(取1为起点)：1,2,b,3,C,D,4,d,5,G,6,1ABCDEFGeabcd12345640第六章图形的裁剪6.1二维裁剪的概念6.2直线段的裁剪算法6.3多边形的裁剪算法6.4文本裁剪416.4文本裁剪6.6.1字符串裁剪法将包含整个字符串的外接矩形边框对窗口作裁剪如果文本边框全部含在窗口内，则整个字符串可见；否则，认为整个字符串不可见具体实现时，只需判断文本边框的两条对角线是否全部可见即可。426.4文本裁剪6.6.2字符裁剪法将包含每个字符的外接矩形边框分别对窗口作裁剪判定处在窗口边框上的字符，然后把字符串一分为二即可只要字符与窗口相交或者在其外面，都将被删除。STRINGTYPEINGTYPE裁剪436.4文本裁剪6.6.3笔划裁剪法把每个字符看成一系列直线（笔划）的集合，字符的裁剪就归结为对组成这些字符的直线（笔划）裁剪如果一个字符与边框相交，只删除该字符在窗口外的部分裁剪精度高，速度慢STRINGTYPERIN