第6章裁剪.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,6.1,点的裁剪,6.2,直线段裁剪,6.3,多边形裁剪,第六章裁剪,裁剪,裁剪：,确定图形中哪些部分落在显示区之内，哪些落在显示区之外,以便只显示落在显示区内的那部分图形。这个选择过程称为,裁剪,。,在使用计算机处理图形信息时，计算机内部存储的图形往往比较大，而屏幕显示的只是图的一部分。,图形裁剪算法，直接影响图形系统的效率。,6.1,点的裁剪,图形裁剪中最基本的问题。,假设窗口的左下角坐标为,(,x,L,y,B,),右上角坐标为,(,x,R,y,T,),对于给定点,P(x,y,),则,P,点在窗口内的条件是要满足下列不等式：,x,L,=x=,x,R,并且,y,B,=y,t,l,则可见线段区间,t,l,t,u,t,0,t,1,t,2,t,3,0,1,梁友栋,-,Barsky,算法：,交点计算,梁友栋,-,Barsky,算法,始边和终边的确定及交点计算：,令,Q,L,=-x D,L,=x,0,-x,L,Q,R,=x D,R,=x,R,-x,0,Q,B,=-y D,B,=y,0,-y,B,Q,T,=y D,T,=y,T,-y,0,交点为,t,i,=D,i,/,Q,i,i=L,R,B,T,Q,i,0,t,i,为与终边交点参数,Q,i,=0 D,i,0,时,线段不可见,E,F,A,B,梁友栋,-,Barsky,算法,当,Q,i,=0,时,若,D,i,0,时,线段不可见,（如图中,AB,，有,Q,R,=0,，,D,R,0,时,（如图中的,EF,就是这种情况，它使,Q,L,=0,，,D,L,0,和,Q,R,=0,，,D,R,0,。这时由于,EF,和,x=,x,L,及,x=,x,R,平行，故不必去求出,EF,和,x=,x,L,及,x=,x,R,的交点，而让,EF,和,y=,y,T,及,y=,y,B,的交点决定直线段上的可见部分。）,E,F,A,B,void LB_LineClip(x0,y0,x1,y1,rect),float x0,y0,x1,y1;rectangle*,rect,;,float dx,dy,t0,t1;,t0=0;t1=1;,dx,=x1-x0;dy=y1-y0;,if(ClipT(-dx,x0-rect-xmin,&t0,&t1),if(ClipT(dx,rect,-xmax-x0,&t0,&t1),if(ClipT(-dy,y0-rect-ymin,&t0,&t1),if(ClipT(dy,rect,-ymax-y0,&t0,&t1),line(int(x0+t0*dx),int(y0+t0*,dy),(int,)(x0+t1*dx),(int)(y0+t1*,dy,),return;,bool,ClipT(q,d,t0,t1),float,q,d,*t0,*t1;,float r;,if(q,*t1),return FALSE;,else,if(r,*t0),*t0=r;,return TRUE;,else,if(q,0),r=,d/q,;,if(r,*t0),return FALSE;,else,if(r,*t1),*t1=r;,return TRUE;,else,if(d,0),return FALSE;,return TRUE;,6.1,点的裁剪,6.2,直线段裁剪,6.3,多边形裁剪,第五章裁剪,6.3,多边形裁剪,对于一个多边形，可将它分解为边界的线段逐段进行裁减？,新的问题,：,1,）边界不再封闭，需要用窗口边界的恰当部分来封闭它，如何确定其边界？,Sutherland-,Hodgman,算法,基本思想：,采用分割处理策略，将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪,流水线过程,(,左上右下,),：,前边的结果是后边的输入,亦称,逐边裁剪算法,Sutherland-,Hodgman,算法,算法的输入：以顶点序列表示的多边形。用,p1p2,pn,表示把,p1,连到,p2,，,p2,连到,p3,，,最后把,pn,连到,p1,所成的多边形,算法的输出：也是一个顶点序列，构成一个或多个多边形,算法的每一步，以窗口的一条边,以及延长线构成裁剪线，该线将平面分成两个部分,:,一部分包含窗口，称为可见一侧；另一部分为不可见一侧,Sutherland-,Hodgman,算法,依次考虑多边形各条边的两端点,S,、,P,。它们与裁剪线的位置关系只有四种,每条线段端点,s,、,p,经裁减后，可输出,0,至,2,个顶点,Sutherland-,Hodgman,算法,情况（,1,）仅输出顶点,P,；,情况（,2,）输出,0,个顶点；,情况（,3,）输出线段,SP,与裁剪线的交点,I,；,情况（,4,）输出线段,SP,与裁剪线的交点,I,和终点,P,Sutherland-,Hodgman,算法,算法一条裁减边对多边形进行裁减，得到一个顶点序列，作为下一条裁减边处理过程的输入,Sutherland-,Hodgman,算法,框图,处理线段,SP,过程子框图,Sutherland-,Hodgman,算法,上述算法仅用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下一条裁剪边处理过程的输入。,对于每一条裁剪边，算法框图同上，只是判断点在窗口哪一侧以及求线段,SP,与裁剪边的交点算法应随之改变。,Sutherland-Hodgeman,算法,对凸多边形应用本算法可以得到正确的结果，但是对凹多边形的裁剪将如图所示显示出一条多余的直线。这种情况在裁剪后的多边形有两个或者多个分离部分的时候出现。因为只有一个输出顶点表，所以表中最后一个顶点总是连着第一个顶点。,解决这个问题有多种方法，一是把凹多边形分割成若干个凸多边形，然后分别处理各个凸多边形。二是修改本算法，沿着任何一个裁剪窗口边检查顶点表，正确的连接顶点对。再有就是,Weiler,-Atherton,算法。,Sutherland-,Hodgman,算法,思考：,如何推广到任意凸多边形,裁剪窗口？,Weiler-Athenton,算法,裁剪窗口为任意多边形（,凸、凹、带内环）,的情况：,主多边形：被裁剪多边形，记为,A,裁剪多边形：裁剪窗口，记为,B,主多边形和裁剪多边形把二维平面分成两部分。,内裁剪,：,AB,外裁剪,：,A-B,Weiler-Athenton,算法,裁剪结果区域的边界由,A,的部分边界和,B,的部分边界两部分构成，并且在交点处边界发生交替，即由,A,的边界转至,B,的边界，或由,B,的边界转至,A,的边界,Weiler-Athenton,算法,如果主多边形与裁剪多边形有交点，则交点成对出现，它们被分为如下两类：,进点：主多边形的边由此进入裁剪多边形内,如，,I,1,I,3,I,5,I,7,I,9,I,11,出点：主多边形边界由,此离开裁剪多边形区域,如，,I,0,I,2,I,4,I,6,I,8,I,10,Weiler-Athenton,算法,在算法中，主多边形和裁减多边形都采用顶点表示来定义，它们的外部边界,顶点取逆时针方向，其内部边界顶点或孔取顺时针方向。这样可保证，多边形区域位于有向边的左侧。,Weiler-Athenton,算法,该算法中采用下列一些表：,主多边形的顶点表：用来定义主多边形,裁减多边形的顶点表：定义裁减多边形,进点表：包含主多边形进入裁减多边形内部时的交点,出点表：包含主多边形离开裁减多边形内部时的交点,Weiler-Athenton,算法,1,）建顶点表；,2,）求交点；,3,）裁剪,1,、建立主多边形和裁剪多边的顶点表,2,、求主多边形和裁剪多边形的交点，并将这些交点按顺序插入两多边形的顶点表中。在两多边形顶点表中的相同交点间建立双向指针。,3,、裁剪,:,如果存在没有被跟踪过的交点，执行以下步骤：,Weiler-Athenton,算法,Weiler-Athenton,算法,(1),建立空的裁剪结果多边形的顶点表,(2),选取任一没有被跟踪过的交点为始点，将其输出到结果多边形顶点表中,(3),如果该交点为进点，跟踪主多边形边边界；否则跟踪裁剪多边形边界,(4),跟踪多边形边界，每遇到多边形顶点，将其输出到结果多边形顶点表中，直至遇到新的交点,(5),将该交点输出到结果多边形顶点表中，并通过连接该交点的双向指针改变跟踪方向（如果上一步跟踪的是主多边形边界，现在改为跟踪裁剪多边形边界；如果上一步跟踪裁剪多边形边界，现在改为跟踪主多边形边界）,(6),重复,(4),、,(5),直至回到起点,取,I,7,为起点，所得裁剪结果多边形,I,7,I,0,q,0,I,3,I,4,I,5,I,6,I,7,。取,I,8,为起点，所得裁剪结果多边形为,I,8,I,9,I,10,I,11,I,2,q,2,I,1,I,8,。,Weiler-Athenton,算法,交点的奇异情况处理,1,、与裁剪多边形的边重合的主多边形的边不参与求交点；,2,、对于顶点落在裁剪多边形的边上的主多边形的边，如果落在该裁剪边的内侧，将该顶点算作交点；而如果这条边落在该裁剪边的外侧，将该顶点不看作交点,6.3,字符裁剪,1),基于字符串,2),基于字符,6.3,字符裁剪,基于构成字符的最小元素,点阵字符：点裁剪,矢量字符：线裁剪,