裁剪算法

直线段裁剪算法

该算法是复杂图形裁剪的基础.
直线段与裁剪窗口可能的位置关系:

1. 完全落在窗口内: 保留直线段, 称为"简取".
2. 与窗口边界相交: 继续对直线段进行截取.
3. 完全落在窗口外: 丢弃直线段, 称为"简弃".

算法的设计将围绕这三种主要关系展开.

Cohen-Sutherland 算法

思想: 编码.

1. 将直线段的两个端点分别赋予一个 4 位二进制编码 ([D3, D2, D1, D0]) code1 和 code2, 表示其相对于窗口的位置.
   其中 D0 对应窗口左边界, D1 对应有边界, D2 对应下边界, D3 对应上边界. 若在对应窗口边界外则该位为 1, 否则为 0.
2. 若 code1 | code2 = 0, 则简取之: 两端点皆在窗口内, 全部保留.
   该位运算判断 code1 和 code2 之间是否有为 1 的位, 有则代表有至少一个端点在窗口边界外.
3. 若 code1 & code2 != 0, 则简弃之: 两端点皆在窗口外, 全部舍去.
   该位运算判断 code1 与 code2 是否有相同的位都为 1, 有则代表两个端点至少都位于窗口同一条边界外, 所以直线段完全落在窗口外. 但如果两个端点分别落在窗口两个边界之外且不与窗口相交的情况则没有被考虑到.
4. 否则, 直线段与窗口相交. 将直线段从交点处一分为二, 分别再带入该算法进行裁剪. 最终, 被分割为若干段的直线段都会分别满足简取或简弃的条件.

Question

能不能用交点代替端点.

中点分割法

思想: 编码, 二分逼近.
先对端点进行编码和分类, 与 Cohen-Sutherland 算法的 1-3 步骤相同. 然后将直线段通过中点一分为二.

Liang-Barsky 算法

背景: 该算法由梁友栋先生 (浙江大学) 和 Brian A. Barsky 博士 (加州伯克利分校) 提出.

评论