计算机图形学第五章第五章裁剪第五章裁剪5.1裁剪概述裁剪可以在世界坐标系中进行，即相对于窗口进行；也可以把对象变换为设备坐标之后相对于视区进行。前者可以把不在窗口范围内的部分剪掉，避免了不必要的变换处理；后者在设备坐标系中裁剪易于用硬件实现。裁剪处理的基础是：点在窗口区域内外的判断以及计算图形元素与窗口区域边界的交点。其原理虽然简单，但涉及的图形元素多，提高裁剪速度是算法应考虑的重要问题。以下介绍直线段裁剪算法及多边形裁剪算法。最简单的裁剪方法是把各种图形扫描转换为点之后，再判断各点是否在窗内。但那样太费时，一般不可取。这是因为有些图形组成部分全部在窗口外，可以完全排除，不必进行扫描转换。所以一般采用先裁剪再扫描转换的方法。裁剪算法有二维的和三维的，裁剪对象也可以是规则形体，也可以是不规则形体。本章重点介绍二维裁剪，三维裁剪涉及到后面章节三维消隐等内容，后面再简要介绍。大家应该也有点累了，稍作休息5.2.1直线段裁剪直接求交算法Cohen-Sutherland算法中点分割算法Liang-Barskey算法参数化裁剪算法5.2.2多边形裁剪Sutlerland_Hodgman算法Weiler-Athenton算法直线段裁剪算法是复杂图元裁剪的基础。复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。所以本章重点讨论直线段的裁剪算法。算法一般取的裁剪多边形都是矩形，有些特殊的算法采用任意多边形裁剪。点的裁剪直线段裁剪直接求交算法Cohen-Sutherland裁剪图5.1区域划分及编码图5.2区位码各位含义编码的思想在图形学中非常重要。Sutherland：Coons,图灵,IEEE计算机先驱奖。Cohen-Sutherland算法Cohen-Sutherland裁剪Cohen-Sutherland直线裁剪算法小结中点分割裁剪算法中点分割裁剪算法问：算法为什么可行？会不会无限循环、不断二分？因为屏幕像素是有限的，一般计算次数不会太多，而且算法思想是用取中点的方法最后在误差允许的范围内去逼近真正的与裁剪矩形边的交点。下面我们仅介绍如何在线段P1P2上求离P1最远的可见点(求P2最远的可见点同p1),其具体步骤如下：①测试P2是否在窗口内，若是，则P2就是离P1最远的可见点，结束。否则，进行下一步。②测试P1P2是否在窗外同侧，若是，P1P2全部不可见，结束。否则，进行下一步。③取P1P2的中点Pm，若PmP2在窗外同侧，舍去，剩余段以P2代替Pm重复第二步。否则，以P1代替Pm重复第二步。直到线段不能再分为止。图中,对线段a,求离P1最远的可见点算法在第一步结束;对线段b,算法在第二步结束;对线段c,算法进入第三步后开始对分线段,最终重复第二步结束。中点分割裁剪算法的优点Liang-Barsky算法设要裁剪的线段是P0P1。P0P1和窗口边界交于A,B,C,D四点，见图。算法是从A,B和P0三点中找出最靠近的P1点，图中要找的点是P0。从C,D和P1中找出最靠近P0的点。图中要找的点是C点。那么P0C就是P0P1线段上的可见部分。Liang-Barsky算法求出P0P1与两条始边的交点参数t0,t1,令tl=max(t0,t1,0)，则tL即为三者中离p1最近的点的参数求出p0p1与两条终边的交点参数t2,t3,令tu=min(t2,t3,1)，则tU即为三者中离p0最近的点的参数若tu>tl,则可见线段区间[tl,tu]Liang-Barsky算法Liang-Barsky算法思考：前面几种裁剪直线段算法的裁剪窗口都是矩形区域，如何推广裁剪区域呢？参数化算法(Cyrus-Beck)是研究使用凸多边形区域作为裁剪区域进行二维直线段裁剪的算法。参数化算法(Cyrus-Beck)则对于线段P1P2上任一点P(t)N·(P(t)-A)<0->外侧N·(P(t)-A)>0->内侧N·(P(t)-A)=0->边界或其延长线上参数化算法(Cyrus-Beck)参数化算法(Cyrus-Beck)参数化算法(Cyrus-Beck)参数化算法(Cyrus-Beck)总结补充知识：外裁剪错觉：直线段裁剪的组合？新的问题：边界不再封闭，需要用窗口边界的恰当部分来封闭它，如何确定其边界？用直线段裁剪法可以解决折线以及封闭折线(多边形)的裁剪问题。但对多边形区域(如需进行多边形区域填充时)的裁剪则不适用。多边形区域裁剪后剩余部分应该仍然是多边形区域，如下页图5.3~5.5所示，裁剪后的多边形区域的边界由原来多边形经裁剪的线段及窗口区域的若干段边界组成。图5.3边界线段的连接图5.4边界线段的连接图5.5边界线段的连接(a)正确；(b)不正确多边形裁剪-1/2Sutherland-Hod