[计算机软件及应用]二维图形裁剪

《[计算机软件及应用]二维图形裁剪》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、二维图形裁剪裁剪概述线段裁剪直接求交算法；Cohen-Sutherland算法；（重点，算法实现）梁友栋-Barsky算法多边形裁剪Sutlerland_Hodgman算法（难点，算法实现）Weiler-Athenton算法字符裁剪裁剪二维图形裁剪预备知识：求交（矩形窗口）裁剪三维裁剪长方体裁剪体棱锥体体裁剪体直接求交算法编码裁剪算法中点分割算法……被裁剪对象：直线段、多边形、三维实体……一、裁剪概述裁剪：是裁去窗口之外物体或物体部分的一种操作。剪裁的应用1、从定义的场景中抽取出用于观察的部分；2、在三维视图中标识出可见面；3、防止线段或对象

2、的边界混淆；4、用实体造型来创建对象；5、显示多窗口的环境；6、允许选择图形的一部分来进行拷贝，移动和删除。“取景器”=窗口视区1视区2（viewport）裁剪的目的判断图形元素是否落在裁剪窗口之内并找出其位于内部的部分裁剪处理的基础图元关于窗口内外关系的判别图元与窗口的求交假定条件矩形裁剪窗口：[xmin,xmax]×[ymin,ymax]待裁剪点或线段：点裁剪点(x,y)在窗口内的充分必要条件是：问题：对于任何多边形窗口，如何判别？WytWybWxlWxrP1P2P3线段相对于该窗口的情况有:①线段全部位于窗口的内部（A）；②线段全部位于

3、窗口外部（B、C）；③线段的中间部分在窗口内，而二端点在窗口外部（D）；④线段的一端在窗口内，而另一端在窗口外（E）。x=xLx=xRy=yBy=yTABCDE二、线段裁剪待裁剪线段和窗口的关系线段完全可见显然不可见线段至少有一端点在窗口之外，但非显然不可见保留丢弃裁剪为提高效率，算法设计时应考虑：(一）快速判断线段完全在窗口内或外的情形；(二)设法减少裁剪情形中求交次数和每次求交时所需的计算量。直接求交算法基本思想是：判断直线与窗口的位置关系，确定该直线是完全可见、部分可见或完全不可见，然后输出处于窗口内线段的端点，并显示此线段。根据直线段

4、和窗口的关系可知：（1）整条线在窗口之内。此时，不需剪裁，显示整条线段。（2）整条线在窗口之外，此时，不需剪裁，不显示整条线段。（3）部分线在窗口之内，部分线在窗口之外。此时，需要求出线段与窗口边界的交点，并将窗口外的线段部分剪裁掉，显示窗口内的部分。例1设有直线段P0P1，有一个矩形裁剪窗口，写出对该线段裁剪的算法。1）求出直线P0P1与窗口的交点I，如图（a）所示。2）取P0I线段显示，擦除IP1线段，并将P1替换I，即得P0P1线段，裁剪结束。如图（b）所示。P0P1IP0P1（a）（b）求线段与窗口交点设线段两端点坐标为：　　　和　　

5、　　　则过这两点的直线方程为：其中k为斜率。上述直线方程与窗口各边界的交点为：左：右：下：上：基本思想：对于每条待裁剪的线段P1P2分三种情况处理：①若P1P2完全在窗口内，则显示该线段P1P2，简称“取”之；②若P1P2完全在窗口外，则丢弃该线段，简称“舍”之；③若线段既不满足“取”的条件，也不满足“舍”的条件，则求线段与窗口边界的交点，在交点处把线段分为两段，其中一段完全在窗口外，可舍弃之，然后对另一段重复上述处理。核心思想：分区编码和线段分割。Cohen-Sutherland算法(编码算法)分区编码方法：图形区域划分成九个区域。四位编码

6、表示端点所处的位置：(--->)上下右左第一位为“1”时，表示点在y=yT的上方；第二位为“1”时，表示点在y=yB的下方；第三位为“1”时，表示点在x=xR的右方；第四位为“1”时，表示点在x=xL的左方。000000010010100001001001101001010110x=xLx=xRy=yBy=yT11111111#defineLEFT1#defineRIGHT2#defineBOTTOM4#defineTOP8编码原则每个区域赋予一个四位编码，CtCbCrCl，上下右左；编码方法练习：请给出右图的线段端点编码（端点编码：定义为它

7、所在区域的编码）x=xLx=xRy=yBy=yTABCDE第一步判别线段两端点是否都落在窗口内，如果是，则线段完全可见；否则进入第二步；第二步判别线段是否为显然不可见，如果是，则裁剪结束；否则进行第三步；第三步求线段与窗口边延长线的交点，这个交点将线段分为两段，其中一段显然不可见，丢弃。对余下的另一段重新进行第一步，第二步判断，直至结束Cohen-Sutherland算法步骤当线段的两个端点的编码的逻辑“与”非零时，线段为显然不可见的。也可以进行“按位与”运算，可知这两个端点是否同在视区的上、下、左、右；如code1=0101,code2=0

8、110，则code1&code2=0100,表示在窗口下方。问题：显然可见的编码如何判断？？编码判断当线段的两个端点的编码的逻辑“与”非零时，线段为显然不可见的。也