1 Basics

说明

本文档仅涉及部分内容，仅可用于复习重点知识

1 Vector

记 \(|\vec{a}|\) 为向量 \(\vec{a}\) 的长度（模），\(\hat{a} = \dfrac{\vec{a}}{|\vec{a}|}\) 为单位向量（长度归一化为 1）。点乘与叉乘是几何计算中用得最多的两种向量运算，前者得到标量，后者得到向量

1.1 Dot Product

点乘（dot product / 内积）把两个向量映射成一个标量，它刻画的是两个向量的"同向程度"：同向为正、垂直为零、反向为负

定义（代数形式）：设 \(\vec{a} = (a_x, a_y, a_z)\)，\(\vec{b} = (b_x, b_y, b_z)\)，则

\[ \vec{a} \cdot \vec{b} = a_xb_x + a_yb_y + a_zb_z = \sum_{i = 1}^{n}a_ib_i \]

定义（几何形式）：设 \(\theta\) 为两向量的夹角，则

\[ \vec{a} \cdot \vec{b} = |\vec{a}||\vec{b}|\cos\theta \]

两个定义是等价的（用余弦定理即可互推）。由几何形式可直接得到 夹角公式：

\[ \cos\theta = \dfrac{\vec{a} \cdot \vec{b}}{|\vec{a}||\vec{b}|} \qquad \Longrightarrow \qquad \theta = \arccos\left(\dfrac{\vec{a} \cdot \vec{b}}{|\vec{a}||\vec{b}|}\right) \]

性质

1. 交换律： \(\vec{a} \cdot \vec{b} = \vec{b} \cdot \vec{a}\)
2. 分配律： \(\vec{a} \cdot (\vec{b} + \vec{c}) = \vec{a} \cdot \vec{b} + \vec{a} \cdot \vec{c}\)
3. 数乘结合： \((k\vec{a}) \cdot \vec{b} = k(\vec{a} \cdot \vec{b})\)
4. 无结合律： \((\vec{a} \cdot \vec{b}) \cdot \vec{c}\) 没有意义（标量与向量之间不能再点乘，只有 \(\vec{a} \cdot \vec{b}\) 这样的"向量·向量"才有定义）
5. 自身点乘等于长度平方： \(\vec{a} \cdot \vec{a} = |\vec{a}|^2\)，由此 \(|\vec{a}| = \sqrt{\vec{a} \cdot \vec{a}}\)
6. 垂直判定： \(\vec{a} \perp \vec{b} \iff \vec{a} \cdot \vec{b} = 0\)（零向量与任意向量点乘都为 \(0\)）

1.1.1 几何意义：投影

单位向量 \(\hat{b} = \dfrac{\vec{b}}{|\vec{b}|}\) 与 \(\vec{a}\) 点乘，得到的是 \(\vec{a}\) 在 \(\vec{b}\) 方向上的 带符号投影长度：

\[ \vec{a} \cdot \hat{b} = |\vec{a}||\hat{b}|\cos\theta = |\vec{a}|\cos\theta \]

（若点乘的不是单位向量，则结果是投影长度再乘上 \(|\vec{b}|\)）

据此可以把 \(\vec{a}\) 分解为平行于 \(\vec{b}\) 和垂直于 \(\vec{b}\) 的两个分量：

\[ \vec{a}_{\parallel} = (\vec{a} \cdot \hat{b})\hat{b}, \qquad \vec{a}_{\perp} = \vec{a} - \vec{a}_{\parallel} \]

1.1.2 图形学中的应用

• Lambert 漫反射（光照）：光线方向 \(\hat{l}\) 与表面法线 \(\hat{n}\) 的夹角决定表面接收到的光强，点乘正好给出 \(\cos\theta\)，是光照模型的核心。实现时要取 \(\max(0, \hat{n} \cdot \hat{l})\)，负值表示表面背对光源

\[ L_d = k_d \cdot \max(0, \hat{n} \cdot \hat{l}) \cdot I \]

• 夹角与朝向判断：\(\hat{n} \cdot \vec{v} > 0\) 说明观察方向与法线同侧（看到的是背面），可用于背面剔除、判断物体是否在相机前方
• 距离比较：\((\vec{a} - \vec{b}) \cdot (\vec{a} - \vec{b})\) 是距离的平方，比较远近或计算衰减时不必开平方，这是很常用的性能优化

1.2 Cross Product

叉乘（cross product / 外积）把两个向量映射成一个向量，新向量同时垂直于原来的两个向量

注意： 叉乘只在 3 维空间中有定义（7 维也有，但图形学用不到），2 维没有真正意义的叉乘，只有它的"标量退化版"（见下文）

定义（代数形式 / 行列式形式）：

\[ \vec{a} \times \vec{b} = \begin{vmatrix} \mathbf{i} & \mathbf{j} & \mathbf{k} \\ a_x & a_y & a_z \\ b_x & b_y & b_z \end{vmatrix} = \begin{pmatrix} a_yb_z - a_zb_y \\ a_zb_x - a_xb_z \\ a_xb_y - a_yb_x \end{pmatrix} \]

定义（几何形式）：设 \(\theta\) 为两向量的夹角，则叉乘的模长为

\[ |\vec{a} \times \vec{b}| = |\vec{a}||\vec{b}|\sin\theta \]

方向垂直于 \(\vec{a}, \vec{b}\) 所确定的平面，指向由 右手定则 确定：右手四指从 \(\vec{a}\) 弯向 \(\vec{b}\)，拇指指向即为 \(\vec{a} \times \vec{b}\) 的方向

性质

1. 反交换律： \(\vec{a} \times \vec{b} = -\vec{b} \times \vec{a}\)（顺序决定方向，顺序反过来方向也反过来）
2. 分配律： \(\vec{a} \times (\vec{b} + \vec{c}) = \vec{a} \times \vec{b} + \vec{a} \times \vec{c}\)
3. 数乘结合： \((k\vec{a}) \times \vec{b} = k(\vec{a} \times \vec{b})\)
4. 无结合律： \((\vec{a} \times \vec{b}) \times \vec{c} \neq \vec{a} \times (\vec{b} \times \vec{c})\)
5. 平行/共线： \(\vec{a} \times \vec{a} = \vec{0}\)；更一般地 \(\vec{a} \parallel \vec{b} \iff \vec{a} \times \vec{b} = \vec{0}\)
6. 垂直于两向量： \((\vec{a} \times \vec{b}) \cdot \vec{a} = (\vec{a} \times \vec{b}) \cdot \vec{b} = 0\)

1.2.1 几何意义：面积与法线

\(|\vec{a} \times \vec{b}|\) 等于以 \(\vec{a}, \vec{b}\) 为邻边的 平行四边形面积，因此

\[ S_{\text{平行四边形}} = |\vec{a} \times \vec{b}|, \qquad S_{\text{三角形}} = \dfrac{1}{2}|\vec{a} \times \vec{b}| \]

叉乘的结果与这两个向量都垂直，也就是"由平面上的两个向量造出该平面的法线"，这正是它在图形学中最重要的用途

1.2.2 图形学中的应用

• 求面法线：已知三角形的三个顶点 \(P_0, P_1, P_2\)，用两条边的叉乘即可得到法线（法线是光照、着色、阴影、背面剔除的基础）

\[ \vec{n} = (P_1 - P_0) \times (P_2 - P_0) \]

法线方向取决于顶点的绕序（逆时针 / 顺时针），而绕序决定表面朝向，也就决定了光照是否算得正确

• 判断点在直线的哪一侧（2D）：把 2D 向量看作 \(z = 0\) 的 3D 向量，叉乘结果只有 \(z\) 分量非零，可退化成标量

\[ \vec{a} \times \vec{b} = a_xb_y - a_yb_x \]

它的符号表示"\(\vec{b}\) 在 \(\vec{a}\) 的左侧还是右侧"，是光栅化判断三角形覆盖区域、点在多边形内测试、凸包等算法的基础

• 判断点在三角形内：若点 \(P\) 与顶点 \(P_2\) 在边 \(P_0P_1\) 的同一侧，且对三条边都成立，则 \(P\) 在三角形内；用叉乘的符号就能判断，这也是重心坐标的几何来源
• 构建局部坐标系：已知一个法线 \(\hat{n}\)，再任取一个参考方向，用两次叉乘就能得到一组互相垂直的单位基向量（切线空间、相机坐标系）
• 面积计算：三角形、多边形的面积，以及上面提到的符号判据

记忆方法

• 点乘看 \(\cos\)，衡量两个方向 有多像，所以结果是一个数
• 叉乘看 \(\sin\)，衡量两个方向 有多不像（张成了多大面积），所以结果是一个垂直的新向量

2 Affine Transformation

图形学中物体的摆放、相机的观察、投影到屏幕，最终都归结为对点坐标做一次矩阵乘法。缩放、旋转、切变这类变换可以用矩阵表示，但最常用的平移不能；把平移也纳入矩阵，就得到了 仿射变换（affine transformation）

2.1 Linear Transformation

定义： 一个变换 \(\mathbf{f}\) 如果满足可加性与齐次性

\[ \mathbf{f}(\vec{a} + \vec{b}) = \mathbf{f}(\vec{a}) + \mathbf{f}(\vec{b}), \qquad \mathbf{f}(k\vec{a}) = k\mathbf{f}(\vec{a}) \]

就称为线性变换。有限维空间中的线性变换总可写成矩阵形式 \(\vec{v}' = \mathbf{M}\vec{v}\)，所以 线性变换一定把原点映射到原点（\(\mathbf{M}\vec{0} = \vec{0}\)）。它的几何特征是：直线仍是直线、平行线仍平行、原点保持不动

2.1.1 常见的线性变换

变换	2D 矩阵	说明
缩放（scale）	\(\begin{pmatrix} s_x & 0 \\ 0 & s_y \end{pmatrix}\)	各轴独立放缩，\(s < 0\) 时含镜像
切变（shear）	\(\begin{pmatrix} 1 & a \\ 0 & 1 \end{pmatrix}\)	沿 \(x\) 方向按 \(y\) 成比例错切
旋转（rotate）	\(\begin{pmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{pmatrix}\)	绕原点逆时针旋转 \(\theta\)
反射（reflect）	\(\begin{pmatrix} -1 & 0 \\ 0 & 1 \end{pmatrix}\)	关于 \(y\) 轴镜像

3D 中旋转必须指定转轴，例如绕 \(z\) 轴旋转

\[ \mathbf{R}_z(\theta) = \begin{pmatrix} \cos\theta & -\sin\theta & 0 \\ \sin\theta & \cos\theta & 0 \\ 0 & 0 & 1 \end{pmatrix} \]

旋转矩阵是正交矩阵（\(\mathbf{R}^{-1} = \mathbf{R}^T\)，\(\det\mathbf{R} = 1\)），求逆只需转置，这在推导法线变换时很有用

2.2 Homogeneous Coordinates

2.2.1 为什么需要齐次坐标

平移 \(\vec{v}' = \vec{v} + \vec{t}\) 不是线性变换：只要 \(\vec{t} \neq \vec{0}\)，就有 \(\mathbf{f}(\vec{0}) = \vec{t} \neq \vec{0}\)，与"原点不动"矛盾，所以 它无法写成 \(2\times2\)（或 \(3\times3\)）矩阵。但图形学中平移无处不在（物体位置、相机位置、投影中心），因此需要一种能把平移也变成矩阵乘法的统一表示

解决办法是给坐标 再加一维，这就是 齐次坐标（homogeneous coordinates）：

• 点： \((x, y, z, 1)\)，平移会作用于它
• 向量： \((x, y, z, 0)\)，平移不作用于它（方向不应随平移改变）

一般地，齐次坐标 \((x, y, z, w)\) 在 \(w \neq 0\) 时表示 3D 点 \((x/w, y/w, z/w)\)。最后一个分量 \(w\) 区分了"点"和"向量"，也正是透视投影要做齐次除法的原因

为什么要区分点和向量

1. 点 − 点 = 向量，点 + 向量 = 点，向量 + 向量 = 向量，而点 + 点没有意义
2. 用 \(w = 1\) 与 \(w = 0\) 恰好能自动实现这套规则：只需看 \(w\) 分量相加的结果是 1 还是 0
3. 若给方向向量也填 \(w = 1\)，平移会"顺手"把方向改掉，光照、法线之类的计算全都会出错

2.2.2 平移与仿射变换的矩阵形式

仿射变换 = 线性变换 + 平移：

\[ \vec{v}' = \mathbf{A}\vec{v} + \vec{t} \]

用齐次坐标即可合并成一次矩阵乘法（3D 用 \(4\times4\) 矩阵）：

\[ \begin{pmatrix} \vec{v}' \\ 1 \end{pmatrix} = \begin{pmatrix} \mathbf{A} & \vec{t} \\ \mathbf{0}^T & 1 \end{pmatrix} \begin{pmatrix} \vec{v} \\ 1 \end{pmatrix} \]

\(4\times4\) 矩阵的四个分块各有明确含义：

分块	含义
左上 \(3\times3\)	线性部分：旋转、缩放、切变、反射
右上 \(3\times1\)	平移向量 \(\vec{t}\)
左下 \(1\times3\)	恒为 \(\mathbf{0}^T\)
右下 \(1\times1\)	恒为 \(1\)

仿射矩阵与透视矩阵的区别

看 最后一行：仿射矩阵的最后一行恒为 \((0, 0, 0, 1)\)，所以输入点的 \(w = 1\) 经过变换后 \(w\) 仍是 1，不发生齐次除法；而透视投影矩阵最后一行的前三个分量不为 0，变换后 \(w \neq 1\)，必须做齐次除法，于是 平行线会相交于灭点

性质

1. 保直线与平面： 直线映射后仍是直线，平面映射后仍是平面
2. 保平行： 平行线映射后仍然平行，这是仿射变换与透视投影最本质的区别
3. 保比例： 线段上的定比分点仍是定比分点，中点仍是中点；更一般地，仿射变换不改变重心坐标（见第 3 节）
4. 可复合： 仿射 × 仿射 = 仿射，所以可以把一串变换预先乘成一个矩阵，例如 \(\mathbf{M} = \mathbf{T}\mathbf{R}\mathbf{S}\)
5. 保长度与角度？ 一般不保。只有线性部分是正交矩阵的 刚体变换（rigid transformation） 才保长度和角度；等比缩放（相似变换）保角度但不保长度
6. 可逆： 只要 \(\det\mathbf{A} \neq 0\) 就可逆，且逆矩阵仍是仿射矩阵（左上为 \(\mathbf{A}^{-1}\)，右上为 \(-\mathbf{A}^{-1}\vec{t}\)）

2.2.3 图形学中的应用

• 场景图与物体摆放：局部坐标 → 世界坐标 → 相机坐标 → 裁剪空间，靠一串 \(4\times4\) 矩阵连乘得到，典型顺序是 \(\mathbf{M} = \mathbf{T}\mathbf{R}\mathbf{S}\)（先缩放、再旋转、最后平移）。注意 矩阵乘法不满足交换律，顺序写错结果完全不同
• 视图（相机）变换：把世界坐标搬到相机坐标系，本质是一次刚体变换，所以它的逆矩阵可以廉价地由转置得到
• 正交与透视投影：同样用 \(4\times4\) 矩阵实现，透视投影是唯一需要齐次除法的那一类
• 法线变换：顶点位置直接乘 \(\mathbf{M}\)，但法线要用 \(\mathbf{M}\) 左上 \(3\times3\) 部分的 逆转置 \(\mathbf{A}^{-T}\) 来变换，否则非等比缩放下法线不再垂直于表面

3 Barycentric Coordinates

3.1 Definition

仿射组合： 若一组点的线性组合 \(\sum_i\alpha_iP_i\) 满足系数之和为 1，即 \(\sum_i\alpha_i = 1\)，则称为仿射组合

定义： 设三角形的三个顶点为 \(A, B, C\)，若平面上一点 \(P\) 可写成

\[ P = \alpha A + \beta B + \gamma C, \qquad \alpha + \beta + \gamma = 1 \]

则 \((\alpha, \beta, \gamma)\) 称为 \(P\) 关于该三角形的 重心坐标（barycentric coordinates）

直观理解：把 \(\alpha, \beta, \gamma\) 看作三个顶点的 权重。约束 \(\alpha + \beta + \gamma = 1\) 保证结果是仿射组合，因此 重心坐标由三角形自身决定，与坐标系无关；也正因为有这个约束，三角形所在平面上的每个点都有唯一一组重心坐标（三点不共线时）

几个特例：

• 顶点的重心坐标就是单位坐标：\(A \leftrightarrow (1, 0, 0)\)，\(B \leftrightarrow (0, 1, 0)\)，\(C \leftrightarrow (0, 0, 1)\)
• 边 \(BC\) 上的点满足 \(\alpha = 0\)，重心坐标退化为 \(B, C\) 的一维线性插值 \(P = (1 - t)B + tC\)，即 \((0, 1 - t, t)\)
• 三角形重心（三条中线的交点）的坐标是 \(\left(\dfrac{1}{3}, \dfrac{1}{3}, \dfrac{1}{3}\right)\)，这也是"重心坐标"这个名字的来源

3.1.1 几何意义：面积比

\((\alpha, \beta, \gamma)\) 分别等于 \(P\) 与 对边 围成的小三角形面积与整个三角形面积之比：

\[ \alpha = \dfrac{S_{PBC}}{S_{ABC}}, \qquad \beta = \dfrac{S_{PCA}}{S_{ABC}}, \qquad \gamma = \dfrac{S_{PAB}}{S_{ABC}} \]

由此得到判断点与三角形位置关系的实用判据：

• 三个坐标都非负 \(\iff\) \(P\) 在三角形内（含边界）
• 某个坐标为 \(0\) 表示 \(P\) 落在对应的边上
• 出现负值表示 \(P\) 在三角形外

为什么面积比就是重心坐标

面积在仿射变换下按统一比例缩放，所以可以先用仿射变换把三角形搬到最简形式 \(\tilde{A} = (0, 0)\)，\(\tilde{B} = (1, 0)\)，\(\tilde{C} = (0, 1)\)

此时 \(P = (\beta, \gamma)\) 且 \(\alpha = 1 - \beta - \gamma\)，于是 \(S_{PBC} = \dfrac{1}{2}|1 - \beta - \gamma| = \dfrac{1}{2}\alpha\)，而 \(S_{ABC} = \dfrac{1}{2}\)，所以 \(S_{PBC} / S_{ABC} = \alpha\)。另外两个坐标同理

3.2 Computation

3.2.1 叉乘法（面积法）

2D 情况下，用 1.2 中的 2D 叉乘（标量）可以直接算出面积比。记 \(u \times v = u_xv_y - u_yv_x\)，令

\[ D = (B - A) \times (C - A) \]

则三个重心坐标为

\[ \alpha = \dfrac{(C - B) \times (P - B)}{D}, \qquad \beta = \dfrac{(A - C) \times (P - C)}{D}, \qquad \gamma = \dfrac{(B - A) \times (P - A)}{D} \]

三个分母都等于 \(2S_{ABC}\)（带符号面积），只需算一次。\(D\) 的符号由三角形的绕序决定，与 1.2.2 中判断点在直线哪一侧的符号判据是同一套东西

3.2.2 解线性方程组

把 \(P = \alpha A + \beta B + \gamma C\) 与 \(\alpha + \beta + \gamma = 1\) 联立并消去 \(\alpha\)，得到关于 \(\beta, \gamma\) 的 \(2\times2\) 方程组

\[ \begin{pmatrix} x_B - x_A & x_C - x_A \\ y_B - y_A & y_C - y_A \end{pmatrix} \begin{pmatrix} \beta \\ \gamma \end{pmatrix} = \begin{pmatrix} x_P - x_A \\ y_P - y_A \end{pmatrix} \]

解出 \(\beta, \gamma\) 后由 \(\alpha = 1 - \beta - \gamma\) 得到最后一个坐标。这其实就是解 \(\mathbf{T}\mathbf{x} = P - A\)，其中 \(\mathbf{T}\) 的两列是三角形的两条边向量，射线与三角形求交（Möller–Trumbore）等算法用的正是这个形式

3.2.3 图形学中的应用

• 顶点属性插值：\(f_P = \alpha f_A + \beta f_B + \gamma f_C\)，任何定义在顶点上的量（颜色、法线、纹理坐标、深度）都能这样插值，Gouraud 着色与纹理映射就建立在这条公式上
• 光栅化：对每个像素算出 \((\alpha, \beta, \gamma)\)，三个坐标都非负则该像素被三角形覆盖，同时顺便完成属性插值；实现上常用增量法递推，避免逐像素重复除法
• 射线与三角形求交：Möller–Trumbore 算法直接给出重心坐标，既判命中（坐标非负），又能立即插值交点处的法线与纹理坐标
• 细分与裁剪：在边上做线性插值生成新顶点（新顶点的重心坐标形如 \(\left(0, \dfrac{1}{2}, \dfrac{1}{2}\right)\)），把多边形剖分成三角形
• 仿射不变性：仿射变换不改变重心坐标，所以"先在局部坐标里算权重、再对世界坐标的顶点加权"与"先变换顶点、再算权重"结果完全一致

4 Point in Polygon

给定由 \(n\) 个顶点 \(P_0, P_1, \dots, P_{n-1}\) 按顺序首尾相接围成的闭合多边形（先假设不自交），以及平面上一点 \(Q\)，判断 \(Q\) 是否在多边形内部

凸多边形与凹多边形的判据完全不同：凸多边形可以用"点是否始终在所有边的同一侧"来判，凹多边形不行，必须用射线法或环绕数法

4.1 问题定义

约定： 多边形顶点按某一绕序（顺时针或逆时针）给出，边为 \(P_iP_{i+1}\)（下标对 \(n\) 取模）；"内部"是否包含边界要事先约定，通常实现里先单独判断边界情形

凸性判定

一个多边形是凸的 \(\iff\) 相邻两条边的叉乘符号全部一致（且没有退化的零长边），即 \(\text{cross}(P_{i+1} - P_i,\ P_{i+2} - P_{i+1})\) 对所有 \(i\) 同号

等价的说法是：任取一条边所在的直线把平面分成两半，其余所有顶点都落在同一半中。这正是凸多边形能使用"同侧"判据的原因

4.2 Convex Polygon

4.2.1 叉乘同侧判据

设顶点按 逆时针 排列。\(Q\) 在凸多边形内 \(\iff\) \(Q\) 位于每一条有向边 \(P_i \to P_{i+1}\) 的左侧：

\[ \text{cross}(P_{i+1} - P_i,\ Q - P_i) \ge 0 \qquad \forall i \in [0, n) \]

其中 2D 叉乘就是 1.2 中的标量形式 \(u \times v = u_xv_y - u_yv_x\)

• 若顶点按顺时针给出，则不等号整体反向（全部 \(\le 0\)）
• 结果等于 \(0\) 表示 \(Q\) 落在该边所在的直线上，再配合投影区间判断即可区分"在边上"与"在边的延长线上"
• 时间 \(O(n)\)、空间 \(O(1)\)，这是凸多边形上最快也最简单的做法

凸多边形可以更快

先把凸多边形按某个顶点扇状三角化，再用二分查找定位 \(Q\) 落在哪个扇区，最后在对应的那个三角形里用 3.1 的重心坐标判据确认，单次查询可以做到 \(O(\log n)\)。多边形固定而查询次数很多（例如反复拾取）时值得这么做

4.3 Concave Polygon

4.3.1 射线法（奇偶规则）

思想： 从 \(Q\) 向任意方向（实现里取正 \(x\) 方向）引一条射线，统计它与多边形边界的交点个数。由 Jordan 曲线定理，交点个数为奇数 \(\iff\) 在内部，为偶数 \(\iff\) 在外部——因为每穿过一次边界，就会从"内"翻到"外"（或反过来）

def point_in_polygon(poly, q):
    inside = False
    n = len(poly)
    for i in range(n):
        x1, y1 = poly[i]
        x2, y2 = poly[(i + 1) % n]

        # 半开区间：只有恰好一个端点严格高于 q.y 的边才算跨过这条水平线，
        # 这样射线穿过顶点时只会被统计一次，水平边也会被自动排除
        if (y1 > q.y) != (y2 > q.y):
            # 求边与水平线 y = q.y 的交点横坐标，只统计 q 右侧的交点
            x_int = x1 + (q.y - y1) * (x2 - x1) / (y2 - y1)
            if x_int > q.x:
                inside = not inside

    return inside

这里的 inside = not inside 就是在数交点个数的奇偶

4.3.2 非零环绕数

思想： 数多边形 绕过 \(Q\) 的净圈数，它比奇偶规则更贴近"轮廓实际把点围了几圈"的直觉。对每条跨越 \(Q\) 水平线的边，按跨越方向以及 \(Q\) 在边的哪一侧，给环绕数 \(w\) 加 1 或减 1

def cross(u, v):                      # 2D 叉乘（标量）
    return u[0] * v[1] - u[1] * v[0]

def winding_number(poly, q):
    wn = 0
    n = len(poly)
    for i in range(n):
        x1, y1 = poly[i]
        x2, y2 = poly[(i + 1) % n]
        edge = (x2 - x1, y2 - y1)
        to_q = (q.x - x1, q.y - y1)

        if y1 <= q.y:                            # 边的起点在水平线下方
            if y2 > q.y and cross(edge, to_q) > 0:
                wn += 1                          # 从下往上跨越，且 q 在边的左侧
        else:                                    # 边的起点在水平线上方
            if y2 <= q.y and cross(edge, to_q) < 0:
                wn -= 1                          # 从上往下跨越，且 q 在边的右侧

    return wn

• \(w \neq 0\) → 在内部；\(w = 0\) → 在外部
• 奇偶规则只看"穿了几次"，环绕数还看穿越的方向，所以两者在 自交多边形 上结论可能不同：五角星的中心区域被边界绕过 2 圈，奇偶规则判为外部，非零环绕数判为内部
• 代价是每条边都要多算一次叉乘，但它对方向不一致的轮廓（多个子路径拼接的图形、字体轮廓）更符合直觉

4.3.3 通用做法：三角化 + 重心坐标

凹多边形可以先 三角化（耳切法、单调剖分等）得到一组三角形，再用 3.1 的判据判断 \(Q\) 是否落在其中任一三角形内：

\[ Q \text{ 在多边形内} \iff \exists\, T_i \text{ 使得 } Q \text{ 在 } T_i \text{ 内（含边界）} \]

• 三角化只需做一次，之后每次查询遍历三角形（或配合层次结构加速），同一多边形被反复查询时最划算
• 这也解释了图形硬件为什么只处理三角形：一旦多边形变成三角形，"内外"判断就退化成一行重心坐标的符号判断

4.3.4 图形学中的应用

• 拾取（picking）：鼠标点选不规则区域、地图选区、UI 蒙版
• 裁剪与遮罩：判断像素或顶点是否落在给定的多边形区域内
• 碰撞检测预检：2D 物理中判断点是否落在某个碰撞体轮廓内部
• 字体与矢量图形填充：字形轮廓由多个子路径组成且可能自交，填充规则（even-odd 还是 non-zero）直接影响渲染结果
• 区域采样：只在多边形区域内做统计、绘制或纹理生成

方法对比与选择

方法	适用范围	单次查询时间	关键点
叉乘同侧判据	仅凸多边形	\(O(n)\)	最简单最快，凹多边形上会给错
二分 + 重心坐标	仅凸多边形	\(O(\log n)\)	多边形固定、查询频繁时用
射线法（奇偶）	任意简单多边形	\(O(n)\)	必须正确处理顶点与水平边
非零环绕数	任意多边形（含自交）	\(O(n)\)	与填充规则一致，符号与绕序有关
三角化 + 重心坐标	任意多边形	\(O(\log n)\) 到 \(O(n)\)	预处理 \(O(n)\)，多次查询最划算

5 Curves and Surfaces

图形学里的"形状"最终都要落到某种数学描述上：曲线 是一维的点集，曲面 是二维的点集。同一个几何体往往有多种写法，用哪种形式取决于你要对它做什么操作（判断内外？求交？遍历生成网格？还是只为渲染？）

下面四种形式在图形学里反复出现，它们是同一件事的四种"视角"

5.1 Explicit Form

显式形式 是最熟悉的写法：把一个变量直接用其余变量表示出来

\[ \text{曲线：}\ y = f(x), \qquad \text{曲面：}\ z = f(x, y) \]

• 优点：求值最直接，给定 \(x\)（或 \((x, y)\)）立刻算出 \(y\)（或 \(z\)），描点、生成高度图都非常方便
• 缺点：一个 \(x\) 只能对应一个 \(y\)，所以圆、椭圆这类多值曲线必须拆成两段 \(y = \pm\sqrt{r^2 - x^2}\)
• 缺点：无法表示竖直线 \(x = c\)，也写不出任何带垂直切线的部分
• 缺点：曲面 \(z = f(x, y)\) 本质是 高度场（height field），表示不了闭合曲面——球面只能写成上下两半
• 缺点：与坐标轴绑定，旋转一下方程就得重写

因此显式形式主要用在高度图、地形、位移贴图这些天然"单值"的场景

5.2 Implicit Form

隐式形式 把所有项移到一边，用"等于零"的方程来刻画点集

\[ \text{曲线：}\ f(x, y) = 0, \qquad \text{曲面：}\ f(x, y, z) = 0 \]

思路和显式完全不同：不关心怎么走到曲线上，只关心一个点满不满足方程

优点：

• 内外判断极其便宜，把点代进 \(f\) 看符号即可（\(f < 0\) 在内、\(f > 0\) 在外），这是碰撞检测、裁剪、符号距离场（SDF）的基础
• 求交直接，把射线的参数形式 \(\mathbf{p}(t) = \mathbf{o} + t\mathbf{d}\) 代入 \(f = 0\) 就得到关于 \(t\) 的方程（球面情形就是一个二次方程）
• 能表示 多值、闭合、任意朝向 的曲线与曲面
• 法线就是 梯度 \(\nabla f\)，归一化后直接用于光照

缺点：

• "求点"是反问题，需要解方程，通常有多个根，要配合符号变化来定位
• 想采样、画线，得用步进算法（marching squares / marching cubes），不能像参数形式那样让参数递增
• 很难从方程直观控制形状的走向和局部细节

5.3 Parametric Form

参数形式 把曲线、曲面看成"参数域到空间的映射"：

\[ \text{曲线：}\ \mathbf{p}(t) = \big(x(t),\ y(t)\big), \qquad \mathbf{p}(t) = \big(x(t),\ y(t),\ z(t)\big), \qquad t \in [a, b] \]

\[ \text{曲面：}\ \mathbf{p}(u, v) = \big(x(u, v),\ y(u, v),\ z(u, v)\big), \qquad (u, v) \in [0, 1]^2 \]

曲线是一个参数的一维映射，曲面是两个参数的二维映射，这也是"曲线是 1D、曲面是 2D"这句话的确切含义

优点：

• 生成点最容易，让 \(t\)（或 \((u, v)\)）走一遍就得到一串点，画折线、铺网格都是这么来的
• 切向量与法线可以求导得到，曲线切线是 \(\mathbf{p}'(t)\)，曲面法线是 \(\dfrac{\partial\mathbf{p}}{\partial u} \times \dfrac{\partial\mathbf{p}}{\partial v}\)，光照、着色、偏移都依赖它
• 参数 \((u, v)\) 天然就是 纹理坐标，采样纹理、插值顶点属性都用它
• 与坐标系无关，可以整体做仿射变换（第 2 节）
• 能表示多值曲线与闭合曲线（如圆），还能给曲线规定方向

缺点：

• 内外判断困难，不能像隐式那样算个符号就完事，往往要反解参数
• 参数化不唯一、参数速度不均匀，同一个几何体有无穷多种参数化，按参数等间隔采样并不等于几何上均匀分布（均匀采样要做弧长参数化）

一个方程还是两个参数

这里有一条规律：余维（codimension）。一个方程只能"削掉"一个自由度，所以 2D 中的曲线、3D 中的曲面都只需要一个隐式方程；而参数化的参数个数等于形状自身的维数，所以曲线要 1 个参数、曲面要 2 个参数

推论：3D 中想用隐式形式表示 曲线，需要两个方程联立（例如两曲面求交），因为曲线在 3D 中的余维是 2

5.4 Piecewise Form

分段形式 不追求用一个公式描述整个形状，而是 把复杂的曲线、曲面拆成若干简单片段，每段用低次多项式（通常是参数形式）表示，并在接缝处维持连续性

• 曲线：折线（每段是线段，piecewise linear）、Bézier 曲线、B-spline、NURBS
• 曲面：三角网格（每片是平面三角形）、Bézier patch、细分曲面（subdivision surface）

以三次 Bézier 曲线为例，一段曲线由 4 个控制点决定：

\[ \mathbf{p}(t) = (1 - t)^3\mathbf{p}_0 + 3t(1 - t)^2\mathbf{p}_1 + 3t^2(1 - t)\mathbf{p}_2 + t^3\mathbf{p}_3, \qquad t \in [0, 1] \]

把许多这样的段首尾相接、并要求接缝处光滑，就得到样条（spline），这正是 CAD 与矢量字体里"曲线"的标准做法

• 为什么必须分段：单个低次多项式能力有限，既要多个拐点又要光滑就得上高次，而高次多项式既会振荡（Runge 现象）又极难控制
• 好处一：局部性，修改一个控制点只影响相邻的几段，便于交互式编辑
• 好处二：用低次多项式拼出任意复杂形状，求值、求导、求交都很便宜

• 连续性 的几个层次：

  • \(C^0\)：位置连续，两段接上了
  • \(G^1\)：几何连续，切线方向一致（看起来光滑）
  • \(C^1\)：参数连续，切线方向一致且切向量本身也相等（比 \(G^1\) 更强）

四种形式的对比

形式	曲线	曲面	擅长	短板
显式	\(y = f(x)\)	\(z = f(x, y)\)	求值、高度场	多值形状、竖直线、闭合曲面
隐式	\(f(x, y) = 0\)	\(f(x, y, z) = 0\)	判内外、求交、梯度求法线	求点困难、采样要额外算法
参数	\(\mathbf{p}(t)\)	\(\mathbf{p}(u, v)\)	生成点、网格化、纹理坐标、求导	判内外困难、参数速度不均匀
分段	折线 / Bézier / B-spline	三角网格 / patch	复杂形状 + 局部编辑	接缝连续性要额外维护

5.5 示例：球

同一个球有好几种写法，正好说明"形式的选择取决于操作"：

形式	表达式	适合做什么
隐式	\(x^2 + y^2 + z^2 - r^2 = 0\)	判内外、光线求交、碰撞检测
参数	\((\sin\phi\cos\theta,\ \sin\phi\sin\theta,\ \cos\phi)\)	生成网格、贴纹理
显式	\(z = \pm\sqrt{r^2 - x^2 - y^2}\)	只能表示上、下半球，基本不用
分段	大量三角形拼出来	交给 GPU 光栅化

5.6 图形学中的应用

• 光线求交：隐式形式最省事（射线代入解关于 \(t\) 的方程）；参数曲面要解 \(f(\mathbf{p}(u, v)) = 0\)，更麻烦，所以求交常用隐式或最简单的分段形式——三角形
• 渲染与网格化：参数形式 + 分段形式，用细分（tessellation）把 patch 拆成三角形
• 法线与光照：参数曲面用 \(\mathbf{p}_u \times \mathbf{p}_v\)，隐式曲面用梯度 \(\nabla f\)
• 纹理映射：参数 \((u, v)\) 直接当纹理坐标用
• 建模：Bézier / B-spline / NURBS 都是"参数 + 分段"的组合
• SDF 与碰撞：隐式（符号距离场）在实时渲染与物理中有大量应用
• 硬件的现实：GPU 只会光栅化三角形，所以 任何曲线曲面最终都要被离散成分段的三角网格

评论区

欢迎在评论区指出文档错误，为文档提供宝贵意见，或写下你的疑问