《五讲剪裁ppt课件》由会员分享，可在线阅读，更多相关《五讲剪裁ppt课件（16页珍藏版）》请在金锄头文库上搜索。
1、五讲剪裁ppt课件 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life, there is hope。有生命必有希望。有生命必有希望内容摘要裁剪裁剪窗口视图变换窗口视图变换线段裁剪线段裁剪线段端点与窗口区域关系判断线段端点与窗口区域关系判断Cohen-SutherlandCohen-Sutherland线段线段裁剪算法裁剪算法中点分割算法中点分割算法最远可见点算法最远可见点算法中点分割算法处理流程中点分割算法处理流程多边形裁剪多边形裁剪多边形裁剪多边形裁剪多边形裁剪流程图多边形裁剪流程图2024/8/17裁剪裁剪在在使使用用计
2、计算算机机处处理理图图形形信信息息时时，往往往往计计算算机机内内部部存存储储的的图图形形比比较较大大，而而屏屏幕幕显显示示只只是是图图的的一一部部分分。例例如如，虽虽然然计计算算机机内内部部可可以以存存储储全全国国地地图图。但但是是，如如果果把把全全国国整整幅幅显显示示在在屏屏幕幕上上，则则不不能能看看到到各各地地局局部部的的细细节节。这这时时，可可以以使使用用缩缩放放技技术术，把把地地图图中中的的局局部部区区域域放放大大显显示示。在在放放大大一一幅幅图图形形的的一一部部分分区区域域，必必须须确确定定图图形形中中哪哪些些部部分分落落在在显显示示区区之之内内，哪哪些些部部分分落落在在显显示示区区
3、之之外外，以以便便显显示示落落在在显显示示区区内内的的那那部部分分图图形形。这这个个选选择择处处理理过过程程称称为为裁裁剪剪，就就好好象象从从一一个个大大的的图图形形中中剪剪出出需需要的一个小块。要的一个小块。裁裁剪剪在在图图形形处处理理中中很很有有意意义义，本本章章节节专专门门研研究究裁裁剪剪的的方法，根据这些方法还可以构造出更高级的裁剪算法方法，根据这些方法还可以构造出更高级的裁剪算法2024/8/17窗口视图变换窗口视图变换窗口：窗口：由用户坐标系定义的一个矩形区由用户坐标系定义的一个矩形区域；域；视口：视口：由设备坐标系定义的一个矩形区由设备坐标系定义的一个矩形区域；域；当把用户坐标系
4、中的图形在图形设备上当把用户坐标系中的图形在图形设备上输出时，可以定义适当的窗口和视口，输出时，可以定义适当的窗口和视口，使窗口的图形在视口内显示，处于窗口使窗口的图形在视口内显示，处于窗口外或视口外的图形则不被显示即称被裁外或视口外的图形则不被显示即称被裁剪掉。固定视口而改变窗口，就可以在剪掉。固定视口而改变窗口，就可以在视口HVLV(XV1，YV1)窗口HW(XW1，YW1)LW窗口与视口的关系用户坐标系设备坐标系视口中观察到用户描述的全部图形了视口中观察到用户描述的全部图形了。窗口与视口存在变换关系：窗口与视口存在变换关系：设：视口的宽为设：视口的宽为L LV V，高为高为H HV V，
5、左下角为左下角为( (X XV1V1，Y YV1V1) )，窗口的宽为窗口的宽为L LW W，高为高为H HW W，左下角为左下角为( (X XW1W1，Y YW1W1) )，如图所示。对视口中的点如图所示。对视口中的点( (X XV V，Y YV V) )，在窗口中有一点（在窗口中有一点（X XW W，Y YW W）与之对应，与之对应，且有：且有：( (X XW W-X-XW1W1)/(X)/(XV V-X-XV1V1) )L LW WL LV V (Y(YW W-Y-YW1W1)/(Y)/(YV V-Y-YV1V1) )H HW WH HV V 2024/8/17线段裁剪线段裁剪裁裁剪剪算
6、算法法有有二二维维的的和和三三维维的的，裁裁剪剪对对象象可可以以是是规规则则形形体体，也也可可以以是是不不规规则则形形体体，其其裁裁剪剪算算法法可可以以用用硬硬件件实实现现，也也可可以以用用软软件件实实现。现。在在进进行行裁裁剪剪时时，画画面面中中对对应应于于屏屏幕幕显显示示的的那那部部分分区区域域也也即即窗窗口口，把把其其定定义义为为矩矩形形，由由上上、下下、左左、右右四四条条边边围围成成，即即：( (x xL L，y yB B) )，(x(xR R，y yH H) )。裁裁剪剪的的实实质质就就是是决决定定图图形形中中哪哪些些点点、线线段段、文文字字、以以及及多多边边形形在裁剪窗口之内，在裁
7、剪窗口之内，在窗口内的图形被保留显示，而窗口之外的画面被裁去。如图所示。在窗口内的图形被保留显示，而窗口之外的画面被裁去。如图所示。对于点对于点( (x x，y)y)，只要判别两对不等式：只要判别两对不等式：x xL L x x x xR R，y yB B y y y yH H若若四四个个不不等等式式均均成成立立，则则点点在在窗窗口口矩矩形形之之内内；否否则则，点点在在窗窗口口矩矩形形之之外外。其其中中, ,等等号号表示点位于窗口的边界上。表示点位于窗口的边界上。12024/8/17线段端点与窗口区域关系判断线段端点与窗口区域关系判断完完全全在在窗窗口口内内的的线线段段和和完完全全不不在在窗窗
8、口口内内的的线线段段可可以以用用下下面的语句判断。面的语句判断。 if Xif Xa aXXXR R then 1 then 1 if X if Xb bXXXR R then 1 then 1 if Y if Ya aYYYH H then 1 then 1 if Y if Yb bYYYH H then 1 then 1line(Xline(Xa a,Y,Ya a,X,Xb b,Y,Yb b) ) 在窗口之内在窗口之内1: 1: if Xif Xa aXXL L and X and Xb bXXXR R and Xand Xb bXXR R then 2then 2 if Y if Ya
9、aYYH H and Y and Yb bYYH H then 2 then 2 if Y if Ya aYYB B and Y and Yb bYYB B then 2 then 2一部分在窗口内一部分在窗口内, ,需要裁剪需要裁剪. .2:2:line(Xline(Xa a,Y,Ya a,X,Xb b,Y,Yb b) )完完 全全 在在窗口之外。窗口之外。这样就可以首先将这两种特殊情况进行简单的判别而得到结果，剩下来的问题就是对这样就可以首先将这两种特殊情况进行简单的判别而得到结果，剩下来的问题就是对于那些一部分在窗口内而另一部分在窗口外的线段的处理了。于那些一部分在窗口内而另一部分在窗口
10、外的线段的处理了。(Xa,Ya) (Xb,Yb )32024/8/17由Dan Cohen和Ivan Sutherland提出的区域编码判断方法，它采用四位数码来标识线段的端点与窗口区域的关系。 如右图所示。编码规则为：线段端点的区域编码裁剪矩形010001010110000000010010100010011010端点位于窗口左侧1 1 1 1端点位于窗口右侧端点位于窗口下侧端点位于窗口上侧线段端点与窗口区域关系判断线段端点与窗口区域关系判断从表3-1中可以看出，当两端点编码当两端点编码进行逻辑进行逻辑“与与” ” 运算后，当结果不为零时，该线段完全在窗口外面，而当结果为零时，还要进一步判断
11、。 12024/8/17Cohen-SutherlandCohen-Sutherland线段线段裁剪算法裁剪算法算法的基本思想如下：算法的基本思想如下：1 1检查线段检查线段P P1 1P P2 2是否为完全可见，或完全不可见，对于是否为完全可见，或完全不可见，对于这两种情况或完全取之，或完全弃之，否则这两种情况或完全取之，或完全弃之，否则 “2” “2”。2 2找到找到P P1 1P P2 2在窗口外的一个端点在窗口外的一个端点P P1 1（或或P P2 2）；）；3 3用窗口的边与用窗口的边与P P1 1P P2 2的交点取代端点的交点取代端点P P1 1（或或P P2 2）；）；4 4P
12、 P1 1P P2 2线段是否完全可见，若是，则结束，否则转到线段是否完全可见，若是，则结束，否则转到“2“2“继续执行。继续执行。图中，线段不完全可见，也不是完全不可见，是部分在图中，线段不完全可见，也不是完全不可见，是部分在窗口内、部分在窗口外。窗口内、部分在窗口外。P P1 1点的编码为点的编码为01010101，P P2 2点的编码为点的编码为00100010。首先获得首先获得P P1 1点为窗口外的点，由于点为窗口外的点，由于P P1 1点的第一位编码为点的第一位编码为1 1，因此先求，因此先求P P1 1P P2 2与左边界与左边界X=1X=1的交点的的交点的P P1 1 ，对对P
13、 P1 1编码有编码有01000100仍然是窗口外的点，再求（仍然是窗口外的点，再求（P P1 1 P P1 1 ） P P1 1 P P2 2与下与下边界边界Y=1Y=1的交点得的交点得P P1 1，编码是编码是00000000，故为窗口内的点，故为窗口内的点，而而P P2 2点仍在窗口外由于编码中第二位为点仍在窗口外由于编码中第二位为1 1，故可求，故可求P P1 1 P P2 2与右边界与右边界X4的交点，求得后为的交点，求得后为P P2 2点的编码为点的编码为00000000，用，用P P2 2P P2 2代替原来的代替原来的P P2 2点，点， 此时此时P P1 1P P2 2线段就
14、为完全可见线段了。线段就为完全可见线段了。已知直线：（已知直线：（X X1 1，Y Y1 1），（），（X X2 2，Y Y2 2），），与水平线与水平线Y YK K的交点为：的交点为：与垂直线与垂直线X=RX=R的交点为的交点为: :所以，在进行裁剪时除了要求直线与边界的交点外，还要判断端点与窗口的位置关系。为此有：所以，在进行裁剪时除了要求直线与边界的交点外，还要判断端点与窗口的位置关系。为此有：若 编码&00010，端点落在左边界;若 编码&00100，端点落在右边界;若 编码&01000，端点落在下边界;若 编码&10000，端点落在上边界;32024/8/17中点分割算法中点分割算法
15、在图在图3-423-42中的中的b b线段，线段，检查端点编码可知它检查端点编码可知它既不是完全可见段，既不是完全可见段，也不是完全不可见段，也不是完全不可见段，则在中点则在中点P Pm1m1处将处将b b分为分为二段，两段的情况仍二段，两段的情况仍然相同。先不考虑然相同。先不考虑P P1 1P Pm1m1，在在P Pm2m2处将处将P Pm1m1P P2 2分为二段从图中可见，分为二段从图中可见，P Pm1m1P Pm2m2完全可见，而完全可见，而P Pm2m2P P2 2部分可见。这样部分可见。这样处理的结果将导致线处理的结果将导致线段的可见部分被划分段的可见部分被划分成一系列的可见小段成
16、一系列的可见小段然后再逐段画出，显然后再逐段画出，显然效率降低。然效率降低。22024/8/17最远可见点算法最远可见点算法求求P P1 1最远可见点的算法：最远可见点的算法：1) 若若P P2 2在窗口内，则在窗口内，则P P2 2就就是离是离P P1 1最远的可见点，结最远的可见点，结束该算法，否则进行下一束该算法，否则进行下一步步; ;2) 若若P P1 1P P2 2为完全不可见，为完全不可见，则结束该算法，则结束该算法， 否则进否则进行下一步；行下一步；3) 取取P P1 1P P2 2中点中点P Pm m，若若P Pm m点点在窗口内部，则处理在窗口内部，则处理P Pm mP P2
17、 2线段来寻找线段来寻找P P1 1的最远可见的最远可见点，即用点，即用P Pm m代替代替P P1 1，执行执行2 2，否则，否则P P2 2用用P Pm m代替，执行代替，执行2 2。直到。直到P Pm m与线段端点的距与线段端点的距离达到分辩率精度为止。离达到分辩率精度为止。72024/8/17多边形裁剪多边形裁剪多多边边形形可可以以看看作作是是线线段段的的集集合合。但但是是，这这样样做做会会使使原原来来封封闭闭的的多多边边形形变变成成不不封封闭闭的的或或者者成成为为一一些些离离散散的的线线段段。如如果果只只考考虑虑画画线线图图形形，问问题题还还不不大大。但但是是当当多多边边形形作作为为
18、实实体体考考虑虑时时，封封闭闭的的多多边边形形裁裁剪剪后后还还应应是是封封闭闭的的多多边边形形，以以便便进进行行填填充充。为为了了达达到到这这个个目目的的，可可以以使使用用SutherlandSutherland和和HodgemanHodgeman所所发发明明的的逐逐次次多多边边形形裁裁剪剪（Reentrant Reentrant Polygon Polygon ClippingClipping）算算法法。该该算算法法的的基基本本思思想想是是一一次次用用窗窗口口的的一一条条边边裁裁剪剪多多边边形，如图所示。形，如图所示。2024/8/17多边形裁剪多边形裁剪算算法法的的输输入入是是以以顶顶点点
19、序序列列表表示示的的多多边边形形。用用P P1 1P P2 2P Pn n表表示示把把P P1 1连连到到P P2 2，P P2 2连连到到P P3 3，最最后后把把P Pn n连连到到P P1 1所所成成的的多多边边形形，如如右右上上图图所所示示。算算法法的的输输出出也也是是一一个个顶顶点点序序列列，构构成成一一个个或或多多个个多多边边形形，如如右右上角图所示。上角图所示。算算法法的的每每一一步步，考考虑虑以以窗窗口口的的一一条条边边以以及及延延长长线线构构成成的的裁裁剪剪线线。该该线线把把平平面面分分成成两两部部分分: :一一部部分分包包含含窗窗口口，称称为为可可见见一一侧侧; ;另另一一
20、部部分分称称为为不不可可见见一一侧侧。依依序序考考虑虑多多边边形形各各条条边边的的两两端端点点S S、P P。它它们们与与裁裁剪剪线线的的位位置置关关系系只只有有四种。如右下图所示。四种。如右下图所示。2024/8/17多边形裁剪多边形裁剪每每条条线线段段端端点点S S、P P与与裁裁剪剪线线比比较较之之后后，可可输输出出0 0至至2 2个个顶顶点点。对对于于情情况况：( (I)I)两两端端点点S S、P P都都在在可可见见一一侧侧，则则输输出出P P；(II)(II)若若S S、P P都都在在不不可可见见一一侧侧，则则输输出出0 0个个顶顶点点；( (III)III)若若S S在在可可见见一
21、一侧侧，P P在在不不可可见见一一侧侧，则则输输出出线线段段SPSP与与裁裁剪剪线线的的交交点点I I；(IV)(IV)若若S S在在不不可可见见一一侧侧，P P在在可可见见一一侧侧，则则输输出出线线段段SPSP与裁剪线的交点与裁剪线的交点I I和线段终点和线段终点P P。如图所示。如图所示。( ( ( (I I I I) )( ( ( (I I)( ( ( (IIIIIIII) )( ( ( (IIII)( ( ( (IIIIIIIIIIII) )( (IIIIII)( ( ( (IVIVIVIV) )( ( ( (IVIV)2024/8/17多边形裁剪流程图多边形裁剪流程图该该算算法法仅仅用用一一条条裁裁剪剪边边对对多多边边形形进进行行裁裁剪剪，得得到到一一个个顶顶点点序序列列，作作为为下下一一条条裁裁剪剪边边处处理理过过程程的的输输入入。对对于于每每条条裁裁剪剪边边，算算法法框框图图一一样样，只只是是判判断断点点在在窗窗口口哪哪一一侧侧以以及及求求线线段段SPSP与与裁裁剪剪边边的的交交点点算算法应随之改变。法应随之改变。2024/8/172024/8/172024/8/17
