计算机图形学笔记（三）：裁剪

第三章裁剪

3.1 裁剪概述

裁剪
- 计算机内部存储的图形往往比较大，而屏幕显示的只是图形的一部分。
- 因此需要确定图形哪些部分落在显示区之内，哪些落在显示区之外。这个选择的过程就称为裁剪。
- 最简单的裁剪方法是把各种图形扫描转换为点之后，再判断点是否在窗口内。
点的裁剪
- 对于任意一点 $P(x,y)$，若满足 $x_{left}\leq x\leq x_{right}$ 且 $y_{bottom}\leq y\leq y_{top}$，则点 $P$ 在矩形窗口内，否则点 $P$ 在矩形窗口内。
- 缺点：太费时，不可取。
直线段的裁剪
- 直线段裁剪算法是复杂图形裁剪的基础。

3.2 Cohen-Sutherland 算法

算法概述
- 此算法又称为编码裁剪方法，算法的基本思想是对每条直线段分三种情况处理。
算法原理
- ① 点 $p_1$ 和 $p_2$ 完全在裁剪窗口内，”简取” 之。
- ② 若点 $p_1(x_1,y_1)$ 和 $p_2(x_2,y_2)$ 均在窗口外，且满足下列四个条件之一，”简弃” 之。
  - $x_1<x_{left}$ 且 $x_2<x_{left}$
  - $x_1>x_{right}$ 且 $x_2>x_{right}$
  - $y_1<y_{bottom}$ 且 $y_2<y_bottom$
  - $y_1>y_{top}$ 且 $y_2>y_{top}$
- ③ 其它情况需要对直线段按交点进行分段，分段后判断是 “简取” 还是 “简弃”。
  - 每条线段的端点都赋以四位二进制码 $D_3D_2D_1D_0$，编码规则如下
  - 若 $x<x_{left}$，则 $D_0=1$，否则 $D_0=0$
  - 若 $x>x_{right}$，则 $D_1=1$，否则 $D_1=0$
  - 若 $y<y_{bottom}$，则 $D_2=1$，否则 $D_2=0$
  - 若 $y>y_{top}$，则 $D_3=1$，否则 $D_3=0$
  - 裁剪一条线段时，先求出端点 $p_1$ 和 $p_2$ 的编码 $code_1$ 和 $code_2$ ，然后进行二进制 “或” 运算和 “与” 运算。若 $code_1|code_2=0$，简取之；若 $code_1$ & $code_2 \neq 0$，简弃之。
  - 若上述两条件均不成立，则需求出直线段与窗口边界的交点，并在交点处把线段一分为二。
  - 如下所示，先求出交点 $p_4$，舍弃 $p_1p_3$ 之后，再次求出交点 $p_4$，舍弃 $p_4p_2$，得到 $p_3p_4$。
总结
- Cohen-Sutherland 算法体现了编码思想，意义重大。
- 比较适合两种情况：大部分线段完全可见、大部分线段完全不可见。

3.2 中点分割算法

算法概述
- 首先将直线段的端点进行编码，将线段和窗口的关系分成三种情况：
  - 完全在窗口内
  - 完全在窗口外
  - 和窗口有交点
- 核心思想：通过二分逼近来确定直线段与窗口的交点。
- 注意
  - 若中点不在窗口内，则把中点和离窗口边界最远点构成的线段丢掉，以线段上的另一点和该中点再构成线段求其中点。
  - 如中点在窗口内，则又以中点和最远点构成线段，并求其中点，直到中点与窗口边界的坐标值在规定的误差范围内相等。

3.3 Liang-Barsky 算法

算法过程
- 用参数方程表示一条直线，$x=x_1+u*(x_2-x_1)=x_1+\Delta x*u$，$y=y_1+u*(y_2-y_1)=y_1+\Delta y*u$，$0\leq u\leq 1$。
- 把被裁剪的红色直线段看成是一条有方向的线段，把窗口的四条边分成两类：入边和出边
  - 裁剪结果的线段起点是直线和两条入边的交点以及始端点三个点里最前面的一个点，即参数 $u$ 最大的那个点。
  - 裁剪线段的终点是和两条出边的交点以及端点最后面的一个点，取参数 $u$ 最小的那个点。
  - 当 $u$ 从 $-inf$ ~ $inf$ 遍历直线时，首先对裁剪窗口的两条边界直线 (下边和左边) 从外面向里面移动，再对裁剪窗口两条边界直线 (上边和右边) 从里面向外面移动。
- 用 $u_1$ 和 $u_2$ 分别表示线段 $(u_1\leq u_2)$ 可见部分的开始和结束
  - $u_1=max(0,u_l,u_b)$，$u_2=min(1,u_t,u_r)$
具体步骤
- $p_1=-\Delta x$，$p_2=\Delta x$，$p_3=-\Delta y$，$p_4=\Delta y$
- $q_1=x_1-x_{left}$，$q_2=x_{right}-x_1$，$q_3=y_1-y_{bottom}$，$q_4=y_{top}-y_1$
- ① 输入直线段的两端点坐标 $(x_1,y_1)$、$(x_2,y_2)$ ，以及窗口的四条边界坐标：$wxl$、$wxr$、$wyb$、$wyt$ 。
- ② 若 $\Delta x=0$，则 $p_1=p_2=0$，此时进一步判断是否满足 $q_1<0$ 或 $q_2<0$，若满足，则该直线段不在窗口内，算法转 ⑦ 结束。否则，满足 $q_1\geq 0$ 且 $q_2\geq 0$ ，则进一步计算 $u_{max}$ 和 $u_{min}$ 。
  - $u_{max}=max(0,u_k|p_k<0)$，$u_{min}=min(1,u_k|p_k>0)$。
  - 其中 $u_k=\frac{q_k}{p_k}$，$(p_k \neq 0,k=3,4)$。算法转 ⑤。
- ③ 若 $\Delta y=0$，则 $p_3=p_4=0$，此时进一步判断是否满足 $q_3<0$ 或 $q_4<0$，若满足，则该直线段不在窗口内，算法转 ⑦ 结束。否则，满足 $q_3\geq 0$ 且 $q_4\geq 0$ ，则进一步计算 $u_{max}$ 和 $u_{min}$ 。
  - $u_{max}=max(0,u_k|p_k<0)$， $u_{min}=min(1, u_k|p_k>0)$ 。
  - 其中 $u_k=\frac{q_k}{p_k}$，$(p_k \neq 0,k=1,2)$。算法转 ⑤。
- ④ 若上述两条均不满足，则有 $p_k\neq0\ \ \ (k=1,2,3,4)$，此时计算 $u_{max}$ 和 $u_{min}$。
  - $u_{max}=max(0,u_k|p_k<0)$，$u_{min}=min(1, u_k|p_k>0)$ 。
  - 其中 $u_k=\frac{q_k}{p_k}$，$(p_k \neq 0,k=1,2,3,4)$。
- ⑤ 求得 $u_{max}$ 和 $u_{min}$ 后，进行判断：
  - 若 $u_{max}>u_{min}$，则直线段在窗口外，算法转 ⑦
  - 若 $u_{max}\leq u_{min}$，利用直线参数方程求出裁剪后的直线端点。
  - $x=x_1+u*(x_2-x_1)$，$y=y_1+u*(y_2-y_1)$
- ⑥ 绘制直线段。
- ⑦ 算法结束。
举例
- 直线 $AB$
- $p_1=0,q_1=10$ ; $p_2=0,q_2=-2$; $p_3=-4,q_3=4$; $p_4=4,q_4=2$
- $AB$ 完全在右边界之右
- 直线 $CD$
  - $p_1=0,q_1=2$ ; $p_2=0,q_2=6$; $p_3=-3,q_3=5$; $p_4=3,q_4=1$
  - $u_3=-\frac{5}{3},u_4=\frac{1}{3}$
  - $u_{max}=max(0,u_3)=0$，$u_{min}=min(1,u_4)=\frac{1}{3}$
  - 裁剪后两个端点为 $(3,7)$ 和 $(3,8)$
- 直线 $EF$
  - $p_1=-2,q_1=5$ ; $p_2=2,q_2=3$; $p_3=-3,q_3=4 $; $p_4=3,q_4=2$
  - $u_1=-\frac{5}{2},u_2=\frac{3}{2},u_3=-\frac{4}{3},u_4=\frac{2}{3}$
  - $u_{max}=max(0,u_1,u_3)=0$，$u_{min}=min(1,u_2,u_4)=\frac{2}{3}$
  - 裁剪后两个端点为 $(6,6)$ 和 $(7.33,8)$
总结
- 直线段看成是有方向的

直线参数化
- $x=x_1+\Delta x*u$，$y=y_1+\Delta y*u$，$0\leq u\leq 1$。
Liang-Barsky 裁剪算法和 Cohen-Sutherland 算法均只能应用于矩形窗口。

3.4 多边形、字符裁剪

3.4.1 多边形的裁剪

Sutherland-Hodgeman 多边形裁剪
- 基本思想
  - 将多边形边界作为一个整体，每次用窗口的一条边对要裁剪的多边形和中间结果多边形进行裁剪，体现一种分而治之的思想。
  - 包含有窗口区域的一个域称为可见侧，不包含窗口区域的域为不可见侧。
算法具体过程
- 第一点 $S$ 在不可见侧面，而第二点 $P$ 在可见侧。
  - 交点 $I$、$P$ 均被加入到输出顶点表中。
- 第一、二点 $S$ 和 $P$ 都在可见侧。
  - $P$ 被加入到输出顶点表中。
- $S$ 在可见侧，而 $P$ 在不可见侧。
  - 交点 $I$ 被加入到输出顶点表中。
- $S$ 和 $P$ 都在不可见侧。
  - 输出顶点表中不增加任何顶点。
- 在窗口在一条裁剪边界处理完所有顶点后，其输出顶点表将用窗口的下一条边界继续裁剪。
举例
缺点
- 可能会有多余线段产生。