五讲剪裁ppt课件

1、内容摘要 裁剪裁剪 窗口视图变换窗口视图变换 线段裁剪线段裁剪 线段端点与窗口区域关系判别线段端点与窗口区域关系判别 Cohen-SutherlandCohen-Sutherland线段裁剪算法线段裁剪算法 中点分割算法中点分割算法 最远可见点算法最远可见点算法 中点分割算法处置流程中点分割算法处置流程 多边形裁剪多边形裁剪 多边形裁剪多边形裁剪 多边形裁剪流程图多边形裁剪流程图裁剪裁剪在运用计算机处置图形信息时，往往计算机内部存储在运用计算机处置图形信息时，往往计算机内部存储的图形比较大，而屏幕显示只是图的一部分。例如，的图形比较大，而屏幕显示只是图的一部分。例如，虽然计算机内部可以存储全国

2、地图。但是，假设把全虽然计算机内部可以存储全国地图。但是，假设把全国整幅显示在屏幕上，那么不能看到各地部分的细节国整幅显示在屏幕上，那么不能看到各地部分的细节。这时，可以运用缩放技术，把地图中的部分区域放。这时，可以运用缩放技术，把地图中的部分区域放大显示。在放大一幅图形的一部分区域，必需确定图大显示。在放大一幅图形的一部分区域，必需确定图形中哪些部分落在显示区之内，哪些部分落在显示区形中哪些部分落在显示区之内，哪些部分落在显示区之外，以便显示落在显示区内的那部分图形。这个选之外，以便显示落在显示区内的那部分图形。这个选择处置过程称为裁剪，就好象从一个大的图形中剪出择处置过程称为裁剪，就好象从

3、一个大的图形中剪出需求的一个小块。需求的一个小块。裁剪在图形处置中很有意义，本章节专门研讨裁剪的裁剪在图形处置中很有意义，本章节专门研讨裁剪的方法，根据这些方法还可以构造出更高级的裁剪算法方法，根据这些方法还可以构造出更高级的裁剪算法窗口视图变换窗口视图变换窗口：由用户坐标系定义的一个矩形区窗口：由用户坐标系定义的一个矩形区域；域；视口：由设备坐标系定义的一个矩形区视口：由设备坐标系定义的一个矩形区域；域；当把用户坐标系中的图形在图形设备上当把用户坐标系中的图形在图形设备上输出时，可以定义适当的窗口和视口，输出时，可以定义适当的窗口和视口，使窗口的图形在视口内显示，处于窗口使窗口的图形在视口内

4、显示，处于窗口外或视口外的图形那么不被显示即称被外或视口外的图形那么不被显示即称被裁剪掉。固定视口而改动窗口，就可以裁剪掉。固定视口而改动窗口，就可以在在视口HVLV(XV1，YV1)窗口HW( X W 1 ，YW1)LW窗口与视口的关系用户坐标系设备坐标系视口中察看到用户描画的全部图形了。视口中察看到用户描画的全部图形了。窗口与视口存在变换关系：窗口与视口存在变换关系：设：视口的宽为设：视口的宽为LVLV，高为，高为HVHV，左下角为，左下角为(XV1(XV1，YV1)YV1)，窗口的宽为，窗口的宽为LWLW，高为，高为HWHW，左下，左下角为角为(XW1(XW1，YW1)YW1)，如下图。

5、对视口中的点，如下图。对视口中的点(XV(XV，YV)YV)，在窗口中有一点，在窗口中有一点XWXW，YWYW与与之对应，且有：之对应，且有：(XW-XW1)/(XV-XV1)(XW-XW1)/(XV-XV1)LWLWLV LV (YW-YW1)/(YV-YV1)(YW-YW1)/(YV-YV1)HWHWHV HV 线段裁剪线段裁剪裁剪算法有二维的和三维裁剪算法有二维的和三维的，裁剪对象可以是规那的，裁剪对象可以是规那么形体，也可以是不规那么形体，也可以是不规那么形体，其裁剪算法可以么形体，其裁剪算法可以用硬件实现，也可以用软用硬件实现，也可以用软件实现。件实现。在进展裁剪时，画面中对在进展裁

6、剪时，画面中对应于屏幕显示的那部分区应于屏幕显示的那部分区域也即窗口，把其定义为域也即窗口，把其定义为矩形，由上、下、左、右矩形，由上、下、左、右四条边围成，即：四条边围成，即：(xL(xL，yB)yB)，(xR(xR，yH)yH)。裁剪的。裁剪的本质就是决议图形中哪些本质就是决议图形中哪些点、线段、文字、以及多点、线段、文字、以及多边形在裁剪窗口之内，边形在裁剪窗口之内，在窗口内的图形被保管显示，而窗口之外的画面被裁去。如下图。在窗口内的图形被保管显示，而窗口之外的画面被裁去。如下图。对于点对于点(x(x，y)y)，只需判别两对不等式：，只需判别两对不等式：xLxLx x xR xR，yBy

7、By yyHyH假设四个不等式均成立，那么点在窗口矩形之内；否那么，点在窗口矩形之外。其假设四个不等式均成立，那么点在窗口矩形之内；否那么，点在窗口矩形之外。其中中, ,等号表示点位于窗口的边境上。等号表示点位于窗口的边境上。1线段端点与窗口区域关系判别线段端点与窗口区域关系判别完全在窗口内的线段和完全完全在窗口内的线段和完全不在窗口内的线段可以用下不在窗口内的线段可以用下面的语句判别。面的语句判别。 if XaXR if XaXR then 1then 1 if XbXR if XbXR then 1then 1 if YaYH if YaYH then 1then 1 if YbYH if

8、 YbYH then 1then 1line(Xa,Ya,Xb,Yb) line(Xa,Ya,Xb,Yb) 在窗口在窗口之内之内1: if XaXL and XbXL 1: if XaXL and XbXR and XbXR if XaXR and XbXR then 2then 2 if YaYH and YbYH if YaYH and YbYH then 2then 2 if YaYB and YbYB if YaYB and YbYB then 2then 2一部分在窗口内一部分在窗口内, ,需求裁剪需求裁剪. .2:line(Xa,Ya,Xb,Yb)2:line(Xa,Ya,Xb,Y

9、b)完全完全在窗口之外。在窗口之外。这样就可以首先将这两种特殊情况进展简单的判别而得到结果，剩下来的问题就是对这样就可以首先将这两种特殊情况进展简单的判别而得到结果，剩下来的问题就是对于那些一部分在窗口内而另一部分在窗口外的线段的处置了。于那些一部分在窗口内而另一部分在窗口外的线段的处置了。(Xa,Ya) (Xb,Yb )3由Dan Cohen和Ivan Sutherland提出的区域编码判别方法，它采用四位数码来标识线段的端点与窗口区域的关系。 如右图所示。编码规那么为：线段端点的区域编码裁剪矩形010001010110000000010010100010011010端点位于窗口左侧1 1

10、1 1端点位于窗口右侧端点位于窗口下侧端点位于窗口上侧线段端点与窗口区域关系判别线段端点与窗口区域关系判别从表3-1中可以看出，当两端点编码进展逻辑“与 运算后，当结果不为零时，该线段完全在窗口外面，而当结果为零时，还要进一步判别。1Cohen-SutherlandCohen-Sutherland线段裁剪算法线段裁剪算法算法的根本思想如下：算法的根本思想如下：1 1检查线段检查线段P1P2P1P2能否为完全可见，或完全不可见，对能否为完全可见，或完全不可见，对于这两种情况或完全取之，或完全弃之，否那么于这两种情况或完全取之，或完全弃之，否那么 “2 2。2 2找到找到P1P2P1P2在窗口外的

11、一个端点在窗口外的一个端点P1P1或或P2P2；3 3用窗口的边与用窗口的边与P1P2P1P2的交点取代端点的交点取代端点P1P1或或P2P2；4 4P1P2P1P2线段能否完全可见，假设是，那么终了，否那线段能否完全可见，假设是，那么终了，否那么转到么转到“2 2“继续执行。继续执行。图中，线段不完全可见，也不是完全不可见，是部分在图中，线段不完全可见，也不是完全不可见，是部分在窗口内、部分在窗口外。窗口内、部分在窗口外。P1P1点的编码为点的编码为01010101，P2P2点的编码为点的编码为00100010。首先获得首先获得P1P1点为窗口外的点，由于点为窗口外的点，由于P1P1点的第一

12、位编码为点的第一位编码为1 1，因此先求，因此先求P1P2P1P2与左边境与左边境X=1X=1的交点的的交点的P1P1 ，对，对P1P1编码编码有有01000100依然是窗口外的点，再求依然是窗口外的点，再求P1P1 P1 P1 P1 P2 P1 P2与下边境与下边境Y=1Y=1的交点得的交点得P1P1，编码是，编码是00000000，故为窗口内的，故为窗口内的点，而点，而P2P2点仍在窗口外由于编码中第二位为点仍在窗口外由于编码中第二位为1 1，故可求，故可求P1 P2P1 P2与右边境与右边境X X4 4的交点，求得后为的交点，求得后为P2P2点的编码为点的编码为00000000，用，用P

13、2P2P2P2替代原来的替代原来的P2P2点，点， 此时此时P1P2P1P2线段就为完全可见线段了。线段就为完全可见线段了。知直线：知直线：X1X1，Y1Y1，X2X2，Y2Y2，与程度线，与程度线Y YK K的交点为：的交点为：与垂直线与垂直线X=RX=R的交点为的交点为: :所以，在进展裁剪时除了要求直线与边境的交点外，还要判别端点与窗口的位置关系。为此有：所以，在进展裁剪时除了要求直线与边境的交点外，还要判别端点与窗口的位置关系。为此有：假设假设 编码编码&0001&00010 0，端点落在左边境，端点落在左边境; ;假设假设 编码编码&0010&0010

14、0 0，端点落在右边境，端点落在右边境; ;假设假设 编码编码&0100&01000 0，端点落在下边境，端点落在下边境; ;假设假设 编码编码&1000&10000 0，端点落在上边境，端点落在上边境; ;3中点分割算法中点分割算法在图在图3-423-42中的中的b b线段，线段，检查端点编码可知它检查端点编码可知它既不是完全可见段，既不是完全可见段，也不是完全不可见段也不是完全不可见段，那么在中点，那么在中点Pm1Pm1处将处将b b分为二段，两段的情分为二段，两段的情况依然一样。先不思况依然一样。先不思索索P1Pm1P1Pm1，在，在Pm2Pm2处将处将P

15、m1P2Pm1P2分为二段从图中分为二段从图中可见，可见，Pm1Pm2Pm1Pm2完全可完全可见，而见，而Pm2P2Pm2P2部分可见部分可见。这样处置的结果将。这样处置的结果将导致线段的可见部分导致线段的可见部分被划分成一系列的可被划分成一系列的可见小段然后再逐段画见小段然后再逐段画出，显然效率降低。出，显然效率降低。2最远可见点算法最远可见点算法求求P1P1最远可见点的算法：最远可见点的算法：1) 1) 假设假设P2P2在窗口内，那在窗口内，那么么P2P2就是离就是离P1P1最远的可见最远的可见点，终了该算法，否那么点，终了该算法，否那么进展下一步进展下一步; ;2) 2) 假设假设P1P

16、2P1P2为完全不可为完全不可见，那么终了该算法，见，那么终了该算法， 否那么进展下一步；否那么进展下一步；3) 3) 取取P1P2P1P2中点中点PmPm，假设，假设PmPm点在窗口内部，那么处点在窗口内部，那么处置置PmP2PmP2线段来寻觅线段来寻觅P1P1的最的最远可见点，即用远可见点，即用PmPm替代替代P1P1，执行，执行2 2，否那么，否那么P2P2用用PmPm替代，执行替代，执行2 2。直到。直到PmPm与与线段端点的间隔到达分辩线段端点的间隔到达分辩率精度为止。率精度为止。7多边形裁剪多边形裁剪多边形可以看作是线段的多边形可以看作是线段的集合。但是，这样做会使集合。但是，这样

17、做会使原来封锁的多边形变成不原来封锁的多边形变成不封锁的或者成为一些离散封锁的或者成为一些离散的线段。假设只思索画线的线段。假设只思索画线图形，问题还不大。但是图形，问题还不大。但是当多边形作为实体思索时当多边形作为实体思索时，封锁的多边形裁剪后还，封锁的多边形裁剪后还应是封锁的多边形，以便应是封锁的多边形，以便进展填充。为了到达这个进展填充。为了到达这个目的，可以运用目的，可以运用SutherlandSutherland和和HodgemanHodgeman所所发明的逐次多边形裁剪发明的逐次多边形裁剪R e e n t r a n t P o l y g o n R e e n t r a n

18、 t P o l y g o n ClippingClipping算法。该算法算法。该算法的根本思想是一次用窗口的根本思想是一次用窗口的一条边裁剪多边形，如的一条边裁剪多边形，如下图。下图。多边形裁剪多边形裁剪算法的输入是以顶点序列表算法的输入是以顶点序列表示的多边形。用示的多边形。用P1P2P1P2PnPn表表示把示把P1P1连到连到P2P2，P2P2连到连到P3P3，最后把，最后把PnPn连到连到P1P1所成的所成的多边形，如右上图所示。算多边形，如右上图所示。算法的输出也是一个顶点序列法的输出也是一个顶点序列，构成一个或多个多边形，构成一个或多个多边形，如右上角图所示。如右上角图所示。算法的每一步，思索以窗口算法的每一步，思索以窗口的一条边以及延伸线构成的的一条边以及延伸线构成的裁剪线。该线把平面分成两裁剪线。该线把平面分成两部分部分: :一部分包含窗口，称一部分包含窗口，称为可见一侧为可见一侧; ;另一部分称为另一部分称为不可见一侧。依序思索多边不可见一侧。依序思索多边形各条边的两端点形各条边的两端点S S、P