【文档说明】[计算机软件及应用]二维图形裁剪课件.ppt，共(47)页，852.020 KB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-2134.html

以下为本文档部分文字说明：

二维图形裁剪◆裁剪概述◆线段裁剪直接求交算法；Cohen-Sutherland算法；（重点，算法实现）梁友栋-Barsky算法◆多边形裁剪Sutlerland_Hodgman算法（难点，算法实现）Weiler-Athenton算法

◆字符裁剪裁剪二维图形裁剪预备知识：求交（矩形窗口）裁剪三维裁剪长方体裁剪体棱锥体体裁剪体直接求交算法编码裁剪算法中点分割算法……被裁剪对象：直线段、多边形、三维实体……一、裁剪概述裁剪：是裁去窗口之外物体或物体部分的一种操作。剪裁的应用1、从定义的场景中抽取出用于观察的部分；2、在三

维视图中标识出可见面；3、防止线段或对象的边界混淆；4、用实体造型来创建对象；5、显示多窗口的环境；6、允许选择图形的一部分来进行拷贝，移动和删除。“取景器”=窗口视区1视区2（viewport）⚫裁剪的目的判断图形元素是否落在裁剪窗口之内并找出其位于内部的部分⚫裁剪处理的基础

图元关于窗口内外关系的判别图元与窗口的求交⚫假定条件矩形裁剪窗口：[xmin,xmax]×[ymin,ymax]待裁剪点或线段：•点裁剪–点(x,y)在窗口内的充分必要条件是：问题：对于任何多边形窗口，如何判别？xxxminmaxyyyminmaxWytWybWxlWxrP1P2P3

线段相对于该窗口的情况有:①线段全部位于窗口的内部（A）；②线段全部位于窗口外部（B、C）；③线段的中间部分在窗口内，而二端点在窗口外部（D）；④线段的一端在窗口内，而另一端在窗口外（E）。x=xLx=xRy=yBy=yTABCDE二、线段裁剪待裁剪线段和窗口的关系线段完全可见显然不可见线段至少有

一端点在窗口之外，但非显然不可见保留丢弃裁剪为提高效率，算法设计时应考虑：(一）快速判断线段完全在窗口内或外的情形；(二)设法减少裁剪情形中求交次数和每次求交时所需的计算量。直接求交算法基本思想是：判断直线

与窗口的位置关系，确定该直线是完全可见、部分可见或完全不可见，然后输出处于窗口内线段的端点，并显示此线段。根据直线段和窗口的关系可知：（1）整条线在窗口之内。此时，不需剪裁，显示整条线段。（2）整条线在窗口之外，此时，不

需剪裁，不显示整条线段。（3）部分线在窗口之内，部分线在窗口之外。此时，需要求出线段与窗口边界的交点，并将窗口外的线段部分剪裁掉，显示窗口内的部分。例1设有直线段P0P1，有一个矩形裁剪窗口，写出对该线段裁剪的算法。1）求出直线P0P1与窗口的交点I，如图（a

）所示。2）取P0I线段显示，擦除IP1线段，并将P1替换I，即得P0P1线段，裁剪结束。如图（b）所示。P0P1IP0P1（a）（b）求线段与窗口交点设线段两端点坐标为：和则过这两点的直线方程为：其中k为斜率。上述直线方程与窗口各边界的交点为：左：右：下：上：11111212

)()(yxxkyxxxxyyy+−=+−−−=+−==kyxxkyxxLL11)(+−==kyxxkyxxRR11)(0))(/1(11=−+=kyyyykxxBB0))(/1(11=−+=kyyyykxxTT)(11

1yxP，)(222yxP，基本思想：对于每条待裁剪的线段P1P2分三种情况处理：①若P1P2完全在窗口内，则显示该线段P1P2，简称“取”之；②若P1P2完全在窗口外，则丢弃该线段，简称“舍”之；③若线段既不满足“取”的条件，也不满足“舍”的条件，则求线

段与窗口边界的交点，在交点处把线段分为两段，其中一段完全在窗口外，可舍弃之，然后对另一段重复上述处理。核心思想：分区编码和线段分割。Cohen-Sutherland算法(编码算法)分区编码方法：图形区域划分成九个区

域。四位编码表示端点所处的位置：(--->)上下右左第一位为“1”时，表示点在y=yT的上方；第二位为“1”时，表示点在y=yB的下方；第三位为“1”时，表示点在x=xR的右方；第四位为“1”时，表示点在x=xL的左方。000000

010010100001001001101001010110x=xLx=xRy=yBy=yT11111111#defineLEFT1#defineRIGHT2#defineBOTTOM4#defineTOP8编码原则每个区域赋予一个四位编码，C

tCbCrCl，上下右左；=elseyyCt0max1当=elsexxCr0max1当=elsexxCl0min1当=elseyyCb0min1当编码方法练习：请给出右图的线段端点编码（端点编码：定义为它所在区域的编码）x=xLx=xRy=yBy=yTABCDE第一

步判别线段两端点是否都落在窗口内，如果是，则线段完全可见；否则进入第二步；第二步判别线段是否为显然不可见，如果是，则裁剪结束；否则进行第三步；第三步求线段与窗口边延长线的交点，这个交点将线段分为两段，其中一段显然不可见，丢弃。对余下的另一段重新进行第一步，第二步判断，直至结束Cohen-S

utherland算法步骤当线段的两个端点的编码的逻辑“与”非零时，线段为显然不可见的。也可以进行“按位与”运算，可知这两个端点是否同在视区的上、下、左、右；如code1=0101,code2=0110，则code1&code2=0100

,表示在窗口下方。问题：显然可见的编码如何判断？？编码判断当线段的两个端点的编码的逻辑“与”非零时，线段为显然不可见的。也可以进行“按位于”运算，可知这两个端点是否同在视区的上、下、左、右；如code1=0101,code2=0110，则code1&code2=01

00,表示在窗口下方。问题：显然可见的编码如何判断？？编码判断对一条线段的可见性测试方法：（1）若线段两个端点的四位二进制编码全为0000，即两端点编码逻辑或运算为0，那么该线段完全位于窗口内，可直接保留；（2）对两端点的四位二进制编码进行逻

辑与运算，若结果不为零，那么整条线段必位于窗口外，可直接舍弃；（3）否则，这条线段既不能直接保留，也不能直接舍弃，它可能与窗口相交。此时，需要对线段进行再分割，即找到与窗口边线的一个交点，根据交点位置，赋予四位二进制编码，并对分割后的线段按照一定的顺序（如左右下上）进行检查，决定保

留、舍弃或再次进行分割。重复这一过程，直到全部线段均被舍弃或保留为止。例：分别给下列直线段编码，并判断是否需要剪裁。P1P2C1=0001C2=0000P1P2C1=0100C2=0101BCP1P2C1=0101C2=1010

P1P2ADC1=0000C2=0000例：Cohen-SutherLand算法过程：过程：1）输入线段AB的两端点坐标A（x0,y0）、B（x1,y1），以及裁剪窗口的四条边界：yt,yb,xl,xr。2）对A

B编码，A的编码codeA=0001，B的编码为codeB=0110。3）线段AB裁剪的基本过程（按左右下上的顺序）：①由于codeA|codeB≠0，对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）所示。④A的编码还没有达到0000，再求得下边交点为P2，AP2必定在窗口外，故裁剪掉，并用A替换P

2。如图（d）所示。⑤对剩下的直线段AB再进行判断，现在A编码为0000，B编码为0000，由于codeA|codeB=0，全在窗口中，故全部保留。最后得到裁剪后的线段为AB，算法结束。•求交测试顺序固定(左上右下）•最坏情形，线段求交四次。对于那些非完全可见、又非显然不可见的线段，需要

求交（如线段AD)，求交前先测试与窗口哪条边所在直线有交？(按序判断端点编码中各位的值ClCtCrCb）1）特点：用编码方法可快速判断线段--完全可见和显然不可见。2）特别适用二种场合：大窗口场合；窗口特别小的场合(如,光标拾取图形时,光

标看作小的裁剪窗口。）编码算法特点设要裁剪的线段是P0P1。P0P1和窗口边界交于A,B,C,D四点，见图。算法的基本思想是从A,B和P0三点中找出最靠近的P1点，图中要找的点是P0。从C,D和P1中找出最

靠近P0的点。图中要找的点是C点。那么P0C就是P0P1线段上的可见部分。梁友栋-Barsky算法线段的参数表示x=x0+t△xy=y0+t△y0<=t<=1△x=x1-x0△y=y1-y0窗口边界的四条边分为两类

：始边和终边。========为始边。为终边，若为终边。为始边，若为始边。为终边，若为终边。为始边，若TBTBRLRLyyyyyyyyyyxxxxxxxxxx0000

1.求出P0P1与两条始边的交点参数t0,t1,令tl=max(t0,t1,P0)，则tL即为三者中离p1最近的点的参数2.求出p0p1与两条终边的交点参数t2,t3,令tu=min(t2,t3,P1)，则tU即为三者中离p0最近的点的参数若tu>tl,则可见线段区间[

tl,tu]t0t1t2t3P01交点计算P13.始边和终边的确定及交点计算：令QL=△xDL=x0-xLQR=△xDR=xR-x0QB=△yDB=y0-yBQT=△yDT=yT-y0参数交点为:ti=Di

/Qii=L,R,B,TQi<0ti为与始边交点参数Qi>0ti为与终边交点参数当Qi=0时若Di<0时,线段不可见（如图中AB，有QR=0，DR<0）若Di>0时,分析另一D,（如图中的EF就是这种情况，它使QL=0，DL>0和QR=0，DR>0。这

时由于EF和x=xL及x=xR平行，故不必去求出EF和x=xL及x=xR的交点，而让EF和y=yT及y=yB的交点决定直线段上的可见部分。）ABEFAB三、多边形裁剪•错觉：直线段裁剪的组合？关键：要保持窗口内多边形的边界部分，而且要将窗框的有关部分按一定

次序插入多边形的保留边界之间，从而使剪裁后的多边形的边仍然保持封闭状态。•新的问题：1）边界不再封闭，需要用窗口边界的恰当部分来封闭它，如何确定其边界？2）一个凹多边形可能被裁剪成几个小的多边形，如何确定这些小多边形的边界？Sutherland-Hodgman算法◼思路：将多边形边界作为一个整

体，分而治之。将多边形的各边先相对于窗口的某一条边界进行裁剪，然后将裁剪结果再与另一条边界进行裁剪，如此重复多次，便可得到最终结果。◼流水线过程(左上右下)：左边的结果是上边的开始。亦称逐边裁剪算法–内侧空间与外侧空间–多边形的边与

半空间的关系PIS可见侧PS可见侧PIS可见侧PS可见侧(a)从外到内(b)从内到内(c)从内到外(d)从外到外输出P和I输出P输出I不输出p1p2p3p4p5q1q2q3q4需要设置二个表：输入顶点表(向量)—存放被裁剪多边形的顶点p1-pm。输出

顶点表(线性链表)—存放裁剪过程中及结果的顶点q1-qn。q5q6q7q8q1q2p3q7q8q5q6q4q3裁剪前：裁剪后：输入顶点表：p1p2p3p4p5输入顶点表:不变输出顶点表：空输出顶点表:q1q2p3q7q8

q5q6q4q3需要设置二个表：输入顶点表(向量)—存放被裁剪多边形的顶点p1-pm。输出顶点表(线性链表)—存放裁剪过程中及结果的顶点q1-qn。实现方法：①设置二个表输入顶点表(向量)—存放被裁剪多边形的顶点

p1-pm。输出顶点表(线性链表)—存放裁剪过程中及结果的顶点q1-qn。②输入顶点表中各顶点要求按一定顺序排列，一般可采用顺时针或逆时针方向。③相对于裁剪窗口的各条边界，按顶点表中的顺序，逐边进行裁剪。算法中相对于各窗口边界的裁剪过程相同，且每次都是相对于

前一次的结果进行处理。裁剪结果的顶点构成：裁剪边内侧的原顶点；多边形的边与裁剪边的交点。顺序连接。特点：⚫裁剪算法采用流水线方式，适合硬件实现。⚫可推广到任意凸多边形裁剪窗口问题：一个凹多边形可能被裁剪成几个小的多边形，如何确定这

些小多边形的边界？AFEDCBV1V2V3V4AFEDCBV1V2V3V4AEDSutherland-Hodgman多边形裁剪：输入顶点BAFEDC，输出顶点：V1AV2V3EDV4Sutherland-Hodgman算法Weile

r-Athenton算法裁剪窗口为任意多边形（凸、凹、带内环）的情况：–主多边形：被裁剪多边形，记为A–裁剪多边形：裁剪窗口，记为B•主多边形和裁剪多边形把二维平面分成两部分。•内裁剪：A∩B•外裁剪：A-B裁剪结果区域的边界由A的

部分边界和B的部分边界两部分构成，并且在交点处边界发生交替，即由A的边界转至B的边界，或由B的边界转至A的边界Weiler-Athenton算法–如果主多边形与裁剪多边形有交点，则交点成对出现，它们被分为如下两类：•进点：主多边形边界由此

进入裁剪多边形内如，I1,I3,I5,I7,I9,I11•出点：主多边形边界由此离开裁剪多边形区域.如，I0,I2,I4,I6,I8,I10Weiler-Atherton（W-A）算法（双边裁剪法）可以用一个有内孔的凹多边形去裁剪另一个也有内孔的凹多边形。被裁剪的多边形——

主多边形裁剪区域——裁剪多边形各多边形的外部边界取顺时针方向，而其内部边界或孔取逆时针方向。思路：主多边形和裁剪多边形均用它们的顶点表来定义。这两类交点分别用进点表和出点表来存放。主多边形和裁剪多边形的边界若相交，交点必定成对地出现，其中一个交点为主多边形边进入裁剪多边形内部时的

交点（称进点），另一个交点则为离开时的交点（称出点）。c1c2c3c4s1s2s3s4s5s6s7I1I2I3I4I5I6I7I8裁剪窗口多边形主多边形主多边形裁剪窗口顶点表顶点表s1c1I1I8I2I1s2c2I3I2s3I3I4c3s4

I4I5I5I6c4s5I6I7I7s6c1I8s7s1起点简单例4:W-A算法进行多边形裁剪进点出点算法：1.分别建立主多边形和裁剪多边形的顶点表；2.求出主多边形与裁剪多边形的交点（进点和出点）并分别建立进点表和出点表；3.将交点加入各顶点表中；4.i

f进点表为空thenfinish（1）取一进点作为始点；（2）跟踪主多边形顶点表，直至发现下一交点，复制这一段主多边形顶点到内表中；根据交点处指针，转到裁剪多边形顶点表中的相应位置跟踪裁剪多边形顶点表，直至发现下一交点，复制这一段裁剪多边形

顶点到内表中；if该交点不是起始点then（2）if进点表中还有未遍历到的交点then（1）（3）finish复杂例5，分析裁剪过程，分别写出主多边形、裁剪多边形的顶点表，以及最终裁剪结果。Weiler-Athenton算法–交点的奇异情况处理1.与裁剪多边形边重合的主多边形的边不

参与求交点；2.对于顶点落在裁剪多边形的边上的主多边形的边，如果落在该裁剪边的内侧，将该顶点算作交点；而如果这条边落在该裁剪边的外侧，将该顶点不看作交点四、字符裁剪方法点阵字符——每个字符用一个位图(掩膜)来表示，其大小由位图的尺寸

来确定，如7×9，9×16，16×24等。111100001001000100100011100001000000100000010000011100000000000P在字库的表示P的显示结果矢量字符——选一个正方形网格，作为字符的局部坐标空间，网格的大小可选16×1

6，32×32，64×64等。每个字符由构成它的笔画组成，每个笔画又由其两端确定。每个端点保存它的坐标值及连线标志。xyop1p2p3p4p5p66363字符的编码x1y10x2y21x3y30x4y41x5y50x6y61－10表示不连线1表示连线字符结束标志特点：除用直线段表示

笔画外，还可采用二次三次曲线段。对矢量字符的变换是对其端点进行图形的几何变换。（一）字符的裁剪1.简单裁剪方法：用点阵字符的掩膜或矢量字符的网格大小作为字符的包围框，若该包围框在窗口内，则显示字符；否则，不予显示。4.精确裁剪方法

：对于点阵字符，判断组成其笔画的每个像素点是否位于窗口内。对于矢量字符，对组成其笔画的每条线段进行裁剪。