cg-4-3 图形裁剪

《cg-4-3 图形裁剪》由会员分享，可在线阅读，更多相关《cg-4-3 图形裁剪（43页珍藏版）》请在金锄头文库上搜索。

1、第六章 图形的裁剪6.1 二维裁剪的概念6.2 直线段的裁剪算法6.3 多边形的裁剪算法6.4 文本裁剪16.1 二维裁剪的概念6.1.1 裁剪裁剪的原因u在现实或想像的空间中，图形可以有任意，甚至无限大的尺寸u但显示器的尺寸是有限的，被显示的图形有的部分落在窗口之内，有的部分落在窗口之外u落在窗口之外的图形的部分不应该被显示，需要舍弃26.1 二维裁剪的概念裁剪的概念u确定图形中哪些部分落在显示区之内，哪些部分落在显示区之外,以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪36.1 二维裁剪的概念裁剪的过程u逐个判断构成图形的点、线段、文字等，是否包含在指定窗口区域内裁剪算法的效率u

2、裁剪的运算量非常大,算法的效率很重要裁剪方法的选择u根据实际情况来选择裁剪方法,或考虑用硬件来实现46.1 二维裁剪的概念6.1.2 点的裁剪对于给定点P(x,y),则P点在窗口内的条件是： ux1xx2uy1yy2否则，P点就在窗口外等号成立时，表明点在窗口边界上，也认为是可见的(x1,y1)(x2,y2)56.1 二维裁剪的概念6.1.3 直线段的裁剪直线和窗口的关系分为三类：u 整条直线在窗口内，完全显示,例如直线au 整条直线在窗口外，不显示,例如直线b u 直线的一部分在窗口内，一部分在窗口外,例 如直线c,da cbd66.1 二维裁剪的概念直线段AB两端点(A,B)的位置关系：u

3、 两个端点都窗口内：整条直线在窗口内u 两个端点一内一外：直线的一部分在窗口内 u 两个端点都窗口外：一部分在窗口外，如直线d整条直线在窗口外,如直线ba cbd76.1 二维裁剪的概念l直线裁剪的传统法直接求交点法u求直线与窗口边框的交点，然后对交点的性质作分 析,显示交点与窗口内端点（或另一交点）之间的可 见部分86.1 二维裁剪的概念主要步骤：u通过端点位置关系,直接判断出完全在窗口内的直线u对其余直线，逐条与边框求交点，对交点进行分析，并将窗口外的部分删去算法特点u该算法清楚解释了二维裁剪的含义，但效率较低9第六章 图形的裁剪6.1 二维裁剪的概念6.2 直线段的裁剪算法6.4 多边形

4、的裁剪算法6.4 文本裁剪106.2 直线段的裁剪l直线的裁剪算法直线段裁剪算法是复杂图形裁剪的基础u复杂的曲线可以通过折线段来近似常用的直线段裁剪算法：uuCohen-SutherlandCohen-Sutherland算法算法uu中点分割算法中点分割算法u梁友栋barskey算法116.2.1 Cohen-SutherlandCohen-Sutherland算法算法l基本思想：对于每条直线段P1P2分为三种情况处理:u（1）若P1P2完全在窗口内，则显示该线段P1P2u（2）若P1P2明显在窗口外，则丢弃该线段u（3）若线段不满足（1）或（2）的条件：在直线与边框的交点处把线段分为两段其中

5、一段完全在窗口外，可弃之，然后对另一段重复上述处理。12Cohen-Sutherland算法l编码算法：将窗口边线两边沿长，得到九个区域，每一个区域都用一个四位二进制数（0或1）编码来表示编码方法：u四位数分别按其区域相对于上、下、右、左 四条边框线的位置编码为0（位于窗口侧）或1（位于非窗口侧）直线的端点都按其所处区域赋予相应的区域码13Cohen-Sutherland算法四位区域码的确定：u按照上、下、右、左 四条边框线的顺序u位于窗口侧编码为0 ，位于非窗口侧编码为1100100010101100000000100101000100110x = xRx = xLy = yTy = yB窗

6、口14Cohen-Sutherland裁剪l判断规则： 若code1=0,且code2=0,则P1P2完全在窗口内，“取” ；若code1&code20，则P1P2完全在窗口外，“弃”； 否则，求直线与边框的交点，在交点处把线段分为两 段u其中一段完全在窗口外，可弃之u对另一段重复上述处理。15说明：1.当两个端点在窗口边线外的同侧位置，则它们的四位代码中，有一相同位，同时为“1”，显然两个端点代码的逻辑与不等于零。即：code1&code20 。此检查判断直线在窗口外，应全部舍弃。2.如果直线两端点不符合上述两种情况，不能简单地全部保留或全部舍弃直线时，则需计算出直线与窗口边线的交点，将直线

7、分段后继续进行检查判断。这样可以逐 段地舍弃位于窗口外的线段，保留剩在窗口内的线段。 163.用编码裁剪算法对 P1P2线段裁剪，可以在C点分割，对 P2C，CP1进行判别，舍弃P2C；再分割CP1于D点，对CD，DP1作 判别，舍弃CD，而DP1全部位于窗口内，算法结束。应该指出的是，分割线段是从C点还是D点开始，这是 难以确定的，因此只能随机的，但是最后结果是相同的17ABCDEFGHIJ例题: 写出图中线段端点的区域编码，并将线段分 类（可见、不可见、需裁剪）。【解解】 （上、下、右、左）A(0001)B(1000)C(0000)D(1010)E（0000）F（0000）G（0100）H

8、（0010）I（1001）J（1000）000100011001100110001000101010100010001001100110010001000101010100000000181、可见线段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点以下部分显示ABA(0001)B(1000）C(0000)D(10

9、10)E(0000)F(0000)I(1001)J(1000)B（0000）线段分类：19Cohen-Sutherland算法lCohen-Sutherland算法小结特点：可快速判断线段的完全可见和显然不可见优点：本算法的优点在于简单，易于实现。局限：u本算法对于其它形状的窗口未必同样有效u在这个算法中求交点计算量较大206.2.2 中点分割裁剪算法中点分割裁剪算法l中点分割裁剪算法基本思想：与Cohen-Sutherland算法一样，首先对线段端点进行编码，并把线段与窗口的关系分为三种情况，对前两种情况的处理，与Cohen-Sutherland算法相同；对于第三种情况，求线段与窗口的交点时

10、采用中点分割的方法。21（3）分割直线段P1P2于中点Pm。如果Pm在窗口之外，那 么以线段P1Pm作为新的P1P2线段，从算法的第一步重新 开始执行。反之，以线段PmP2为新的线段P1P2（如图的 线段c）开始执行。分割直线段 P1P2于中点PmPm在窗口之外,以线段P1Pm 作为新的P1P2再取中点Pm在窗口之内,以线段PmP2作 为新的P1P2再取中点22中点分割裁剪算法中点分割裁剪算法l中点分割法求交点（以求靠近P0的交点为例）求P0P1的中点Pm选择新的P0P1u若Pm在窗口外，用PmP1代替P0P1u若Pm在窗口内，用P0Pm代替P0P1对新的P0P1求中点Pm，重复上述过程u直到

11、PmP1长度小于给定的控制常数为止，此时Pm收敛于交点23l中点分割法算法分析中点算法的执行时间决定于图中所含直线的数量、长度和点阵图形的分辨率对分辩率为2N*2N的显示器，上述二分过程至多进行N次可以用左右移位来代替乘除法，适合硬件实现，大大加快了速度。中点分割裁剪算法24第六章 图形的裁剪6.1 二维裁剪的概念6.2 直线段的裁剪算法6.3 多边形的裁剪算法6.4 文本裁剪256.3多边形裁剪l多边形裁剪多边形的剪裁不是直线段裁剪的组合u多边形的剪裁要保持窗口内多边形的边界部分，使 剪裁后的多边形仍然保持封闭状态266.3多边形裁剪边界不再封闭，需要用窗口边界的恰当部分来封闭它276.3多

12、边形裁剪一个凹多边形可能被裁剪成几个小的、互不相连多边 形，需要用窗口边界的恰当部分来来连接它286.3 多边形的裁剪l常用的多边形裁剪算法：多边形逐边裁剪法uSutherland-Hodgman算法多边形窗口的双边裁剪法uWeiler-Athenton算法296.3.1 多边形逐边裁剪法l逐边裁剪法（Sutherland-Hodgman法）将多边形关于矩形窗口的裁剪，分解为关于窗口四条边所在直线的裁剪u用窗口的某一条边界裁剪多边形把多边形分成两部分:可见一侧；不可见一侧u然后将裁剪结果再用另一条边界进行裁剪如此重复多次，便可得到最终结果。u重复进行，完成四条边的裁剪适用于裁剪窗口为规则四边形

13、状（矩形）30流水线过程(左、上、右、下)u前边的结果是后边的输入6.3.1 多边形逐边裁剪法31（a）裁剪前 图形（b）以AB边 裁剪（c）以BC边裁 剪剪图形（d）以CD边 裁剪剪图形（e）以DA边裁 剪先用窗口的第一条 边界对要裁剪的多 边形进行裁剪，去 掉窗口外的图形， 保留窗口内的图形再用窗口的第二条 边界对要裁剪的多 边形进行裁剪，去 掉窗口外的图形， 保留窗口内的图形32起点终点边P4P5完全可见 ，则输点P5边P6P7完全不可 见，则无输出边部分可见，则 需计算此边与窗 口边界的交点假设以P4作为起点，最终输出的结果为：P5-S1- S2-P1-S3-S4-S5-S6-P4S1

14、S2S3S4S5S6336.3.2 多边形窗口的双边的裁剪法l双边的裁剪法（Weiler-Athenton法）适用于裁剪窗口为任意多边形（凸、凹、带内环）u主多边形：被裁剪多边形，记为A u裁剪多边形：裁剪窗口，记为B如果主多边形与裁剪多边形有交点，则交点成对出现，它们被分为如下两类：u进点：主多边形边界由此进入裁剪多边形内 u出点：主多边形边界由此离开裁剪多边形区域34多边形顶点的排序u多边形的外部边界取顺时针方向u内部边界或内空取逆时针方向以使多边形内部总是位于前进方向的右侧裁剪结果u结果区域的边界由A的部分边界和B的部分边界两部分构成，并且在交点处边界发生交替，即由A的边界转至B的边界，

15、或由B的边界转至A的边界6.3.2 多边形窗口的双边的裁剪法35l算法步骤1、建立物体多边形和裁剪多边形的顶点表2、求物体多边形和裁剪多边形的交点u将这些交点按顺序插入两多边形的顶点表中u在两顶点表中的相同交点间建立双向指针 3、建立空的裁剪结果顶点表4、裁剪u取一个交点，执行以下步骤。6.3.2 多边形窗口的双边的裁剪法36 裁剪过程：(1)沿着物体多边形顶点表顺序查找，直到发现下一个交点，将到该点为止的部分输出到结果顶点表中(2)把连接指针转到裁剪多边形表中；(3)沿着裁剪多边形顶点表顺序查找，直到发现下一个交点，将到该点为止的部分输出到结果顶点表中(4)把连接指针转到物体多边形表中 ；(

16、5)重复(1)(4)直至回到起始点 。6.3.2 多边形窗口的双边的裁剪法37例：用双边裁剪法的应用例：用双边裁剪法的应用l用双边边裁剪法裁剪下图红多边形表示裁剪窗口ABCDE FGeabcd12345638用双边裁剪法的应用用双边裁剪法的应用物体顶点表 裁剪顶点表A 1 2 B 3 CD 4 E F5G6Aa 2 b 3 c 4 d 5 e 61a 裁剪结果顶点表(取1为起点) ：1,2,b,3,C,D,4,d,5,G,6,1ABCDE FGeabcd12345639第六章 图形的裁剪6.1 二维裁剪的概念6.2 直线段的裁剪算法6.3 多边形的裁剪算法6.4 文本裁剪406.4 文本裁剪6.6.1 字符串裁剪法将包含整个字符串的外接矩形边框对窗口作裁剪u如果文本边框全部含在窗口内，则整个字符串可见 ；否则，认为整个字符串不可见具体实现时，只需判断文本边框的两条对角线是否全 部可见即