计算机图形学二维图形裁剪课件.ppt

计算机图形学二维图形裁剪第1页，此课件共44页哦第2页，此课件共44页哦主要内容主要内容1.点的裁剪2.直线的裁剪3.多边形的裁剪4.字符的裁剪第3页，此课件共44页哦1.点的裁剪点的裁剪设窗口由x=xL,x=xR,y=yB,y=yT围成。对于点(x,y)判别两对不等式：xL=x=xR，yB=y=yT；若四个不等式均成立，则点在窗口之内；否则，点在窗口之外。最简单的裁剪方法是把各种图形扫描转换为点之后，再判断各点是否在窗内。但那样太费时，一般不可取。这是因为有些图形组成部分全部在窗口外，可以完全排除，不必进行扫描转换。所以一般采用先裁剪再扫描转换的方法。第4页，此课件共44页哦2.直线段裁剪直线段裁剪算法比较简单，但非常重要，是复杂图元裁剪的基础。因为复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。常用的线段裁剪方法有三种：Cohen-Sutherland，中点分割算法和参数化算法。第5页，此课件共44页哦Cohen-Sutherland裁剪算法该算法的思想是：对于每条线段P1P2分为三种情况处理。（1）若P1P2完全在窗口内，则显示该线段P1P2简称“取”之。（2）若P1P2明显在窗口外，则丢弃该线段，简称“弃”之。（3）若线段既不满足“取”的条件，也不满足“弃”的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。第6页，此课件共44页哦第7页，此课件共44页哦问题：如何判断线段与窗口的关系？问题：如何判断线段与窗口的关系？为使计算机能够快速判断一条直线段与窗口属何种关系，采用如下编码方法。延长窗口的边，将二维平面分成九个区域。每个区域赋予4位编码CtCbCrCl.其中各位编码的定义如下：第8页，此课件共44页哦第9页，此课件共44页哦裁剪一条线段时，先求出P1P2所在的区号code1,code2。若code1=0,且code2=0，则线段P1P2在窗口内，应取之。若按位与运算code1&code20，则说明两个端点同在窗口的上方、下方、左方或右方。可判断线段完全在窗口外，可弃之。否则，按第三种情况处理。求出线段与窗口某边的交点，在交点处把线段一分为二，其中必有一段在窗口外，可弃之。在对另一段重复上述处理。在实现本算法时，不必把线段与每条窗口边界依次求交，只要按顺序检测到端点的编码不为0，才把线段与对应的窗口边界求交。Cohen-Sutherland裁剪算法步骤：裁剪算法步骤：第10页，此课件共44页哦第11页，此课件共44页哦已知直线：（X1，Y1）（X2，Y2）与水平线YK的交点为：与垂直直线XR的交点为：第12页，此课件共44页哦在进行裁剪是除了要求直线与边界线的交点外，还要判断端点与窗口的位置关系。为此有：若编码&00010，端点与左边界有交点；若编码&00100，端点与右边界有交点；若编码&01000，端点与下边界有交点；若编码&10000，端点与上边界有交点；第13页，此课件共44页哦Cohen-Sutherland裁剪如何判定应该与窗口的哪条边求交呢？如何判定应该与窗口的哪条边求交呢？编码中对应位为1的边。计算线段P1(x1,y1)P2(x2,y2)与窗口边界的交点if(LEFT&code!=0)x=XL;y=y1+(y2-y1)*(XL-x1)/(x2-x1);else if(RIGHT&code!=0)x=XR;y=y1+(y2-y1)*(XR-x1)/(x2-x1);else if(BOTTOM&code!=0)y=YB;x=x1+(x2-x1)*(YB-y1)/(y2-y1);else if(TOP&code!=0)y=YT;x=x1+(x2-x1)*(YT-y1)/(y2-y1);第14页，此课件共44页哦算法伪代码#defineLEFT1#defineRIGHT2#defineBOTTOM4#defineTOP8intencode(floatx,floaty)intc=0;if(xXR)c|=RIGHT;if(xYB)c|=BOTTOM;if(xYT)c|=TOP;retrunc;第15页，此课件共44页哦voidCS_LineClip(x1,y1,x2,y2,XL,XR,YB,YT)floatx1,y1,x2,y2,XL,XR,YB,YT;/(x1,y1)(x2,y2)为线段端点坐标，其他参数定义窗口边界intcode1,code2,code;code1=encode(x1,y1);code2=encode(x2,y2);while(code1!=0|code2!=0)if(code1&code2!=0)return;code=code1;if(code1=0)code=code2;if(LEFT&code!=0)x=XL;y=y1+(y2-y1)*(XL-x1)/(x2-x1);第16页，此课件共44页哦elseif(RIGHT&code!=0)x=XR;y=y1+(y2-y1)*(XR-x1)/(x2-x1);elseif(BOTTOM&code!=0)y=YB;x=x1+(x2-x1)*(YB-y1)/(y2-y1);elseif(TOP&code!=0)y=YT;x=x1+(x2-x1)*(YT-y1)/(y2-y1);if(code=code1)x1=x;y1=y;code1=encode(x,y);elsex2=x;y2=y;code2=encode(x,y);displayline（x1,y1,x2,y2);第17页，此课件共44页哦第18页，此课件共44页哦Cohen-Sutherland直线裁剪算法小结本算法的优点在于简单，易于实现。他可以简单的描述为将直线在窗口左边的部分删去，按左，右，下，上的顺序依次进行，处理之后，剩余部分就是可见的了。在这个算法中求交点是很重要的，他决定了算法的速度。特点：用编码方法可快速判断线段的完全可见和显然不可见。第19页，此课件共44页哦中点分割裁剪算法中点分割裁剪算法基本思想：从P0点出发找出离P0最近的可见点，和从P1点出发找出离P1最近的可见点。这两个可见点的连线就是原线段的可见部分。与Cohen-Sutherland算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况，对前两种情况，进行一样的处理；对于第三种情况，用中点分割的方法求出线段与窗口的交点。A、B分别为距P0、P1最近的可见点，Pm为P0P1中点。第20页，此课件共44页哦中点分割算法-求线段与窗口的交点从P0出发找距离P0最近可见点采用中点分割方法先求出P0P1的中点Pm,若P0Pm不是显然不可见的，并且P0P1在窗口中有可见部分，则距P0最近的可见点一定落在P0Pm上，所以用P0Pm代替P0P1；否则取PmP1代替P0P1。再对新的P0P1求中点Pm。重复上述过程，直到PmP1长度小于给定的控制常数为止，此时Pm收敛于交点。从P1出发找距离P1最近可见点采用上面类似方法。第21页，此课件共44页哦对分辩率为2N*2N的显示器，上述二分过程至多进行N次。主要过程只用到加法和除法运算，适合硬件实现，它可以用左右移位来代替乘除法，这样就大大加快了速度。中点分割裁剪算法第22页，此课件共44页哦参数化算法(Cyrus-Beck)考虑凸多边形区域R和直线段P1P2P(t)=(P2-P1)*t+P1设A是区域R的边界上一点，N是区域边界在A点的内法线向量AP2RNP1第23页，此课件共44页哦参数化算法(Cyrus-Beck)则对于线段P1P2上任一点P(t)N(P(t)-A)外侧N(P(t)-A)0-内侧N(P(t)-A)=0-边界或其延长线上AP2RNP1第24页，此课件共44页哦参数化算法(Cyrus-Beck)凸多边形的性质：点P(t)在凸多边形内的充要条件是，对于凸多边形边界上任意一点A和该点处内法向N，都有N(P(t)-A)0第25页，此课件共44页哦参数化算法(Cyrus-Beck)k条边的多边形，可见线段参数区间的解:Ni(p(t)-Ai)=0,i=0,k,0t1.即：Ni(P1-Ai)+Ni(P2-P1)t=0(1)式可得：令ti=Ni(P1-Ai)/Ni(P2-P1)第26页，此课件共44页哦参数化算法(Cyrus-Beck)Ni(P2-P1)=0-平行于对应边。此时判断Ni(P1-Ai)若Ni(P1-Ai)P1P2在多边形外侧-不可见，若Ni(P1-Ai)0-P1P2在多边形内侧-继续其它边的判断第27页，此课件共44页哦参数化算法(Cyrus-Beck)对于t值的选择：首先，要符合0t1；其次，对于凸窗口来说，每一个线段与其至多有两个交点，即有两个相应的t值。所以我们可以把计算出的t值分成两组：一组为下限组，是分布在线段起点一侧的；一组为上限组，是分布在线段终点一侧的。这样，只要找出下限组中的最大值及上限组中的最小值，就可确定线段了。分组的依据是：如果Ni(P2-P1)0，则计算出的值属于上限组如果Ni(P2-P1)0，则计算出的值属于下限组第28页，此课件共44页哦下限上限P1P2参数化算法的几何意义下限组以Ni(P2-P1)0为特征，表示在该处沿P1P2方向前进将接近或进入多边形内侧。上限组以Ni(P2-P1)0tu=min1,minti:Ni(P2-P1)0若tl=tu,tl，tu是可见线段的交点参数区间，否则，线段不可见。第30页，此课件共44页哦参数化算法l当凸多边形是矩形窗口且矩形的边与坐标轴平行时，该算法退化为Liang-Barsky算法。第31页，此课件共44页哦Liang-BarskyLiang-Barsky算法所用的量算法所用的量第32页，此课件共44页哦voidLB_LineClip(p1,p2,tmin,tmax,visible)floatp12,p22,y2,XL,XR,YB,YT;floatdx,dy,u1,u2;tl=0;tu=1;dx=x2-x1;dy=y2-y1;if(ClipT(-dx,x1-Xl,&u1,&u2)if(ClipT(dx,XR-x1,&u1,&u2)if(ClipT(-dy,y1-YB,&u1,&u2)if(ClipT(dy,YT-y1,&u1,&u2)displayline(x1+u1*dx,y1+u1*dy,x1+u2*dx,y1+u2*dy)return;第33页，此课件共44页哦boolClipT(p,q,u1,u2)floatp,q,*u1,*u2;floatr;if(p*u2)returnFALSE;elseif(r*u1)*u1=r;returnTRUE;第34页，此课件共44页哦elseif(p0)r=p/q;if(r*u1)returnFALSE;elseif(r*u2)*u2=r;returnTRUE;elseif(q0)returnFALSE;returnTRUE;第35页，此课件共44页哦3.多边形裁剪多边形裁剪ABCDEF第36页，此课件共44页哦错觉错觉：多边形裁剪是直线段裁剪的组合？新的问题新的问题：1)边界不再封闭，需要用窗口边界的恰当部分来封闭它，如何确定其边界？第37页，此课件共44页哦2）一个凹多边形可能被裁剪成几个小的多边形，如何确定这些小多边形的边界？第38页，此课件共44页哦Sutherland-HodgmanSutherland-Hodgman算法算法分割处理策略分割处理策略：将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪。流水线过程流水线过程(左上右下左上右下)：前边的结果是后边的输入。亦称逐边裁剪算法亦称逐边裁剪算法第39页，此课件共44页哦基本思想是一次用窗口的一条边裁剪多边形。这里明确一点这里明确一点:多边形用顶点序列表示，被窗口的一条多边形用顶点序列表示，被窗口的一条边裁剪后，仍为多边形，仍用顶点序列表示，裁剪的结边裁剪后，仍为多边形，仍用顶点序列表示，裁剪的结果就是一系列的顶点。果就是一系列的顶点。考虑窗口的一条边以及延长线构成的裁剪线,该线把平面分成两个部分:可见一侧；不可见一侧;多边形的各条边的两端点S、P。它们与裁剪线的位置关系只有四种第40页，此课件共44页哦Sutherland-Hodgman算法情况（1）仅输出顶点P；情况（2）输出0个顶点；情况（3）输出线段SP与裁剪线的交点I；情况（4）输出线段SP与裁剪线的交点I和终点P第41页，此课件共44页哦逐次多边形裁剪算法框图上述算法仅用一条裁剪边对多边形进行裁剪，得到一个上述算法仅用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下一条裁剪边处理过程的输入。顶点序列，作为下一条裁剪边处理过程的输入。对于每一条裁剪边，算法框图同上，只是判断点在窗口哪一对于每一条裁剪边，算法框图同上，只是判断点在窗口哪一侧以及求线段侧以及求线段SPSP与裁剪边的交点算法应随之改变。与裁剪边的交点算法应随之改变。第42页，此课件共44页哦Sutherland-Hodgeman算法对凸多边形应用本算法可以得到正确的结果，但是对凹多边形的裁剪将如图所示显示出一条多余的直线。这种情况在裁剪后的多边形有两个或者多个分离部分的时候出现。因为只有一个输出顶点表，所以表中最后一个顶点总是连着第一个顶点。解决这个问题有多种方法，一是把凹多边形分割成若干个凸多边形，然后分别处理各个凸多边形。二是修改本算法，沿着任何一个裁剪窗口边检查顶点表，正确的连接顶点对。再有就是Weiler-Atherton算法。第43页，此课件共44页哦4字符裁剪字符裁剪前面我们介绍了字符和文本的输出。当字符和文本前面我们介绍了字符和文本的输出。当字符和文本部分在窗口内，部分在窗口外时，就提出了部分在窗口内，部分在窗口外时，就提出了字符裁剪字符裁剪问题问题。字符串裁剪可按三个精度来进行：字符串裁剪可按三个精度来进行：串精度串精度、字符精字符精度度、以及、以及笔画笔画象素精度象素精度。采用串精度进行裁剪时，将包围字串的外接矩形对窗采用串精度进行裁剪时，将包围字串的外接矩形对窗口作裁剪。当字符串方框整个在窗口内时予以显示，否口作裁剪。当字符串方框整个在窗口内时予以显示，否则不显示。采用字符精度进行裁剪时，将包围字的外接则不显示。采用字符精度进行裁剪时，将包围字的外接矩形对窗口作裁剪，某个字符方框整个落在窗口内予以矩形对窗口作裁剪，某个字符方框整个落在窗口内予以显示，否则不显示。采用笔画显示，否则不显示。采用笔画象素精度进行裁剪时，象素精度进行裁剪时，将笔划分解成直线段对窗口作裁剪，处理方法同上。将笔划分解成直线段对窗口作裁剪，处理方法同上。第44页，此课件共44页哦