计算机图形学第6章二维图形的裁剪(1).ppt

1、第七章 二维图形的裁剪,重点：掌握二维图形点、线段、多边形和字符的裁剪算法 。 难点：理解二维图形的裁剪算法思想并且用C语言进行算法的实现。,一、裁剪的意义 为了描述图形对象，我们必须存储它的全部信息，但有时为了达到分区描述或重点描述某一部分的目的，往往将要描述的部分置于一个窗口内，而将窗口外的部分“剪掉”，这个处理过程叫做裁剪，裁剪在计算机图形处理中具有十分重要的意义。 裁剪实质上是从数据集合中抽取信息的过程，这个过程是通过一定的计算方法来实现。 裁剪就是将指定窗口作为图形边界，将窗口内的图形保留，而窗口外的图形则被舍弃。 二、裁剪的目的 裁剪的基本目的是判断某个图形元素是否落在窗口之内，如

2、落在窗口之内则进一步求出位于窗口内的部分。 三、裁剪处理涉及 1、图元在窗口内外的判别； 2、图形元素与窗口的求交。,7.1 点的裁剪,先看简单的点图元裁剪，它是线段裁剪以及后面的多边形裁剪的基础。 如果矩形窗口的左、右横坐标为：xmin、xmax；上、下纵坐标为：ymin，ymax。 某点（x，y）在窗口内的充分必要条件是：,如果上面四个不等式中任何一个不满足，则点（x，y）位于窗口之外。 对于任意多边形窗口，需要根据多边形内点的判别准则进行判断。,7.2 线段的裁剪,直线段的裁剪比点复杂，其裁剪方法又是多边形裁剪和三维图形裁剪的基础。 一、直线裁剪的基本思想 判断直线与窗口的位置关系： 1

3、确定直线是完全可见； 2部分可见； 3还是完全不可见。 对部分可见线段，求出它与窗口边界的交点，并将窗口内的线段输出。,五种位置关系?,二、裁剪线段和窗口的关系 假定窗口左下角坐标为(xmin，ymin)，右上角坐标为(xmax，ymax)，待裁剪线段和窗口的关系如图所示，这五种位置关系存在下面三种情况：,7.2 线段的裁剪,1、直线的两个端点均在窗口内，如图中AB线。这时直线完全可见，可被简单接受。 2、直线的两个端点都在窗口外，并且位于窗口某一边界的同一外侧，如图中EF线。则直线完全不可见，可被简单舍弃。 3、除此之外需要求交点，以确定直线在窗口某一边界内是否有可见部分,并裁掉外部线段，显

4、示内部线段。如CD、GH、IJ线。 为了提高裁剪效率，算法设计一般可从下面两方面作出考虑： (1) 快速判断情况1和情况2。 (2)在情况3中，设法减少求交的次数和每次求交时所需的计算量。,7.2 线段的裁剪,三、直线求交计算 当线段P1P2穿过某边界L时，交点P的计算如图中所示。,根据直线两点式方程：,整理后得通用交点公式：,7.2 线段的裁剪,1、与上边界的求交公式：,2、与下边界的求交公式：,3、与右边界的求交公式：,4、与左边界的求交公式：,7.2 线段的裁剪,四、直线裁剪的常用算法直线 1CohenSutherland算法 2中点分割算法 3梁友栋-Barsky裁剪算法,7.2.1

5、CohenSutherland算法,一、CohenSutherland算法思想： 该算法也称为编码算法，首先对线段的两个端点按所在的区域进行分区编码，根据编码可以迅速地判明全部在窗口内的线段和全部在某边界外侧的线段。只有不属于这两种情况的线段，才需要求出线段与窗口边界的交点，求出交点后，舍去窗外部分。 对剩余部分，把它作为新的线段看待，又从头开始考虑。两遍循环之后，就能确定该线段是部分截留下来，还是全部舍弃。,Cohen-Sutherland 算法 (编码算法),算法思想： 第一步 判别线段两端点是否都落在窗口内，如果是， 则线段完全可见；否则进入第二步； 第二步 判别线段是否为显然不可见，如

6、果是，则裁 剪结束；否则进行第三步 ； 第三步 求线段与窗口边延长线的交点，这个交点将 线段分为两段，其中一段显然不可见，丢弃。 对余下的另一段重新进行第一步，第二步判断， 直至结束,裁剪过程是递归的。,7.2.1 CohenSutherland算法,二、CohenSutherland算法步骤： 1、分区编码 延长裁剪边框将二维平面分成九个区域，每个区域各用一个四位二进制代码标识。各区代码值如图中所示。 四位二进制代码的编码规则是：,(1)第一位置1：区域在左边界外侧 (2)第二位置1：区域在右边界外侧 (3)第三位置1：区域在下边界外侧 (4)第四位置1：区域在上边界外侧 裁剪窗口内（包括边

7、界上）的区域，四位二进制代码均为0。 设线段的两个端点为P1（x1，y1）和P2（x2，y2），根据上述规则，可以求出P1和P2所在区域的分区代码C1和C2。,7.2.1 CohenSutherland算法,2、判别 根据C1和C2的具体值，可以有三种情况： （1）C1=C20，表明两端点全在窗口内，因而整个线段也在窗内，应予保留。 （2）C1&C20（两端点代码按位作逻辑乘不为0），即C1和C2至少有某一位同时为1，表明两端点必定处于某一边界的同一外侧，因而整个线段全在窗外，应予舍弃。 （3）不属于上面两种情况，均需要求交点。,3、求交点 假设算法按照：左、右、下、上边界的顺序进行求交处理，

8、对每一个边界求完交点，并相关处理后，算法转向第2步，重新判断，如果需要接着进入下一边界的处理。 为了规范算法，令线段的端点P1为外端点，如果不是这样，就需要P1和P2交换端点。 当条件(C1&00010)成立时，表示端点P1位于窗口左边界外侧，按照前面介绍的求交公式，进行对左边界的求交运算。 依次类推，对位于右、下、上边界外侧的判别，应将条件式中的0001分别改为0010、0100、1000即可。 求出交点P后，用P1=P来舍去线段的窗外部分，并对P1重新编码得到C1，接下来算法转回第2步继续对其它边界进行判别。,7.2.1 CohenSutherland算法,1）特点：用编码方法可快速判断线

9、段- 完全可见和显然不可见。 2）特别适用二种场合： 大窗口场合 窗口特别小的场合,Cohen-Sutherland 算法的特点,7.2.2 中点分割算法,CohenSutherland直线裁剪算法，充分利用了直线段与裁剪边框的相关性，使裁剪速度大大提高，但在求交过程中仍采用了乘除运算，裁剪速度受到影响。而中点分割法的特点，就在于它是用连续平分线段最终求得交点的方法代替用乘除法实现求交运算。这样只需进行整数的加法和用运算器右移一位来实现除法运算，从而避免去做大量的乘除法。,一、中点分割算法思想： 1、中点公式,7.2.2 中点分割算法,2、中点分割法求交点的规则 如图中所示，当线段P1P2求出

10、中点P后，舍弃线段的哪部分，由下面两条规则决定：,中点分割法求交点规则,（1）如果P1与P同侧，移动P1点；（即可能的交点只能出现在PP2段）if(C1,7.2.2 中点分割算法,二、中点分割算法实现： 1、将直线的两端点P1、P2编码得：C1、C2； 2、判别 根据C1和C2的具体值，可以有三种情况： （1）C1C20，表明两端点全在窗口内，因而整个线段也在窗内，应予保留。 （2）C1&C20（两端点代码按位作逻辑乘不为0），即C1和C2至少有某一位同时为1，表明两端点必定处于某一边界的同一外侧，因而整个线段全在窗外，应予舍弃。 （3）不属于上面两种情况，均需要求交点。,3、求交点 （1）令窗外端点为P1，如果窗外点不是P1，则P1和P2交换端点； （2）保留窗内端点P2到暂存器里； （3）对P1编码为C1； （4）用中点公式求出中点，并编码得C； （5）按照中点算法的求交规则： 若P1和P同侧，移动P1点；if(C1 （6）流程转（3），直到P1和P2相差一个单位时：令交点为P2，取出暂存器的端点赋给P1，然后转向流程1。,