二维变换和裁剪.ppt

在二维观察中，需要在观察坐标系下根据窗口大小对用户坐标系中的二维图形进行裁剪（clipping），只将位于窗口内的图形变换到视区输出。直线段的裁剪是二维图形裁剪的基础，裁剪的实质是判断直线段是否与窗口相交，如相交则进一步确定位于窗口内的部分。 5.5.1 编码原理 Cohen-Sutherland直线裁剪算法是最早流行的编码算法。每条直线的端点都被赋予一组四位二进制代码，称为区域编码(Region Code，RC)，用来标识直线端点相对于窗口边界及其延长线的位置。假设窗口是标准矩形，由上（y=wyt）、下（y=wyb）、左（x=wxl）、右（x=wxr）四条边组成，如图5-23所示。延长窗口四条边形成9个区域，如图5-24所示。这样根据直线的任一端点P(x,y)所处的窗口区域位置，可以赋予一组4位二进制区域码RC＝C4C3C2C1。 5-23 窗口坐标 5-24 区域编码 为了保证窗口内直线端点的编码为零，编码规则定义如下： 第一位：若端点位于窗口之左侧，即xwxl ，则C1=1，否则C1=0。 第二位：若端点位于窗口之右侧，即xwxr，则C2=1，否则C2=0。 第三位：若端点位于窗口之下侧，即ywyb，则C3=1，否则C3=0。 第四位：若端点位于窗口之上侧，即ywyt，则C4=1，否则C4=0。 5.5.2 裁剪步骤 （1）若直线的两个端点的区域编码都为零，即RC1|RC2=0，说明直线两端点都在窗口内，应“简取”之。 （2）若直线的两个端点的区域编码都不为零，即RC1RC2≠0，即直线位于窗外的同一侧，说明直线的两个端点都在窗口外，应“简弃”之。 （3）若直线既不满足“简取”也不满足“简弃”的条件，直线必然与窗口或窗口边界的延长线相交，需要计算直线与窗口边界的交点。交点将直线分为两段，其中一段完全位于窗口外，可“简弃”之。对另一段重复进行上述处理，直至该直线段完全被舍弃或找到完全位于窗口内的直线段为止。 实现时，一般按固定顺序左（x=wxl），右（x=wxr）、下（y=wyb）、上（y=wyt）求解窗口与直线的交点。 P1 P2 5.5.3 交点计算公式 对于端点坐标为P1（x1，y1)和P2（x2，y2）的直线，与窗口左边界（x＝wxl）或右边界（x＝wxr）交点的y坐标的计算公式为： 其中 与窗口上边界（y＝wyt）或下边界（y＝wyb）交点的x坐标的计算公式为： 其中 （5-13） （5-14） 5.6中点分割直线段裁剪算法 5.6.1 中点分割算法原理 5.6.2 中点计算公式 5.6.1 中点分割算法原理 Cohen-Sutherland裁剪算法提出对直线段端点进行编码，并把直线段与窗口的关系划分为三种情况，对前两种情况进行了“简取”和“简弃”的简单处理。对于第三种情况，需要根据公式（5-13）和（5-14）计算直线段与窗口边界的交点。中点分割算法对第三种情况做了改进，不需要求解直线段与窗口边界的交点就可以对直线段进行裁剪。 中点分割直线段裁剪算法原理是简单地把直线段等分为两段直线，对每一段直线重复“简取”和“简弃”的处理，对于不能处理的直线段再继续等分为两段直线，直至每一段完全能够被“简取”或“简弃”，也就是说直至每段直线完全位于窗口之内或完全位于窗口之外，就完成了直线段的裁剪工作。直线段中点分割裁剪算法是采用二分算法的思想来逐次计算直线段的中点以逼近窗口边界。中点分割算法的计算过程只用到了加法和移位运算，易于使用硬件实现。 5.6.2 中点计算公式 对于端点坐标为P1（x1，y1)，P2（x2，y2）的直线段，中点坐标的计算公式为： ， （5-15） 5.7 梁友栋－Barsky直线段裁剪算法 5.7.1梁友栋算法原理 5.7.2 算法分析 5.7.3 算法的几何意义 5.7.1梁友栋算法原理 梁友栋和Barsky提出了比Cohen－Sutherland算法速度更快的直线段裁剪算法。该算法是以直线段的参数方程为基础设计的，把判断直线段与窗口边界求交的二维裁剪问题转化为求解一组不等式，确定直线段参数的一维裁剪问题。梁友栋－Barsky算法把直线段和窗口的相互位置关系划分为两种情况进行讨论：平行于窗口边界的直线段和不平行于窗口边界的直线段。 设直线段的参数方程为： 式中，0≤t≤1 （5-16） 对于坐标为（wxl，wyt）、（wxr，wyb）的裁剪窗口，直线段裁剪条件为： （5-17） 分解后有： （5-18） 令： 则（5-18）统一表示为： n代表直线段裁剪时，窗口的边界顺序，n＝1表示左边界；n＝2表示右边界；n＝3表示下边界；n＝4表示上边界。公式（5-19）给出了直线段