计算机图形学之裁剪(Clipping).ppt

1、第三章 裁剪（ Clipping),裁剪：确定图形中哪些部分落在显示区之内，哪些落在显示区之外,以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪。 在使用计算机处理图形信息时，计算机内部存储的图形往往比较大，而屏幕显示的只是图的一部分。,3.1 线段裁剪,线段裁剪算法是复杂图元裁剪的基础。复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为线段的裁剪问题。 所谓线段裁剪就是把线段位于裁剪区域的部分找出来，而把位于裁剪区域之外的部分去掉。 最常见的裁剪区域是长方形。,裁剪前,裁剪后,线段裁剪的基本思想,判断线段与窗口的位置关系： 1确定直线是完全可见； 2部分可见； 3还是完全不可见。

2、 对部分可见线段，求出它与窗口边界的交点，并将窗口内的线段输出。,Cohen-Sutherland线段裁剪算法,1 基本思想 该算法也称为编码算法，首先对线段的两个端点按所在的区域进行分区编码，根据编码可以迅速地判明全部在窗口内的线段和全部在某边界外侧的线段。只有不属于这两种情况的线段，才需要求出线段与窗口边界的交点，求出交点后，舍去窗外部分。 对剩余部分，把它作为新的线段看待，又从头开始考虑。,2 区域编码 Cohen-Sutherland算法针对水平长方形区域(Upright rectangle)。 长方形的四条边所在的四条直线把整个平面区域分成9个部分。,我们用四个二进制位来描述9个区域

3、进行编码.目的是能快速地确定线段所在区域。 第1位：1,位于窗口的左边;0,其它 第2位：1,位于窗口的右边;0,其它 第3位：1,位于窗口的下方;0,其它 第4位：1,位于窗口的上方;0,其它,长方形划分的9个区域有如下编码：,3 区域测试 对于一条直线段， 设其两端点的上述编码为 和 。 那么： (i) 时线段位于长方形区域内； (ii) 和 的位与不为0，则线段位于窗口外。 (iii)其它情形需要进一步测试。,可以通过端点区域码直接测试的例子：,不能直接测试的例子：,4 线段求交 对于不能马上判定位于窗口外还是窗口内的线段，需要进行求交(裁剪)。 具体实现时，可按编码顺序(即左、右、下、

4、上)对窗口的边界逐个次测试，如与线段相交则裁剪。,例 (i)线段位于左边界的两边(两端点的第1位不同)，求出交点，并把左边的线段去掉。,例 (ii)线段位于右边界的两边(两端点的第2位不同)，求出交点，并把右边的线段去掉。,例 (iii)线段位于下边界的两边(两端点的第3位不同)，求出交点，并把下边的线段去掉。,例 (iv)线段位于左边界的两边(两端点的第1位不同)，求出交点，并把上边的线段去掉。,5 求交 由于窗口边界与坐标轴平行，求交比较简单。 以左边界为例, 其边界的方程为 而线段的方程为： 因此交点为：,6 算法步骤 (i) 对两个端点进行编码； (ii) 如果两个代码的位“或”为0说

5、明线段位于窗口内，保存线段，结束； (iii) 如果两个代码的位“与”不为0说明线段位于窗口某边界的外侧，结束； (iv) 逐个边界进行求交测试，如果位于该边界的两侧则求交并回到(i)；否则再取下一条边进行求交测试。 (v) 如果有线段位于窗口内则画出直线段。,编码： Code(int x,int y,int *c) *c=0; /*（xmin，ymin）和（xmax，ymax）为窗口左下角、右上角坐标。*/if(yymax) *c=*c|0 x08; else if(yxmax)*c=*c|0 x02;else if(xxmin)*c=*c|0 x01;,求交： 计算线段P1(x1,y1)P

6、2(x2,y2)与窗口边界的交点 if(LEFT,7 讨论 (i)Cohen-Sutherland算法有时要进行多次(最多4次)求交才能求出位于窗口内的线段，也可能没有。 (ii)算法不能处理窗口为任意多边形的情况。 (iii)用编码方法可快速判断线段- 完全可见和显然不可见。,3.2 多边形区域裁剪,在图形学中的多边形常认为是一封闭多边形，如果用直线段裁剪算法，可以吗？ 新的问题：,边界不再封闭，需要用窗口边界的恰当部分来封闭它,当被裁剪对象为多边形时，称为多边形区域裁剪。 我们希望多边形被裁剪后得到的结果仍是多边形。从而正确地把多边形位于窗口内的区域表示出来。,不正确结果,裁剪后,裁剪前,

7、Sutherland-Hodgman算法,分割处理策略：将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪。一次用窗口的一条边裁剪多边形。 考虑窗口的一条边以及延长线构成的裁剪线 该线把平面分成两个部分:可见一侧；不可见一侧,为窗口各边界裁剪的多边形存储输入与输出顶点表。在窗口的一条裁剪边界处理完所有顶点后，其输出顶点表将用窗口的下一条边界继续裁剪。 窗口的一条边以及延长线构成的裁剪线把平面分为两个区域，包含有窗口区域的一个域称为可见侧；不包含窗口区域的域为不可见侧。,多边形的各条边的两端点S、P。它们与裁剪线的位置关系只有四种,对于 情况（1）仅输出顶点S； 情况（2）输出0个顶点； 情况（3）输出线段SP与裁剪线的交点I和S； 情况（4）输出线段SP与裁剪线的交点I。,上述算法仅用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下一条裁剪边处理过程的输入。 对于每一条裁剪边，只是判断点在窗口哪一侧以及求线段SP与裁剪边的交点算法应随之改变。,流水线过程(左上右下)：左边的结果是上边的开始。,亦称逐边裁剪算法,裁剪结果的顶点构成： 裁剪边内侧的原顶点； 多边形的边与裁剪边的交点。 顺序连接。,优点： 裁剪算法采用流水线方式，适合硬件实现。 可推广到任意凸多边形裁剪窗口,例子,3 多边形裁剪算法 只需把被裁剪多边形依