光栅图形学算法的研究内容
- 直线段的扫描转换算法
- 多边形的扫描转换与区域填充算法
- 直线裁剪算法
- 反走样算法
- 消隐算法
一、裁剪简述
使用计算机处理图形信息时，计算机内部存储的图形往往比
较大,而屏幕显示的只是图形的一部分 。
因此需要确定图形哪些部分落在显示区之内，哪些落在显示
区之外。这个选择的过程就称为
裁剪
。
常见的裁剪方式有点的裁剪、以及直线段的裁剪。
1、点的裁剪
最简单的裁剪方法是把各种图形扫描转换为点之后，再判断
点是否在窗口内 。
对于任意一点P（x，y），
若满足下列两对不等式 ：
则点P在矩形窗口内；否则，点P在矩形窗口之外 。
判断图形中每个点是否在窗口内，太费时，一般不可取 。
2、直线段的裁剪
直线段裁剪算法复杂图形裁剪的基础 。
直线段和剪裁窗口的可能关系：
- 完全落在窗口内
- 完全落在窗口外
- 与窗口边界相交
要裁剪一条直线段，首先要判断：
（1） 它是否完全落在裁剪窗口内？
（2）它是否完全在窗口外？
（3） 如果不满足以上两个条
件，则计算它与一个或
多个裁剪边界的交点。
常用的裁剪算法有三种，即
Cohen-Sutherland、中点分割法
和 Liang-Barsky 裁剪算法 。
1） Cohen - Sutherland算法
此算法又称
编码裁剪算法，算法的基本思想是对每
条直线段分三种情况处理：
- 若点p1和p2完全在裁剪窗口内 。“简取”之
- 若点 p1(x1,y1)和p2(x2,y2)均在窗口外，且满足下列四个条件之一：
- 如果直线段既不满足“简取”的条件，也不满足“简弃”的条件？
需要对直线段按交点进
行分段，分段后判断直
线是“简取”还是“简
弃”。
每条线段的端点都赋以四
位二进制码D
3
D
2
D
1
D
0
，编
码规则如下：
- 若X<Xleft， 则 D0=1， 否则 D0=0
- 若X>Xright，则 D1=1， 否则 D1=0
- 若y<ybottom，则 D2=1， 否则 D2=0
- 若y>ytop， 则 D3=1， 否则 D3=0
窗口及其延长线所构
成了9个区域。根据该
编码规则：
- D0对应窗口左边界
- D1对应窗口右边界
- D2对应窗口下边界
- D3对应窗口上边界
裁剪一条线段时，先
求出端点p
1
和p
2
的编
码code
1
和code
2 ,
然后进行二进制“
或
”
运算和“
与
”运算 。
- 若code1|code2=0，对直线段应简取之
- 若code1&code2≠0，对直线段可简弃之
- 若上述两条件均不成立，则需求出直线段与窗口边界的交点在交点处把线段一分为二 。
小结： 该算法
用编码的方法实现了对直线段的裁剪 。
编码的思想
在图形学中甚至在计算机科学里也是非常重要 。
2）
中点分割算法
该算法与
Suthland算法一样，首先对直线段的端
点进行编码。
把线段和窗口的关系分成三种情况：
1、完全在窗口内
2、完全在窗口外
3、和窗口有交点
中点分割算法的
核心思想
是通过
二分逼近
来确定直线段与
窗口的交点 。
1、若中点不在窗口内，
则把中点和离窗口边界
最 远 点 构 成 的 线 段 丢
掉，以线段上的另一点
和该中点再构成线段求
其中点 。
2 、 如 中点 在窗口
内，则又以中点和
最远点构成线段，
并求其中点，直到
中点与窗口边界的
坐标值在规定的误
差范围内相等 。
问题：
中点分割算法会不会无限循环二分下去？
3）
Liang-Barsky算法
-
梁算法的主要思想：
- 用参数方程表示一条直线 。
- 把被裁剪的红色直线段看成是一条有方向的线段，把窗口的四条边分成两类： 入边 和 出边
- 裁剪结果的线段起点是直线和两条入边的交点以及始端点三个点里最前面的一个点，即参数u最大的那个点；
- 裁剪线段的终点是和两条出边的交点以及端点最后面的一个点，取参数u最小的那个点 。
- 值得注意的是，当u从 -∞ 到 +∞ 遍历直线时，首先对裁剪窗口的两条边界直线（下边和左边）从外面向里面移动，再对裁剪窗口两条边界直线（上边和右边）从里面向外面移动 。
- 如果用u1，u2分别表示线段（u1≤u2）可见部分的开始和结束。
这就是梁先生的重大发现！以及算法的重要思想 。
裁剪算法是非常底层的算法，任何一个图形显示的算法和
软件都离不开这些底层算法 。虽然
这些底层算法目前都已经固化到计算机硬件里了，但这些图形学算法思想以及
改进底层算法对提高图形显示和处理效率具有至
关重要的作用 。
还涉及到多边形的裁剪以及文字裁剪已在上一篇文章中提及了 。