CG10-裁剪技术.ppt

深圳大学计算机系 李坚强博士 二维裁剪定义 裁剪：识别图形在指定区域内、外部分的过程。 裁剪窗口：用来裁剪对象的区域。 对不同应用，裁剪窗口可是多边形或曲线边界。 裁剪的应用包括： 从定义的场景中抽取出用于观察的部分； 在三维视图中标识出可见面； 防止线段或对象的边界混淆； 用实体造型来创建对象； 显示多窗口的环境； 允许选择图形的一部分来进行拷贝、移动或删除等绘图操作。 二维裁剪时机选择 裁剪算法可用于世界坐标系中， 世界坐标系下的裁剪只有窗口内的部分映射到设备空间中，而将落在窗口外的图形部分删除。 裁剪算法也可将世界坐标系的图形首先映射到设备坐标系或规格化设备坐标系中，然后用视区边界裁剪。 视区裁剪可通过合并观察变换和几何变换矩阵来减少计算。 视区裁剪需要对所有对象(包括窗口之外的部分)变换到设备坐标系。 在光栅系统中，裁剪算法需与扫描转换结合。 二维裁剪：点的裁剪 设裁剪位置是一个在标准位置的矩形， 如果点P＝(x,y)满足下列不等式，则保存点P： xwmin≤x≤xwmax； ywmin≤y≤ywmax。 其中：(xwmin,xwmax,ywmin,ywmin)是世界坐标系的窗口边界或视区边界。 如果四个不等式中有任何一个不满足，则该点被裁剪掉(不被存储和显示)。 二维裁剪：线段裁剪 线段裁剪处理的基础有两个方面： 给定线段与裁剪窗口的相互位置关系测试，包括： 完全在裁剪窗口之内； 显然完全在窗口之外； 至少一个端点在窗口外，但并非显然在窗口外。 给定线段与一个或多个裁剪边界的交点计算。 问题：需要大量的计算 线段裁剪举例 线段P1P2 由下端点P1开始，依次按左、右、上、下边界对P1检查，发现端点位于裁剪窗口下。 找出线段P1P2与底边界的交点P1′，并舍弃P1到P1′之间的线段。 线段缩短到从P1′到P2之间。 P2在裁剪窗口之外，将P2用各个边界检查，发现P2位于窗口的左边，计算出交点P2′； 该点在窗口的上方，因此再做一次求交计算得到交点P2”，存储P1′到P2”的线段。该线段的裁剪就处理完毕了。 线段裁剪举例 线段P3P4 线段P3P4的端点P3在裁剪矩形的左边， 求出交点P3′； 并舍弃从P3到P3′的线段。 检查从P3′到P4线段的端点区域码，发现剩下的线段在裁剪窗口以下，也应该舍弃。 线段求交：截距方程 与裁剪边界的交点计算 （用斜率-截距式直线方程计算） 对于端点坐标为(x1,y1)和(x2,y2)的直线， 与垂直边界交点的y坐标可由下式计算得到： y=y1+m(x－x1)， 其中：x值置为xwmin或xwmax， 斜率：m=(y2-y1)/(x2-x1) 。 与水平边界交点的x坐标可由下式计算得到： x=x1+(y－y1)/m ， 其中：y值置为ywmin或ywmax， 斜率：m=(y2-y1)/(x2-x1) 。 线段求交：参数求交 端点是(x1,y1)和(x2,y2)其中之一或两个端点都在裁剪矩形外的线段，其参数表达式为： x = x1+u (x2-x1)； y = y1+u (y2-y1)。(0≤u≤1) 该线段与裁剪边界求交时，可得出参数u值。 如果与矩形边界交点的u值不在0和1之间，则该线段不在该边界处进入窗口内； 如果u值在0和1之间，线段穿过了裁剪区。 此方法可用于各个裁剪边界，以便确定该线段的显示部分。 平行于窗口边界的线段可作为特殊情况处理。 使用参数线段裁剪法需要大量计算。 线段裁剪：Cohen-Sutherland 算法 Cohen-Sutherland 算法是最早、最流行的线段裁剪算法，也称编码算法。 通过编码测试来减少要计算的交点数目。 区域通过如图所示边界设定。 每条线段的端点都赋以四位二进制码，称为区域码， 用来标识出端点相对于裁剪矩形边界的位置。 区域码的各位指出线段端点与裁剪窗口四个相对坐标位置的关系。 裁剪窗口的四个相对坐标位置：左、右、上、下； 区域码各位从右到左编号： 位1：左；位2：右；位3：下；位4：上。 任何位赋值为1代表端点落在相应位置上； 否则该位置为0。 Cohen-Sutherland 算法：区域码生成 区域码各位的值通过将端点坐标值(x,y)与裁剪边界比较来确定： 如果x＜xwmin，则第1位置1，否则置0； 其他三位依此类推。 对于可进行位操作的语言，区域码各位的值可按下列两步确定： 计算端点坐标和裁剪边界之间的差值； 用各差值符号来设置区域码各位的值： 第1位为x-xwmin的符号位； 第2位为xwm