计算机图形与OpenGL学习六(二维观察4.Cohen-Sutherland线段裁剪算法)
Cohen-Sutherland线段裁剪算法
Cohen-Sutherland线段裁剪算法，通过初始测试来减少交点计算，从而减少线段裁剪算法所用的时间。每条线段的端点都赋以称为区域码的四位二进制码，每一位用来标识端点相对于相应裁剪矩形边界的里面还是外面。我们可以按任意顺序引用窗口边界，图1给出了一种编码顺序。
图1 区域码的各位与相应裁剪窗口边界的一种顺序
编码规则为：码位的值为1（真）表示端点在相应窗口边界的外面；码位的值为0（假）表示端点不在相应窗口边界的外面（在内部或在边界上）。在这种顺序下，四个窗口边界一起生成了九个区域，图2列出了这些区域的二进制码。
图2 标识线段端点相对于裁剪窗口位置的9个二进制区域码
区域码的位值通过将端点的坐标值(x,y)与裁剪窗口边界相比较而确定，如x<xwmin则位1为1，如y>ywmax，则位4为1，其他各位与此类似。除了使用不等式测试，我们还可以使用位处理操作和下列两步操作来高效地确定区域码的值：(1)计算端点坐标与裁剪边界的差。(2)用各差值计算的符号位来设置区域码中相应的值。按图1的顺序，位1设置x-xwmin的符号位；位2设置xwmax-x的符号位；位3设置y-ywmin的符号位; 位4设置ywmax-y的符号位。(计算机中的符号位,就是在处理二进制数据时,专门规定有一位,是用来确定数据的正负,符号位是1表示负数,是0表示正数)。
一旦给所有的线段端点建立了区域码，就可以快速判断哪条线段完全在裁剪窗口之内，哪条线段完全在窗口之外。完全在窗口边界内的线段，其两个端点的区域码均为0000，因此保留这些线段。有一对相同码位都为1的线段，则完全落在裁剪矩形之外，因此丢弃这些线段。
测试线段是否在内部或外部的方法是对两个端点的区域码进行逻辑操作。如果两个端点的区域码逻辑或运算结果为0000，则线段完全位于裁剪区域之内。如果两个端点的区域码逻辑与运算结果为真（不为0000），则线段完全位于裁剪区域之外。
对于不能判断为完全在窗口外或窗口内的线段，则要测试其与窗口边界的交点。如图3所示，这些线段可能穿过或不穿过窗口内部。因此可能要进行多次求交运算才能完成一条线段的裁剪。
我们以上图的EF线段进行一个模拟，假定窗口边界的处理顺序如下：左、右、下、上。E端点的区域码为1000,F端点的区域码为0110。详细处理过程如下：
1.检查左边界，两端点的左边界区域码都为0，说明都在左边界的内部，不与左边界相交。
2.检查右边界，E端点右边界区域码为0，说明E端点在右边界内部；F端点右边界区域码为1，说明F端点在右边界外部，线段在右边界相交，我们计算线段与右边界相交点（p1），并裁剪p1-F线段部分，如图4。
3.检查下边界，E端点下边界区域码为0，说明E端点在下边界内部；P1端点下边界区域码为1，说明P1端点在下边界外部，线段在下边界相交，我们计算线段与下边界相交点（P2），并裁剪p2-p1线段部分，如图5。
4. 检查上边界，E端点上边界区域码为1，说明E端点在上边界外部；P2端点上边界区域码为0，说明P2端点在上边界内部，线段在上边界相交，我们计算线段与下边界相交点（P3），并裁剪E-P3线段部分，如图6。
至此，线段裁剪完成。
上述手工模拟只是阐述了算法过程，但是还有一个问题是如何求取交点？
线段与裁剪边界的交点计算可以使用斜率截距式的直线方程。对于端点坐标为(x0,y0),(x_end,y_end)的线段，与垂直边界交点的y坐标可以由下列等式计算得到：
同样，要寻找水平边界相交的交点，其x坐标可以由下列等式计算得到：