第六章 图形裁剪 在用户坐标系中定义的图形往往是大而复杂的，而输出设备如显示屏幕的尺寸及其分辨率却是有限的，为了能够清晰地观察某一部分或对其进行某些绘图操作，就需要将所关心的这一局部区域的图形从整个图形中区分出来,这个区分指定区域内和区域外的图形过程称为裁剪，所指定的区域称为裁剪窗口。 裁剪通常是对用户坐标系中窗口边界进行裁剪，然后把窗口内的部分映射到视区中，也可以首先将用户坐标系的图形映射到设备坐标系或规范化设备坐标系中，然后用视区边界裁剪。

Presentation on theme: "第六章 图形裁剪 在用户坐标系中定义的图形往往是大而复杂的，而输出设备如显示屏幕的尺寸及其分辨率却是有限的，为了能够清晰地观察某一部分或对其进行某些绘图操作，就需要将所关心的这一局部区域的图形从整个图形中区分出来,这个区分指定区域内和区域外的图形过程称为裁剪，所指定的区域称为裁剪窗口。 裁剪通常是对用户坐标系中窗口边界进行裁剪，然后把窗口内的部分映射到视区中，也可以首先将用户坐标系的图形映射到设备坐标系或规范化设备坐标系中，然后用视区边界裁剪。"— Presentation transcript:

1 第六章 图形裁剪 在用户坐标系中定义的图形往往是大而复杂的，而输出设备如显示屏幕的尺寸及其分辨率却是有限的，为了能够清晰地观察某一部分或对其进行某些绘图操作，就需要将所关心的这一局部区域的图形从整个图形中区分出来,这个区分指定区域内和区域外的图形过程称为裁剪，所指定的区域称为裁剪窗口。 裁剪通常是对用户坐标系中窗口边界进行裁剪，然后把窗口内的部分映射到视区中，也可以首先将用户坐标系的图形映射到设备坐标系或规范化设备坐标系中，然后用视区边界裁剪。 下面假定裁剪是针对用户坐标系中窗口边界进行的，裁剪完成后，再把窗口内图形映射到视区。所以裁剪的目的是显示可见点和可见部分，删除视区外的部分。 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

2 6.1 窗口区和视图区 6.1.1 坐标系 1.用户坐标系(World Coordinates)
又称为世界坐标系、完全坐标系等，它可以是用户用来定义设计对象的各种标准坐标系，例直角坐标、极坐标、球坐标、对数坐标等。用户坐标系所拥有的区域范围从理论上说是连续的、无限的。 2.观察坐标系(Viewing Coordinates) 在用户坐标中设置观察坐标系，在观察坐标系中定义一个观察窗口。观察坐标系用来任意设置矩形窗口的方向。一旦建立了观察参考系，就可以将用户坐标系下的描述变换到观察坐标系下。 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

3 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

4 3.规范化设备坐标系(Normalized Device Coordinates)
在规范化坐标系下（取值范围从0到1）定义视区，将观察坐标系下的场景描述映射到规范坐标系下。 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

5 4.设备坐标系(Device Coordinates)
图形输出时需要一定的设备，如绘图仪、显示器等，使用的是设备坐标系。设备坐标系一般为二维坐标，如屏幕坐标。它的范围有限，单位一般为整数。设备坐标一般采用无量刚方式，可以转换为有量刚坐标。一旦场景变换到规范化坐标系下的单位正方形中，以后该单位面积只需要简单地映射到具体输出设备的显示区。给出合适的设备驱动程序，就可以使用不同的输出设备。 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

6 6.1.2 窗口区和视图区 用户可以在用户坐标系中指定感兴趣的任意区域，把这部分区域内的图形输出到屏幕上，这个指定区域称为窗口区。窗口区一般是矩形区域，可以用左下角和右上角两点坐标来定义其大小和位置。定义窗口的目的是要选取图形中需要观察的那一部分图形。在计算机图形学术语中，窗口最初是指要观察的图形区域，但是目前窗口也用于窗口管理系统。在本章中，我们将窗口理解为用户坐标系中要显示的区域。 图形设备上用来输出图形的最大区域称之为屏幕域，它是有限的整数域，大小随具体设备而异。任何小于或等于屏幕域的区域都可定义为视图区。视图区由用户在屏幕域中用设备坐标定义，一般也定义成矩形，由其左下角和右上角两点坐标来定义。所以，用户可以利用窗口来选择需要观察那一部分图形，而利用视图区来指定这一部分图形在屏幕上显示的位置。标准的窗口区和视图区一般都是矩形，其各边分别与坐标轴平行。 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

7 用户定义的图形从窗口区到视图区的输出过程如下：
从应用程序得到图形的用户坐标(WC-World Coordinates)→对窗口区进行裁剪(WC)→窗口区到视图区的规格化变换(NDC-Normalized Device Coordinate)→视图区从规格化设备系到设备坐标系的变换(DC-Device Coordinate)→在图形设备上输出图形。 下图是从用户坐标系取图形在设备坐标系下显示的示意图： 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

8 6.1.3 窗口区和视图区之间的坐标变换 由于窗口和视图是在不同坐标系中定义的，因此，在把窗口中图形信息转换到视图区之前，必须进行坐标变换，即把用户坐标系的坐标值转化为设备坐标系的坐标值。 设在用户坐标系下，矩形窗口左下角点坐标为(Wxl,Wyb), 右上角点坐标为(Wxr,Wyt)。屏幕中视图区的两个角点在设备坐标系下分别为(Vxl,Vyb)和(Vxr,Vyt)。则在窗口中的点(xw,yw)对应视图区中的点（xv, yv)，其变换公式为： 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

9 下图为示图： 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

10 记: 公式可以化简为： 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

11 写成矩阵形式为： 上述变换是二维变换中比例变换和平移变换的组合变换。通过变换，可以实现将用户坐标系中窗口区中任意一点转换成设备坐标系中视图区中一点，从而可以把实际图形转换到具体输出设备的显示区。 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

12 6.2 直线段裁剪 直线段是组成其它图形的基础，其它任何图形，一般都能用不同直线段或近似为直线段组合形成。直线段裁剪是其他裁剪的基础，下面介绍几种基本的线段裁剪方法。 6.2.1 点的裁剪 裁剪算法中最基本的也是最简单的是点的裁剪。设裁剪窗口是一个标准矩形，窗口左下角点坐标为(Wxl,Wyb), 右上角点坐标为(Wxr,Wyt)，若点P(x,y)满足下列不等式： Wxl≤x≤Wxr Wyb≤y≤Wyt 则该点在窗口内，其中等号表示点位于窗口边界上。这样的点属于可见点，应予保留，如果这四个不等式中有任何一个不满足，则该点在窗口外，应被裁剪掉。 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

13 6.2.2 编码裁剪算法 这是一个最早最流行的线段裁剪算法，是由Cohen和Sutherland提出的，也称为Cohen-Sutherland线段裁剪算法。该算法通过初始测试来减少需要计算的交点数目，从而加快线段裁剪算法的速度。 1. 线段同窗口的关系 在许多情形中，大多数线段不是在裁剪窗口之内就是在裁剪窗口之外，因此需要迅速决定是否接受或抛弃线段。对于任意一条直线段，它相对于裁剪窗口的可能关系如右图所示。 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

14 （1）若一线段两端点均位于裁剪窗口内，则该线段也位于窗口内且可见，如图中的线段P1P2；
（3）但当线段两端点在窗口之外，而不位于裁剪窗口的同一侧时，该线段可能完全在窗口的外面，如图中的线段P9P10，也可能不全部在窗口的外面，如图中的线段P7P8。 （4）若线段的两端点一个位于窗口之内，一个位于窗口之外，则该线段部分可见，如图中的线段P5P6。 对于上述(1)(2)两种情况，可以通过判断一线段两端点位置直接决定是否接受或抛弃线段。而对于(3)(4)两种情况，则需要进一步计算线段与裁剪窗口的交点，得到需要保留的部分线段。 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

15 2 编码方法 根据上面的分析，把包含窗口的平面区域沿窗口的四条边线分成九个区域，如下图所示。用四位二进制码来标识线段的端点位于九个区域中的哪一个区域内。四位编码规则如下： 第一位置1： 线段端点位于窗口左侧； 第二位置1： 线段端点位于窗口右侧； 第三位置1： 线段端点位于窗口下面； 第四位置1： 线段端点位于窗口上面； 否则相应位置零。 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

16 一旦给所有的线段端点建立了编码，就可以快速判断哪条线段完全在裁剪窗口内，哪条线段完全在窗口外。其方法如下：
由编码规则可知，若线段完全在裁剪窗口内，则线段两端点编码均为0000。当线段两端点均在窗口之外，且位于裁剪窗口的同一侧时，则两端点编码必有一位同时为1。 一旦给所有的线段端点建立了编码，就可以快速判断哪条线段完全在裁剪窗口内，哪条线段完全在窗口外。其方法如下： （1）线段两端点的编码逐位取逻辑“或”，若结果为零，则该线段必为完全可见，应保留。 （2）线段两端点的编码逐位取逻辑“与”，若结果非零，则该线段必为完全不可见，因而可立即抛弃。 通过上面两步判定得知完全可见线段和完全不可见线段后，剩下线段两端点编码逻辑“或”不为零，或两端点编码的逻辑“与”均为零，这些线段可能部分可见，也可能完全不可见。 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

17 对于不能判定完全可见和完全不可见的线段，需要对线段进行再分割，即找到与窗口一个边框的交点，根据交点位置，也赋予4位代码，并对分割后的线段进行检查，或者接受，或者舍弃，或者再次进行分割。重复这一过程，直到全部线段均被舍弃或被接受为止。线段与窗口边求交次序的选择是任意的。但是无论哪种次序，对于有些线段的裁剪，可能不得不重复4次，计算与4条窗口边的交点。 下面介绍交点的求法。设线段两端点坐标分别为P1(x1,y1)和P2(x2,y2)，通过P1(x1,y1)和P2(x2,y2)两点的直线方程为： 或 其中 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

18 利用两点式直线方程，线段与窗口四条边线的交点坐标，可分别确定如下：
同窗口左边线的交点： 同窗口右边线的交点： 同窗口上边线的交点： 同窗口下边线的交点： 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

19 更快的线段裁剪算法基于线段的参数化方程的分析，它是由粱友栋和Barsky提出的，也称为粱友栋-Barsky线段裁剪算法。
在上面的求交点计算过程中，需要考虑对某些特殊情形的处理。若直线的斜率m为无穷大，则直线平行于窗口的左边和右边，故仅需检查直线与上、下两边的交点。同样，若直线斜率为零，则它平行于窗口的上、下两边，这时仅需检查直线与左、右两边的交点。 参数化线段裁剪算法 更快的线段裁剪算法基于线段的参数化方程的分析，它是由粱友栋和Barsky提出的，也称为粱友栋-Barsky线段裁剪算法。 设线段两端点坐标分别为P1(x1,y1)和P2(x2,y2),则其参数化直线方程可写成下列形式： 0≤u≤1 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

20 坐标(x,y)表示直线上两端点之间的任一点。当u=0时，得点P1，当u=1时，得点P2。线段的裁剪条件可以由下面的不等式表示：
Wxl≤x1﹢uΔx≤Wxr Wyb≤y1﹢uΔy≤Wyt 这四个不等式可以表示为： upk≤qk k=1,2,3,4 其中，参数p,q定义为： p1﹦-Δx, q1﹦x1﹣Wxl p2﹦Δx, q2﹦Wxr﹣x1 p3﹦-Δy, q3﹦y1﹣Wyb p4﹦Δy, q4﹦Wyt﹣y1 下标k=1,2,3,4分别对应裁剪窗口的左、右、下、上四条边界线。 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

21 如果线段平行于裁剪窗口的某两边界，则必有相应的pk﹦0，如果还满足qk＜0，则线段的端点位于窗口外部，即线段在窗口外，应该舍弃。如果qk≥0，线段在窗口内。
当pk＜0时，直线是从裁剪窗口第k条边界线的外部延伸到内部。例如当p1＜0时，则x2＞x1, 直线必然从裁剪窗口的左边界线的外部进入内部，如下图中的线段P1P2。当pk＞0时，直线是从裁剪窗口第k条边界线的内部延伸到外部。例如p2＞0时，则x2＞x1, 直线必然从裁剪窗口的右边界线的内部进入外部,如下图中的线段P3P4。 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

22 当pk不等于零时，可以计算出线段与第k条裁剪窗口边界线的交点参数：
根据定义，对于每条线段，pk中必有两个小于零，而另两个大于零。对于小于零的pk，直线同第k条裁剪窗口边线是从外到内相遇的，此时如果线段同第k条裁剪窗口边界线有交点的话，是参数u从0变大时遇到的，这时计算出相应的rk值，取0和各个rk值之中的最大值记为u1。与此相反，对于大于零的pk，计算出相应的rk值，取1和各个rk值之中的最小值记为u2。两个参数u1和u2定义了在裁剪窗口内的线段部分。如果u1＞u2，则线段完全落在裁剪窗口之外，应被舍弃。否则被裁剪线段可见部分的端点由参数u1和u2计算出来。 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

23 设：Wxl=2; Wxr=4; Wyb=2; Wyt=4 被裁剪线段的两端点：（1，2），（5，3） 计算：Δx=5-1=4
梁友栋线的裁剪算法例子 设：Wxl=2; Wxr=4; Wyb=2; Wyt=4 被裁剪线段的两端点：（1，2），（5，3） 计算：Δx=5-1=4 Δy=3-2=1 p1= -4，q1= -1 p2=4， q2=3 p3= -1，q3= 0 p4=1， q4=2 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

24 p1，p3小于0，决定u1，取0与r1和r3中的大者，u1=1/4 p2，p4大于0，决定u2，取1与r2和r4中的小者，u2=3/4
两交点由u1，u2决定： 计算：(1) (2) 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

25 通常粱友栋-Barsky算法比Cohen-Sutherland算法更有效，因为需要计算的交点数目减少了。一次计算就可以确定出线段的可见性及可见部分。这两种线段裁剪算法都可以扩展为三维线段裁剪算法。
2019/4/7 计算机图形学演示稿 纪玉波制作(C)

26 6.3 多边形裁剪 尽管多边形是由线段组成的，但却不能简单地将线段裁剪方法用于多边形裁剪。这是因为，在线段裁剪中，是把一条线段的两个端点孤立地加以考虑的，而多边形是由一些有序的线段组成的，裁剪后的多边形仍应保持原多边形各边的连接顺序。还有，一个完整的封闭多边形经裁剪后一般不再是封闭的，需要用裁剪窗口边界适当部分来形成一个或多个封闭区域。所以，多边形裁剪后的输出应该是定义裁剪后的多边形边界的顶点序列。下图示出了一个多边形裁剪的例子。图(a)中是矩形裁剪窗口和需要裁剪的三角形，图(b)中是不正确的非封闭裁剪结果，图(c)是正确的封闭裁剪结果。 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

27 多边形裁剪方法很多，下面介绍两种常用的多边形裁剪算法。
2019/4/7 计算机图形学演示稿 纪玉波制作(C)

28 6.3.1 逐边裁剪法 这个算法是由Sutherland和Hodgman提出来的, 也称为Sutherland-Hoeman多边形裁剪方法。对于矩形裁剪窗口的一条边界线，如果称窗口区域所在的一侧为内侧，另一侧为外侧，则方法的具体做法是：每次用裁剪窗口的一条边界对要裁剪的多边形进行裁剪，把落在此边界外侧的多边形部分去掉，只保留内侧部分，形成一个新的多边形，并把它作为下一次待裁剪的多边形。若依次用裁剪窗口的4条边界对要裁剪的原始多边形进行裁剪，则最后形成了裁剪出来的多边形。下图说明了这个过程。 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

29 当多边形顶点序列中一条边的起点和终点被一窗口边界裁剪时，会遇到边与窗口的四种情况之一，做如下处理：
在剪取过程中，实际是多边形的每一边与窗口的一边界进行比较，从而确定它们的位置关系。多边形是用顶点表示的，相邻的一对顶点构成一条边。具体实现时首先把待裁剪多边形各顶点按照一定方向有次序地组成顶点序列。然后用窗口的一条边界裁剪多边形，产生新的顶点序列。 当多边形顶点序列中一条边的起点和终点被一窗口边界裁剪时，会遇到边与窗口的四种情况之一，做如下处理： ① 如果起点在窗口边界外侧而终点在窗口边界内侧，则将多边形的该边与窗口边界的交点和终点都加到输出顶点表中； ② 如果两顶点都在窗口边界内侧，则只有终点加入输出顶点表中； ③ 如果起点在窗口边界内侧而终点在外侧，则只将与窗口边界的交点加到输出顶点表中； ④ 如果两个点都在窗口边界外侧，输出表中不增加任何点。 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

30 边与窗口的四种可能的关系如下图所示： 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

31 按照上述处理方法，窗口的一条裁剪边界处理完所有顶点后，其输出是一个新的封闭多边形顶点序列表，用于窗口的下一条边界继续裁剪。所有的窗口边界都裁剪完后，得到的是裁剪后的多边形顶点序列，它自然也是封闭的。
要实现上述算法还涉及到点处于窗口边界内外侧判别和求多边形的边和窗口边界的交点。前一节线段裁剪中所述的判别和求交方法都是可用的，下面再各介绍一种方法。 二维多边形裁剪中，用两矢量叉积的方法判别点处于窗口边界内外侧十分简单。设在右手坐标系中，裁剪窗口位于XY平面上，平面的法线与Z轴方向相同，所以只有z分量。假定裁剪窗口各边取顺时针方向，记一边界起点为W1,终点为W2。多边形的一顶点P与W1和W2可构成平面上的两矢量 和 ，作两矢量的叉积，如下图所示，也只有z分量不为零： 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

32 上式中的下标x,y分别表示点的x,y坐标分量。
2019/4/7 计算机图形学演示稿 纪玉波制作(C)

33 线段与窗口边界的交点可以使用直线的参数方程求取。线段的参数方程为:
记： 当P点位于窗口边界的右面时为内侧,其矢量叉积同Z轴的正方向，此时C＞0，点可见。当点位于窗口边界的左面时为外侧，其矢量叉积同Z轴方向相反，此时C＜0，点不可见。当点位于窗口边界上时作为可见，此时C=0。如是通过多边形顶点和窗口边界端点的坐标值，用上式计算C值可判断出点的可见性。 线段与窗口边界的交点可以使用直线的参数方程求取。线段的参数方程为: 0≤u≤1 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

34 记被裁剪线段的两个端点为P1(x1,y1),P2(x2,y2), 窗口边界线段的两端点为W1(W1x,W1y), W2(W2x,W2y)。并记两线段的参数分别为u1,u2。如果两线段相交，则交点处的参数值可以由下面方程求出： 解方程组可得： 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

35 当解在[0,1]区间时,将u1和u2代入方程中得到交点坐标。否则两线段不相交。分母为零时两线段平行。
当分母 时，u1和u2有相同的唯一解。 当解在[0,1]区间时,将u1和u2代入方程中得到交点坐标。否则两线段不相交。分母为零时两线段平行。 算法描述如下： ① 依次取窗口的一边作为裁剪边，各窗口边都处理完后转⑤； ② 用此裁剪边对多边形的各条边依次进行裁剪； ③ 按被裁剪边相对于裁剪边相交、重合、完全可见，完全不可见分情况处理； ④ 多边形全部边裁剪完否？完转①，否则转②； ⑤ 结束。 由于在这一剪取方法中，被剪取多边形的每一边是依次处理的，故只需作少许变动，用同一子程序可以处理多边形的每一边。 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

36 凸多边形可以用Sutherland-Hodgeman算法获得正确的裁剪结果，但是对凹多边形的裁剪，可能出现如下图所示多余的连线。这种情况在裁剪后的多边形有两个或者多个分离部分的时候出现。因为只有一个输出顶点表，所以表中最后一个顶点总是连着第一个顶点。如下面所述的另一算法可以消除这一问题。 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

37 ①如果线段起点在窗口外部而终点在窗口内部，则求出交点，输出线段可见部分，继续沿多边形方向往下处理；
6.3.2 双边裁剪法 此算法是由Weiler和Atherton提出来的。算法的基本做法是：有时沿着多边形边的方向来处理顶点，有时沿着窗口的边界方向来处理，从而避免产生多余的连线。设被裁剪多边形和裁剪窗口都按顺时针确定排列方向，因此，沿多边形的一条边前进，其右边为多边形的内部。算法首先沿多边形的任一点出发，跟踪检测多边形的每一条线段，当线段与裁剪窗口边界相交时： ①如果线段起点在窗口外部而终点在窗口内部，则求出交点，输出线段可见部分，继续沿多边形方向往下处理； ②如果线段起点在窗口内部而终点在窗口外部，则求出交点，输出线段可见部分。从此交点开始，沿着窗口边界方向往前检测，找到一个多边形与窗口边界的新交点后，输出由前交点到此新交点之间窗口边界上的线段； ③返回到前交点，再沿着多边形方向往下处理，直到处理完多边形的每一条边，回到起点为止。 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

38 Weiler-Atherton算法可适用于任何凸的或凹的多边形裁剪，不会产生多余连线。
下图说明了双边裁剪算法的执行过程。 Weiler-Atherton算法可适用于任何凸的或凹的多边形裁剪，不会产生多余连线。 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

39 6.4 其它类型的图形裁剪 6.4.1 非矩形裁剪窗口的线段裁剪
在某些应用中，需要用任意形状的多边形对线段裁剪。对凸多边形裁剪窗口，可以修改粱友栋-Barsky的参数化线段裁剪方法，使参数化方程适合裁剪区域的边界，按照裁剪多边形的坐标范围处理线段。这就成为另一种称之为Cyrus-Beck线段裁剪方法的算法。而前面介绍的两种多边形裁剪方法都适应于任意凸多边形裁剪窗口。 圆或其他曲线边界也可以用作为裁剪窗口，但用的很少。用这些区域的裁剪算法速度更慢，因为它的求交计算涉及非线性曲线方程。加快速度的一个方法是可以首先使用曲线裁剪区域的外接矩形裁剪，完全落在外接矩形之外的裁剪对象被舍弃。如果是用圆作为窗口对线段裁剪，可以通过计算圆心到直线端点的距离来识别出内部线段。其他线段通过解联立方程来计算交点。 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

40 6.4.2 曲线的裁剪 曲线的裁剪过程涉及到非线性方程，需要更多的处理。圆或者其它曲线对象的外接矩形可以用来首先测试是否与矩形裁剪窗口有重叠。如果曲线对象的外接矩形完全落在裁剪窗口内，则曲线对象完全可见，如果曲线对象的外接矩形完全落在裁剪窗口外，则曲线对象完全不可见。两种情况都不满足时，一般需要解直线和曲线的联立方程求交点。 处理曲线对象的另一有效方法是把它们近似为直线段，然后使用线段或多边形的裁剪算法。曲线绘制时通常也使用直线段逼近的方法，由于逼近时总是将线段取的很短，为了减少计算时间，裁剪时可以不计算交点，只要线段的端点中至少有一个在裁剪窗口外，就舍弃该线段，从而提高裁剪效率。 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

41 字符既可由单个的线段或笔划构成，也可以用点阵来表示。由裁剪精度要求不同，字符裁剪也采用不同的方法。
6.4.3字符的裁剪 字符既可由单个的线段或笔划构成，也可以用点阵来表示。由裁剪精度要求不同，字符裁剪也采用不同的方法。 精确裁剪是对单个字符进行裁剪。此时笔划式字符可看作是短直线段的集合，用裁剪线段的方法进行裁剪。点阵式字符必须将字符方框中每一象素同裁剪窗口进行比较，以确定它位于窗口内还是窗口外。若位于窗口内，该象素被激活，否则不予考虑。 如果把每个字符看作是不可分割的整体，那么对每一个字符串就可用逐字裁剪的方法。这可将字符方框同裁剪窗口进行比较，若整个方框位于窗口内，则显示相应字符，否则不予显示。 最后一种处理方法是把一个字符串作为不可分割的整体来处理，或者全部显示，或者全部不显示。将字符串用一个字符串框封闭起来，若整个方框位于窗口内，则显示整串字符，否则整串字符就不显示。 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

42 下图示出了这几种裁剪情况。 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

43 6.5 三维裁剪 三维裁剪空间 三维图形的显示需要投影到二维投影面上实现。但在投影之前应对三维图形进行裁剪，把图形中不关心的部分去掉，留下感兴趣的部分投影到投影面上显示出来。这就需要在用户坐标系中指定一个观察空间，将这个观察空间以外的图形裁剪掉，只对落在这个空间内的图形部分作投影变换并予以显示。 观察空间的确定取决于投影类型、投影平面、和投影中心的位置。对于透视投影，观察空间是顶点在投影中心、其棱边穿过投影平面四个角点、没有底面的四棱锥，如下图(a)所示。而对于平行投影，观察空间是一个四边平行于投影方向、两端没有底面的长型方管如下图(b)所示。 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

44 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

45 在大多数场合，希望观察空间是有限的。通常使用平行于投影平面的一截面将无限的观察空间截成有限的观察空间。截面的位置由从投影中心沿投影平面法向的距离z=E确定。对于透视投影，投影平面与截面之间的观察空间是一个正四棱台，如上图(c)所示。对于平行投影，投影平面与截面之间的观察空间是一个正四棱柱，如上图(d)所示。有限的观察空间又叫裁剪空间。裁剪空间具有六个边界平面，即左侧面、右侧面、上面、下面、前面和后面。这六个边界平面把整个三维空间分割成裁剪空间内部和裁剪空间外部两部分。把落在裁剪空间内的图形从整个空间的图形中分离出来，这就是三维裁剪所要做的工作。 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

46 假设投影平面为正方形，边长2f，到坐标原点的距离是d，则平行投影观察空间正四棱柱的左、右、上、下、前、后六个边界平面的平面方程分别是：
对于透视投影，观察空间正四棱台的六个边界平面的平面方程分别是： 三维裁剪方法很多，我们在二维图形裁剪中介绍的编码裁剪方法和参数化裁剪方都可以推广应用到三维图形裁剪。下面介绍三维编码裁剪方法。 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

47 第一位为1，表示端点在裁剪空间的上方，即y＞fz/d； 第二位为1，表示端点在裁剪空间的下方，即y＜-fz/d；
三维编码裁剪算法 对二维图形裁剪，使用4位二进制码来标示线段端点与裁剪窗口边界的位置关系。对三维图形裁剪，相对于裁剪空间的6个边界平面需要6位二进制码来标示位置关系。设最左边的位是第一位，对一线段的两端点P1(x1,y1,z1)和P2(x2,y2,z1)，对于透视投影，可以定义其区域码中的二进制位为： 第一位为1，表示端点在裁剪空间的上方，即y＞fz/d； 第二位为1，表示端点在裁剪空间的下方，即y＜-fz/d； 第三位为1，表示端点在裁剪空间的右方，即x＞fz/d； 第四位为1，表示端点在裁剪空间的左方，即x＜-fz/d； 第五位为1，表示端点在裁剪空间的后边，即z＞E； 第六位为1，表示端点在裁剪空间的前边，即z＜d。 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

48 对于平行投影，定义其区域码中的二进制位为： 第一位为1，表示端点在裁剪空间的上方，即y＞f；
第三位为1，表示端点在裁剪空间的右方，即x＞f； 第四位为1，表示端点在裁剪空间的左方，即x＜-f； 第五位为1，表示端点在裁剪空间的后边，即z＞E； 第六位为1，表示端点在裁剪空间的前边，即z＜d。 例如，编码100010表示端点在裁剪空间的上面及后面，编码000000表示端点在裁剪空间内部。正如同在二维裁剪中所做的一样，对线段的两端点编码按位取逻辑“或”，若结果为零，则该线段完全可见，应保留。两端点的编码按位取逻辑“与”，若结果非零，则该线段完全不可见，可抛弃。 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

49 如果上述两种情况都不满足，则要计算线段与裁剪空间边界平面的交点来确定线段的可见性和可见部分。对任意一条三维线段，参数方程可写成：
0≤u≤1 裁剪空间六个边界平面方程的一般表达式为： 为找出线段与裁剪空间边界平面之交点，把直线方程代入平面方程，求得： 2019/4/7 计算机图形学演示稿 纪玉波制作(C)

50 平行投影和透视投影裁剪空间6个边界平面的平面方程都是简单的平面方程，因而u的计算也简化了。例如，求线段与裁剪空间后面的交点，则：
上式中，若A(x2-x1)+B(y2-y1)+C(z2-z1)=0，则说明线段在边界平面上或同边界平面平行；若u值不在[0,1]区间时, 则说明交点在裁剪空间以外，所以是无效交点；若u值在[0,1]区间范围内，将u代入方程中便可得到交点坐标。 平行投影和透视投影裁剪空间6个边界平面的平面方程都是简单的平面方程，因而u的计算也简化了。例如，求线段与裁剪空间后面的交点，则： 当u值在[0,1]区间范围内时为有效交点，将u代入方程中便可得到交点坐标。 类似地可求得其它五个面与线段的有效交点。连接有效交点可得到落在裁剪空间内的有效线段。 2019/4/7 计算机图形学演示稿 纪玉波制作(C)