时间戳

首页 > 技术文章 > 线段裁剪算法

线段裁剪算法

iamfatotaku 2020-03-15 12:40 原文

裁剪：确定图形中哪些部分落在显示区之内，哪些落在显示区之外,以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪。

图形裁剪算法，直接影响图形系统的效率。

Cohen-SutherLand直线裁剪算法

1、基本思想

对于每条线段P1P2分为三种情况处理:

  1. 若P1P2完全在窗口内，则显示该线段P1P2。
  2. 若P1P2明显在窗口外，则丢弃该线段。
  3. 若线段不满足（1）或（2）的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。

2、编码方法

为了使计算机能够快速的判断一条线段与窗口属于何种关系，采用如下编码方法：把窗口的边界延长成直线，窗口平台就分成9个分区，每个区设定一个4位的编码与之对应。

平面上每一条直线的端点根据其所在的区域都可定义出两个编码。

img

编码（以二进制形式自右向左给出）的意义如下：

  1. 第0位：如果端点在窗口左边界左侧，则为1，否则为0；
  2. 第1位：如果端点在窗口右边界右侧，则为1，否则为0；
  3. 第2位：如果端点在窗口下边界下侧，则为1，否则为0；
  4. 第3位：如果端点在窗口上边界上侧，则为1，否则为0。

3、线段裁剪

img

裁剪一条线段时，先求出端点p1和p2的编码code1和code2：

  1. 如果code1和code2均为0，则说明P1和P2均在窗口内，那么线段全部位于窗口内部，应取之。（c）
  2. 如果code1和code2经过按位与运算后的结果code1&code2不等于0，说明P1和P2同时在窗口的上方、下方、左方或右方，那么线段全部位于窗口的外部，应弃之。（e，d）
  3. 如果上述两种条件均不成立，则可按如下方法处理：求出线段与窗口边界的交点，在交点处把线段一分为二，其中必有一段完全在窗口外，可以弃之。再对另一段重复进行上述处理，直到该线段完全被舍弃或者找到位于窗口内的一段线段为止。（a，b，d’）

4、检查顺序

编码中对应位为1的边。

// 与左边界相交
if (LEFT & code != 0) {
    // 横坐标是左边界的位置
	x = XL;
    // 计算出y的位置
	y = y1 + (y2 - y1) * (XL - x1) / (x2 - x1);
} else if (RIGHT & code != 0) {
	x = XR;
	y = y1 + (y2 - y1) * (XR - x1) / (x2 - x1);
} else if (BOTTOM & code != 0) {
	y = YB;
	x = x1 + (x2 - x1) * (YB - y1) / (y2 - y1);
} else if (TOP & code != 0) {
	y = YT;
	x = x1 + (x2 - x1) * (YT - y1) / (y2 - y1);
}

5、小结

  • 本算法的优点在于简单，易于实现。他可以简单的描述为将直线在窗口左边的部分删去，按左，右，下，上的顺序依次进行，处理之后，剩余部分就是可见的了。在这个算法中求交点是很重要的，他决定了算法的速度。另外，本算法对于其他形状的窗口未必同样有效。
  • 特点：用编码方法可快速判断线段的完全可见和显然不可见。

推荐阅读