图形学笔记（四）——二维观察与变换

二维几何变换

为方便计算，使用齐次坐标表示像素点，即 $p=[x,y,1]'$ 表示笛卡尔坐标 $(x,y)$ ，所有简单变换都可以表示为 $Mp$ ，其中M为变换矩阵。

平移变化： $\left\{\begin{array}{cc}x'=x+\Delta x\\y'=y+\Delta y \end{array} \right .$ ，矩阵形式为 $T=\left[\begin{array}{ccc}1 & 0 & t_x \\0 & 1 & t_y \\ 0 & 0 & 1\end{array} \right ]$
旋转变换：绕原点逆时针旋转 $\theta$ 度，则 $\left\{\begin{array}{cc}x'=xcos\theta - ysin\theta\\y'=xsin\theta+ycos\theta \end{array} \right .$ ，矩阵形式为 $R=\left[\begin{array}{ccc}cos\theta & -sin\theta & 0 \\sin\theta & cos\theta & 0 \\ 0 & 0 & 1\end{array} \right ]$
缩放变换：以原点为固定点缩放， $\left\{\begin{array}{cc}x'=s_xx\\y'=s_yy \end{array} \right .$ ，矩阵形式为 $S=\left[\begin{array}{ccc}s_x & 0 & 0 \\0 & s_y & 0 \\ 0 & 0 & 1\end{array} \right ]$
复合变换：只需利用矩阵的连乘即可实现复合运算，如先旋转后平移为 $T(Rp)=(TR)p$ ，新的变换矩阵为 $M=TR$ ，即按照从右到左的顺序书写即可。
其他变换：
- 镜像变换：坐标轴镜像只需改变系数正负即可， $M=\left[\begin{array}{ccc}-1 & 0 & 0 \\0 & 1 & 0 \\ 0 & 0 & 1\end{array} \right ]$ 为y轴镜像变化矩阵。绕指定直线镜像可由如下步骤获得：
  - 平移对称轴和图元，使得对称轴过原点
  - 旋转对称轴和图元使得对称轴和坐标轴重合
  - 沿坐标轴镜像变换
  - 执行上述过程的逆过程
- 错切变换：即从矩形到平行四边形的变化，变换矩阵为x(y)的线性函数

二维观察变换

二维观察是要指定图形中要显示的部分及在显示器的位置，即将窗口中的内容映射到视区中，一般窗口和视区都是矩形。

二维观察变换一般是简单变换的复合变换，即对窗口中的每个像素执行相同的变换。在实际实现时可以采用前向映射和后向映射的方法（和DIP算法中一致）。

二维图形裁剪

裁剪实际上是为了加速计算的，即只计算视区内部的图元部分。在以下讨论中， $p(x,y)$ 都表示完成窗口到视区映射后点 $p_0$ 的坐标。

点裁剪

由于点不具有除了位置以外的二维性质，因此只需判断是否在视区内部即可。

线段裁剪

在朴素的思想中，只需求得线段方程和视区四个边界的交点并判断位置关系即可，不过计算量较大。好的算法应该可以使用非常小的代价过滤不可能在视区内的直线，并利用硬件优化。

Cohen-Sutherland算法

Cohen-Sutherland算法为最早、最流行的线段裁剪算法，通过为区域编码减少运算次数。其基本思想由下图表示：

图形学笔记（四）——二维观察与变换

由于窗口有八个相邻区域，因此使用4位编码方式为线段的端点编码，从左至右分别表示：上边界，下边界，右边界，左边界（编码顺序可随意改变）。如上图中直线的两端点编码分别为 $c_1=0001$ 和 $c_2=1000$ 。对两端点的编码只需8个cpu周期即可完成

端点编码有如下性质：

线段在窗口内部 $\iff$ 两端点编码都为0000，即 $c_1|c_2=0000$
两端点都在同一区域中，或在同一侧的不同区域中，即 $c_1\&c_2\neq 0000\Rightarrow$ 线段在窗口外

上述过滤需要两个cpu周期

过滤后的线段和窗口一定有相交区域，之后通过计算交点即可完成裁剪。

梁友栋-Barsky参数裁剪算法

Liang-Barsky算法利用了直线的参数方程形式： $\left\{\begin{array}{cc}x=x_1+u\Delta x\\y=y_1+u\Delta y \end{array} \right .$ ，其中 $\Delta x=(x_2-x_1)，\Delta y=(y_2-y_1)$ ，点P在线段内部当且仅当 $0\leq u\leq 1$ 。

基本思想：

将裁剪窗口的四个边界双延长为直线，则不平行于窗口边界的直线和边界延长线有四个交点。

定义直线方向为线段方向 $P_1\rightarrow P_2$ ，四个边界可将二维空间分割成两个部分，定义包含裁剪窗口的一侧为内部，则直线相对于每个边界都是从外部延伸到内部的或从内部延伸到外部的。

如右图图形学笔记（四）——二维观察与变换此直线即为从左边界的外部延伸到内部的。

Liang-Brasky算法的思想即为线段参数设立初始值 $u_1=0$ 和 $u_2=1$ 表示线段在窗口内部的部分，之后计算线段所在直线和窗口边界的交点参数 $u_k$

如果为从外部延伸到内部，则更新 $u_1=max\{u_1,u_t\}$
如果为从外部延伸到内部，则更新 $u_2=min\{u_2,u_t\}$
如果 $u_1\geq u_2$ ，则该线段完全在窗口外部，终止算法
否则四轮计算后的 $u_1,u_2$ 内部区域即为裁剪后线段。

实现优化

如果点P（x，y）位于由坐标（xmin，ymin）和（xmax，ymax）所确定的窗口内，那么下式成立：
$x_{min}\leq x_1+u\Delta x\leq x_{max}$

$y_{min}\leq y_1+u\Delta y\leq y_{max}$

变形后可以统一表示为： $up_k \leq q_k$ ，其中 $p_k\ in\ \{-\Delta x,\Delta x,-\Delta y, \Delta y\};q_k\ in\ \{x_1-x_{min},x_{max}-x_1,y_1-y_{min},y_{max}-y_1\}$

若 $p_k=0\ and\ q_k<0$ ，则 $up_k=0<0$ 不成立，线段在窗口外。
$\Delta x>0\Rightarrow p_1<0,p_2>0$ ，因此直线从左边界外部延伸到内部，从右边界内部延伸到外部。
$\Delta y>0\Rightarrow p_3<0,p_4>0$ ，直线从上边界外部延伸到内部，从下边界内部延伸到外部。

Nicholl-Lee-Nicholl算法

Nicholl-Lee-Nicholl算法通过线段一个端点 $P_1$ 到裁剪窗口四个端点绘制四射线将二维平面重新划分为更多部分，然后通过 $P_1$ 在九宫格中的位置分情况讨论，根据 $P_2$ 在哪个区域中判断线段和裁剪窗口的交集和具有交点的边界。

多边形裁剪

多边形裁剪实际上即对多边形边界线段的裁剪。

Sutherland-Hodgman算法

SH算法通过对四个边界执行四次裁剪获得有序的裁剪后顶点集合，每次裁剪的输出作为下一次裁剪的输入。

每次裁剪中，按照顺时针（逆时针）方向遍历所有线段：

若起点和终点都在外部区域，则舍弃
若起点在外部区域，终点在内部区域，则将交点和终点按顺序加入顶点集
若两点都在内部区域，则将两点按顺序加入顶点集
若起点在内部区域，终点在外部区域，则将起点和交点按顺序加入顶点集

问题和优化：对于凹多边形的裁剪，可能会出现多余的线段，如右图：图形学笔记（四）——二维观察与变换。可以通过将凹多边形分割为多个凸多边形避免。

Weilerr-Atherton算法

在连接裁剪后的顶点时，对于多边形边界和窗口边界的交点，可以按照多边形边界继续连接或沿窗口边界连接。WA算法即定义了连接规则（假设顺时针遍历顶点）：

若交点处多边形边界为从外部进入内部，则按照多边形边界顺时针连接
若交点处多边形边界为从内部进入外部，则按照窗口边界顺时针连接

实现：

在实现时通过建立多边形顶点表和裁剪窗口顶点表优化算法，按顺序将交点加入两表中，当遇到边界后按照连接规则切换顶点表跟踪。如下图：

图形学笔记（四）——二维观察与变换

多边形定点表为： $v_1,v_1',v_2,v_3,v_3',v_4,v_4',v_5,v_5',v_6$

窗口边界定点表为： $p_1,p_2,p_3,p_4,v_5',v_4',v_3',v_1'$

从交点 $v_1'$ 开始跟踪，则跟踪过程为：

图形学笔记（四）——二维观察与变换