计算机图形学裁剪技术.ppt

裁剪算法 反走样方法 裁剪 直线段裁剪 点裁剪 点(x, y)在窗口内的充分必要条件是： 直线段裁剪 假定条件 矩形裁剪窗口：xmin,xmaxymin,ymax 待裁剪线段： 直线段裁剪 待裁剪线段和窗口的关系 （1）完全落在窗口内 （2）完全落在窗口外 （3）部分在内，部分在外 求交测试顺序固定(左右下上） 最坏情形，线段求交四次。 对于那些非完全可见、又非完全不可见的线段，需要求交， 求交前先测试与窗口哪条边所在直线有交？(按序判断端点编 码中各位的值ClCtCrCb） Cohen-Sutherland 算法 直线段裁剪 裁剪 直线段裁剪 Cohen-Sutherland算法 中点分割算法 参数化裁剪算法 Liang-Barskey算法 多边形裁剪 Sutlerland_Hodgman算法 Weiler-Athenton算法 字符裁剪 裁剪：确定图形中哪些部分落在显示区之内， 哪些落在显示区之外,以便只显示落在显示区 内的那部分图形。这个选择过程称为裁剪。在 进行裁剪时，画面中对应于屏幕显示的那部分 区域称为窗口。 图形裁剪算法，直接影响图形系统的效率。 裁剪 点的裁剪 图形裁剪中最基本的问题。 假设窗口的左下角坐标为 (xL,yB),右上角坐标为(xR,yT) ，对于给定点P(x,y),则P点在 窗口内的条件是要满足? (xL,yB ) (xR,yT ) 直线段裁剪 直线段裁剪算法是复杂图形裁剪的基础。复杂的 曲线可以通过折线段来近似，从而裁剪问题也可 以化为直线段的裁剪问题。 常用的线段裁剪方法三种： lCohen-Sutherland算法 l中点分割算法 l参数化裁剪算法 Cohen-Sutherland裁剪 基本思想： 对于每条线段P1P2分为三种情况处理: （1）若P1P2完全在窗口内，则显示该线段P1P2。 （2）若P1P2明显在窗口外，则丢弃该线段。 （3）若线段不满足（1）或（2）的条件，则在交点处把线段 分为两段。其中一段完全在窗口外，可弃之。然后对另一段 重复上述处理。 如何实现上述的处理呢？ 实现方法：采用下面的编码方法 将窗口边线两边沿长，得到九个区域，每一个区 域都用一个四位二进制数标识，直线的端点都按 其所处区域赋予相应的区域码，用来标识出端点 相对于裁剪矩形边界的位置。 1001 0001 0101 1000 0000 0100 1010 0010 0110 Cohen-Sutherland算法 将区域码的各位从右到左编号，则坐标区 域与各位的关系为： 任何位赋值为1，代表端点落在相应的位置上，否则该 位为0。若端点在剪取矩形内，区域码为0000。如果端 点落在矩形的左下角，则区域码为0101。 直线段裁剪 裁剪线段与窗口的关系：(1)线段完全可见；(2) 显然不可见；(3)其它 提高裁剪效率： 快速判断情形(1)(2)， 对于情形(3)，设法减 少求交次数和每次求 交时所需的计算量。 一旦给定所有的线段端点的区域 码，就可以快速判断哪条直线完 全在剪取窗口内，哪条直线完全 在窗口外。 Cohen-Sutherland算法 l若P1P2完全在窗口内code1=0,且code2=0,则“取” l若P1P2明显在窗口外code1 if(xXmax) c= c|RIGHT; if(yYmax) c= c| TOP; retrun c; Cohen-Sutherland裁剪 如何判定应该与窗口的哪条边求交呢？ 编码中对应位为1的边。 计算线段P1(x1,y1)P2(x2,y2)与窗口边界的交点 if(LEFT y=y1+(y2-y1)*(Xmin-x1)/(x2-x1); else if(RIGHT y=y1+(y2-y1)*(Xmin-x1)/(x2-x1); else if(BOTTOM x=x1+(x2-x1)*(Ymax-y1)/(y2-y1); else if(TOP x=x1+(x2-x1)*(Ymax-y1)/(y2-y1); void CS_LineClip(x1,y1,x2,y2,XL,XR,YB,YT) float x1,y1,x2,y2,XL,XR,YB,YT; /(x1,y1)(x2,y2)为线段的端点坐标，其他四个参数定义窗口的边界 int code1,code2,code; code1=encode(x1,y1);/对线段A端编码 code2=encode(x2,y2);/对线段B端编码 while(code1!=0 |code2!=0)/条件当有一个端点不是零时 if(code1/不在窗口内,退出 code = code1; if(code1=0) code = code2;/如此,定有code2不为零 if(LEFT y=y1+(y2-y1)*(Xmin-x1)/(x2-x1); else if(RIGHT y=y1+(y2-y1)*(Xmax-x1)/(x2-x1); else if(BOTTOM x=x1+(x2-x1)*(Ymin-y1)/(y2-y1); else if(TOP x=x1+(x2-x1)*(Ymax-y1)/(y2-y1); if(code =code1) x1=x;y1=y; code1 =encode(x,y); else x2=x;y2=y; code2 =encode(x,y); line（x1,y1,x2,y2);/画线 Cohen-Sutherland 直线裁剪算法小结 本算法的优点在于简单，易于实现。他可以简单的描 述为将直线在窗口左边的部分删去，按左，右，下， 上的顺序依次进行，处理之后，剩余部分就是可见的 了。在这个算法中求交点是很重要的，他决定了算法 的速度。 特点：用编码方法可快速判断线段的完全可见和显然 不可见。 中点分割法 基本思想： 从P0点出发找出距P0最近的可见点 从P1点出发找出距P1最近的可见点 不断地在中点处将线段一分为二，对每段线段重复Cohen- Sutherland裁剪算法的线段可见性测试方法，直至找到每段线段与窗 口边界线的交点或分割子段的长度充分小可视为一点为止 取中点Pm=(P1+P2)/2。 Pm P1 用P1Pm代替P1P2 P2 P2 用PmP2代替P1P2 Pm P1 直线段裁剪 （1）如果P1与P同侧，移动P1点；（即可能的 交点只能出现在PP2段） if(C1 （2）如果P1与P不同侧，移动P2点。（即可能 的交点只能出现在P1P段） if(C1 中点分割法 1、将直线的两端点P1、P2编码得：C1、C2； 2、判别 根据C1和C2的具体值，可以有三种情况： （1）C1C20，表明两端点全在窗口内，因而整个线段也在窗内 ，应予保留。 （2）C1 否则，移动P2点。 else P2=P; （6）流程转（3），直到P1和P2相差一个给定误差时：令交点为P2 ，取出暂存器的端点赋给P1，然后转向流程1。 中点分割法 Liang-Barsky裁剪算法 直线L与区域的交： 当Q为空集时，线段AB不可能在窗口中有可见线段。 当Q不为空集时，Q可看成是一个一维窗口 P4 P1 P3 P2 ymax ymin xminxmax R T S U L A B AS是一维窗口TS中的可见部分 直线段裁剪 基本思想： 把二维裁剪化为一维裁剪问题，并向x （或y）方向投影以决定可见线段。 Liang-Barsky裁剪算法 P4 P1 P3 P2 ymax ymin xminxmax R T S U L A B AS是一维窗口TS中的可见部分 直线段裁剪 存在可见线段的充要条件 不为空集 向x轴投影，就得到可见线段上点的坐标的变化范围为 左端点 右端点 Liang-Barsky裁剪算法 AB有可见部分的充分必要条件也可表示为 直线段裁剪 多边形裁剪-1/2 用直线段裁剪算法，可以吗？ 新的问题： 图1 因丢失顶点信息而无法确定裁剪区域 A B A B 图2 原来封闭的多边形变成了孤立的线段 边界不再封闭，需要用窗口边界的恰当部分来封闭它 1 2 1 2 3 (a)(b)(c) AB 图3 裁剪后的多边形顶点形成的几种情况 分裂为几个多边形 多边形裁剪-2/2 关键： 不仅在于求出新的顶点，删去界外顶点 还在于形成正确的顶点序列 Sutherland-Hodgman算法 分割处理策略： 将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所 在直线的裁剪。 流水线过程：左边的结果是右边的开始。 亦称逐边裁剪算法 Sutherland-Hodgman算法 裁剪结果的顶点构成： 裁剪边内侧的原顶点； 多边形的边与裁剪边的交点。 顺序连接。 优点： 裁剪算法采用流水线方式，适合硬件实现。 可推广到任意凸多边形裁剪窗口 基本思想是一次用窗口的一条边裁剪多边形。 考虑窗口的一条边以及延长线构成的裁剪线该线把平面 分成两个部分:可见一侧；不可见一侧 多边形的各条边的两端点S、P。它们与裁剪线的位置关 系只有四种 Sutherland-Hodgman算法 Sutherland-Hodgman算法 情况（1）仅输出顶点P； 情况（2）输出0个顶点； 情况（3）输出线段SP与裁剪线的交点I； 情况（4）输出线段SP与裁剪线的交点I和终点P Sutherland-Hodgman算法 线段与当前裁剪边的位置关系 可见一侧 (a) 输出I1和P2 当前裁剪边 S=P1 P=P2 P3 P4 I1 可见一侧 P1 S=P2 P=P3 P4 I1 (b) 输出P3 可见一侧 P1 P2 S=P3 P=P4 I2 可见一侧 P=P1 S=P2 P=P3 S=P4 (c) 输出I2 (d) 无输出 字符裁剪 前面我们介绍了字符和文本的输出。当字符和 文本部分在窗口内，部