计算机图形学

基本光栅图形的生成

直线的生成算法

画一条从 $(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}$ 。

当 $\Delta x > \Delta y$ 时，以 $x$ 为基准，每次递增 $1$ ，即 $x_{k+1} = x_k + 1$ ，计算出 $y$ 的增量 $\Delta y = m$ ，则 $y_{k+1} = y_k + m$ 。
当 $\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}$ 。

当 $|\Delta x| > |\Delta y|$ 时， $x$ 的增量为 $1$ ， $y$ 的增量为 $m$ ；
当 $|\Delta x| \leq |\Delta y|$ 时， $x$ 的增量为 $\frac{1}{m}$ ， $y$ 的增量为 $1$ 。
增量的符号由 $\Delta x$ 和 $\Delta y$ 的符号决定。

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算法思想：

画点 $(x_1, y_1)$ ， $dx = x_2 - x_1$ ， $dy = y_2 - y_1$ ，计算误差初值 $P_1 = 2dy - dx, \quad i = 1;$
求直线的下一点位置 $x_{i+1} = x_i + 1$ ，如果 $P_i > 0$ ，则 $y_{i+1} = y_i + 1$ ，否则 $y_{i+1} = y_i$ ；
画点 $(x_{i+1}, y_{i+1})$ ；
求下一个误差 $P_{i+1}$ ，如果 $P_i > 0$ ，则 $P_{i+1} = P_i + 2dy - 2dx$ ，否则 $P_{i+1} = P_i + 2dy$
$i = i + 1$ ；如果 $i < dx + 1$ 则转步骤 2；否则结束操作。

Bresenham算法的优点：

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

注意：以上讨论的是 $0 < \Delta y < \Delta x$ 的情况，对于适用所有 8 个方向的直线的生成算法，则要考虑以判断条件 $|dx| > |dy|$ 为分支，并分别将 2a、3a 象限的直线和 3b、4b 象限的直线变换到 1a、4a 和 2b、1b 象限方向去，以实现程序处理的简洁。

圆的生成算法

基础知识

给出圆心 $(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圆周生成算法思想

求误差初值， $p_1 = 3 - 2r$ ， $i = 1$ ，画点 $(0, r)$ ；
求下一个光栅位置，其中 $x_{i+1} = x_i + 1$ ，如果 $p_i < 0$ 则 $y_{i+1} = y_i$ ，否则 $y_{i+1} = y_i - 1$ ；
画点 $(x_{i+1}, y_{i+1})$ ；
计算下一个误差，如果 $p_i < 0$ 则 $p_{i+1} = p_i + 4x_i + 6$ ，否则 $p_{i+1} = p_i + 4(x_i - y_i) + 10$ ；
$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}

圆的中点画圆法思想

输入圆半径 $r$ ；
求误差初值， $p_0 = \frac{5}{4} - r$ ，画点 $(0, r)$ ；
求下一个光栅位置，其中 $x_{i+1} = x_i + 1$ ，如果 $p_i < 0$ 则 $y_{i+1} = y_i$ ，否则 $y_{i+1} = y_i - 1$ ；
画点 $(x_{i+1}, y_{i+1})$ ；
计算下一个误差，如果 $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$ ；
确定其他七个八分圆中的对称点；
$i = i + 1$ ，如果 $x = y$ 则结束，否则返回步骤 3。

区域填充算法

区域填充基础知识

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

计算机图形学中，多边形区域有两种重要的表示方法：顶点表示和点阵表示。
所谓顶点表示，即是用多边形的顶点序列来表示多边形。这种表示直观、几何意义强、占内存少，易于进行几何变换，但由于它没有明确指出哪些像素在多边形内，故不能直接用于区域填充。
所谓点阵表示，则是用位于多边形内的像素集合来刻画多边形。这种表示丢失了许多几何信息，但便于进行填充。

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

扫描线填色算法

算法的基本思想:

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

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

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

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

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

左、右顶点处理

当以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连通

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

字符的生成

点阵式字符

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

矢量式字符

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

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

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

三角形的光栅化

选择三角形的原因

最基础的多边形，任意多边形都可以由三角形组成；
保证三点在一个平面上
便于判断内部
便于插值计算（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}

如何判断点是否在三角形内

\begin{align*} \vec{V_1} &= \vec{P_0P_1} \times \vec{P_0Q} \\ \vec{V_2} &= \vec{P_1P_2} \times \vec{P_1Q} \\ \vec{V_3} &= \vec{P_2P_0} \times \vec{P_2Q} \end{align*}

如果 $\vec{V_1}, \vec{V_2}, \vec{V_3}$ 的方向相同，则点 $Q$ 在三角形内。

使用包围盒判断三角形是否在屏幕内

反走样（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*}

当 $S_x or S_y < 0$ 时，图形会发生镜像变换

齐次坐标

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

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

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

当 $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}

齐次坐标的优点

将各种变换用阶数统一的矩阵来表示。提供了用矩阵运算把二维、三维甚至高维空间上的一个点从一个坐标系变换到另一坐标系的有效方法。
便于表示无穷远点。例如： $(x \times h, y \times h, h)$ ，令 $h$ 等于 $0$ 。
齐次坐标变换矩阵形式把直线变换成直线段，平面变换成平面，多边形变换成多边形，多面体变换成多面体。
变换具有统一表示形式的优点：便于变换合成，便于硬件实现

变换矩阵

平移矩阵

平移矩阵运算表示为

\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$ $d = 0$ 时， $(x', y', 1) = (x + by, y, 1)$ $(x^{'}, y^{'}, 1) = (x + b y, y, 1)$ ：图形的 $y$ $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类：

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

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

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

Cohen-Sutherland 算法

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

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

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

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

对直线两端点 $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\}$ 。
如果 $a_i = b_i = c_i = d_i = 0$ ，则显示整条直线，取出下一条直线，返回步骤 (1)。否则，进入步骤 (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})$ 的交点，并删去交点以左部分。
返回步骤 (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$ $p_{k} = 0$ ，其中 $k$ $k$ 对应于裁剪边界（ $k = 1, 2, 3, 4$ $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}$ 。

梁友栋-Barsky裁剪算法在寻找线段可见部分（如果有可见线段）时可以归结为四个步骤：

如果对所有的 $k$ 都有 $p_k=0$ 和 $q_k<0$ ，删除线段并结束。否则继续执行下一步。
对所有 $p_k<0$ 的 $k$ ，计算 $r_k=\frac{q_k}{p_k}$ ，将 $0$ 和各个 $r_k$ 值之中的最大值赋给 $u_1$ 。
对所有 $p_k>0$ 的 $k$ ，计算 $r_k=\frac{q_k}{p_k}$ ，将 $1$ 和各个 $r_k$ 值之中的最小值赋给 $u_2$ 。
如果 $u_1>u_2$ ，则线段完全落在裁剪窗口之外，不可见，可直接舍弃。否则，裁剪后线段的端点由参数 $u$ 的两个值 $u_1$ 、 $u_2$ 计算出来。

多边形的裁剪

Sutherland-Hodgman 算法

思路：将多边形的各边先相对于窗口的某一条边界进行裁剪，然后将裁剪结果再与另一条边界进行裁剪，如此重复多次，便可得到最终结果。

实现方法：

设置两个表：
- 输入顶点表（向量）：用于存放被裁剪多边形的顶点 $p_1$ - $p_m$ 。
- 输出顶点表（线性链表）：用于存放裁剪过程中及结果的顶点 $q_1$ - $q_n$ 。
输入顶点表中各顶点要求按一定顺序排列，一般可采用顺时针或逆时针方向。
相对于裁剪窗口的各条边界，按顶点表中的顺序，逐边进行裁剪。

具体操作：

若 $P_i$ 位于边界线的可见一侧，则 $P_i$ 送输出顶点表。
若 $P_i$ 位于边界线的不可见一侧，则将其舍弃。
除第一个顶点外，还要检查每一个 $P_i$ 和前一顶点 $P_{i-1}$ 是否位于窗口边界的同一侧，若不在同一侧，则需计算出交点送输出顶点表。
最后一个顶点 $P_n$ 则还要与 $P_1$ 一起进行同样的检查。

沿着多边形依次处理顶点会遇到四种情况。在将相邻的一对多边形顶点传到窗口的边界裁剪程序时，可以进行下列测试：

如果第一点在窗口边界外而第二点在窗口边界内，则将多边形的这条边与窗口边界的交点和第二点加到输出顶点表中。
如果两顶点都在窗口边界内，则只有第二点加到输出顶点表中。
如果第一点在窗口边界内而第二点在窗口外，则只有与窗口边界的交点加到输出顶点表中。
如果两个点都在窗口边界外，那么输出顶点表中不增加任何点。

真实感图形的生成技术

线消隐

线消隐是一种物空间消隐技术：在物体空间中，对物体的各个线段进行消隐处理，以确定哪些线段是可见的，哪些是不可见的。

for (每个多边形) {
  for (每个多边形的边) {
    if (边在窗口内) {
      if (边不在任何多边形的背面) {
        画线
      }
    }
  }
}

凸多面体的隐藏线/面消隐

设平面方程为 $a_ix + b_iy + c_iz + d_i = 0$ ，变换方程的系数，使 $(a_i, b_i, c_i)$ 指向物体外部。

将视线向量 $\vec{V_{\text{view}}}$ 与面法向量 $\vec{N_i}$ 的点积 $P_i = \vec{V_{\text{view}}} \cdot \vec{N_i}$ 代入平面方程，若 $P_i > 0$ ，则该面是背面。

凹多面体的隐藏线/面消隐

假设凹多面体用它的表面多边形的集合表示，消除隐藏线的问题可归结为：对于一条空间线段 $P_1P_2$ 和一个多边形 $a$ ，判断线段是否被多边形遮挡。如果被遮挡，求出隐藏部分。

直线与多边形的遮挡判断

若线段的两端点与视点在给定平面的同一侧，则线段位于给定平面的前面，是可见的，转步骤 9。
求线段与相应的无限平面的交。若无交点，转步骤 4；否则，转步骤 3。
交点将该线段分成两段，与视点同侧的一段是可见的，它没有被遮挡；另一段的可见性还不能确定，转步骤 4，继续测试。
若线段的投影与给定平面的投影的包围盒不相交，则线段可见，它不被该平面遮挡，转步骤 9。
求所剩线段的投影与平面边界投影的所有交点。
将线段的投影在交点处依次分成若干段，根据交点在原直线参数方程中的参数值的大小对线段进行排序。
求出第一投影线段的中点，若第一段的中点在多边形的投影内，则相应的线段被遮挡，否则不被遮挡。
其它各段的遮挡关系可依次按“遮挡/可见”交替地取值。例如：
- 如果第一段被遮挡，则后面线段的可见性依次为“可见，遮挡，可见，…”
- 若第一段可见，则后面的线段依次为“遮挡，可见，遮挡，…”
结束。

面消隐

面消隐是一种像素空间消隐技术：在屏幕空间中，对屏幕上的各个像素进行消隐处理，以确定哪些像素是可见的，哪些是不可见的。

for (每个像素) {
  确定像素对应的距离视点最近的物体
  以该物体的颜色填充像素
}

深度缓存法（Z-Buffer）

Z-Buffer 算法的基本思想是：在屏幕上为每个像素点建立一个深度缓存，用来存放该像素点对应的物体表面的深度值。在绘制物体时，对于每个像素点，首先计算该像素点对应的物体表面的深度值，然后将该深度值与深度缓存中的值进行比较，若该深度值小于深度缓存中的值，则将该深度值存入深度缓存，并将该像素点的颜色值存入颜色缓存；否则，不更新深度缓存和颜色缓存。

步骤

初始化ZB和CB，使得 $ZB(i, j) = \infty$ ， $CB(i, j) = 0$ 。
对于每个多边形，计算其在屏幕上的投影，对于每个像素 $(i, j)$ ，计算其对应的深度值 $Z(i, j)$ 。
如果 $Z(i, j) < ZB(i, j)$ ，则更新 $ZB(i, j) = Z(i, j)$ 和 $CB(i, j)$ 。
最后，将 $CB(i, j)$ 的值填充到屏幕上的像素 $(i, j)$ 。
重复步骤 2-4，直到所有多边形都被处理。

判断点 $(i, j)$ 是否在多边形 $F_k$ 在投影面上的投影内：采用包含测试（射线法）
计算多边形 $F_k$ 在点 $( i, j )$ 处的深度值 $Z_{i, j}$ ：若多边形 $F_k$ 的平面方程为： $ax + by + cz + d = 0$ ，则有： $Z_{i, j} = -\frac{ax_i + by_j + d}{c}, c \neq 0$ 。

相邻点 $(i+1,j)$ 处 $Z_{i+1, j} = Z-\frac{A}{C}$

光照模型

光源特性

光的色彩
光的强度： $0.30*R+0.59*G+0.11*B$
光的方向

物体的表面特性

反射系数
透射系数： $0 \leq T \leq 1$
表面方向

光照模型的计算

漫射光照模型

漫反射光照模型

该公式表示区域内的漫反射光强，其计算方式为：

\vec{E_{Pd}} = \vec{R_P} \vec{I_d}

$\vec{R_P}$ 表示物体在点 $P$ 的反射系数
$\vec{I_d}$ 表示漫反射光强

直射光照模型

该公式表示直接光照成分，其计算方式为：

\vec{E_{Ps}} = \vec{R_P} \cos i \vec{I_{Ps}} + W_P(i)\cos^n s \vec{I_{Ps}}

$\cos i$ 为光线入射与法线方向的夹角余弦
$W_P(i)$ 为与高光相关的权重函数
$n$ (会聚系数) 用于控制高光的聚散程度
$\vec{I_{Ps}}$ 表示光源直射光强

透射光照模型

\vec{E_{Pt}} = \vec{T_p} \vec{I_{Pb}}

$\vec{E_{Pt}}$ ：物体表面 $P$ 点处透射出的光强
$\vec{T_P}$ ： $P$ 点的透射系数（取值范围为 $0 ～ 1$ ）
$\vec{I_{Pb}}$ ：到达 $P$ 点背后的光强

合并光照模型

\begin{align*} \vec{E_P} &= \vec{E_{Pd}} + \vec{E_{Ps}} + \vec{E_{Pt}} &= \vec{R_P} \vec{I_d} + (\vec{R_P} \cos i+ W_P(i)\cos^n s) \vec{I_{Ps}} + \vec{T_p} \vec{I_{Pb}} \end{align*}

$\cos i = \frac{\vec{N} \cdot \vec{L}}{|\vec{N}||\vec{L}|} = \hat{\vec{N}} \cdot \hat{\vec{L}}$
$\cos s = \frac{\vec{R} \cdot \vec{V}}{|\vec{R}||\vec{V}|} = \hat{\vec{R}} \cdot \hat{\vec{V}}$

多光源光照模型

\vec{E_P} = \vec{R_P} \vec{I_d} + \sum_{i=1}^n(\vec{R_P} \cos i+ W_P(i)\cos^n s) \vec{I_{Ps}} + \vec{T_p} \vec{I_{Pb}}

明暗的光滑处理

Gourand 光滑处理

在每个顶点处计算光照强度，然后在多边形内部进行插值。

基本步骤

先计算出多面体顶点的法线方向
用光照模型求得 $V$ 点的亮度
由两个相邻顶点的亮度插值得到棱上各点的亮度。由棱上各点的亮度插值得到面内各点的亮度。

计算顶点法向量

设与多面体顶点 $V$ 相邻的多边形为 $P_1, P_2, \dots, P_n$ ，它们的法线分别为 $N_1(a_1, b_1, c_1), N_2(a_2, b_2, c_2), \dots, N_n(a_n, b_n, c_n)$ 。则 $V$ 的法线 $n_V$ 取做：

n_V = (a_1 + a_2 + \dots + a_n)\vec{i} + (b_1 + b_2 + \dots + b_n)\vec{j} + (c_1 + c_2 + \dots + c_n)\vec{k}

用光照模型求得V点的亮度
由两顶点的亮度，插值得出棱上各点的亮度。由棱上各点的亮度，插值得出面上各点的亮度。

如果希望在某处不处理成光滑而要保留折痕效果，方法是在顶点 $b$ 处设置两条法线，分别用于 $A$ 和 $B$ 、 $C$ 和 $D$ 之间的插值。

优点：能有效地显示漫反射曲面，计算量小

缺点：

高光有时会异常。
当对曲面采用不同的多边形进行分割时会产生不同的效果。
Gouraud 明暗处理会造成表面上出现过亮或过暗的条纹，称为马赫带（Mach band）效应。

改进：Phong 提出双线性法向插值，以时间为代价，解决高光问题。

Phong 光滑处理

通过对多边形顶点的法矢量进行插值，获得其内部各点的法矢量，又称为法向插值着色方法。

基本步骤

计算多边形单位法矢量
计算多边形顶点单位法矢量
对多边形顶点法矢量进行双线性插值，获得内部各点的法矢量
利用光照明方程计算多边形内部各点颜色

比较

Phong着色方法绘制的图形比Gouraud方法更真实，体现在两个方面：高光区域的扩散，产生正确的高光区域。

Phong着色方法计算量远大于Gouraud着色方法。
在处理某些多边形分割的曲面时，Phong算法还不如Gouraud算法好。

阴影处理

阴影的分类

本影：光线无法到达的区域
半影：光线部分到达的区域

场景绘制时，先利用消隐技术确定物体表面的可见部分或者是像素所对应的物体表面上的可见点，然后应用光照模型计算物体表面上可见点的亮度，这时如果根据光源是否可以直接照射到物体表面上当前可见点来取舍光源的照明效果，则绘制出来的图像具有阴影的效果。

影域多边形方法

所谓影域，就是物体投射出的台体。判断点是否在台体中即可确定是否在阴影中。

整体光照模型

Whitted 光照模型

Whitted光照模型基于如下假设：

物体表面向视点方向 $V$ 辐射的光亮度 $I$ 由三部分组成：
1. 光源直接照射引起的反射光亮度 $I_c$ ；
2. 来自 $V$ 的镜面反射方向 $R$ 的其它物体反射或折射来的光的亮度 $I_s$ ；
3. 来自 $V$ 的透射方向 $T$ 的其它物体反射或折射来的光的亮度 $I_t$ 。
Whitted光照模型： $I = I_c + k_s I_s + k_t I_t$
- $I_s$ 为镜面反射方向的入射光强度； $k_s$ 为镜面反射系数，为 $0～1$ 之间的一个常数
- $I_t$ 为折射方向光强， $k_t$ 为透射系数，是 $0 ～ 1$ 之间的常数
- $I_c$ 的计算可采用Phong模型
- 因此，关键是 $I_s$ 和 $I_t$ 的计算。由于 $I_s$ 和 $I_t$ 是来自 $V$ 的镜面反射方向 $r$ 和规则透射方向 $t$ 的环境光亮度，因而首先必须确定 $r$ 和 $t$ 。

Whitted光照模型的反射和折射计算

已知视线方向 $V$ ，求其反射方向 $R$ 与折射方向 $T$ （ $N$ 是表面的法向方向）

视线 $V$ 的反射方向 $r$ ：
$r = 2N - V$
折射方向 $t$ ：
$t=k_f(N-V') - N$
其中， $k_f$ 是折射系数。

Graphics Pipeline

Vertex Processing（顶点处理）

对输入的每个顶点执行以下操作：

应用建模变换(Model Transform)：将模型空间坐标转换到世界空间
应用视图变换(View Transform)：将世界空间坐标转换到相机空间
应用投影变换(Projection Transform)：将相机空间坐标转换到规范化设备坐标(NDC)

Triangle Processing（三角形处理）

将顶点组装成三角形
背面剔除：剔除背对相机的三角形
裁剪：剔除或裁剪完全/部分在视锥体外的三角形
投影除法：将裁剪空间坐标转换到NDC
屏幕映射：将NDC映射到屏幕空间坐标

Rasterization（光栅化）

三角形遍历：确定三角形覆盖的像素
插值：对每个像素计算其深度值、颜色、纹理坐标等属性
三角形覆盖测试：判断像素中心是否在三角形内

Fragment Processing（片元处理）

对每个片元(fragment)执行：

纹理采样：获取纹理颜色
着色计算：应用光照模型计算片元颜色
Alpha测试：根据透明度值决定是否丢弃片元

FrameBuffer Operations（帧缓存操作）

最终阶段的测试和操作：

深度测试(Z-test)：比较片元深度值
模板测试(Stencil test)：用于实现阴影等特效
混合(Blending)：处理透明物体
颜色写入：将最终颜色写入帧缓存

光线追踪

光线跟踪方法沿着到达视点的光线的反方向跟踪，经过屏幕上每一像素，找出与视线所交的物体表面点 $P_0$ ，并继续跟踪，找出影响 $P_0$ 点光强的所有光源，从而算出 $P_0$ 点上光照强度。

视线 $V$ 在 $P_0$ 处产生反射和透射，所产生的反射线和透射线作为新的视线与各平面求出新的交点 $P_1$ 、 $P_2$ ，并分别产生新的反射线和透射线……这样不断深入，直至所产生的射线射出场景。由此得到视线跟踪轨迹上的一系列交点 $P_0$ ， $P_1$ ， $P_2$ ，…， $P_n$ 。这个过程可以表示为一棵光线跟踪树。

光强计算方法是以后序周游的算法遍历这棵光线跟踪树。

光线跟踪方法优点：

各物体之间反射的影响，因此显示效果十分逼真。
有消隐功能
有影子效果
该算法具有并行性质

辐射度量学

Radient Energy and Flux (Power) （辐射能量和通量）

辐射能量（Radiant energy）是电磁辐射的能量。它的单位是焦耳，用符号表示：
$Q [J = 焦耳]$
辐射通量（功率）（Radiant flux (power) ）是每单位时间内发射、反射、传输或接收的能量。
$\Phi \equiv \frac{dQ}{dt} [W = 瓦特] [lm = 流明]$

Radiant Intensity （辐射强度）

辐射（光）强度是点光源每单位立体角发射的功率。

I(\omega) \equiv \frac{d\Phi}{d\omega} [W/sr = 瓦特/立体角][lm/sr == cd = 坎德拉]

Differential Solid Angles（微分立体角）

\begin{align*} dA &= (r d\theta)(r \sin \theta d\phi) = r^2 \sin \theta d\theta d\phi\\ d\omega &= \frac{dA}{r^2} = \sin \theta d\theta d\phi \end{align*}

$\omega$ 将用来表示方向向量（单位长度）

Irradiance （辐照度）

辐照度是指单位面积上入射到表面点的功率。

E(x) \equiv \frac{d\Phi}{dA} [W/m^2][lm/m^2 = lux = 勒克斯]

Radiance （辐射度）

辐射度（亮度）是单位立体角、单位投影面积上由表面发射、反射、透射或接收的功率。

L(p, \omega) \equiv \frac{d^2\Phi(p,\omega)}{dA d\omega \cos \theta} [W/(m^2 sr)][lm/(m^2 sr) = cd/m^2 = nit = 尼特]

Incident Radiance （入射辐射度）

入射辐射度是指单位立体角、单位投影面积上入射到表面点的辐射度。

L_i(p, \omega) \equiv \frac{dE(p)}{d\omega \cos \theta}

Exiting Radiance （出射辐射度）

出射辐射度是指单位立体角、单位投影面积上由表面点发射、反射、透射或接收的辐射度。

L_o(p, \omega) \equiv \frac{dI(p, \omega)}{dA\cos \theta}

Irradiance vs. Radiance （辐照度与辐射度）

E(p) = \int_{H^2} L_i(p, \omega) \cos \theta d\omega

BRDF（双向反射分布函数）

双向反射分布函数（BRDF）表示从每个入射方向反射到每个出射方向的光量。

f_r(\omega_i \rightarrow \omega_o) = \frac{dL_r(\omega_r)}{dE_i(\omega_i)} = \frac{dL_r(\omega_r)}{L_i(\omega_i) \cos \theta_i d\omega_i} [sr^{-1}]

渲染方程

L_r(X, \omega_r) = L_e(X, \omega_r) + \int_{\Omega} L_r(X', -\omega_i) f_r(X, \omega_i, \omega_r) (\omega_i \cdot N) d\omega_i

$L_r(X,\omega_r)$ ：点 $X$ 处沿方向 $\omega_r$ 的反射光亮度。
$L_e(X,\omega_r)$ ：点 $X$ 处沿方向 $\omega_r$ 的自发光亮度。
$L_r(X',\omega_i)$ ：点 $X'$ 处沿方向 $\omega_i$ 的反射光亮度。
$f_r(X,\omega_i,\omega_r)$ ：点 $X$ 处从方向 $\omega_i$ 到方向 $\omega_r$ 的双向反射分布函数（BRDF）。
$(\omega_i \cdot n)$ ：入射方向 $\omega_i$ 与法线 $n$ 的点积，用于表示入射光的角度对亮度的影响。

Ray Intersection的计算

光线方程： $\vec{r(t)} = \vec{o} + t\vec{d}, t \geq 0$
平面方程： $\vec{p}: (\vec{p}-\vec{p}') \cdot \vec{N} = 0$

t = \frac{(\vec{p}' - \vec{o}) \cdot \vec{N}}{\vec{d} \cdot \vec{N}}

表面图案与纹理

表面图案的描绘

将一幅平面图案描绘到物体表面上的过程如下：

将平面图案上的各点 $(x', y')$ 映射到物体表面的各点 $(x, y, z)$ 。
求出点 $(x, y, z)$ 处新的反射系数。
用光照模型计算物体表面点 $(x, y, z)$ 的色彩明暗。

表面纹理的描绘

Blinn 在 1978 年提出，用扰动物体表面法线方向的方法来模拟表面凹凸纹理的真实感显示效果。

物体的新表面 $S(u, v)$ 定义为 ( $Q(u, v)$ 为原表面):

S(u, v) = Q(u, v) + P(u, v)(\frac{N}{|N|})

上式对 $u$ 、 $v$ 分别求偏导函数，得：

\begin{align*} S_u &= Q_u + P_u\frac{N}{|N|}\\ S_v &= Q_v + P_v\frac{N}{|N|} \end{align*}

记 $N_S$ 为 $S(u, v)$ 的法向量。法向量可以表示为两个偏导向量 $S_u$ 和 $S_v$ 的叉积，即

\begin{align*} N_S &= S_u \times S_v\\ &= (Q_u + P_u\frac{N}{|N|}) \times (Q_v + P_v\frac{N}{|N|})\\ &= N + \frac{P_u(Q_v \times N)+P_v(N \times Q_u)}{|N|}\\ \end{align*}

色彩空间

颜色的基本概念

格拉斯曼(Grassmann H.)定律，从视觉的角度看，颜色包含3个要素，即色调、饱和度和亮度。分别对应光学中的术语：主波长、纯度和辉度。

CIE色度图

红、绿、蓝是三种原色。国际照明委员会（CIE）规定了三种标准原色：X、Y、Z。

颜色可以表示为：

c = xX + yY + zZ

权值规格化：

\begin{align*} x &= \frac{X}{X + Y + Z} \\ y &= \frac{Y}{X + Y + Z} \\ z &= \frac{Z}{X + Y + Z} \end{align*}

几种常见的色彩空间

RGB色彩空间：红、绿、蓝
CMYK色彩空间：青、品红、黄、黑

Geometry

几何体的表示

隐式表示
- algebraic surface（代数曲面）
- level sets（等值集）
- distance functions（距离函数）
- constructive solid geometry（CSG，构造实体几何）
- fractals（分形）
显式表示
- point cloud（点云）
- polygon mesh（多边形网格）
- subdivision, NURBS（细分曲面，非均匀有理B样条曲面）

几何体表示的优缺点

隐式表示
- 优点：
  - 紧凑的描述（例如一个函数）
  - 某些查询容易（物体内部、到表面的距离）
  - 适合射线-表面相交计算
  - 对于简单形状，有精确描述/无采样误差
  - 容易处理拓扑变化（例如流体）
- 缺点：
  - 难以建模复杂形状
显式表示
- 优点：容易采样，容易计算法向量
- 缺点：测试点是否在几何体内部困难

曲线与曲面

曲线与曲面的表示

有一空间点A，从原点O到A点的连线表示一个矢量，此矢量称为位置矢量。
空间一点的位置矢量有三个坐标分量，而空间曲线是空间动点运动的轨迹，也就是空间矢量端点运动形成的矢端曲线，其矢量方程为：

C(u) = (x(u), y(u), z(u))

此式也称为单参数的矢函数。它的参数方程为：

\begin{cases} x = x(u)\\ y = y(u)\\ z = z(u) \end{cases} ,u \in [u_0, u_n]

曲线的矢函数求导

设当参数 $u$ 变为 $u + \Delta u$ 时，矢函数对应的位置由 $\vec{C}(u)$ 变为 $\vec{C}(u + \Delta u)$ ，线段对应的矢量差为：

\Delta \vec{C}(u) = \vec{C}(u + \Delta u) - \vec{C}(u)

其变化率为：

\frac{\vec{C}(u + \Delta u) - \vec{C}(u)}{\Delta u}

当 $\Delta u \to 0$ 时，这个矢量的极限叫做 $\vec{C}(u)$ 的一阶导矢，记为 $\frac{d\vec{C}}{du}$ 或：

\vec{C}'(u) = \lim_{\Delta u \to 0} \frac{\vec{C}(u + \Delta u) - \vec{C}(u)}{\Delta u}

又设 $\vec{r(u)} = [x(u), y(u), z(u)]$ ，因为：

\frac{\vec{C}(u + \Delta u) - \vec{C}(u)}{\Delta u} = [\frac{x(u + \Delta u) - x(u)}{\Delta u}, \frac{y(u + \Delta u) - y(u)}{\Delta u}, \frac{z(u + \Delta u) - z(u)}{\Delta u}]

所以：

\vec{C}'(u) = [x'(u), y'(u), z'(u)]

矢函数的导矢也是一个矢函数，因此也有方向和模。矢量 $\frac{[\vec{C}(u + \Delta u) - \vec{C}(u)]}{\Delta u}$ 的方向平行于割线 $MM_1$ ；当 $\Delta u \to 0$ 时， $\frac{\vec{C}(u)}{\Delta u}$ 就转变为 $M(u)$ 点的切线矢量，故又称导矢为切矢。

曲线的自然参数方程

设在空间曲线 $C(u)$ 上任取一点 $M_0(x_0, y_0, z_0)$ 作为计算弧长的初始点，曲线上其他点 $(x, y, z)$ 到 $M_0$ 之间的弧长 $s$ 是可以计算的（如用弧长积分公式或累计弦长公式），这样曲线上每个点的位置与它的弧长之间有一一对应关系。以曲线弧长作为曲线方程的参数，这样的方程称为曲线的自然参数方程，弧长则称为自然参数：

C = C(s) = [x(s), y(s), z(s)]

曲线的法矢量

设空间曲线的自然参数方程为 $C=C(s)$ ，曲线的切矢为单位矢量，记为 $T$ ：

T(s) = \dot{C}(s)

因为 $(T(s))^2 = 1$ ，对左式求导，得到：

2T(s) \cdot \dot{T}(s) = 0

说明 $T(s)$ 垂直于 $\dot{T}(s)$ ，鉴于 $\dot{T}(s)$ 不是单位矢量，可以认为：

\dot{T}(s) = k(s)N(s)

单位矢量 $N(s)$ 定义为曲线的主法线单位矢量，简称主法矢；主法矢 $N(s)$ 总是指向曲线凹入的方向；而 $k(s)$ 是一标量系数，称为曲线的曲率，而矢量 $\ddot{C}(s) = \dot{T}(s)$ 称为曲率矢量，其模就是该曲线的曲率：

|\ddot{C}(s)| = k(s)

记 $\rho(s) = \frac{1}{k(s)}$ ，称为曲率半径。

令垂直于 $T$ 和 $N$ 的单位矢量为 $B$ ，称此矢量为此法线单位矢量或副法线单位矢量：

B(s) = T(s) \times N(s)

由切线和主法线所确定的平面称为密切平面；由主法线和副法线组成的平面称为法平面；由切线和副法线构成的平面称为从切面。

曲面的切矢和法矢

空间曲面采用双参数表示：

S = S(u, v) = [x(u, v), y(u, v), z(u, v)]

当 $v$ 为常数时，上式变成单参数 $u$ 的矢函数，它是曲面上的空间曲线，我们称它为 $v$ 线；

当 $u$ 为常数时，上式变成单参数 $v$ 的矢函数，它是曲面上的空间曲线，我们称它为 $u$ 线；

将矢函数对 $u$ 求导，得切矢：

\frac{\partial S}{\partial u} = \lim_{\Delta u \to 0} \frac{S(u + \Delta u) - S(u)}{\Delta u} = [x_u(u, v), y_u(u, v), z_u(u, v)]

切矢的方向指向参数 $u$ 增长的方向。

同样，将矢函数对 $v$ 求导，得切矢：

\frac{\partial S}{\partial v} = \lim_{\Delta v \to 0} \frac{S(v + \Delta v) - S(v)}{\Delta v} = [x_v(u, v), y_v(u, v), z_v(u, v)]

切矢的方向指向参数 $v$ 增长的方向。

经过曲面上某一点 $M$ 处的切平面的法矢量为：

N = \frac{\partial S}{\partial u} \times \frac{\partial S}{\partial v} = \begin{vmatrix} i & j & k \\ x_u & y_u & z_u \\ x_v & y_v & z_v \end{vmatrix}

参数表示的优点

有更大的自由度控制曲线曲面的形状；
可对参数曲线曲面的方程直接进行几何变换，而不需要对曲线曲面的每个数据点进行几何变换；
可以处理斜率无穷大的情况；
代数、几何相关和无关的变量是完全分离的，对变量个数不限，便于将低维空间中的曲线曲面扩展到高维空间中；
便于采用规格化的参数变量
易于用矢量和矩阵表示几何分量，简化计算。

插值、逼近和拟合

曲线曲面设计的基本概念

型值点：通过测量或计算得到的曲线/曲面上少量描述其几何形状的数据点
控制点：用来控制或调整曲线曲面形状的特殊点，曲线曲面本身不一定通过控制点
插值与逼近：
- 插值：建立的数学模型严格通过所有已知型值点
- 逼近：建立的数学模型只是近似接近已知型值点
拟合：在设计过程中，用插值或逼近方法使生成的曲线曲面达到特定设计要求

曲线段间的连续性定义

C0连续（0阶参数连续）：前一段曲线的终点与后一段曲线的起点相同。
C1连续（一阶参数连续）：两相邻曲线段的连接点处有相同的一阶导数。
C2连续（二阶参数连续）：两相邻曲线段的连接点处有相同的一阶导数和二阶导数。

对于参数曲线段 $C_1(u), C_2(u), u \in [0,1]$ ，若在点 $P$ 处 $C_1(1) = C_2(0) = P$ ，则在 $P$ 处具有 $C^0$ ， $G^0$ 连续；
$C_1(u), C_2(u), u \in [0,1]$ 在点 $P$ 处重合，且在点 $P$ 处的切矢量方向相同，大小不相等，则在点 $P$ 处具有 $G^1$ 连续；
$C_1(u), C_2(u), u \in [0,1]$ 在点 $P$ 处重合，且在 $P$ 点处的切矢量方向相同，大小相等，则在点 $P$ 处具有 $C^1$ 连续；
$C_1(u), C_2(u), u \in [0,1]$ 若在点 $P$ 处已有 $C^0$ 、 $C^1$ 连续性，且 $C''_1(0)$ 、 $C''_2(1)$ 的大小和方向均相同，则在点 $P$ 处具有 $C^2$ 连续；
$C_1(u), C_2(u), u \in [0,1]$ 若在点 $P$ 处已有 $G^0$ 、 $G^1$ 连续性，且 $C''_1(0)$ 、 $C''_2(1)$ 的方向相同，大小不相等，则在点 $P$ 处具有 $G^2$ 连续。

Bézier曲线

在给定空间 $n+1$ 个点 $P_0, P_1, \dots, P_n$ ，称下列参数曲线为 $n$ 次的 Bézier 曲线：

C_n(u) = \sum_{i=0}^n P_i B_{i,n}(u)

其中， $B_{i,n}(u)$ 是 Bernstein 基函数，即：

B_{i,n}(u) = C_n^i u^i(1-u)^{n-i}, \quad C_n^i = \frac{n!}{i!(n-i)!}

（注：Bézier 本人也不能解释该公式的来源）

一般称折线 $P_0, P_1, \dots, P_n$ 为 $C(u)$ 的控制多边形； $P_0, P_1, \dots, P_n$ 各点为 $C(u)$ 的控制顶点。控制多边形是 $C(u)$ 的大致形状的勾画； $C(u)$ 是对 $P_0, P_1, \dots, P_n$ 的逼近。

Bernstein基函数性质

非负性

对于所有的 $i$ ， $n$ 以及 $u \in [0,1]$ 均有 $B_{i,n}(u) \geq 0$ 成立；

规范性

\sum_{i=0}^n B_{i,n}(u) \equiv 1, \quad u \in [0,1]

对称性

B_{i,n}(u) = B_{n-i,n}(1-u), \quad i = 0,1,...,n

递推性

B_{i,n}(u) = (1-u)B_{i,n-1}(u) + uB_{i-1,n-1}(u), \quad i = 0,1,...,n

端点性

B_{i,n}(0) = \begin{cases} 1, & i = 0 \\ 0, & \text{else} \end{cases}

B_{i,n}(1) = \begin{cases} 1, & i = n \\ 0, & \text{else} \end{cases}

最大性

$B_{i,n}(u)$ 在 $u = \frac{i}{n}$ 处达到最大值；

可导性

\frac{dB_{i,n}(u)}{du} = n[B_{i-1,n-1}(u) - B_{i,n-1}(u)], \quad i = 0,1,...,n

升阶公式

\begin{align*} \frac{i}{n+1}B_{i,n}(u) &= (1-u)B_{i,n+1}(u) \\ \frac{n-i+1}{n+1}B_{i,n}(u) &= uB_{i+1,n+1}(u) \\ B_{i,n}(u) &= \frac{n-i+1}{n+1}B_{i,n+1}(u) + \frac{i+1}{n+1}B_{i+1,n+1}(u) \end{align*}

分割性

B_{i,n}(cu) = \sum_{j=0}^n B_{i,j}(c)B_{j,n}(u)

积分性

\int_0^1 B_{i,n}(u)du = \frac{1}{n+1}

Bézier曲线性质

端点性质

\begin{align*} C(0) &= P_0 \\ C(1) &= P_n \end{align*}

端点切矢量

\begin{align*} C'(u) &= n\sum_{i=0}^{n-1} B_{i,n-1}(u)(P_{i+1} - P_i) \\ C'(0) &= n(P_1 - P_0) \\ C'(1) &= n(P_n - P_{n-1}) \end{align*}

Bézier曲线在 $P_0$ 点处与边 $P_0P_1$ 相切，在点 $P_n$ 处与边 $P_{n-1}P_n$ 相切。

端点的曲率

在 $C(u)$ 两端点的曲率分别为：

\begin{align*} K(0) &= \frac{n-1}{n} \frac{|P_0P_1 \times P_1P_2|}{|P_0P_1|^3} \\ K(1) &= \frac{n-1}{n} \frac{|P_{n-2}P_{n-1} \times P_{n-1}P_n|}{|P_{n-1}P_n|^3} \end{align*}

这是因为：

\begin{align*} C''(u) &= n(n-1)\sum_{i=0}^{n-2} (P_{i+2} - 2P_{i+1} + P_i)B_{i,n-2}(u) \\ C''(0) &= n(n-1)(P_2 - 2P_1 + P_0) \\ C''(1) &= n(n-1)(P_n - 2P_{n-1} + P_{n-2}) \end{align*}

对称性

若保持原全部顶点的位置不变，只是把次序颠倒过来，则新的 Bézier 曲线形状不变，但方向相反。

几何不变性

Bézier 曲线的位置和形状只与特征多边形的顶点的位置有关，它不依赖坐标系的选择。移动第 $i$ 个控制顶点 $P_i$ 将对曲线上参数为 $u = \frac{i}{n}$ 的那个点 $C(\frac{i}{n})$ 处发生最大的影响。

凸包性

因为是控制顶点 $P_0, P_1, \dots, P_n$ 的加权平均，而权因子 $B_{i,n}(u) \in [0,1]$ 范围内，这在几何意义上有两层含义：

Bézier 曲线 $C(u)$ 位于其控制顶点 $P_0, P_1, \dots, P_n$ 的凸包之内；
Bézier 曲线 $C(u)$ 随着其控制多边形的变化而变化。

常用Bézier曲线的矩阵表示

由Bézier曲线C(u)的定义，可推出常用的一次、二次、三次Bézier曲线矩阵表示。

一次Bézier曲线

\begin{align*} C(u) &= (1-u)P_0 + uP_1 \\ &= [u, 1]\begin{bmatrix}-1 & 1 \\ 1 & 0\end{bmatrix}\begin{bmatrix}P_0 \\ P_1\end{bmatrix} \end{align*}

二次Bézier曲线

\begin{align*} C(u) &= (1-u)^2P_0 + 2u(1-u)P_1 + u^2P_2 \\ &= [u^2, u, 1]\begin{bmatrix}1 & -2 & 1 \\ -2 & 2 & 0 \\ 1 & 0 & 0\end{bmatrix}\begin{bmatrix}P_0 \\ P_1 \\ P_2\end{bmatrix} \end{align*}

三次Bézier曲线

\begin{align*} C(u) &= (1-u)^3P_0 + 3u(1-u)^2P_1 + 3u^2(1-u)P_2 + u^3P_3 \\ &= [u^3, u^2, u, 1]\begin{bmatrix} -1 & 3 & -3 & 1 \\ 3 & -6 & 3 & 0 \\ -3 & 3 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} P_0 \\ P_1 \\ P_2 \\ P_3 \end{bmatrix} \end{align*}

Bézier曲线的De Casteljau算法

给定三维空间点 $P_0, \dots, P_n$ 以及一维标量参数 $u$ ；假定：

P_i^r = (1-u)P_i^{r-1} + uP_{i+1}^{r-1}(u) \quad \begin{cases} r = 1,\dots,n \\ i = 0,\dots,n-r \end{cases}

并且 $P_i^0(u) = P_i$ ，那么 $P_0^n(u)$ 即为Bézier曲线上参数 $u$ 处的点。

Bézier曲线的几何作图法

利用 De Casteljau 算法可以以几何方式计算参数值 $u$ 处的曲线点：

根据给定的参数值 $u$ ，在控制多边形的每条边上确定某一分割点，使分割后的线段之比为 $u:(1-u)$ ；由此得分割点为：

$P_i^1 = (1-u)P_i + uP_{i+1}, \quad i = 0, 1, 2, \dots, n-1$

由此组成一个边数为 $(n-1)$ 的新的多边形。
用相同的方法对该多边形再次分割，得到分割点 $P_i^2(i = 0,\dots,n-2)$ 形成另一个新的多边形；
按相同的过程分割 $n-1$ 次后，得到两个顶点 $P_0^{n-1}, P_1^{n-1}$ ，再分割得到所求的点 $P_0^n$ 即为所求的 $u$ 处的曲线点；

Bézier曲线的分割

几何作图法中计算 $P_0^n$ 得到的同时也将原 Bézier 曲线分为两个子曲线段： $P_0$ , $P_0^1$ , …, $P_0^n$ 就是定义在 $[0,u]$ 上的子曲线段，而 $P_0^n$ , $P_1^{n-1}$ , …, $P_n^0$ 是定义在 $[u,1]$ 上的子曲线段。

Bézier 曲线的任意分割是指给定两个参数值 $u_1$ , $u_2$ $(0 \leq u_1 \leq u_2 \leq 1)$ ，求原 Bézier 曲线 $C(u), u \in [0,1]$ 上由两点 $C(u_1)$ 与 $C(u_2)$ 所界定的那段子曲线段的控制顶点：

先用 $u = u_1$ 对原曲线做一分为二的分割；
对 $u \in [0,u_2]$ 那个子曲线用 $u = \frac{u_1}{u_2}$ 做一分为二的分割，所得子曲线段 $P(u), u \in [\frac{u_1}{u_2},1]$ 就是所求的原 Bézier 曲线的子曲线段 $P(u), u \in [u_1,u_2]$ 。

Bézier曲线的拼接

设有两条 Bézier 曲线 $P(u)$ 和 $Q(w)$ ，其控制顶点分别为： $P_0, P_1, \dots, P_n$ 和 $Q_0, Q_1, \dots, Q_m$ ：

\begin{align*} P(u) &= \sum_{i=0}^n P_i B_{i,n}(u), & u \in [0,1] \\ Q(w) &= \sum_{j=0}^m P_j B_{j,m}(w), & w \in [0,1] \end{align*}

考虑两条曲线的拼接，几何连续的条件如下：

一阶连续性

根据端矢量条件：

P'(1) = m(P_m - P_{m-1})\\ Q'(0) = n(Q_1 - Q_0)

其连续条件为：

P'(1) = \lambda Q'(0)

即：

Q_1=Q_0+\frac{m}{\lambda n}(P_m-P_{m-1})

Bézier曲面

在空间给定 $(m+1)\times(n+1)$ 个点 $P_{ij}(i=0,1,\dots,n; j=0,1,\dots,m)$ ，称下列张量积形式的参数曲面为 $m \times n$ 的 Bézier 曲面：

S(u,v) = \sum_{i=0}^n \sum_{j=0}^m P_{ij} B_{i,n}(u)B_{j,m}(v), \quad u,v \in [0,1]

一般称 $P_{ij}$ 为 Bézier 曲面 $S(u,v)$ 的控制顶点；把由两组多边形 $P_{i0}P_{i1}\dots P_{im}(i=0,1,\dots,n)$ 和 $P_{0j}P_{1j}\dots P_{nj}(j=0,1,\dots,m)$ 组成的网称为 Bézier 曲面 $S(u,v)$ 的控制网格，记为 $\{P_{ij}\}$ 。

Bézier曲面的性质

端点位置

四个端点分别是 $P_{00}$ , $P_{0m}$ , $P_{n0}$ , $P_{nm}$ 。这是因为：

\begin{align*} S(0, 0) &= P_{00} \\ S(1, 0) &= P_{n0} \\ S(0, 1) &= P_{0m} \\ S(1, 1) &= P_{nm} \end{align*}

边界曲线

$S(u, 0)$ , $S(u, 1)$ , $S(0, v)$ , $S(1, v)$ 的四条边界线分别是以 $P_{00}, P_{01}, P_{02}, \dots, P_{0m}$ 和 $P_{n0}, P_{n1}, P_{n2}, \dots, P_{nm}$ 以及 $P_{00}, P_{10}, P_{20}, \dots, P_{n0}$ 和 $P_{0m}, P_{1m}, P_{2m}, \dots, P_{nm}$ 为控制多边形的 Bézier 曲线。

端点的切平面

由控制顶点 $P_{00}$ , $P_{10}$ , $P_{01}$ 所在的平面在点 $P_{00}$ 处与曲面 $S(u, v)$ 相切。同理，控制顶点 $P_{0m}$ , $P_{1m}$ , $P_{0(m-1)}$ 所在的平面在点 $P_{0m}$ 处与曲面 $S(u, v)$ 相切；控制顶点 $P_{n0}$ , $P_{(n-1)0}$ , $P_{n1}$ 所在的平面在点 $P_{n0}$ 处与曲面 $S(u, v)$ 相切；控制顶点 $P_{nm}$ , $P_{(n-1)m}$ , $P_{n(m-1)}$ 所在的平面在点 $P_{nm}$ 处与曲面 $S(u, v)$ 相切。

端点法线方向

由端点的切平面可知， $P_{00}$ 点的法线方向为 $P_{00}P_{01} \times P_{00}P_{10}$ 。其余各端点 $P_{0m}$ , $P_{n0}$ , $P_{nm}$ 的法线方向情况也类似。

凸包性

曲面 $S(u, v)$ 位于其控制顶点 $P_{ij} (i = 0, \dots, n; j = 0, \dots, m)$ 的凸包内。