lesson06-图形裁剪.ppt

1、2020/7/30,1,第四节 图形裁剪 1、点的裁剪 2、线段的裁剪 3、多边形的裁剪 4、文本的裁剪,2020/7/30,2,点的裁剪,点的裁剪,任何图形都可能包含点、直线、字符、和多边形乃至直线， 但它们都可以分解成点的集合。所以点的裁剪是图形裁剪中最基本的问题。 假设窗口的左下角坐标为(xmin,ymin),右上角坐标为(xmax,ymax)，对于给定点P(x,y),则P点在窗口内的条件是要满足下列不等式：xmin = x = xmaxand ymin = y = ymax否则，P点就在窗口外。,(xmin,ymin ),(xmax,ymax ),2020/7/30,3,线段的裁剪,线

2、段的裁剪,当窗口采用凸多边形时，任何一条线段只会至多有一段在窗口内： 当一条线段的两个端点全在窗口内时，该线段整个在窗口内 当一条线段的两个端点，一个在窗口内，一个在窗口外时，该线段部分在窗口内，部分在窗口外 当一条线段的两个端点全在窗口外时，该线段可能整个在窗口外，也可能部分在窗口内，部分在窗口外,整个线段全在窗口内；,整个线段全在窗口外；,线段部分在窗口外，部分在窗口内。,线段与窗口的关系通常有以下三种,2020/7/30,4,Cohen-Sutherland算法基本原理,线段的裁剪,这是一个最早最流行的线段裁剪算法。该算法通过初始测试来减少要计算的交点数目从而加快线段裁剪算法的速度。每条

3、线段的端点都赋以四位二进制码，称为区域码（region code）,用来标识出端点相对于裁剪矩形边界的位置。区域通过如下所示的边界设定。 区域码的各位指出端点对于裁剪矩形边界 的四个相对坐标位置： 左，右，下，上。将区域码的各位从右到左编号，则坐标区域与各位的关系为：上 下 右 左 X X X X任何位赋值为1，代表端点落在相应的位置上，否则该位为0。若端点在裁剪矩形内，区域码为0000。如果端点落在矩形的左下角，则区域码为0101。,2020/7/30,5,Cohen-Sutherland算法基本原理,直线的裁剪,如果两端点的编码均为0000，表示该线段在窗口内。 如果两端点的编码相与不为0

4、000，表示该线段在窗口外。 如果两端点的编码不全为0000，但相与为0000，则该线段不可见或部分可见，需计算线段与窗口的交点，确定哪一部分可见。,一旦给定所有的线段端点的区域码，就可以快速判断哪条线段完全在裁剪窗口内，哪条线段完全在窗口外。所以得到一下规则：,2020/7/30,6,线段的裁剪,Cohen-Sutherland算法描述,Cohen-Sutherland算法的关键在于总是先确定窗口外的一个端点，这样位于此端点至与窗口边的交点之间的线段必为不可见，故可将其抛弃。然后利用此法处理剩余的部分。Cohen-Sutherland算法描述如右：,BOOL done,draw;done表示

5、是否完成，draw表示是否可见；Unsigned char code1,code2；端点1，端口2的编码 While (!done) begin if (判断code1,code2,若为第一种情况) begin done = TRUE; draw = TRUE; end else if (为第二种情况) begin done = TRUE; draw = FALSE; end else if(检查code1 ,若在窗口内) begin 交换端点及端点的编码； 以左，右，下，上的次序对端点1进行判断及求交； 将交点的值赋给端点1； end end,2020/7/30,7,线段的裁剪,Cohen-

6、SutherlandC算法描述,#define LEFT 1 #define RIGHT 2 #define BOTTOM 4 #define TOP 8 int encode(float x,float y, float XL,float XR,float YB,float YT) int c=0; if(xXR) c|=RIGHT; if(yYT) c|=TOP; retrun c; void CS_LineClip(x1,y1,x2,y2,XL,XR,YB,YT) float x1,y1,x2,y2,XL,XR,YB,YT; /(x1,y1)(x2,y2)为线段的端点坐标，其他四个参数定

7、义窗口的边界 int code1,code2,code; code1=encode(x1,y1); code2=encode(x2,y2);,while(code1!=0 |code2!=0)/线不全在窗口内 if(code1 ,2020/7/30,8,Cohen-Sutherland线段裁剪算法小结,线段的裁剪,本算法的优点在于简单，易于实现。他可以简单的描述为将线段在窗口左边的部分删去，按左，右，下，上的顺序依次进行，处理之后，剩余部分就是可见的了。在这个算法中求交点是很重要的，他决定了算法的速度。中点求交法是对于硬件很适合的，它可以用左右移位来代替乘除法，这样就大大加快了速度。另外，本算

8、法对于其他形状的窗口是否同样有效就值得讨论了，这也证明了在图形算法中，没有几个是对大多数情况有效的。,算法动画演示,2020/7/30,9,中点裁剪算法,线段的裁剪,中点分割算法的大意是，与前一种Cohen-Sutherland算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况: 全在、完全不在和线段和窗口有交。对前两种情况，进行一样的处理。对于第三种情况，用中点分割的方法求出线段与窗口的交点。 先求出P0P1的中点Pm 若P0Pm不是显然不可见的，并且P0P1在窗口中有可见部分，则距P0最近的可见点一定落在P0Pm上，所以用P0Pm代替P0P1； 否则取PmP1代替P0P1。

9、再对新的P0P1求中点Pm。 重复上述过程，直到PmP1长度小于给定的控制 常数为止，此时Pm收敛于交点。 从P1出发找距离P1最近可见点采用上面类似方法,2020/7/30,10,中点裁剪算法,线段的裁剪,2020/7/30,11,Nicholl-Lee-Nicholl算法,P0的三种情况,2020/7/30,12,Nicholl-Lee-Nicholl算法,P0在窗口内。此时，如果P1也在窗口内，那么P0P1完全可见；否则，从P0向窗口的四个角点引射线，将窗口外部划分为T、B、R、L四个区域，P1位于哪一个区域中，就求P0P1与对应边界的交点，P0到交点之间部分为线段的可见部分。,2020

10、/7/30,13,Nicholl-Lee-Nicholl算法,P0在左边区。从P0向窗口的四个角点引射线，得到L、LR、LT、LB四个区域（如上图 所示），这四个区域确定了P0P1与窗口边界相交的情况。例如，如果P1在区域L中，我们就求P0P1与左边界的交点，交点到P1之间部分为线段的可见部分；如果P1在区域LB中，我们分别求P0P1与左边界以及P0P1与下边界的交点，两个交点之间部分为线段的可见部分；如果P1不在L、LR、LT、LB这四个区域中，那么P0P1完全不可见。,2020/7/30,14,Nicholl-Lee-Nicholl算法,P0在左上角区。从P0向窗口的四个角点引射线，得到如

11、上图 所示两种可能的区域划分。如果P1在L、T、LB、TB、TR、LR等区域中，可以求P0P1与对应边界的交点，得到线段的可见部分；如果P1不在上述区域中，那么P0P1完全不可见。,2020/7/30,15,设要裁剪的线段是P0P1。 P0P1和窗口边界交于A,B,C,D四点，见图。算法的基本思想是从A,B和P0三点中找出最靠近的P1点，图中要找的点是P0。从C,D和P1中找出最靠近P0的点。图中要找的点是C点。那么P0C就是P0P1线段上的可见部分。,梁友栋-Barsky算法,2020/7/30,16,梁友栋-Barsky算法,线段的参数表示 x=x0+tx y=y0+ty 0=t=1 x=

12、x1-x0 y=y1-y0 窗口边界的四条边分为两类：始边和终边。,2020/7/30,17,求出P0P1与两条始边的交点参数t0, t1 , 令tl=max(t0 ,t1,0)，则tl即为三者中离p1最近的 点的参数 求出p0p1与两条终边的交点参数t2, t3, 令tu=min(t2,t3,1) ，则tu即为三者中离p0最近的 点的参数 若tu tl,则可见线段区间 tl , tu,t0,t1,t2,t3,0,1,梁友栋-Barsky算法：交点计算,2020/7/30,18,梁友栋-Barsky算法,始边和终边的确定及交点计算： 令 QL= - x DL= x0-xL QR= x DR=

13、xR-x0 QB= - y DB= y0-yB QT= y DT= yT-y0 交点为 ti= Di / Qi i=L,R,B,T Qi 0 ti为与终边交点参数 Qi =0 Di 0 时, 分析另一D,E,F,A,B,2020/7/30,19,梁友栋-Barsky算法,当Qi =0时 若Di 0 时, 分析另一D, （如图中的EF就是这种情况，它使QL=0，DL0和QR=0，DR0。这时由于EF和x=xL及x=xR平行，故不必去求出EF和x=xL及x=xR的交点，而让EF和y=yT及y=yB的交点决定直线段上的可见部分。）,E,F,A,B,2020/7/30,20,Cyrus-Beck算法基

14、本原理,线段的裁剪,Cyrus-Beck算法的基本思想是采用法矢量的概念来判定线段上的一点是在窗口之内，之外，还是在窗口的边界上。点在凸多边形内的充要条件是，对于凸多边形其边界上任意一点a和该处内法向量ni, b为多边形边界上另外一点, ni与其他任一从a到b的矢量之间的夹角一定使：ni(ba)0 。,a,b,n0,ni,2020/7/30,21,线段的裁剪,Cyrus-Beck算法基本原理,如果f是凸区域边界上的一点，n是凸区域边界在f点的内法向量，则对于线段P1P2 上的一点P(t)，满足下式： 若nP(t)f0，则表示P(t)f指向区域的外侧; 若nP(t)f=0，则表示P(t)f与包含

15、f的边界重合且与法矢量n垂直； 若nP(t)f0，则表示P(t)f指向区域的内侧。 由此可知，P(t)满足nP(t)f=0的t值的点即为直线与边界（直线）的交点。,f,n,2020/7/30,22,线段的裁剪,Cyrus-Beck算法基本原理,Cyrus-Beck算法中对于线段的可见性是这样判断的，设：内法矢量与连接线段上一点至一边界上一点的矢量的点积为：ni P(t)-fi(i=1,2,3.)与式子P(t)=P1 +(P2P1)t(0t1) 合并得：niP1+(P2P1)t-fi(i=1,2,3.)线段上点在边界上的条件：niP1 +(P2P1)t-fi=0 (i=1,2,3.) 令：D=P

16、2P1；wi=P1fi，可得 wini t= - Dni 如果Dni=0，则要么D垂直于ni，要么P2=P1 点与区域和窗口的关系可描述如下： 如果wini0，表示点位于区域窗口之外； 如果wini0，表示点位于区域窗口边界上； 如果wini0，表示点位于区域窗口内侧。,2020/7/30,23,线段的剪取,Cyrus-Beck算法基本原理,对于t值的选择：首先，要符合0t1；其次，对于凸窗口来说，每一个线段与其至多有两个交点，即有两个相应的t值。所以我们可以把计算出的t值分成两组：一组为下限组，是分布在线段起点一侧的；一组为上限组，是分布在线段终点一侧的。这样，只要找出下限组中的最大值及上限

17、组中的最小值，就可确定线段了。 分组的依据是： 如果Dni0，则计算出的值属于上限组 如果Dni0，则计算出的值属于下限组 有了这些，整个算法就可以建立了。,2020/7/30,24,2020/7/30,25,线段的剪取,Cyrus-Beck直线剪取算法描述,置下限最小值tL=0,上限最大值tU=1 while 对于每一个窗口边i do begin if Dni=0 then If wini0 then /*寻找下限t值*/ If t1 then tL=max(t,tL) else /*寻找上限t值*/ if t0 then tU=min(t,tU) end if tL tU then 画从P

18、(tL)至P(tU)的线段 end of algorithm,2020/7/30,26,线段的剪取,Liang-Barssky算法描述,当凸多边形是矩型窗口，且矩形的边平行于坐标轴时，上述算法可简化，算法如下 void LB_LineClip(x1,y1,x2,y2,XL,XR,YB,YT) float x1,y1,x2,y2,XL,XR,YB,YT; float dx,dy,u1,u2; tl=0;tu=1; dx =x2-x1; dy =y2-y1; if(ClipT(-dx,x1-XL, ,bool ClipT(p,q,u1,u2) float p,q,*u1,*u2; float r;

19、 if(p*u2)return FALSE; else if(r*u1) *u1=r; return TRUE; else if(p0) r=p/q; if(r*u1) return FALSE; else if(r*u2) *u2=r; return TRUE; else if(q0) return FALSE; return TRUE; ,2020/7/30,27,Cyrus-Beck算法小结,该算法比Cohen-Sutherland算法适用的范围更广一些，它可以对任何凸多边形适用，但对于凹多边形就失效了,为了解决这个问题，我们又引入了下面的算法：叉积法，旋转法。,线段的剪取,2020/7

20、/30,28,多边形的裁剪,多边形的裁剪,多边形的裁剪可分解为一条一条线段进行。如考虑其封闭性，则一个窗口对一个多边形的裁剪可产生一个或者多个多边形。 下面将介绍Sutherland-Hodgman和Weiler-Atherton算法。,2020/7/30,29,通过对单一边或面的裁剪来实现多边形的裁剪。即在算法中，剪取窗口的每一边将逐次对原多边形和每次裁剪所生成的多边形进行裁剪。,Sutherland-Hodgeman多边形裁剪算法基本思想,多边形的裁剪,2020/7/30,30,多边形的裁剪,Sutherland-Hodgeman多边形裁剪算法基本思想,算法的每一次输出（包括中间结果）都是

21、一个多边形的顶点表， 且所有顶点均位于相应窗口裁剪边或面的可见一侧。由于多边形的每一条边需要与裁剪边或面分别进行比较，因此只需要讨论单条边和单个裁剪边或面之间可能的位置关系。假设S,P为多边形的两个相邻顶点，且S为该边的起点，P为该边的终点，则变SP与裁剪边或面之间只有4中可能的关系。,可见一侧,P,S,全部可见 输出点P,可见一侧,P,S,全部不可见无输出点,可见一侧,P,S,离开可见一 侧输出点1,1,可见一侧,P,S,进入可见一侧，输出点1和点P,1,2020/7/30,31,多边形的裁剪,Sutherland-Hodgeman多边形裁剪算法基本思想,由上可见，每一次将多边形的边与裁剪边

22、或面比较后，输出一个或两个顶点，也可能无输出点。如果SP边完全可见，则输出P点，不必输出起点S，因为顶点使按顺序处理的，S是作为前一边的终点输出的。如果SP边完全不可见，则无输出。如果SP边部分可见，则SP边可能进入或离开裁剪边或面的可见一侧。 如果SP边离开裁剪边或面的可见一侧，则输出SP与裁剪边或面焦点。如果SP边进入裁剪边或面的可见一侧，则输出两点，一个为SP与裁剪边或面的交点，一个是P点。 对于多边形的第一个顶点，只需判断其可见性。如果可见，则输出且作为起点S；否则无输出，但还是要作为S保存，以便后续点处理。 对于最后一条边PnP1，其处理方法是：标志第一顶点为F，这样最后一条边则为P

23、nF，可与其他边作相同的处理。,2020/7/30,32,Sutherland-Hodgeman多边形裁剪算法描述,while 对于每一个窗口边或面 do begin if P1在窗口边的可见一侧 then 输出P1 for I=1 到 n do begin if Pi在窗口边的可见一侧 then if Pi+1在窗口边的可见一侧 then 输出Pi+1 else 计算交点并输出交点 else if Pi+1在窗口边的可见一侧，then 计算交点并输出交点，同时输出Pi+1 endend end of algorithm,多边形的裁剪,2020/7/30,33,Sutherland-Hodge

24、man多边形裁剪算法小结,对凸多边形应用本算法可以得到正确的结果，但是对凹多边形的裁剪将如图所示显示出一条多余的直线。这种情况在裁剪后的多边形有两个或者多个分离部分的时候出现。因为只有一个输出顶点表，所以表中最后一个顶点总是连着第一个顶点。 解决这个问题有多种方法，一是把凹多边形分割成若干个凸多边形，然后分别处理各个凸多边形。二是修改本算法，沿着任何一个裁剪窗口边检查顶点表，正确的连接顶点对。再有就是Weiler-Atherton算法。,多边形的裁剪,2020/7/30,34,Weiler-Atherton多边形剪取 算法主要术语及数据结构,主多边形：用来被裁剪的多边形，可以是凸的、凹的、或是

25、有孔的； 裁剪多边形：用来裁剪主多边形的多边形，也可以是凸的、凹的、或是有孔的； 主多边形的顶点表：用来定义主多边形； 裁剪多边形的顶点表：用来定义裁剪多边形； 进点表：包含主多边形进入裁剪多边形内部时的交点； 出点表：包含主多边形离开裁剪多边形内部时的交点； 多边形的内表：位于裁剪多边形内部的主多边形的边界以及位于主多边形内的裁剪多边形的边界（其构成主多边形的孔）； 主多边形的外表：位于裁剪多边形外部的主多边形的边界以及位于主多边形内的裁剪多边形的边界，但不包括位于主多边形外的裁剪多边形的边界。,多边形的裁剪,2020/7/30,35,Weiler-Atherton多边形裁剪算法原理,首先从

26、进入交点(进点，即蓝色大箭处）开始，沿主多边形的外部边界(即按顺时针方向)跟踪，直至找到它与支持分号多边形的另一交点(出点)为止；在交点处向右转，再沿裁剪多边形的外部边界(按顺时针方向)跟踪，直至找到其与主多边形的一个交点(进点)后继续向右转，再次沿主多边形的边界跟踪；重复执行上述过程，直至再回到算法的起始交点(进点)为止。但遇到多边形的内部边界时，按逆时针方向跟踪。,多边形的裁剪,实线描绘的是主多边形，虚线描绘的是剪取多边形。红色箭头为入点，绿色头为出点。,2020/7/30,36,Weiler-Atherton多边形裁剪算法描述,多边形的裁剪,2020/7/30,37,多边形的裁剪,Wei

27、ler-Atherton多边形裁剪算法示例,C2,C3,C4,C1,S1,S7,S6,S5,S3,S2,I1,I2,I3,I4,I5,I6,I7,I8,主多边形表,内侧多边形,外侧多边形,S4,I1,I2,I3,I4,I5,I6,I7,I8,裁剪多边形表,主多边形表,裁剪多边形表,S1,I2,I3,S2,I4,S3,I5,S4,S5,S6,S7,I6,I7,I8,I1,S1,I2,I3,S2,I4,S3,I5,S4,S5,S6,S7,I6,I7,I8,I1,C1,C2,C3,I1,I2,I3,I4,I5,I6,I7,I8,C4,C1,C1,C2,C3,C4,C1,S1,S1,2020/7/30,38,Weiler-Atherton多边形裁剪算法示例,多边形的裁剪,C2,C3,C4,C1,S1,S7,S6,S3,S2,S4,I1,I2,I3,I4,S5,S8,S9,主多边形表,裁剪多边形表,主多边形表,裁剪多边形表,内侧多边形,外侧多边形,S1,I2,I3,S2,I4,S3,S4,S5,S6,S7,I1,C1,C2,C3,I1,I2,I3,I4,C4,C1,S8,S9,S1,S1,I2,I3,S2,I4,S3,S4,S5,S6,S7,I1,C1,C2,C3,I1,I2,I3,I4,C4,C1,S8,S9,S1,2020/7/30,39,Weiler-Atherton多