第3章二维图形裁剪.ppt

《第3章二维图形裁剪.ppt》由会员分享，可在线阅读，更多相关《第3章二维图形裁剪.ppt（56页珍藏版）》请在三一办公上搜索。

1、计算机图形学基础,第3章 二维图形裁剪,本章主要内容,3.1裁剪概述3.2线段裁剪直接求交算法；Cohen-Sutherland算法；（重点，算法实现）中点算法3.3多边形裁剪 Sutlerland_Hodgman算法（难点，算法实现）Weiler-Athenton算法 3.4字符裁剪,三维裁剪,被裁剪对象：直线段、多边形、三维实体,1.裁剪：是裁去窗口之外物体或物体部分的一种操作。,3.1裁剪概述,“取景器”=窗口,视区1 视区2（viewport）,裁剪的目的判断图形元素是否落在裁剪窗口之内并找出其位于内部的部分裁剪处理的基础图元关于窗口内外关系的判别图元与窗口的求交假定条件矩形裁剪窗口：

2、xmin,xmaxymin,ymax待裁剪点或线段：,2.裁剪概述,点裁剪 点(x,y)在窗口内的充分必要条件是：问题：对于任何多边形窗口，如何判别？,线段相对于该窗口的情况有:线段全部位于窗口的内部（A）；线段全部位于窗口外部（B、C）；线段的中间部分在窗口内，而二端点在窗口外部（D）；线段的一端在窗口内，而另一端在窗口外（E）。,3.2 线段裁剪,待裁剪线段和窗口的关系 线段完全可见显然不可见 线段至少有一端点在窗口之外，但非显然不可见,保留,为提高效率，算法设计时应考虑：(一）快速判断线段完全在窗口内或处的情形；(二)设法减少裁剪情形中求交次数和每次求交时所需的计算量。,3.2.1直接求

3、交算法,基本思想是：判断直线与窗口的位置关系，确定该直线是完全可见、部分可见或完全不可见，然后输出处于窗口内线段的端点，并显示此线段。根据直线段和窗口的关系可知：（1）整条线在窗口之内。此时，不需剪裁，显示整条线段。（2）整条线在窗口之外，此时，不需剪裁，不显示整条线段。（3）部分线在窗口之内，部分线在窗口之外。此时，需要求出线段与窗口边界的交点，并将窗口外的线段部分剪裁掉，显示窗口内的部分。,例1 设有直线段P0P1，有一个矩形裁剪窗口，写出对该线段裁剪的算法。,1）判断线段端点的位置，由图4-2（a）可知：P0不在窗口内，P1在窗口内。2）保持线段起始点在裁剪窗口内：交换两点，使P0在内，

4、如图4-2（b）所示。3）求出直线与窗口的交点I，如图4-2（c）所示。4）取P0 I线段显示，擦除I P1线段，并将P1替换I，即得P0P1线段，裁剪结束。如图4-2（d）所示。,求线段与窗口交点,设线段两端点坐标为：和则过这两点的直线方程为：其中k为斜率。上述直线方程与窗口各边界的交点为：左：右：下：上：,基本思想：对于每条待裁剪的线段P1P2分三种情况处理：若P1P2完全在窗口内，则显示该线段P1P2，简称“取”之；若P1P2完全在窗口外，则丢弃该线段，简称“舍”之；若线段既不满足“取”的条件，也不满足“舍”的条件，则求线段与窗口边界的交点，在交点处把线段分为两段，其中一段完全在窗口外，

5、可舍弃之，然后对另一段重复上述处理。核心思想：分区编码和线段分割。,3.2.2Cohen-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,表示在窗口下方。问题：显然可见的编码如何判断？,编码判断,对一条线段的可见性测试方法：（1）若线段两个端点的

7、四位二进制编码全为0000，即两端点编码逻辑或运算为0，那么该线段完全位于窗口内，可直接保留；（2）对两端点的四位二进制编码进行逻辑与运算，若结果不为零，那么整条线段必位于窗口外，可直接舍弃；（3）否则，这条线段既不能直接保留，也不能直接舍弃，它可能与窗口相交。此时，需要对线段进行再分割，即找到与窗口边线的一个交点，根据交点位置，赋予四位二进制编码，并对分割后的线段按照一定的顺序（如左右下上）进行检查，决定保留、舍弃或再次进行分割。重复这一过程，直到全部线段均被舍弃或保留为止。,裁剪过程是递归的,Cohen-Sutherland裁剪算法,如何判定应该与窗口的哪条边求交呢？编码中对应位为1的边。

8、计算线段P1(x1,y1)P2(x2,y2)与窗口边界的交点if(LEFT,左交点,右交点,下交点,上交点,例：分别给下列直线段编码，并判断是否需要剪裁。,例：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不能全部舍弃，因此要对AB进行求交处理。由codeA=0001

9、知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）所示。对剩下的直线段AB再进行判断，现在A编码为0000，B编码为0000，

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

11、每一小段重复上述的检查，直至找到每段与窗口边界的交点或分割小段的长度充分小，可以视为一点时为止。相当于：对分查找法求交，分割次数最多不超过线段端点的表示精度。,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裁剪的基本过程：,例：中点算法裁剪过程：,由于codeA|codeB0，对AB不能全部保留；又因为codeA&codeB=0，对AB不能全部舍弃，因此要对AB求中点处理；求AB中点。判断中点Pm1是否在

12、窗口内，若不在窗口内，则将中点和离窗口最远点构成的线段去掉，以线段另一端点和该中点再构成线段，求其中点；若中点Pm1在窗口内，如上页左图所示。则以中点和最远点构成线段APm1，并求其中点Pm2，直至中点与窗口边界的坐标值在规定的误差范围内，则该中点就是线段落在窗口内的一个端点，用原线段端点A替代每一次保留的中点。若另一端点在窗口内，则经即可确定该线段在窗口内的部分；若不在窗口内，如右图，交换两端点，则该点和所求出的在窗口上的那一点构成一条线段AB，重复步骤，即可求出落进窗口的另外一点。并用原线段端点A替代每一次保留的中点。最后得到裁剪后的线段为AB，算法结束。,对分辩率为2N*2N的显示器，上

13、述二分过程至多进行N次。主要过程只用到加法和除法运算，适合硬件实现，它可以用左右移位来代替乘除法，这样就大大加快了速度。,中点分割裁剪算法特点,设要裁剪的线段是P0P1。P0P1和窗口边界交于A,B,C,D四点，见图。算法的基本思想是从A,B和P0三点中找出最靠近的P1点，图中要找的点是P0。从C,D和P1中找出最靠近P0的点。图中要找的点是C点。那么P0C就是P0P1线段上的可见部分。,3.2.4 梁友栋-Barsky算法,线段的参数表示x=x0+txy=y0+ty 0=t=1 x=x1-x0 y=y1-y0窗口边界的四条边分为两类：始边和终边。,1.求出P0P1与两条始边的交点参数t0,t

14、1,令tl=max(t0,t1,0)，则tL即为三者中离p1最近的点的参数2.求出p0p1与两条终边的交点参数t2,t3,令tu=min(t2,t3,1)，则tU即为三者中离p0最近的点的参数若tu tl,则可见线段区间 tl,tu,t0,t1,t2,t3,0,1,交点计算,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,TQi 0 ti为与终边交点参数Qi=0 Di 0 时,分析另一D,E,F,A,B,当Qi=0时 若Di 0 时,分析另一D,（如图

15、中的EF就是这种情况，它使QL=0，DL0和QR=0，DR0。这时由于EF和x=xL及x=xR平行，故不必去求出EF和x=xL及x=xR的交点，而让EF和y=yT及y=yB的交点决定直线段上的可见部分。）,E,F,A,B,3.始边和终边的确定及交点计算,3.3 多边形裁剪,错觉：直线段裁剪的组合？关键：要保持窗口内多边形的边界部分，而且要将窗框的有关部分按一定次序插入多边形的保留边界之间，从而使剪裁后的多边形的边仍然保持封闭状态。新的问题：1）边界不再封闭，需要用窗口边界的恰当部分来封闭它，如何确定其边界？,多边形裁剪,2）一个凹多边形可能被裁剪成几个小的多边形，如何确定这些小多边形的边界？,

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

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

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

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

20、I6,I8,I10,Weiler-Atherton（W-A）算法（双边裁剪法）可以用一个有内孔的凹多边形去裁剪另一个也有内孔的凹多边形。被裁剪的多边形主多边形 裁剪区域裁剪多边形 各多边形的外部边界取顺时针方向，而其内部边界或孔取逆时针方向。思路：主多边形和裁剪多边形均用它们的顶点表来定义。这两类交点分别用进点表和出点表来存放。,主多边形和裁剪多边形的边界若相交，交点必定成对地出现，其中一个交点为主多边形边进入裁剪多边形内部时的交点（称进点），另一个交点则为离开时的交点（称出点）。,c1,c2,c3,c4,s1,s2,s3,s4,s5,s6,s7,I1,I2,I3,I4,I5,I6,I7,I8

21、,裁剪窗口多边形,主多边形,主多边形 裁剪窗口 顶点表 顶点表 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）跟踪主多边形顶点表，直至发现下一交点，复制这一段主多边形顶点到内表中；根据交点处指针，

22、转到裁剪多边形顶点表中的相应位置跟踪裁剪多边形顶点表，直至发现下一交点，复制这一段裁剪多边形顶点到内表中；if 该交点不是起始点 then（2）if 进点表中还有未遍历到的交点 then（1）（3）finish,复杂例5，分析裁剪过程，分别写出主多边形、裁剪多边形的顶点表，以及最终裁剪结果。,Weiler-Athenton算法,交点的奇异情况处理 1.与裁剪多边形边重合的主多边形的边不参与求交点；2.对于顶点落在裁剪多边形的边上的主多边的边，如果落在该裁剪边的内侧，将该顶点算作交点；而如果这条边落在该裁剪边的外侧，将该顶点不看作交点,3.3 字符裁剪方法点阵字符每个字符用一个位图(掩膜)来表示

23、，其大小由位图的尺寸来确定，如 7 9，9 16，16 24 等。,1 1 1 1 0 0 0,0 1 0 0 1 0 0,0 1 0 0 1 0 0,0 1 1 1 0 0 0,0 1 0 0 0 0 0,0 1 0 0 0 0 0,0 1 0 0 0 0 0,1 1 1 0 0 0 0,0 0 0 0 0 0 0,P在字库的表示,P的显示结果,矢量字符 选一个正方形网格，作为字符的局部坐标空间，网格的大小可选16 16，32 32，64 64等。每个字符由构成它的笔画组成，每个笔画又由其两端确定。每个端点保存它的坐标值及连线标志。,x,y,o,p1,p2,p3,p4,p5,p6,63,63

24、,字符的编码,x1 y1 0,x2 y2 1,x3 y3 0,x4 y4 1,x5 y5 0,x6 y6 1,1,0表示不连线,1表示连线,字符结束标志,特点：除用直线段表示笔画外，还可采用二次三次曲线段。对矢量字符的变换是对其端点进行图形的几何变换。,（一）字符的裁剪 1.简单裁剪方法：用点阵字符的掩膜或矢量字符的网格大小作为字符的包围框，若该包围框在窗口内，则显示字符；否则，不予显示。4.精确裁剪方法：对于点阵字符，判断组成其笔画的每个像素点是否位于窗口内。对于矢量字符，对组成其笔画的每条线段进行裁剪。,（二）字符串的剪裁,字符串剪裁3种可选择的方法。1.串精度裁剪,字符精度裁剪,字符的精

25、密(笔画、像素精度)剪裁,（为了减少计算量，在进行真正的求交计算之前，往往先用凸包等辅助结构进行粗略地比较，排除那些显然不相交的情形。）什么是凸包？一个图形的凸包，就是包含这个图形的凸区域（凸多边形、凸多面体），它不是唯一的。,求交计算：求交点、求交线。,线段的裁剪直接求交算法Cohen-SutherLand算法(编码算法)中点分割算法Liang(梁友栋)-Barsky 算法多边形裁剪Sutherland-Hodgman算法Weiler-Athenton算法（适用于带内孔的各种多边形）,本章小结,练习：,已知P1、P2和Q1、Q2，（的坐标值），写出两条线段求交点的算法（或C语言函数）（程序如何实现？）Cohen-SutherLand与中点分割法有什么异同？分别用Cohen-SutherLand、中点分割法（e=0.01）裁剪如下图所示线段AB。,2,y,5.试用Sutherland-Hodgman算法对所示多边形进行裁剪，要求画出每次裁剪对应的图形，并标明输入和输出的顶点。6.试用Weiler-Atherton算法对所示多边形进行裁剪，标明输入和输出的顶点，与上面算法相比较。,上机作业：编程实现中点线段裁剪算法。调试教材中的多边形裁剪算法，并改变多边形顶点数,