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

《计算机图形学第6章二维图形的裁剪(1).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

3、的裁剪比点复杂，其裁剪方法又是多边形裁剪和三维图形裁剪的基础。一、直线裁剪的基本思想判断直线与窗口的位置关系：1．确定直线是完全可见；2．部分可见；3．还是完全不可见。对部分可见线段，求出它与窗口边界的交点，并将窗口内的线段输出。五种位置关系??二、裁剪线段和窗口的关系假定窗口左下角坐标为(xmin，ymin)，右上角坐标为(xmax，ymax)，待裁剪线段和窗口的关系如图所示，这五种位置关系存在下面三种情况：7.2线段的裁剪1、直线的两个端点均在窗口内，如图中AB线。这时直线完全可见，可被简单接受。2、直线的两个端点都在

4、窗口外，并且位于窗口某一边界的同一外侧，如图中EF线。则直线完全不可见，可被简单舍弃。3、除此之外需要求交点，以确定直线在窗口某一边界内是否有可见部分,并裁掉外部线段，显示内部线段。如CD、GH、IJ线。为了提高裁剪效率，算法设计一般可从下面两方面作出考虑：(1)快速判断情况1和情况2。(2)在情况3中，设法减少求交的次数和每次求交时所需的计算量。7.2线段的裁剪三、直线求交计算当线段P1P2穿过某边界L时，交点P的计算如图中所示。根据直线两点式方程：整理后得通用交点公式：7.2线段的裁剪1、与上边界的求交公式：2、与下边

5、界的求交公式：3、与右边界的求交公式：4、与左边界的求交公式：7.2线段的裁剪四、直线裁剪的常用算法直线1．Cohen－Sutherland算法2．中点分割算法3．梁友栋-Barsky裁剪算法7.2.1Cohen－Sutherland算法一、Cohen－Sutherland算法思想：该算法也称为编码算法，首先对线段的两个端点按所在的区域进行分区编码，根据编码可以迅速地判明全部在窗口内的线段和全部在某边界外侧的线段。只有不属于这两种情况的线段，才需要求出线段与窗口边界的交点，求出交点后，舍去窗外部分。对剩余部分，把它作为新的

6、线段看待，又从头开始考虑。两遍循环之后，就能确定该线段是部分截留下来，还是全部舍弃。Cohen-Sutherland算法(编码算法)算法思想：第一步判别线段两端点是否都落在窗口内，如果是，则线段完全可见；否则进入第二步；第二步判别线段是否为显然不可见，如果是，则裁剪结束；否则进行第三步；第三步求线段与窗口边延长线的交点，这个交点将线段分为两段，其中一段显然不可见，丢弃。对余下的另一段重新进行第一步，第二步判断，直至结束裁剪过程是递归的。7.2.1Cohen－Sutherland算法二、Cohen－Sutherland算法步

7、骤：1、分区编码延长裁剪边框将二维平面分成九个区域，每个区域各用一个四位二进制代码标识。各区代码值如图中所示。四位二进制代码的编码规则是：(1)第一位置1：区域在左边界外侧(2)第二位置1：区域在右边界外侧(3)第三位置1：区域在下边界外侧(4)第四位置1：区域在上边界外侧裁剪窗口内（包括边界上）的区域，四位二进制代码均为0。设线段的两个端点为P1（x1，y1）和P2（x2，y2），根据上述规则，可以求出P1和P2所在区域的分区代码C1和C2。7.2.1Cohen－Sutherland算法2、判别根据C1和C2的具体值，可

8、以有三种情况：（1）C1=C2＝0，表明两端点全在窗口内，因而整个线段也在窗内，应予保留。（2）C1&C2≠0（两端点代码按位作逻辑乘不为0），即C1和C2至少有某一位同时为1，表明两端点必定处于某一边界的同一外侧，因而整个线段全在窗外，应予舍弃。（3）不属于上面两种情况，均需要求交点。3、求交点假设算