《计算机图形学裁剪技术.ppt》由会员分享，可在线阅读，更多相关《计算机图形学裁剪技术.ppt（35页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、裁剪算法裁剪算法 反走样方法反走样方法裁剪裁剪直线段裁剪直线段裁剪点裁剪点裁剪 点点(x,y)在窗口内的充分必要条件是：在窗口内的充分必要条件是：直线段裁剪直线段裁剪假定条件矩形裁剪窗口：xmin,xmaxymin,ymax待裁剪线段：直线段裁剪直线段裁剪待裁剪线段和窗口的关系待裁剪线段和窗口的关系（1）完全落在窗口内）完全落在窗口内（2）完全落在窗口外）完全落在窗口外（3）部分在内，部分在外）部分在内，部分在外求交测试顺序固定求交测试顺序固定(左右下上）左右下上）最坏情形，线段求交四次。最坏情形，线段求交四次。对于那些非完全可见、又非完全不可见的线段，需要求交，对于那些非完全可见、又非完全不
2、可见的线段，需要求交，求交前先测试与窗口哪条边所在直线有交？求交前先测试与窗口哪条边所在直线有交？(按序判断端点编按序判断端点编码中各位的值码中各位的值ClCtCrCb）Cohen-Sutherland 算法算法直线段裁剪直线段裁剪裁剪直线段裁剪直线段裁剪Cohen-Sutherland算法中点分割算法参数化裁剪算法Liang-Barskey算法多边形裁剪多边形裁剪 Sutlerland_Hodgman算法 Weiler-Athenton算法 字符裁剪字符裁剪裁剪：确定图形中哪些部分落在显示区之内，哪些落在显示区之外,以便只显示落在显示区内的那部分图形。这个选择过程称为裁裁剪剪。在进行裁剪时，
3、画面中对应于屏幕显示的那部分区域称为窗口。图形裁剪算法，直接影响图形系统的效率。裁剪点的裁剪图形裁剪中最基本的问题。假设窗口的左下角坐标为(xL,yB),右上角坐标为(xR,yT)，对于给定点P(x,y),则P点在窗口内的条件是要满足?(xL,yB)(xR,yT)直线段裁剪直线段裁剪算法是复杂图形裁剪的基础。复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。常用的线段裁剪方法三种：lCohen-Sutherland算法l中点分割算法l参数化裁剪算法Cohen-Sutherland裁剪基本思想：对于每条线段P1P2分为三种情况处理:（1）若P1P2完全在窗口内，则显示该线段
4、P1P2。（2）若P1P2明显在窗口外，则丢弃该线段。（3）若线段不满足（1）或（2）的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。如何实现上述的处理呢？实现方法：采用下面的编码方法 将窗口边线两边沿长，得到九个区域，每一个区域都用一个四位二进制数标识，直线的端点都按其所处区域赋予相应的区域码，用来标识出端点相对于裁剪矩形边界的位置。100100010101100000000100101000100110Cohen-SutherlandCohen-Sutherland算法算法将区域码的各位从右到左编号，则坐标区域与各位的关系为：任何位赋值为1，代表端
5、点落在相应的位置上，否则该位为0。若端点在剪取矩形内，区域码为0000。如果端点落在矩形的左下角，则区域码为0101。直线段裁剪裁剪线段与窗口的关系：(1)线段完全可见；(2)显然不可见；(3)其它提高裁剪效率：快速判断情形(1)(2)，对于情形(3)，设法减少求交次数和每次求交时所需的计算量。一旦给定所有的线段端点的区域码，就可以快速判断哪条直线完全在剪取窗口内，哪条直线完全在窗口外。Cohen-SutherlandCohen-Sutherland算法算法l若P1P2完全在窗口内code1=0,且code2=0,则“取”l若P1P2明显在窗口外code1&code20，则“弃”l第三种情况：
6、在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。l 编码 线段裁剪Cohen-SutherlandCohen-Sutherland算法算法Cohen-SutherlandCohen-Sutherland裁减算法裁减算法裁减算法裁减算法如何编码呢如何编码呢如何编码呢如何编码呢?#defineLEFT1#defineRIGHT2#defineBOTTOM4#defineTOP8intencode(floatx,floaty)intc=0;if(xXmax)c=c|RIGHT;if(yYmax)c=c|TOP;retrunc;Cohen-Sutherland裁剪如何判
7、定应该与窗口的哪条边求交呢？如何判定应该与窗口的哪条边求交呢？编码中对应位为1的边。计算线段P1(x1,y1)P2(x2,y2)与窗口边界的交点if(LEFT&code!=0)x=Xmin;y=y1+(y2-y1)*(Xmin-x1)/(x2-x1);elseif(RIGHT&code!=0)x=Xmax;y=y1+(y2-y1)*(Xmin-x1)/(x2-x1);elseif(BOTTOM&code!=0)y=Ymin;x=x1+(x2-x1)*(Ymax-y1)/(y2-y1);elseif(TOP&code!=0)y=Ymax;x=x1+(x2-x1)*(Ymax-y1)/(y2-y1
8、);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);/对线段A端编码code2=encode(x2,y2);/对线段B端编码while(code1!=0|code2!=0)/条件当有一个端点不是零时if(code1&code2!=0)return;/不在窗口内,退出code=code1;if(code1=0)code=code2;/如此,定有code2不
9、为零if(LEFT&code!=0)x=Xmin;y=y1+(y2-y1)*(Xmin-x1)/(x2-x1);elseif(RIGHT&code!=0)x=Xmax;y=y1+(y2-y1)*(Xmax-x1)/(x2-x1);elseif(BOTTOM&code!=0)y=Ymin;x=x1+(x2-x1)*(Ymin-y1)/(y2-y1);elseif(TOP&code!=0)y=Ymax;x=x1+(x2-x1)*(Ymax-y1)/(y2-y1);if(code=code1)x1=x;y1=y;code1=encode(x,y);elsex2=x;y2=y;code2=encode
10、(x,y);line（x1,y1,x2,y2);/画线Cohen-Sutherland直线裁剪算法小结本算法的优点在于简单，易于实现。他可以简单的描述为将直线在窗口左边的部分删去，按左，右，下，上的顺序依次进行，处理之后，剩余部分就是可见的了。在这个算法中求交点是很重要的，他决定了算法的速度。特点：用编码方法可快速判断线段的完全可见和显然不可见。中点分割法基本思想：基本思想：从从P0点出发找出距点出发找出距P0最近的可见点最近的可见点从从P1点出发找出距点出发找出距P1最近的可见点最近的可见点不断地在中点处将线段一分为二，对每段线段重复不断地在中点处将线段一分为二，对每段线段重复Cohen-S
11、utherland裁剪算法的线段可见性测试方法，直至找到每段线段与窗裁剪算法的线段可见性测试方法，直至找到每段线段与窗口边界线的交点或分割子段的长度充分小可视为一点为止口边界线的交点或分割子段的长度充分小可视为一点为止取中点取中点Pm=(P1+P2)/2。PmP1用用P1Pm代替代替P1P2P2P2用用PmP2代替代替P1P2PmP1直线段裁剪直线段裁剪（1）如果）如果P1与与P同侧，移动同侧，移动P1点；（即可能的点；（即可能的交点只能出现在交点只能出现在PP2段）段）if(C1&C)!=0)P1=P;（2）如果）如果P1与与P不同侧，移动不同侧，移动P2点。（即可能点。（即可能的交点只能出
12、现在的交点只能出现在P1P段）段）if(C1&C)=0)P2=P;中点分割法1、将直线的两端点P1、P2编码得：C1、C2；2、判别 根据C1和C2的具体值，可以有三种情况：（1）C1C20，表明两端点全在窗口内，因而整个线段也在窗内，应予保留。（2）C1&C20，即C1和C2至少有某一位同时为1，表明两端点必定处于某一边界的同一外侧，因而整个线段全在窗外，应予舍弃。（3）不属于上面两种情况，均需要求交点。3、求交点（1）令窗外端点为P1，如果窗外点不是P1，则P1和P2交换端点；（2）保留窗内端点P2到暂存器里；（3）对P1编码为C1；（4）用中点公式求出中点，并编码得C；（5）按照中点算法
13、的求交规则：若P1和P同侧，移动P1点；if(C1&C)!=0)P1=P;否则，移动P2点。elseP2=P;（6）流程转（3），直到P1和P2相差一个给定误差时：令交点为P2，取出暂存器的端点赋给P1，然后转向流程1。中点分割法Liang-Barsky裁剪算法裁剪算法直线直线L与区域的交：与区域的交：当当Q为空集时，线段为空集时，线段AB不可能在窗口中有可见线段。不可能在窗口中有可见线段。当当Q不为空集时，不为空集时，Q可看成是一个一维窗口可看成是一个一维窗口 P4P1P3P2ymaxyminxminxmaxRTSULABAS是一维窗口是一维窗口TS中的可见部分中的可见部分直线段裁剪直线段裁
14、剪基本思想：基本思想：把二维裁剪化为一维裁剪问题，并向把二维裁剪化为一维裁剪问题，并向x（或（或y）方向投影以决定可见线段。）方向投影以决定可见线段。Liang-Barsky裁剪算法裁剪算法P4P1P3P2ymaxyminxminxmaxRTSULABAS是一维窗口是一维窗口TS中的可见部分中的可见部分直线段裁剪直线段裁剪存在可见线段的充要条件存在可见线段的充要条件 不为空集不为空集 向向x轴投影，就得到可见线段上点的坐标的变化范围为轴投影，就得到可见线段上点的坐标的变化范围为 左端点左端点右端点右端点Liang-Barsky裁剪算法裁剪算法AB有可见部分的充分必要条件也可表示为有可见部分的充
15、分必要条件也可表示为 直线段裁剪直线段裁剪多边形裁剪-1/2用直线段裁剪算法，可以吗？用直线段裁剪算法，可以吗？新的问题新的问题：图图1 因丢失顶点信息而无法确定裁剪区域因丢失顶点信息而无法确定裁剪区域ABAB图图2 原来封闭的多边形变成了孤立的线段原来封闭的多边形变成了孤立的线段边界不再封闭，需要用窗口边界的恰当部分来封闭它边界不再封闭，需要用窗口边界的恰当部分来封闭它12123(a)(b)(c)AB图图3 裁剪后的多边形顶点形成的几种情况裁剪后的多边形顶点形成的几种情况分裂为几个多边形分裂为几个多边形多边形裁剪-2/2关键：关键：不仅在于求出新的顶点，删去界外顶点不仅在于求出新的顶点，删去
16、界外顶点还在于形成正确的顶点序列还在于形成正确的顶点序列Sutherland-Hodgman算法分割处理策略分割处理策略：将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪。在直线的裁剪。流水线过程：流水线过程：左边的结果是右边的开始左边的结果是右边的开始。亦称逐边裁剪算法亦称逐边裁剪算法Sutherland-Hodgman算法裁剪结果的顶点构成裁剪结果的顶点构成：裁剪边内侧的原顶点；裁剪边内侧的原顶点；多边形的边与裁剪边的交点。多边形的边与裁剪边的交点。顺序连接。顺序连接。优点：优点：裁剪算法采用流水线方式，适合硬件实现。裁剪
17、算法采用流水线方式，适合硬件实现。可推广到任意凸多边形裁剪窗口可推广到任意凸多边形裁剪窗口基本思想是一次用窗口的一条边裁剪多边形。考虑窗口的一条边以及延长线构成的裁剪线该线把平面分成两个部分:可见一侧；不可见一侧多边形的各条边的两端点S、P。它们与裁剪线的位置关系只有四种Sutherland-Hodgman算法Sutherland-Hodgman算法情况（1）仅输出顶点P；情况（2）输出0个顶点；情况（3）输出线段SP与裁剪线的交点I；情况（4）输出线段SP与裁剪线的交点I和终点PSutherland-Hodgman算法线段与当前裁剪边的位置关系线段与当前裁剪边的位置关系可见一侧可见一侧(a)
18、输出输出I1和和P2当前裁剪边S=P1P=P2P3P4I1可见一侧可见一侧P1S=P2P=P3P4I1(b)输出输出P3可见一侧可见一侧P1P2S=P3P=P4I2可见一侧可见一侧P=P1S=P2P=P3S=P4(c)输出输出I2(d)无输出输出字符裁剪前面我们介绍了字符和文本的输出。当字符和文本部分在窗口内，部分在窗口外时，就提出了字符裁剪问题。字符串裁剪可按三个精度来进行：串精度、字符精度、以及笔画象素精度。采用串精度进行裁剪时，当字符串方框整个在窗口内时予以显示，否则不显示。采用字符精度进行裁剪时，某个字符方框整个落在窗口内予以显示，否则不显示。采用笔画象素精度进行裁剪时，将笔划分解成直线段对窗口作裁剪，处理方法同上。(a)待裁剪字符串(b)串精度裁剪(c)字符精度裁剪(d)象素精度裁剪 图：字符裁剪