计算机图形学

# 基本光栅图形的生成

# 直线的生成算法

画一条从 $(x_1, y_1)$ 到 $(x_2, y_2)$ 的直线。实质上是一个发现最佳逼近直线的像素序列，并填入色彩数据的过程。这一过程称为直线的光栅化。

# DDA 算法

DDA（Digital Differential Analyzer）算法是一种基本的直线生成算法。它的基本思想是：直线的起点坐标为 $P_1(x_1, y_1)$，终点坐标为 $P_2(x_2, y_2)$，$x$ 和 $y$ 的增量分别为 $\Delta x = x_2-x_1$ 和 $\Delta y= y_2-y_1$，则直线的斜率为 $m = \frac{\Delta y}{\Delta x}$。

1. 当 $\Delta x > \Delta y$ 时，以 $x$ 为基准，每次递增 $1$，即 $x_{k+1} = x_k + 1$，计算出 $y$ 的增量 $\Delta y = m$，则 $y_{k+1} = y_k + m$。
2. 当 $\Delta x \leq \Delta y$ 时，以 $y$ 为基准，每次递增 $1$，即 $y_{k+1} = y_k + 1$，计算出 $x$ 的增量 $\Delta x = \frac{1}{m}$，则 $x_{k+1} = x_k + \frac{1}{m}$。

void DDA(int x1, int y1, int x2, int y2) {

    int dx = x2 - x1, dy = y2 - y1;

    int steps = abs(dx) > abs(dy) ? abs(dx) : abs(dy);

    float xIncrement = dx / (float)steps;

    float yIncrement = dy / (float)steps;

    float x = x1, y = y1;

    for (int i = 0; i <= steps; i++) {

        putPixel(round(x), round(y));

        x += xIncrement;

        y += yIncrement;

    }

}

# Bresenham 算法

设直线从起点 $(x_1, y_1)$ 到终点 $(x_2, y_2)$，直线方程为 $y = mx + b$，其中 $m = \frac{\Delta y}{\Delta x} = \frac{y_2 - y_1}{x_2 - x_1}$，$b = y_1 - mx_1$。

# Bresenham 算法计算公式

$$\begin{align*} y &= m(x_i + 1) + b \quad & (1) \\ d_1 &= y - y_i \quad &(2) \\ d_2 &= y_{i+1} - y \quad &(3) \end{align*}$$

如果 $d_1 - d_2 > 0$，则 $y_{i+1} = y_{i+1}$，否则 $y_{i+1} = y_i$。

将式 (1)、(2)、(3) 代入 $d_1 - d_2$，再用 $\Delta x$ 乘等式两边，并以 $P_i = (d_1 - d_2) \Delta x$ 代入上述等式，得

$$P_i = 2x_i dy - 2y_i dx + 2dy + (2b - 1) dx \quad (4)$$

$d_1 - d_2$ 是用以判断符号的误差。由于在第一象限，$\Delta x$ 总大于 0，所以 $P_i$ 仍旧可以用作判断符号的误差。$P_{i+1}$ 为

$$P_{i+1} = P_i + 2dy - 2(y_{i+1} - y_i) dx \quad (5)$$

求误差的初值 $P_1$，可将 $x_1$、$y_1$ 和 $b$ 代入式 (2.4) 中的 $x_i$、$y_i$ 而得到

$$P_1 = 2dy - dx$$

# 第 1a 象限内的直线 Bresenham 算法思想：​

1. 画点 $(x_1, y_1)$，$dx = x_2 - x_1$，$dy = y_2 - y_1$，计算误差初值$P_1 = 2dy - dx, \quad i = 1;$

2. 求直线的下一点位置 $x_{i+1} = x_i + 1$，如果 $P_i > 0$，则 $y_{i+1} = y_i + 1$，否则 $y_{i+1} = y_i$；

3. 画点 $(x_{i+1}, y_{i+1})$；

4. 求下一个误差 $P_{i+1}$，如果 $P_i > 0$，则$P_{i+1} = P_i + 2dy - 2dx$，否则$P_{i+1} = P_i + 2dy$

5. $i = i + 1$；如果 $i < dx + 1$ 则转步骤 2；否则结束操作。

# Bresenham 算法的优点：​

1. 不必计算直线的斜率，因此不做除法。​
2. 不用浮点数，只用整数。​
3. 只做整数加减运算和乘 2 运算，而乘 2 运算可以用移位操作实现。​Bresenham 算法的运算速度很快，并适于用硬件实现。​

# 圆的生成算法

# 基础知识

给出圆心 $(x_c, y_c)$ 和半径 $r$，则圆上任意一点 $(x, y)$ 满足

$$(x - x_c)^2 + (y - y_c)^2 = r^2$$

由上式导出：

$$y = \pm \sqrt{r^2 - (x - x_c)^2} + y_c$$

也可以使用极坐标方程来表示圆：

$$x = x_c + r \cos \theta, \quad y = y_c + r \sin \theta$$

利用圆周坐标的对称性，此​算法还可以简化。将圆周分为 8​个象限，只要将第 1a 象限中的​圆周光栅点求出，其余 7​部分圆周就可以通过对称法则​计算出来。​

# 圆的 Bresenham 算法

设圆的半径为 $r$。考虑圆心在 $(0, 0)$，并从 $x=0$、$y=r$ 开始的顺时针方向的 $1/8$ 圆周的生成过程。在这种情况下，$x$ 每步增加 $1$，从 $x=0$ 开始，到 $x=y$ 结束。

即: $x_{i+1} = x_i + 1$

相应的 $y_{i+1}$ 则在两种可能中选择：

$$y_{i+1} = y_i \quad \text{or} \quad y_{i+1} = y_i - 1$$

# 圆的 Bresenham 计算公式

计算式为​

$$\begin{align*} y^2 &= r^2 - (x_{i+1})^2 \\ d_1 &= y_i^2 + (x_{i+1})^2 - r^2 \\ d_2 &= r^2 - ((x_{i+1})^2 + (y_i - 1)^2) \end{align*}$$

令 $p_i = d_1 - d_2$，并代入 $d_1$、$d_2$，则有​

$$p_i = 2(x_{i+1})^2 + y_i^2 + (y_i - 1)^2 - 2r^2 \quad (6)$$

$p_i$ 称为误差。如果 $p_i < 0$ 则 $y_{i+1} = y_i$，否则 $y_{i+1} = y_i - 1$。​

$p_i$ 的递归式为​

$$p_{i+1} = p_i + 4x_i + 6 + 2(y_i^2 + 1 - y_i^2) - 2(y_{i+1} - y_i) \quad (7)$$

$p_i$ 的初值由式 (6) 代入 $x_i = 0$，$y_i = r$ 而得​

$$p_1 = 3 - 2r \quad (8)$$

# Bresenham 圆周生成算法思想

1. 求误差初值，$p_1 = 3 - 2r$，$i = 1$，画点 $(0, r)$；

2. 求下一个光栅位置，其中 $x_{i+1} = x_i + 1$，如果 $p_i < 0$ 则 $y_{i+1} = y_i$，否则 $y_{i+1} = y_i - 1$；

3. 画点 $(x_{i+1}, y_{i+1})$；

4. 计算下一个误差，如果 $p_i < 0$ 则 $p_{i+1} = p_i + 4x_i + 6$，否则 $p_{i+1} = p_i + 4(x_i - y_i) + 10$；

5. $i = i + 1$，如果 $x = y$ 则结束，否则返回步骤 2。

void BresenhamCircle(int r, int xc, int yc) {

    int x = 0, y = r;

    int p = 3 - 2 * r;

    while (x < y) {

        plotCirclePoints(x, y, xc, yc);

        if (p < 0) {

            p += 4 * x + 6;

        } else {

            p += 4 * (x - y) + 10;

            y--;

        }

        x++;

    }

    if (x == y) {

        plotCirclePoints(x, y, xc, yc);

    }

}

void plotCirclePoints(int x, int y, int xc, int yc) {

    putPixel(xc + x, yc + y);

    putPixel(xc - x, yc + y);

    putPixel(xc + x, yc - y);

    putPixel(xc - x, yc - y);

    putPixel(xc + y, yc + x);

    putPixel(xc - y, yc + x);

    putPixel(xc + y, yc - x);

    putPixel(xc - y, yc - x);

}

# 圆的中点画圆法

定义圆函数

$$f(x, y) = x^2 + y^2 - r^2$$

$$\begin{cases} f(x, y) > 0, & \text{点在圆外} \\ f(x, y) = 0, & \text{点在圆上} \\ f(x, y) < 0, & \text{点在圆内} \end{cases}$$

# 圆的中点画圆法计算公式

$$p_k = f(x_{k+1}, y_k - \frac{1}{2}) = (x_{k+1})^2 + (y_k - \frac{1}{2})^2 - r^2$$

若 $p_k < 0$，则 $y_{k+1} = y_k$，否则 $y_{k+1} = y_k - 1$。

$$p_{k+1} = \begin{cases} p_k + 2(x_{k} + 1) + 1, & p_k < 0 \\ p_k + 2(x_{k} + 1) + 1 - 2(y_{k} - 1), & p_k \geq 0 \end{cases}$$

# 圆的中点画圆法思想

1. 输入圆半径 $r$；

2. 求误差初值，$p_0 = \frac{5}{4} - r$，画点 $(0, r)$；

3. 求下一个光栅位置，其中 $x_{i+1} = x_i + 1$，如果 $p_i < 0$ 则 $y_{i+1} = y_i$，否则 $y_{i+1} = y_i - 1$；

4. 画点 $(x_{i+1}, y_{i+1})$；

5. 计算下一个误差，如果 $p_i < 0$ 则 $p_{i+1} = p_i + 2x_{i+1} + 1$，否则 $p_{i+1} = p_i + 2(x_{i + 1} - y_{i + 1})+1$；

6. 确定其他七个八分圆中的对称点；

7. $i = i + 1$，如果 $x = y$ 则结束，否则返回步骤 3。

# 区域填充算法

# 区域填充基础知识

区域填充即给出一个区域的边界，要求对边界范围内的所有像素单元赋予指定的颜色代码。区域填充中最常用的是多边形填色。

• 计算机图形学中，多边形区域有两种重要的表示方法：顶点表示和点阵表示。​

• 所谓顶点表示，即是用多边形的顶点序列来表示多边形。这种表示直观、几何意义强、占内存少，易于进行几何变换，但由于它没有明确指出哪些像素在多边形内，故不能直接用于区域填充。​
  

• 所谓点阵表示，则是用位于多边形内的像素集合来刻画多边形。这种表示丢失了许多几何信息，但便于进行填充。​
  

根据区域的定义，可以采用不同的填充算法，其中最具代表性的是：适应于顶点表示的扫描线类算法和适应于点阵表示的种子填充类算法。 ​

# 扫描线填色算法

算法的基本思想:​

多边形以 n 、 x_array 、 y_array ​的形式给出，其中， x_array 、 y_array ​中存放着多边形的 n 个顶点的 x，y 坐标。​

​用水平扫描线从上到下扫描由点线段​构成的多段定义成的多边形。每根扫​描线与多边形各边产生一系列交点。​这些交点按照 x 坐标进行分类，将分​类后的交点成对取出，作为两个端点，​以所需要填的色彩画水平直线。多边​形被扫描完毕后，填色也就完成。​

对于一条扫描线，多边形的填充过程可以分为四个步骤：

1. 求交：计算扫描线与多边形各边的交点；
2. 排序：把所有交点按 x 值递增顺序排序；
3. 配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间；
4. 填色：把相交区间内的像素置成多边形颜色，把相交区间外的像素置成背景色。

# 需要解决或改进的几个问题

# 左、右顶点处理

当以 1，2，3 的次序画多边形外框时，多边形的左顶点和右顶点如右图中所示的顶点 2。它们具有以下性质：

• 左顶点 $2$：$y_1 < y_2 < y_3$
• 右顶点 $2$：$y_1 > y_2 > y_3$

其中 $y_1, y_2, y_3$ 是 3 个相邻的顶点的 $y$ 坐标。

当扫描线与多边形的每个顶点相交时，会同时产生 2 个交点。这时，填色就会因扫描交点的奇偶计数出错而出现错误。因此，对所有左、右顶点作如下处理：

$$\begin{align*} y_1 &= mx_1 + b \\ y_2 &= mx_2 + b \implies b = y_2 - mx_2 \\ y_2 - 1 &= mx + b \implies x = x_2 - \frac{1}{m} \\ m &= \frac{y_2 - y_1}{x_2 - x_1} \end{align*}$$

对于左顶点，入边端点 $(x_1, y_1)$、$(x_2, y_2)$ 修改为 $(x_1, y_1)$、$(x_2 - \frac{1}{m}, y_2 - 1)$；

对于右顶点，入边端点 $(x_1, y_1)$、$(x_2, y_2)$ 修改为 $(x_1, y_1)$、$(x_2 - \frac{1}{m}, y_2 + 1)$；

其中，$m = \frac{y_2 - y_1}{x_2 - x_1}$，即入边的斜率。

对于多边形的上顶点 $(y_2 > y_1, y_2 > y_3)$ 或下顶点 $(y_2 < y_1, y_2 < y_3)$，奇偶计数保持正确。

# 水平边处理

水平边 ($y1=y2$) 与水平扫描线重合无法求交点。因此，将​

水平边画出后删去，不参加求交点及求交点以后的操作。 ​

# 扫描线与边的求交点

采用递归算法，以$(x_1, y_1)$、$(x_2, y_2)$ 为端点的边与第$i+1$ 条扫描线的交点为​

$$\begin{cases} y_{i+1} = y_i - 1 \\ x_{i+1} = x_i + \frac{x_2 - x_1}{y_2 - y_1} \end{cases}$$

# 减少求交计算量

采用活性边表。
对于一根扫描线而言，与之相交的边只占多边形全部边的一部分，每根扫描线与多边形所有边求交的操作是一种浪费，需要加以改进。 ​

活性边表 (Active List of Side) 的采用将多边形的边分成两个子集：与当前扫描线相交的边的集合，以及与当前扫描线不相交的边的集合。对后者不必进行求交运算，这样就提高了算法的效率。​

为了方便活性边表的建立与更新，可为每一条扫描线建立一个新边表 (NET)，存放在该扫描线第一次出现的边。也就是说，若某边的较低端点为$y_{min}$，则该边就放在扫描线$y_{min}$ 的新边表中，下图是新边表的示意图。 ​

# 种子填充算法

种子填色又称边界填色 (Boundary Filling)。​它的功能是，给出多边形光栅化后的边界位置及​边界色代码 boundary_color ，以及多边形内的一​点 (x, y) 位置，要求将颜色 fill_color 填满多边形。​

# 区域连通性​

# 4 连通：​

从区域内任意一点出发，​可通过上、下、左、右​四个方向到达区域内的任意象素； ​

# 8 连通​

从区域内任意一点出发，​可通过上、下、左、右、左上、​左下、右上、右下八个方向​到达区域内的任意象素； ​

# 字符的生成

# 点阵式字符

点阵式字符将字符形状表示为一个矩形点阵，由点阵中点的不​同值表达字符的形状。​
使用点阵式字符时，需将字库中的矩形点阵复制到缓冲器中指​定的单元中去。在复制过程中，可以施加变换，以获得简单的变化。​

# 矢量式字符

矢量式字符将字符表达为点坐标的序列，相邻两点表示一条矢量，字符​的形状便由矢量序列刻画。

# 点阵字符与矢量字符的比较

1. 字符变换不同。对点阵字符的变换需要对每一个像素进行，变换、放大或旋转时会失真；表示矢量字符的是终点坐标，对矢量字符的变换是对端点的变换，属于几何变换，不会影响效果。​
2. 占用空间不同。矢量字符占用空间少，矢量字符只需保存一套字符，其他不同型号的字符可以通过相应的几何变换来产生。​
3. 矢量字符美观。除了直线段外，还可以用二次曲线段、三次曲线段等来表示，使字符更加美观，变换更方便。​

# 三角形的光栅化

# 选择三角形的原因

• 最基础的多边形，任意多边形都可以由三角形组成；
• 保证三点在一个平面上
• 便于判断内部
• 便于插值计算（baricentric interpolation）

# 三角形的采样

for (int x = 0; x < xmax; ++x)

  for (int y = 0; y < ymax; ++y)

    image[x][y] = inside(tri, x + 0.5, y + 0.5);

$$\text{inside}(tri, x, y) = \begin{cases} 1 & \text{if } x, y \text{ is inside the triangle} \\ 0 & \text{otherwise} \end{cases}$$

# 反走样（Antialiasing）

走样是由于图像的分辨率有限，导致图像中的曲线或者对比度较高的区域出现了锯齿状的现象。

# 先模糊再采样（Blurring Before Sampling）

# 傅立叶变换（Fourier Transform）

傅立叶变换是一种信号处理的方法，可以将信号分解为不同频率的正弦波。在图像处理中，可以将图像分解为不同频率的正弦波，然后对每个频率的正弦波进行模糊处理，最后再将这些正弦波合成为图像。

$$\begin{align*} F(\omega) &= \int_{-\infty}^{\infty} f(x) e^{-2\pi i \omega x} dx\\ F(u, v) &= \iint_{-\infty}^{\infty} f(x, y) e^{-2\pi i (ux + vy)} dx dy\\ e^{ix} &= \cos x + i \sin x \end{align*}$$

# 卷积（Convolution）

空间域中的卷积等于频域中的乘法，反之亦然

# 如何减少走样错误

• 增加采样率

  • 本质上是增加傅立叶域中副本之间的距离
  • 更高分辨率的显示器、传感器、帧缓冲区……
  • 但：成本高且可能需要非常高的分辨率

• 反走样

  • 在重复之前使傅立叶内容 “变窄”
  • 即在采样之前滤除高频

# 通过平均值减少走样

• 对 f (x,y) 进行 1 像素的方框模糊卷积
• 然后在每个像素的中心进行采样

# 多重采样抗锯齿（MSAA）

• 通过在每个像素中心周围的多个位置进行采样来减少走样
• 例如，4x MSAA 会在每个像素中心周围的 4 个位置进行采样
  
• 通过对这些采样进行平均值来减少走样

# 图形变换

# 图形的几何变换

# 二维图形的基本变换

# 基本变换

# 平移

$$\begin{align*} x' &= x + t_x \\ y' &= y + t_y \end{align*}$$

# 旋转

$$\begin{align*} x' &= x_r + (x - x_r) \cos \theta - (y - y_r) \sin \theta \\ y' &= y_r + (x - x_r) \sin \theta + (y - y_r) \cos \theta \end{align*}$$

# 缩放

$$\begin{align*} x' &= x \cdot S_x \\ y' &= y \cdot S_y \end{align*}$$

# 齐次坐标

齐次坐标表示法就是由 $n+1$ 维向量表示一个 $n$ 维向量。如 $n$ 维向量 $(P_1, P_2, \ldots, P_n)$ 表示为 $(hP_1, hP_2, \ldots, hP_n, h)$，其中 $h$ 称为哑坐标。

1. $h$ 可以取不同的值，所以同一点的齐次坐标不是唯一的。
2. 普通坐标与齐次坐标的关系为 “一对多”：

• 由普通坐标 $\times h \rightarrow$ 齐次坐标
• 由齐次坐标 $\div h \rightarrow$ 普通坐标

3. 当 $h=1$ 时产生的齐次坐标称为 “规格化坐标”，因为前 $n$ 个坐标就是普通坐标系下的 $n$ 维坐标。

$(x, y)$ 的齐次坐标为 $(x_h, y_h, h)$，其中 $x_h = x \cdot h, y_h = y \cdot h, h \neq 0$。
$(x, y)$ 对应的齐次坐标为三维空间中的一直线：

$$\begin{cases} x_h = hx \\ y_h = hy \\ z_h = h \end{cases}$$

# 变换矩阵

# 平移矩阵

平移矩阵运算表示为

$$\begin{bmatrix} x'&y'&1 \end{bmatrix}= \begin{bmatrix} x&y&1 \end{bmatrix} \begin{bmatrix} 1&0&0 \\ 0&1&0 \\ T_x&T_y&1 \end{bmatrix}$$

简记为 $\vec{p}' = \vec{p} \cdot T(T_x, T_y)$。其中，$\vec{p} = \begin{bmatrix} x&y&1 \end{bmatrix}$，$\vec{p}' = \begin{bmatrix} x'&y'&1 \end{bmatrix}$，$T(T_x, T_y)$ 为平移矩阵 $T(T_x, T_y) = \begin{bmatrix} 1&0&0 \\ 0&1&0 \\ T_x&T_y&1 \end{bmatrix}$。

# 旋转矩阵

旋转矩阵运算表示为

$$\begin{bmatrix} x'&y'&1 \end{bmatrix}= \begin{bmatrix} x&y&1 \end{bmatrix} \begin{bmatrix} \cos \theta&\sin \theta&0 \\ -\sin \theta&\cos \theta&0 \\ 0&0&1 \end{bmatrix}$$

简记为$\vec{p}' = \vec{p} \cdot R(\theta)$。其中，$R(\theta)$ 为旋转矩阵 $R(\theta) = \begin{bmatrix} \cos \theta&\sin \theta&0 \\ -\sin \theta&\cos \theta&0 \\ 0&0&1 \end{bmatrix}$。

# 缩放矩阵

缩放矩阵运算表示为

$$\begin{bmatrix} x'&y'&1 \end{bmatrix}= \begin{bmatrix} x&y&1 \end{bmatrix} \begin{bmatrix} S_x&0&0 \\ 0&S_y&0 \\ 0&0&1 \end{bmatrix}$$

简记为$\vec{p}' = \vec{p} \cdot S(S_x, S_y)$。其中，$S(S_x, S_y)$ 为缩放矩阵 $S(S_x, S_y) = \begin{bmatrix} S_x&0&0 \\ 0&S_y&0 \\ 0&0&1 \end{bmatrix}$。

# 错切矩阵

$$\begin{bmatrix} x'&y'&1 \end{bmatrix}= \begin{bmatrix} x&y&1 \end{bmatrix} \begin{bmatrix} 1&d&0 \\ b&1&0 \\ 0&0&1 \end{bmatrix}= \begin{bmatrix} x+by&y+dx&1 \end{bmatrix}$$

• 当 $d=0$ 时，$(x', y', 1) = (x + by, y, 1)$：图形的 $y$ 坐标不变；
  • 当 $b > 0$：图形沿 $+x$ 方向作错切位移。$ABCD \rightarrow A_1B_1C_1D_1$
  • 当 $b < 0$：图形沿 $-x$ 方向作错切位移。$ABCD \rightarrow A_2B_2C_2D_2$

• 当 $b=0$ 时，$(x', y', 1) = (x, y + dx, 1)$：图形的 $x$ 坐标不变；

  • 当 $d > 0$：图形沿 $+y$ 方向作错切位移。$ABCD \rightarrow A_1B_1C_1D_1$
  • 当 $d < 0$：图形沿 $-y$ 方向作错切位移。$ABCD \rightarrow A_2B_2C_2D_2$
    

• 当 $b \neq 0, d \neq 0$ 时，$(x', y', 1) = (x + by, y + dx, 1)$：图形同时在 $x$ 和 $y$ 方向作错切位移。

# 三维图形的基本变换

# 三维旋转矩阵

# 绕 $z$ 轴旋转

$$\begin{bmatrix} x' & y' & z' & 1 \end{bmatrix} = \begin{bmatrix} x & y & z & 1 \end{bmatrix} \begin{bmatrix} \cos \theta & \sin \theta & 0 & 0 \\ -\sin \theta & \cos \theta & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$$

# 绕 $x$ 轴旋转

$$\begin{bmatrix} x' & y' & z' & 1 \end{bmatrix} = \begin{bmatrix} x & y & z & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & \cos \theta & \sin \theta & 0 \\ 0 & -\sin \theta & \cos \theta & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$$

# 绕 $y$ 轴旋转

$$\begin{bmatrix} x' & y' & z' & 1 \end{bmatrix} = \begin{bmatrix} x & y & z & 1 \end{bmatrix} \begin{bmatrix} \cos \theta & 0 & -\sin \theta & 0 \\ 0 & 1 & 0 & 0 \\ \sin \theta & 0 & \cos \theta & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$$

# 绕任意轴旋转

$$R(\theta) = T(-x_1, -y_1, -z_1) \times R_x(\alpha) \times R_y(\beta) \times R_z(\theta) \times R_y(-\beta) \times R_x(-\alpha) \times T(x_1, y_1, z_1)$$

# 三维缩放矩阵

$$\begin{bmatrix} x' & y' & z' & 1 \end{bmatrix} = \begin{bmatrix} x & y & z & 1 \end{bmatrix} \begin{bmatrix} S_x & 0 & 0 & 0 \\ 0 & S_y & 0 & 0 \\ 0 & 0 & S_z & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$$

# 三维平移矩阵

$$\begin{bmatrix} x' & y' & z' & 1 \end{bmatrix} = \begin{bmatrix} x & y & z & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ T_x & T_y & T_z & 1 \end{bmatrix}$$

# 坐标系统

# 世界坐标系（World Coordinates）

为了描述被处理的对象，要在对象所在的空间中定义一个坐标系，这个坐标系的长度单位和坐标轴的方向要适合对被处理对象的描述，这个坐标系通常就称之为世界坐标系或用户坐标系。世界坐标系一般采用右手三维笛卡儿坐标系。

# 观察坐标系（View Coordinates）

产生三维物体的视图，必须规定观察点 (视点) 和观察方向。
好比照相时选择拍摄的位置和方向。

• 左手笛卡儿坐标系：观察坐标系的原点通常设置在观察点 (视点)，Z 轴作为观察方向。
• 右手笛卡儿坐标系：视点确定在 Z 轴上的某一个位置，Z 轴仍为观察方向。

# 设备坐标系 (Device Coordinates)

与图形设备相关连的坐标系叫设备坐标系。

• 显示器以分辨率确定坐标单位，原点在左下角或左上角；
• 绘图机绘图平面以绘图精度确定坐标单位，原点一般在左下角。

# 规格化设备坐标系 (Normal Device Coordinates)

为了使图形处理过程做到与设备无关，通常采用一种虚拟设备的方法来处理，也就是图形处理的结果是按照一种虚拟设备的坐标规定来输出的。这种设备坐标规定为$0≤X≤1$，$0≤Y≤1$，这种坐标系称之为规格化设备坐标系。

# 规格化变换

世界坐标系指定的显示范围叫窗口。规格化设备坐标系上与窗口对应的区域叫视区（视口）。

从窗口到视区的变换，称为规格化变换 (Normalization Transformation)。

$$\begin{bmatrix} vx&vy&1 \end{bmatrix}= \begin{bmatrix} wx&wy&1 \end{bmatrix} \times N$$

其中，$N$ 为规格化变换矩阵。

$$\begin{align*} N &= \begin{bmatrix} 1&0&0 \\ 0&1&0 \\ -wx_L&-wy_B&1 \end{bmatrix} \begin{bmatrix} S_x&0&0 \\ 0&S_y&0 \\ 0&0&1 \end{bmatrix} \begin{bmatrix} 1&0&0 \\ 0&1&0 \\ vx_L&vy_B&1 \end{bmatrix} \\ S_x &= \frac{vx_R - vx_L}{wx_R - wx_L} \\ S_y &= \frac{vy_T - vy_B}{wy_T - wy_B} \end{align*}$$

# 投影变换

投影 (project) 是一种使三维对象映射为二维对象的变换。它可描述为

$$\text{project}(\text{object}(x, y, z)) \rightarrow \text{object}(x', y')$$

投影的要素包括投影对象、投影面、投影线。

# 平行投影

# 正交平行投影（Orthographic Parallel Projection）

正投影的投影面与某一坐标轴垂直，而投影方向与该坐标轴的方向一致。正投影的图形，在长宽高三个方向上的比例与实物保持一致，因此，常用于工程制图。

# 斜交平行投影（Oblique Parallel Projection）

投影线与投影平面成$\alpha$ 交角

# 透视投影

• 投影中心与投影平面之间的距离为有限
• 参数：投影方向
• 灭点：不平行于投影平面的平行线，经过透视投影之后收敛于一点，称为灭点
• 主灭点：平行于坐标轴的平行线的灭点。
  • 一点透视
  • 两点透视
  • 三点透视
• 特点：产生近大远小的视觉效果，由它产生的图形深度感强，看起来更加真实。
• 投影中主灭点数目由与观察平面相交的主轴数目确定。

# 透视投影矩阵

$$\begin{align*} M_{\text{ortho}}&= \begin{bmatrix} \frac{2}{r-l}&0&0&0 \\ 0&\frac{2}{t-b}&0&0 \\ 0&0&\frac{2}{n-f}&0 \\ 0&0&0&1 \end{bmatrix} \begin{bmatrix} 1&0&0&0 \\ 0&1&0&0 \\ 0&0&1&0 \\ -\frac{r+l}{2}&-\frac{t+b}{2}&-\frac{n+f}{2}&1 \end{bmatrix}\\ M_{\text{ortho}\rightarrow\text{persp}}&= \begin{bmatrix} n&0&0&0 \\ 0&n&0&0 \\ 0&0&n+f&-nf \\ 0&0&1&0 \end{bmatrix}\\ M_{\text{persp}}&=M_{\text{ortho}} \times M_{\text{ortho}\rightarrow\text{persp}} \end{align*}$$

# 图形裁剪

# 直线的裁剪

直线和窗口的关系可以分为如下 3 类：

1. 整条直线在窗口内。此时，不需剪裁，显示整条直线。
2. 整条直线在窗口外。此时，不需剪裁，不显示整条直线。
3. 部分直线在窗口内，部分直线在窗口外。此时，需要求出直线与窗框的交点，并将窗口外的直线部分剪裁掉，显示窗口内的直线部分。

直线剪裁算法有两个主要步骤：

• 首先将不需剪裁的直线挑出，即删去在窗外的直线。
• 然后，对其余直线，逐条与窗框求交点，并将窗口外的部分删去。

# Cohen-Sutherland 算法

Cohen-Sutherland 算法是一种直线裁剪算法，它将平面分为 9 个区域，每个区域用 4 位二进制数表示，称为区域码。

• 内域：区域 (0000)。
• 上域：区域 (1001, 1000, 1010)。
• 下域：区域 (0101, 0100, 0110)。
• 左域：区域 (1001, 0001, 0101)。
• 右域：区域 (1010, 0010, 0110)。

当线段的两个端点的编码的逻辑 “与” 非零时 ，线段为不可见的。因此，对某线段的两个端点的区号进行位与运算，可知这两个端点是否同在视区的上、下、左、右.

算法的主要思想是，对每条直线 $P_1P_2$：

1. 对直线两端点 $P_1$、$P_2$ 编码分别记为 $C_1(P_1) = \{a_1, b_1, c_1, d_1\}$，$C_2(P_2) = \{a_2, b_2, c_2, d_2\}$，其中，$a_i$、$b_i$、$c_i$、$d_i$ 取值范围为 $\{1, 0\}$，$i \in \{1, 2\}$。

2. 如果 $a_i = b_i = c_i = d_i = 0$，则显示整条直线，取出下一条直线，返回步骤 (1)。否则，进入步骤 (3)。

3. 如果 $|a_1 - a_2| = 1$，则求直线与窗上边 $(y = y_{max})$ 的交点，并删去交点以上部分。如果 $|b_1 - b_2| = 1$，则求直线与窗下边 $(y = y_{min})$ 的交点，并删去交点以下部分。如果 $|c_1 - c_2| = 1$，则求直线与窗右边 $(x = x_{max})$ 的交点，并删去交点以右部分。如果 $|d_1 - d_2| = 1$，则求直线与窗左边 $(x = x_{min})$ 的交点，并删去交点以左部分。

4. 返回步骤 (1)。

与裁剪边界的交点计算可以使用斜率 — 截距式的直线方程。

对于端点坐标为 $(x_1, y_1)$ 和 $(x_2, y_2)$ 的直线，与垂直边界交点的 $y$ 坐标可以由下列等式计算得到：

$$y = y_1 + m(x - x_1), \quad m = \frac{y_2 - y_1}{x_2 - x_1}$$

其中，$x$ 的值为 $x_{min}$ 或 $x_{max}$。

与水平边界交点的 $x$ 坐标可以由下列等式计算得到：

$$x = x_1 + \frac{y - y_1}{m}, \quad m = \frac{y_2 - y_1}{x_2 - x_1}$$

其中，$y$ 的值为 $y_{min}$ 或 $y_{max}$。

# Liang-Barsky 算法

对直线的参数化方程$\begin{cases}x = x_1 + u\Delta x\\y = y_1 + u\Delta y\end{cases}$，其中，$0 \leq u \leq 1$。

首先按参数化形式写出裁剪条件：

$$\begin{align*} x_{min} &\leq x_1 + u\Delta x \leq x_{max} \\ y_{min} &\leq y_1 + u\Delta y \leq y_{max} \end{align*}$$

整理得到：$u p_k \leq q_k$，其中，$k = 1, 2, 3, 4$。其中

$$\begin{align*} p_1 &= -\Delta x, &q_1 &= x_1 - x_{min} \\ p_2 &= \Delta x, &q_2 &= x_{max} - x_1 \\ p_3 &= -\Delta y, &q_3 &= y_1 - y_{min} \\ p_4 &= \Delta y, &q_4 &= y_{max} - y_1 \end{align*}$$

算法的基本思想是从 $A, B$ 和 $P_0$ 三点中找出最靠近 $P_1$ 的点，图中要找的点是 $P_0$。从 $C, D$ 和 $P_1$ 中找出最靠近 $P_0$ 的点，图中要找的点是 $C$ 点。那么 $P_0C$ 就是 $P_0P_1$ 线段上的可见部分。

• 任何平行于裁剪边界之一的直线 $p_k = 0$，其中 $k$ 对应于裁剪边界（$k = 1, 2, 3, 4$ 对应于左、右、下、上边界），
  • 如果 $q_k < 0$，则线段完全在边界外，舍弃该线段。
  • 如果 $q_k \geq 0$，则该线段平行于裁剪边界并且在窗口内。
• 当 $p_k < 0$，线段从裁剪边界延长线的外部延伸到内部。
• 当 $p_k > 0$ 时，线段从裁剪边界延长线的内部延伸到外部。
• 当 $p_k \neq 0$ 时，可以计算出线段与边界 $k$ 的延长线的交点的 $u$ 值：$u = \frac{q_k}{p_k}$。