第七章

调查了几种常用的几何基元，并讨论了如何从数学上表示和操作它们。

表示技术 Representation Techniques

我们可以通过定义一个布尔函数 $f (x, y, z)$ 以隐式形式描述一个对象，该函数对于基元的所有点都为 true，对于所有其他点都为 false。如下描述的是一个球形。

x^{2} + y^{2} + z^{2} = 1

描述形状的另一种通用策略是参数形式。图元是由函数定义的，但空间坐标不是函数的输入，而是输出。例如

x (t) = cos 2 π t, y (t) = sin 2 π t .

参数 𝑡称为形参，与所使用的坐标系无关。随着 𝑡从 0 到 1 变化,点 x, y 描绘出我们正在描述的形状的轮廓。

直线和射线 Lines and Rays

在经典几何中，使用以下定义：

直线像两个方向无线延伸
线段是具有两个端点的直线的有限部分
射线是一条直线的“一半”，该直线具有原点并在一个方向上无限延伸。

但在本书中射线定义为有向线段。一条射线有一个原点和一个端点。因此，射线定义了位置、有限长度和方向（除非射线长度为零）。 //

射线 Rays

定义射线的方法是通过射线原点和射线端点我们将其表示为 $p_{org}$ 和 $p_{end}$ 。

p (t) = p_{0} + t d .

$p_{0}$ 包含有关射线的起始位置信息，"增量向量"d 包含其长度和方向，参数 t 限制在归一化范围 $[0, 1]$ 内，因此 $p_{end} = p (1) = p_{0} + d$ 。还可以对每个坐标分量单独写出方程:

x (t) = x_{0} + t Δ x, y (t) = y_{0} + t Δ y .

也有不同的参数定义方式，将 t 限制为 $[0, l]$ 射线长度，d 则仅代表单位射线方向。

直线的特殊二维表示 Special 2D Representations of Lines

斜截形式，这是一种表示二维无限直线的隐式方法：

y = m x + y_{0}

符号 𝑚是传统的符号，用于表示线的斜率，表示为上升与运行的比率：对于我们向上移动的每个上升单位，我们将向右移动运行单位。 y 轴截距是直线与 𝑦轴相交的位置，也是我们在方程中用 $y_{0}$ 表示的值。 // 以稍微不同的隐式形式来表示

a x + b y = d .

如果分配向量 $n = [a, b]$ ，我们可以使用向量符号将方程写为

p \cdot n = d .

// 其方程的几何解释为，向量 𝑛是与直线正交的单位向量， 𝑑给出从原点到直线的带符号距离。该距离是垂直于线（平行于 𝑛）测量的。

定义直线的最后一种方法是作为两点的垂直平分线，我们为其分配变量 q 和 r。这实际上是线的最早定义之一：距两个给定点等距的所有点的集合。 //

球和圆 Spheres and Circles

球体是一个 3D 对象，定义为距给定点固定距离的所有点的集合。从球心到一点的距离称为球体的半径。球体的直接表示是描述其中心 𝑐和半径 𝑟。

球体经常出现在计算几何和图形中，因为与球体相交的方程很简单，旋转球体不会改变其范围。因此，当边界球用于计算边界，如果球体的中心是对象的原点，则可以忽略对象的方向。

球体的隐式形式直接来自其定义：距中心给定距离的所有点的集合。以 𝑐为中心、 𝑟为半径的球体的隐式形式为

∥p - c∥ = r

其中 p 是球体表面的任意点，若要使得球体内部也满足方程，只需将 $=$ 更换为 $\leq$ 。作为圆的隐式定义。另一种更常见的形式是展开向量符号并对两边求平方：

(x - c_{x})^{2} + (y - c_{y})^{2} (x - c_{x})^{2} + (y - c_{y})^{2} + (z - c_{z})^{2} = r^{2} (2D circle) = r^{2} (3D sphere)

同时也给出球或圆的其他属性公式：

D C A S V = 2 r = 2 π r = π D = π r^{2} = 4 π r^{2} = \frac{4}{3} π r^{3} (diameter) (circumference) (area of circle) (surface area of sphere) (volume of sphere)

有趣的是，圆的面积相对于 𝑟的导数是周长，而球体体积的导数是表面积。

包围盒 Bounding Boxes

一种常用作包围体的简单几何基元是包围盒。边界框可以是轴向对齐的，也可以是任意方向的。轴向对齐的边界框有其侧面垂直于主轴的限制。首字母缩略词 AABB 通常用于表示轴向对齐的边界框。 //

另一个常用的缩写是 OBB，它代表定向边界框。轴向对齐的边界框更易于创建和使用。更重要的是，可以将 OBB 视为简单的具有方向的 AABB。每个边界框都是某个坐标空间中的 AABB。换句话说，AABB 和 OBB 之间的区别不在于框本身，而在于是否在与边界框对齐的坐标空间中执行计算。

AABB 表示

AABB 内的点满足不等式：

x_{min} \leq x \leq x_{ma x}, y_{min} \leq y \leq y_{ma x}, z_{min} \leq z \leq z_{ma x} .

两个具有特殊意义的角点是

p_{min} = [x_{min} y_{min} z_{min}], p_{ma x} = [x_{ma x} y_{ma x} z_{ma x}] .

中心点 c 由下式给出

c = (p_{min} + p_{ma x}) /2.

“大小向量（size vector）” s 是两个特殊点向量的差，包含盒子的宽度、高度和长度：

s = p_{ma x} - p_{min} .

"半径向量（radius vector）"是大小向量的一半，解释为中心点到最大点:

r = p_{ma x} - c = s/2 .

在 C 语言中，AABB 可以使用结构体来表示:

struct AABB3 {
    Vector3 min;
    Vector3 max;
};

计算 AABB Computing

计算一组点的 AABB 是一个简单的过程。我们首先将最小值和最大值重置为“无穷大”，或者实际上比我们在实践中遇到的任何数字都大的值。然后，我们遍历点列表，根据需要扩展框以包含每个点。

    public struct AABB3
    {
        public Vector3 min;
        public Vector3 max;

        /// <summary>
        /// 清空AABB
        /// </summary>
        public void Empty()
        {
            min.x = min.y = min.z = float.MaxValue;
            max.x = min.y = max.z = float.MinValue;
        }

        /// <summary>
        /// 添加单点
        /// </summary>
        /// <param name="p"></param>
        public void Add(ref Vector3 p)
        {
            if (p.x < min.x) { min.x = p.x; }
            if (p.x > max.x) { max.x = p.x; }
            if (p.y < min.y) { min.y = p.y; }
            if (p.y > max.y) { max.y = p.y; }
            if (p.z < min.z) { max.z = p.y; }
            if (p.z > max.z) { max.z = p.z; }
        }
    }

包围球 Bounding Spheres

在许多情况下选择使用 AABB 或包围球。 AABB 相对于边界球的第一个优点是计算一组点的最佳 AABB 易于编程并且可以在线性时间内运行。计算最佳边界球是一个更加困难的问题。 // 球体的基本问题是其形状只有一个自由度——球体的半径。 AABB 具有三个自由度——长度、宽度和高度。因此，它通常可以更好地适应不同形状的物体。

转换 AABB Transforming AABBs

假设我们在对象空间中有 AABB，并且希望在世界空间中获得 AABB，然而，我们假设对象形状的描述（可能是具有一千个顶点的三角形网格）比我们已经在对象空间中计算的 AABB 更复杂。因此，为了在世界空间中获得 AABB，我们将变换对象空间 AABB。

要计算转换后的 AABB 的 AABB，仅转换原始 $P_{min}$ 和 $P_{max}$ 是不够的。这可能会导致虚假的边界框。为了计算新的 AABB，我们必须变换八个角点，然后由这八个变换后的点形成 AABB。根据变换的不同，这通常会产生比原始边界框更大的边界框。 //

可以利用 AABB 的结构来加速新 AABB 的生成，因此不需要实际变换所有八个角点并从这些点构建新的 AABB。

public void SetToTransformedBox(ref AABB3 box,ref Matrix4x4 m){
    min = max = getTranslation(m);
    
    if (m.m00 > 0.0f) {
        min.x += m.m00 * box.min.x; max.x += m.m00 * box.max.x;
    } else {
        min.x += m.m00 * box.max.x; max.x += m.m00 * box.min.x;
    }
    
    if (m.m01 > 0.0f) {
        min.y += m.m01 * box.min.x; max.y += m.m01 * box.max.x;
    } else {
        min.y += m.m01 * box.max.x; max.y += m.m01 * box.min.x;
    }
    
    if (m.m12 > 0.0f) {
        min.z += m.m12 * box.min.x; max.z += m.m12 * box.max.x;
    } else {
        min.z += m.m12 * box.max.x; max.z += m.m12 * box.min.x;
    }
    
    if (m.m10 > 0.0f) {
        min.x += m.m10 * box.min.y; max.x += m.m10 * box.max.y;
    } else {
        min.x += m.m10 * box.max.y; max.x += m.m10 * box.min.y;
    }
    
    if (m.m11 > 0.0f) {
        min.y += m.m11 * box.min.y; max.y += m.m11 * box.max.y;
    } else {
        min.y += m.m11 * box.max.y; max.y += m.m11 * box.min.y;
    }
    
    if (m.m12 > 0.0f) {
        min.z += m.m12 * box.min.y; max.z += m.m12 * box.max.y;
    } else {
        min.z += m.m12 * box.max.y; max.z += m.m12 * box.min.y;
    }
    
    if (m.m20 > 0.0f) {
        min.x += m.m20 * box.min.z; max.x += m.m20 * box.max.z;
    } else {
        min.x += m.m20 * box.max.z; max.x += m.m20 * box.min.z;
    }
    
    if (m.m21 > 0.0f) {
        min.y += m.m21 * box.min.z; max.y += m.m21 * box.max.z;
    } else {
        min.y += m.m21 * box.max.z; max.y += m.m21 * box.min.z;
    }
    
    if (m.m22 > 0.0f) {
        min.z += m.m22 * box.min.z; max.z += m.m22 * box.max.z;
    } else {
        min.z += m.m22 * box.max.z; max.z += m.m22 * box.min.z;
    }
}

平面

平面是 3D 的平坦 2D 子空间，3D 中的平面与 2D 中的无限线共享许多属性。例如，它们都将空间细分为两个“半空间”。

平面隐式定义

可以使用类似于描述无限二维线的技术来表示平面。平面的隐式形式由满足平面方程的所有点 $p = (x, y, z)$ 给出：

a x + b y + cz p \cdot n = d (scalar notation), = d (vector notation).

向量 $n$ 称为平面法线，它垂直与平面。 $d$ 定义其位置，它确定在法线方向上测量的从原点到平面的带符号距离。增加 𝑑会使平面沿法线方向向前滑动。通常来说平面的正面是 $n$ 指向的方向。

三点定义平面

定义平面的另一种方法是给出位于平面上的三个不共线的点。 //

按照顺时针顺序构造两个向量

e_{3} = p_{2} - p_{1}, e_{1} = p_{3} - p_{2}, \hat{n} = \frac{e _{3} \times e _{1}}{∥ e _{3} \times e _{1} ∥} .

请注意，如果点共线，则 $e_{3}$ 和 $e_{1}$ 将平行，因此叉积将为 0，无法标准化。

多于三点的“最佳拟合”平面 “Best Fit”

有时我们会需要根据点集计算平面。取其中三点定义平面是较为简单的方法，根据选择的点连成线，它们的顺序极为重要，如果三点共线或者接近共线更为麻烦。一下介绍了一种计算公式，寻找最佳拟合垂直向量 $n$ 。

n_{x} n_{y} n_{z} = i = 1 \sum n (z_{i} + z_{i + 1}) (y_{i} - y_{i + 1}), = i = 1 \sum n (x_{i} + x_{i + 1}) (z_{i} - z_{i + 1}), = i = 1 \sum n (y_{i} + y_{i + 1}) (x_{i} - x_{i + 1}) .

❗注意这里使用循环索引，即 $p_{n + 1} = p_{1}$ 。如果我们希望强制执行 𝑛为单位长度的限制，则必须对该向量进行归一化。

public Vector3 ComputeBestFitNormal(Vector3[] v, int n)
{
    // 初始化结果向量为零向量
    Vector3 result = Vector3.zero;

    // 使用最后一个顶点作为"前一个"顶点
    Vector3 previous = v[n - 1];

    // 遍历顶点
    for (int i = 0; i < n; i++)
    {
        // 获取"当前"顶点的引用
        Vector3 current = v[i];

        // 适当地累加边向量乘积
        result.x += (previous.z + current.z) * (previous.y - current.y);
        result.y += (previous.x + current.x) * (previous.z - current.z);
        result.z += (previous.y + current.y) * (previous.x - current.x);

        // 更新"前一个"顶点为当前顶点
        previous = current;
    }

    // 归一化结果并返回
    result.Normalize();
    return result;
}

最佳拟合 d 值可以计算为每个点的 d 值的平均值：

d = \frac{1}{n} i = 1 \sum n (p_{i} \cdot n) = \frac{1}{n} (i = 1 \sum n p_{i}) \cdot n .

点到平面的距离 Distance

假设 p 是 q 到平面中距离最近的点，那么 pq 的距离 a 便是点到平面的距离。 // 假设平面法线 $\hat{n}$ 是单位向量，则从 p 到 q 的距离为：

p + a \hat{n} (p + a \hat{n}) \cdot \hat{n} p \cdot \hat{n} + (a \hat{n}) \cdot \hat{n} d + a a = q, = q \cdot \hat{n}, = q \cdot \hat{n}, = q \cdot \hat{n}, = q \cdot \hat{n} - d .

三角形 Triangles

复杂 3D 对象（例如汽车或人体）的表面由许多三角形近似。这样一组相连的三角形就形成了一个三角形网格。

三角形的面积 Area of a Triangle

从经典几何中，我们知道平行四边形的面积等于底与高的乘积，三角形为该平行四边形的面积一半。

A = bh /2.

如果高度未知，则可以使用海伦公式，该公式只需要三边的长度。令 𝑠等于周长的一半（也称为半周长）。然后面积由下式给出

s A = \frac{l _{1} + l _{2} + l _{3}}{2} = \frac{p}{2}, = s (s - l_{1}) (s - l_{2}) (s - l_{3}) .

Heron 公式同时可以应用到 3D 空间。空间中的三角形通常只包含顶点的迪卡尔坐标，根据坐标计算边长，进而计算面积是比较容易理解。但希望有一种方式单独根据顶点坐标计算面积避免更多相对昂贵的计算。

梯形面积计算法

2 D 中基本思想是，对于三角形的三个边中的每一个，计算梯形的有符号面积，该梯形的上方以该边为界，下方以 𝑥轴为界。“有符号面积”的意思是，如果边缘从左到右，则该面积为正，如果边缘从右到左，则该面积为负。 // 无论三角形的方向如何，始终都会有至少一条正边和至少一条负边。垂直边缘的面积为零。每条边下面积的公式为：

A (e_{1}) A (e_{2}) A (e_{3}) = \frac{( y _{3} + y _{2} ) ( x _{3} - x _{2} )}{2}, = \frac{( y _{1} + y _{3} ) ( x _{1} - x _{3} )}{2}, = \frac{( y _{2} + y _{1} ) ( x _{2} - x _{1} )}{2} .

通过对三个梯形的有符号面积求和，我们得出三角形本身的面积。事实上，同样的想法可以用来计算任意边数的多边形的面积。

A = A (e_{1}) + A (e_{2}) + A (e_{3}) = \frac{y _{1} ( x _{2} - x _{3} ) + y _{3} ( x _{3} - x _{1} ) + y _{3} ( x _{1} - x _{2} )}{2} .

该公式还能够进一步化简，我们任意选择垂直移动三角形，这并不影响三角形的面积，比如从每个 $y$ 坐标中减去 $y_{3}$ 。

A = \frac{y _{1} ( x _{2} - x _{3} ) + y _{2} ( x _{3} - x _{1} ) + y _{3} ( x _{1} - x _{2} )}{2} = \frac{( y _{1} - y _{3} ) ( x _{2} - x _{3} ) + ( y _{2} - y _{3} ) ( x _{3} - x _{1} ) + ( y _{3} - y _{2} ) ( x _{1} - x _{2} )}{2} = \frac{( y _{1} - y _{3} ) ( x _{2} - x _{3} ) + ( y _{2} - y _{3} ) ( x _{3} - x _{1} )}{2} .

叉积法

在 3D 中，我们可以使用叉积来计算三角形的面积。由于三角形的面积是封闭平行四边形面积的一半，因此我们有一个简单的方法来计算三角形的面积。给定三角形的两个边向量 $e_{1}$ 和 $e_{2}$ ，三角形的面积由下式给出

A = \frac{∥ e _{1} \times e _{2} ∥}{2} .

三角形的重心空间是一个与三角形表面相关且独立于三角形"所在"的 3D 空间的坐标空间。在图形中，通常按顶点编辑（或计算）参数，例如纹理坐标、颜色、表面法线、光照值等。然后，我们经常需要确定这些参数之一在三角形内任意位置的插值。重心坐标使这项任务变得容易。我们首先确定所讨论的内部点的重心坐标，然后对我们寻求的参数的顶点处的值进行加权平均值。另一个重要的例子是交叉测试。执行射线-三角形测试的一种简单方法是确定射线与包含三角形的无限平面的相交点，然后确定该点是否位于三角形内。

三角形平面上的任意点都可以表示为顶点的加权平均值。这些权重称为重心坐标。从重心坐标 $(b_{1}, b_{2}, b_{3})$ 到标准 3D 空间的转换定义为

(b_{1}, b_{2}, b_{3}) \equiv b_{1} v_{1} + b_{2} v_{2} + b_{3} v_{3} .

但重心坐标和普通笛卡尔坐标之间的细微区别在于，对于重心坐标，坐标之和被限制为单位：

b_{1} + b_{2} + b_{3} = 1.

这种归一化约束消除了一个自由度，这就是为什么即使有三个坐标，它仍然是一个二维空间。 //

请注意三角形的三个顶点在重心空间中具有普遍的形式：

(1, 0, 0) \equiv v_{1}, (0, 1, 0) \equiv v_{2}, (0, 0, 1) \equiv v_{3} .

顶点相对侧的所有点对应于该顶点的重心坐标都为零
平面上的任何点都可以用重心坐标来描述，而不仅仅是三角形内的点。三角形内点的重心坐标都在 [0,1] 范围内。三角形之外的任何一点都至少有一个负坐标。重心空间将平面细分为与原始三角形大小相同的三角形 //

还有另一种思考重心坐标的方法。丢弃 $b_{3}$ ，可以将 $(b_{1}, b_{2})$ 解释为常规 $(x, y)$ 2d 坐标，其中原点位于 $v_{3}$ 。

交叉测试中做出决定的一个简单方法是使用此处描述的技术计算该点的重心坐标。如果所有坐标都在 [0,1] 范围内，则该点在三角形内部；否则，至少有一个坐标位于该范围之外，并且该点位于三角形之外。

计算重心坐标 Calculating Barycentric Coordinates

❗需要注意的是“计算重心坐标”代表着计算点在重心空间中的坐标表示，并非计算三角形的“重心”代表的坐标。从二维笛卡尔坐标开始，标记三个顶点 $v_{1}, v_{2}, v_{3}$ 以及点 p, 三个子三角形 $T_{1}, T_{2}, T_{3}$ 它们与同一索引的顶点相对。 //

⎩ ⎨ ⎧ b_{1} x_{1} + b_{2} x_{2} + b_{3} x_{3} b_{1} y_{1} + b_{2} y_{2} + b_{3} y_{3} b_{1} + b_{2} + b_{3} = p_{x}, = p_{y}, = 1.

利用 [[#梯形面积计算法]] 中平移三角形的方式，使得 $v_{1}$ 为原点

⎩ ⎨ ⎧ b_{2} (x_{2} - x_{1}) + b_{3} (x_{3} - x_{1}) b_{2} (y_{2} - y_{1}) + b_{3} (y_{3} - y_{1}) b_{3} = p_{x} - x_{1}, = p_{y} - y_{1}, = 1 - b_{1} - b_{2} .

令 $A = v_{2} - v_{1}, B = v_{3} - v_{1}, C = P - v_{1}$ 得到：

\Rightarrow ⎩ ⎨ ⎧ b_{2} A_{x} + b_{3} B_{x} b_{2} A_{y} + b_{3} B_{y} b_{1} = C_{x}, = C_{y}, = 1 - b_{2} - b_{3} .

根据第一行求解得 $b_{2} = \frac{C _{x} - b _{3} B _{x}}{A _{x}}$ 带入第二行，并且根据该方式求得第二行 $b_{3}$ 带入第一行：

\Rightarrow ⎩ ⎨ ⎧ b_{2} b_{3} b_{1} = \frac{C _{x} B _{y} - C _{y} B _{x}}{A _{x} B _{y} - A _{y} B _{x}}, = \frac{C _{x} A _{y} - C _{y} A _{x}}{B _{x} A _{y} - B _{y} A _{x}}, = 1 - b_{2} - b_{3} .

根据向量叉乘公式和几何意义得到

\Rightarrow ⎩ ⎨ ⎧ b_{2} b_{3} b_{1} = \frac{∥ C \times B ∥}{∥ A \times B ∥} = \frac{∥ C \times A ∥}{∥ B \times A ∥} = 1 - b_{2} - b_{3} = \frac{A ( T _{2} )}{A ( T )} = \frac{A ( T _{3} )}{A ( T )}, = 1 - \frac{A ( T _{2} )}{A ( T )} - \frac{A ( T _{3} )}{A ( T )} = \frac{A ( T _{1} )}{A ( T )} .

3D 中计算推导该方程过于复杂，有效的技巧是只需丢弃 $x 、 y 、 z$ 之一即可将 3D 问题转换为 2D 问题。将三角形投影到三个基平面之一的效果。直观上，这是有效的，因为投影面积与原始面积成正比。此时需要关注得是坐标得丢弃影响投影平面的选择，三角形垂直和接近于垂直投影平面都会让其计算出现问题。解决这个困境的一个解决方案是选择投影平面以使投影三角形的面积最大化。这可以通过检查平面法线来完成，并且具有最大绝对值的坐标就是我们将丢弃的坐标。

/// <summary>
/// 计算任意 3D 点的重心空间坐标
/// </summary>
/// <param name="v">三角形的顶点</param>
/// <param name="p">平面上任意坐标坐标</param>
/// <param name="b">返回重心坐标</param>
/// <returns>在三角形平面上</returns>
public static bool ComputeBarycentricCoords3d(Vector3[] v, Vector3 p, out Vector3 b) {
    // 首先计算两条边向量
    Vector3 d1 = v[1] - v[0];
    Vector3 d2 = v[2] - v[1];

    // 计算三角形平面法线
    Vector3 n = Vector3.Cross(d1, d2);

    // 选择投影轴
    float u1, u2, u3, u4;
    float v1, v2, v3, v4;
    if (Math.Abs(n.x) >= Math.Abs(n.y) && Math.Abs(n.x) >= Math.Abs(n.z)) {

        // 丢弃x轴，投影到yz平面
        u1 = v[0].y - v[2].y;
        u2 = v[1].y - v[2].y;
        u3 = p.y - v[0].y;
        u4 = p.y - v[2].y;

        v1 = v[0].z - v[2].z;
        v2 = v[1].z - v[2].z;
        v3 = p.z - v[0].z;
        v4 = p.z - v[2].z;

    } else if (Math.Abs(n.y) >= Math.Abs(n.z)) {

        // 丢弃y轴投影到xz平面
        u1 = v[0].z - v[2].z;
        u2 = v[1].z - v[2].z;
        u3 = p.z - v[0].z;
        u4 = p.z - v[2].z;

        v1 = v[0].x - v[2].x;
        v2 = v[1].x - v[2].x;
        v3 = p.x - v[0].x;
        v4 = p.x - v[2].x;

    } else {

        // 丢弃z轴投影到xy平面
        u1 = v[0].x - v[2].x;
        u2 = v[1].x - v[2].x;
        u3 = p.x - v[0].x;
        u4 = p.x - v[2].x;

        v1 = v[0].y - v[2].y;
        v2 = v[1].y - v[2].y;
        v3 = p.y - v[0].y;
        v4 = p.y - v[2].y;
    }

    // 计算分母，检查是否无效
    float denom = v1 * u2 - v2 * u1;
    if (denom == 0.0f) {

        // 伪三角形 - 可能三角形的面积为零
        b = Vector3.zero;
        return false;
    }

    // 计算重心空间坐标
    float oneOverDenom = 1.0f / denom;
    b = new Vector3((v4 * u2 - v2 * u4) * oneOverDenom, (v1 * u3 - v3 * u1) * oneOverDenom, 1.0f - b[0] - b[1] );

    // OK
    return true;
}

然而以上方式有一个小问题，叉积的大小对顶点的顺序不敏感。这对三角形外的点不起作用。声明 $d_{1}, d_{2}, d_{3}$ 分别为顶点指向 p 的向量。 // 总结向量的方程，我们有

e_{1} d_{1} = v_{3} - v_{2}, = p - v_{1}, e_{2} d_{2} = v_{1} - v_{3}, = p - v_{2}, e_{3} d_{3} = v_{2} - v_{1}, = p - v_{3} .

现在整个三角形（我们简称为 𝑇）和三个子三角形的面积由下式给出：

A (T) A (T_{1}) A (T_{2}) A (T_{3}) = ∥ e_{1} \times e_{2} ∥ \cdot /2, = ∥ e_{1} \times d_{3} ∥ \cdot /2, = ∥ e_{2} \times d_{1} ∥ \cdot /2, = ∥ e_{3} \times d_{2} ∥ \cdot /2.

我们知道叉积的大小结果永远为正，但叉积得到的向量会有不同的朝向。增加垂直于平面的单位法向量 $\hat{n}$ ，与叉积结果向量点乘，将此结果除以二，就有了一种技巧来计算 3D 三角形的“有符号面积”。变化后的式子如下：

A (T) A (T_{1}) A (T_{2}) A (T_{3}) = ((e_{1} \times e_{2}) \cdot \hat{n}) /2, = ((e_{1} \times d_{3}) \cdot \hat{n}) /2, = ((e_{2} \times d_{1}) \cdot \hat{n}) /2, = ((e_{3} \times d_{2}) \cdot \hat{n}) /2.

每个重心坐标给出

b_{1} b_{2} b_{3} = A (T_{1}) / A (T) = \frac{( e _{1} \times d _{3} ) \cdot n ^}{( e _{1} \times e _{2} ) \cdot n ^}, = A (T_{2}) / A (T) = \frac{( e _{2} \times d _{1} ) \cdot n ^}{( e _{1} \times e _{2} ) \cdot n ^}, = A (T_{3}) / A (T) = \frac{( e _{3} \times d _{2} ) \cdot n ^}{( e _{1} \times e _{2} ) \cdot n ^} .

这种计算重心坐标的技术比投影到二维的方法涉及更多的标量数学运算。然而，它是无分支的，并提供更好的 SIMD 优化。

特殊点 Special Points

重心 center of gravity

重心是三角形完美平衡的点。它是中线的交点。（中线是从一个顶点到对边中点的一条线。） // 重心是三个顶点的几何平均值：

c_{Grav} = \frac{v _{1} + v _{2} + v _{3}}{3} .

重心的重心空间坐标是

(\frac{1}{3}, \frac{1}{3}, \frac{1}{3}) .

重心也称为质心。

中心 incenter

中心也称内心，是三角形中与边等距的点。它被称为内心，因为它是三角形内切圆的中心。内心被构造为角平分线的交点。 // 中心由下式计算

c_{In} = \frac{l _{1} v _{1} + l _{2} v _{2} + l _{3} v _{3}}{p}

其中 $p = l_{1} + l_{2} + l_{3}$ 是三角形的周长。因此，内心的重心空间坐标是

(\frac{l _{1}}{p}, \frac{l _{2}}{p}, \frac{l _{3}}{p})

内切圆的半径可以通过将三角形的面积除以周长来计算：

r_{I n} = \frac{A}{p} .

内切圆解决了求与三条直线相切的圆的问题。

外心 circumcenter

外心是三角形中与顶点等距的点。它是三角形外接圆的中心。外心被构造为边的垂直平分线的交点。 // 为了计算外心，我们首先定义以下中间值：

d_{1} d_{2} d_{3} c_{1} c_{2} c_{3} c = - e_{2} \cdot e_{3}, = - e_{3} \cdot e_{1}, = - e_{1} \cdot e_{2}, = d_{2} d_{3}, = d_{3} d_{1}, = d_{1} d_{2}, = c_{1} + c_{2} + c_{3} .

利用这些中间值，外心的重心坐标由下式给出

(\frac{c _{2} + c _{3}}{2 c}, \frac{c _{3} + c _{1}}{2 c}, \frac{c _{1} + c _{2}}{2 c})

因此，外心由下式给出

c_{Circ} = \frac{( c _{2} + c _{3} ) v _{1} + ( c _{3} + c _{1} ) v _{2} + ( c _{1} + c _{2} ) v _{3}}{2 c} .

外接圆半径由下式给出

r_{Circ} = \frac{( d _{1} + d _{2} ) ( d _{2} + d _{3} ) ( d _{3} + d _{1} ) / c}{2} .

外接半径和外心解决了寻找经过三点的圆的问题。

多边形 Polygons

一般来说，多边形是由顶点和边组成的平面对象。

简单多边形与复杂多边形 Simple versus Complex Polygons

简单多边形没有任何“孔”，而复杂多边形可能有孔。简单多边形可以通过按顺序枚举多边形周围的顶点来描述。简单多边形比复杂多边形使用得更频繁。

我们可以通过添加成对的“接缝”边将任何复杂的多边形变成简单的多边形。我们为每个接缝添加两条边。边缘实际上是重合的，尽管在特写镜头中它们已被分开以便您可以看到它们。当我们考虑围绕多边形排列的边时，两条接缝边指向相反的方向。 //

大多数简单多边形的边并不相互相交。如果边确实相交，则该多边形被视为自相交多边形。 //

凸多边形与凹多边形 Convex versus Concave Polygons

我们可以通过以下定义来识别凸多边形和凹多边形

直观上，凸多边形没有任何“凹痕”。凹多边形至少有一个“凹痕”顶点，称为凹点
在凸多边形中，多边形中任意两点之间的线完全包含在多边形内。在凹多边形中，多边形中至少有一对点，这些点之间的线部分位于多边形之外。
当我们绕凸多边形的周边移动时，在每个顶点我们都会朝相同的方向转动。在凹多边形中，我们将进行一些左转和一些右转。我们将在凹点处转向相反的方向。（请注意，这仅适用于非自相交多边形。）

任何凹多边形都可以分成凸块。基本思想是找到凹点（称为“反射顶点”）并通过添加对角线系统地删除它们。O'Rourke 提供了一种适用于简单多边形的算法，de Berg 等人。展示了一种更复杂的方法，也适用于复杂的多边形。

Joseph O'Rourke. Computational Geometry in C, Second edition. Cambridge, UK: Cambridge University Press, 1994. Peter Schorn and Frederick Fisher. “Testing the Convexity of a Polygon.” In Graphics Gems IV, edited by Paul S. Heckbert. San Diego: Academic Press Professional, 1994.

角度判断方式

如何知道多边形是凸多边形还是凹多边形？一种方法是检查顶点处的角度之和。考虑具有 𝑛顶点的凸多边形。凸多边形的内角和为 $(n - 2) 18 0^{\circ}$ 。

让 $θ_{i}$ 测量顶点 i 处的内角，如果多边形是凸多边形，则 $θ_{i} \leq 18 0^{\circ}$ ，每个顶点的“转动”量为 $18 0^{\circ} - θ_{i}$ 。凸多边形刚好围绕转动一整圈。所以

i = 1 \sum n (18 0^{\circ} - θ_{i}) n 18 0^{\circ} - i = 1 \sum n θ_{i} - i = 1 \sum n θ_{i} i = 1 \sum n θ_{i} i = 1 \sum n θ_{i} = 36 0^{\circ}, = 36 0^{\circ}, = 36 0^{\circ} - n 18 0^{\circ}, = n 18 0^{\circ} - 36 0^{\circ}, = (n - 2) 18 0^{\circ} .

但如果正确计算顶点处的内角，凸多边形和凹多边形总和一样，所以顶点角度值，使用点积法测量外角和内角中角度较小的一个。这样凹多边形的顶点角度值将小于 $(n - 2) 18 0^{\circ}$ 。

/// <summary>
/// 是凸多边形吗
/// </summary>
/// <param name="n">顶点数量</param>
/// <param name="vl">顶点数组</param>
/// <returns></returns>
public static bool IsPolygonConvex(in int n,in Vector3[] vl)
{
    //初始化角度和为0
    float angleSum = 0.0f;

    for (int i = 0; i < n; i++)
    {
        //或边缘矢量。 我们必须要小心循环顶点。
        Vector3 e1;
        if (i == 0)
        {
            e1 = vl[n - 1] - vl[i];
        }
        else
        {
            e1 = vl[i - 1] - vl[i];
        }
        
        Vector3 e2;
        if (i == n-1) 
        {
            e2 = vl[0] - vl[i];
        } 
        else 
        {
            e2 = vl[i+1] - vl[i];
        }
        //标准化计算点乘
        float dot = Vector3.Dot(e1.normalized, e2.normalized);
        //计算获取较小的的角
        float theta = Mathf.PI + Mathf.PI - Mathf.Asin(dot);
        //总和
        angleSum += theta;
    }
    //凸多边形正确弧度
    float convexAngleSum = (float)(n - 2) * Mathf.PI;
    //如果总弧度小于正确值，那他是凹多边形。由于浮点数的精度容忍一点计算偏差
    if (angleSum < convexAngleSum - (float)n * 0.0001f) {
        //凹多边形                
        return false;
    }

    return true;
}

确定凸性的另一种方法是搜索凹点的顶点。如果没有找到，则该多边形是凸多边形。基本思想是每个顶点应该朝相同的方向转动。任何向相反方向转动的顶点都是凹点。我们可以通过边向量的叉积来确定顶点转向的方向。叉积和法线的点积结果，正负能够反映向量旋转方向。当不确定是否是凸多边形的情况下，又无法简单地选择任意三个顶点来计算法线。这种情况下可以使用到 [[#多于三点的“最佳拟合”平面 “Best Fit”]]方法。

在 2D 中，我们可以简单地将多边形视为平面 𝑧=0处的 3D 多边形，并假设法线为 [0,0,−1]。

Peter Schorn and Frederick Fisher. “Testing the Convexity of a Polygon.” In Graphics Gems IV, edited by Paul S. Heckbert. San Diego: Academic Press Professional, 1994.

三角剖分 Triangulation

任何多边形都可以分成三角形。因此，三角形的所有运算和计算都可以分段应用于多边形。

对复杂的、自相交的、甚至简单的凹多边形进行三角剖分参考

Joseph O'Rourke. Computational Geometry in C, Second edition. Cambridge, UK: Cambridge University Press, 1994.

M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry—Algorithms and Applications. Springer-Verlag, 1997.

对简单的凸多边形进行三角剖分是较为容易的事。一种简单的技术是选择一个顶点，并围绕该顶点进行枚举，每两个点与选择点一起组成三角形。该技术被称为扇形三角剖分。 // 扇形往往会创建许多又长又细的条状三角形，这在某些情况下可能会很麻烦，例如计算表面法线。某些消费类硬件在将很长的边缘裁剪到视锥体时可能会遇到精度问题。存在更聪明的技术来尝试最小化这个问题。一种想法是按如下方式进行三角剖分：考虑我们可以将一个多边形分成两部分，两个顶点之间有一条对角线。当这种情况发生时，对角线顶点处的两个内角均被分成两个新的内角。因此，总共创建了四个新的内角。要细分多边形，请选择使这四个新内角中最小的一个最大化的对角线。使用这条对角线将多边形一分为二。递归地将过程应用于每一半，直到只剩下三角形。该算法产生具有较少条子的三角测量。相关技术还有 Bowyer-Watson 、delaunay 、Lawson 等三角剖分算法。

第六章

介绍了矩阵的几个更有趣和有用的性质，如仿射变换和透视投影，并解释了三维世界中四维向量和矩阵的目的和工作原理。

第八章

在三维中表示方向和角位移的不同技术：欧拉角、旋转矩阵、指数映射和四元数。

第七章