第九章：几何图元

几何图元，就是构成几何物体的最小单元。这章节我们将对它们进行讨论。

1.表示技术

如何用数学的方式来描绘物体？是的，用函数。
我们可以用一个布尔函数$f(x,y,z)$以隐含形式进行描绘，当传入空间中的一点的坐标时，只有当这点属于那个物体时才会返回真；
还有一种叫描述方式是参数形式，我们传入一个参数$t$，在$t$的范围内，随着$t$值的变化，会返回不同的坐标，它们就构成了物体的形状；
最后还有一种是直接形式，也是最常见的。就是以描述对象的主要信息为核心来描绘。比如，用两个点描述线段、用半径和球心描述球体等。

2.直线和射线

我们小学就知道3种基本的线性段类型：

直线，可在两个方向上无限延伸；
射线，是具有原点并在一个方向上可以无限延伸；
线段，是具有两个端点的直线的有限部分；

在计算机科学中，射线的定义有了些变化——射线是有向的线段。也就是说它也有一个起点和一个终点。也因此，它可以定义位置、有限长度和方向，也成为了计数几何和图形中的重要组成部分。

根据新的射线定义，我们可以这么来表示射线：

\[p(t)=\vec{p_0}+t\vec{d} \]

其中 $\vec{p_0}$ 是矢量表示的射线原点的坐标，$\vec{d}$ 是射线延伸的方向和长度，而 $t$ 限制在$[0,1]$内。当然，也可以稍微变形成下面这种形式：

\[p(t)=\vec{p_0}+t\hat{d} \]

这时，$t$的范围就可以变为$[0,l]$并且用来表示射线长度。

至于直线(介绍的内容仅用于二维)，则可以用一阶线性函数的方式表示：

\[y = kx + y_0 \]

这是熟悉的斜截式表达，但不能表示直线垂直时的情况。所以我们将它以隐含形式改写：$$ ax + by = d$$如果让矢量$\vec{p}=[x,y]$，$\vec{n}=[a,b]$，就可以得到用矢量表示的直线定义：

\[\vec{p}·\vec{n}=d \]

什么意思呢？说的就是从 $p$ 点到原点的距离在 $\vec{n}$ 方向的投影长度为 $d$ 的所有点的集合。

3.球体和圆形

球体(圆形同理)的表示很简单，只需要描述中心 $\vec{c}$ 和半径 $r$：

\[\begin{Vmatrix} \vec{p} - \vec{c}\end{Vmatrix} = r \]

$\vec{p}$ 表示球面任意一点，将它化为坐标形式就得到了隐式定义：$$(p_x-c_x)^2 + (p_y-c_x)^2 + (p_z - c_Z)^2= r^2$$

4.包围盒

「包围体」是用于近似复杂几何对象的大小的简单几何体，球体因其简单的表示和旋转不变的特点，被应用于简单的包围体，称为 「包围球」，而另一种同样有此应用的是 「包围盒」，它是一个简单的长方体。

包围盒有两种：一种是与体坐标轴轴向对齐的包围盒（英文缩写AABB），另一种是与世界坐标轴对齐的定向的包围盒（英文缩写OBB）。我们将围绕前者进行讨论，因为后者与前者的差异仅在与包围盒对齐的坐标空间，完全可以将它看成是特殊的AABB，并且前者更易于创建和使用。

接下来介绍一下AABB的表示方法。我们只需记录两个具有特殊意义的顶点：

\[\vec{p}_{min}=[x_{min},y_{min},z_{min}],　\vec{p}_{max}=[x_{max},y_{max},z_{max}] \]

包围盒的任意一点坐标都不会超出二者，它们实际上就是包围盒的一条体对角线（具体哪条要看坐标空间）的两端。
根据这两点，我们就可以直接获得其它的6个包围盒顶点，从而定义整个包围盒，而且还可以利用它们计算包围盒的中心点、包围盒的长宽高等等。

相比包围球，AABB主要有以下优点：

计算一个物体的包围盒比计算包围球更简单（可自行搜索计算包围球的算法哦）。
AABB可以提供更紧密、贴合物体的包围体。毕竟包围盒拥有长宽高三个可分配的自由度，比起包围球单单只有半径，确实更好适配物体。

当然，具体情况还要具体分析，并没有哪种绝对好的说法（否则早就被淘汰了）。

有时我们需要获取一个物体在另一个坐标空间下的AABB，这一般不会选择在新坐标空间下重新计算对象的AABB，而是对已有的AABB进行变换。~~（应该能听懂吧~~

经过变换后的包围盒通常会比原本的大（因为需要对齐的轴向不同了，适配的尺寸就会相应调整），我们可以利用原本的AABB快速生成新的AABB。只需要抓住原本的 $\vec{p}_{min}$ 和 $\vec{p}_{max}$，通过以下伪代码的逻辑，我们即可根据变换矩阵 $m$ 的各个元素直接算出新的 $\vec{p}_{min}$ 和 $\vec{p}_{max}$，从而得到新的AABB：

////min和max初始化变换矩阵的平移值，也就是4x4矩阵中的最后一行
min = max = getTransition(m);
//接下来的变换只需考虑3x3部分即可
for(i = 1; i <= 3; ++i)
{
    if(m.mi1 > 0.0f)//mij表示变换矩阵第i行第1列的元素，它们用于变换x
    {
        min.x += m.mi1 * box.min.x;
        max.x += m.mi1 * box.max.x; 
    }
    else
    {
        min.x += m.mi1 * box.max.x;
        max.x += m.mi1 * box.min.x;
    }
    if(m.mi2 > 0.0f)//mij表示变换矩阵第i行第1列的元素，它们用于变换x
    {
        min.y += m.mi2 * box.min.y;
        max.y += m.mi2 * box.max.y;
    }
    else
    {
        min.y += m.mi2 * box.max.y;
        max.y += m.mi2 * box.min.y;
    }
    if(m.mi3 > 0.0f)//mij表示变换矩阵第i行第1列的元素，它们用于变换x
    {
        min.z += m.mi3 * box.min.z;
        max.z += m.mi3 * box.max.z;
    }
    else
    {
        min.z += m.mi3 * box.max.z;
        max.z += m.mi3 * box.min.z;
    }
}

5.平面

模仿直线的隐含形式定义的逻辑，将它扩展到三维，我们就得到了以隐含形式表达的平面：

\[ax + by + cz = d（标量表达法） \]

\[\vec{p} · \vec{n} = d（矢量表达法） \]

我们同样也可以（通常也确实这么做）将 $\vec{n}$ 设置成单位矢量，这可以便利于一些相关计算。

还有一个我们初中就学过的定义平面的方法：3个非共线点（两条不平行的直线）就可以指定一个平面。

但偶尔我们会想要计算一组超过3个点的平面方程，而这些点，可能并没有那么规矩，这时我们就需要 “最佳拟合”平面 的方法。
假设有这么一组点 $\vec{p}_1$、$\vec{p}_2$……$\vec{p}_n$。
首先计算最佳拟合平面的法线 $\vec{n}$（这里利用到了叉积，所以不要对为什么既有加号又有减号感到奇怪啊）：

\[n_x = \sum_{i=1}^n(z_i+z_{i+1})(y_i-y_{i+1}), \]

\[n_y = \sum_{i=1}^n(x_i+x_{i+1})(z_i-z_{i+1}), \]

\[n_z = \sum_{i=1}^n(y_i+y_{i+1})(x_i-x_{i+1}) \]

然后计算最佳拟合 $d$ 值：

\[d = \frac{1}{n}\sum_{i=1}^n(\vec{p}_i·\vec{n}) = \frac{1}{n}(\sum_{i=1}^n\vec{p})·\vec{n} \]

6.三角形

三角形在建模和图形中具有基础意义上的重要性，复杂三维对象的表面都是由多个三角形近似而来的。

要定义一个三角形，只需要记录3个顶点就可以。但这些点的顺序是很重要的，它们会决定这个三角形的正反面（就是涉及法线的计算）。

三角形的周长和面积我们小学就会计算了，但这里要再聊聊面积的计算。由于我们记录的是三角形的3个顶点的坐标，所以并不能直接获取三角形的高，这时我们可以看看另一种单独通过顶点计算思路（仅用于2维的三角形，3维有其它方法）：

如上图，你应该能发现，无论什么形状的三角形，将3个顶点向下沿至x轴，都能得到一大两小，共三个直角梯形，在上图就是s3大，s1、s2小。那用s3-（s1+s2）就可以得到三角形的面积了。考虑到正负号的问题，我们可以用下式进行计算：

垂直平移三角形并不会影响它的面积，并且可以简化计算，比如让三角形的一个顶点的 $y$ 移至$y = 0$的位置就可以少算一个式子，所以，最终我们可以得到计算公式：

而在三维中，利用叉积（小复习：叉积结果的大小 = 两矢量构成的平行四边形面积）就可以得到三角形。给定来自三角形的两个边矢量 $\vec{e}_1$ 和 $\vec{e}_2$，它的面积：

\[A = \frac{\begin{Vmatrix} \vec{e}_1 \times \vec{e}_2 \end{Vmatrix}}{2}\]

为了更好求得三角形所在平面的任意点，我们需要一个三角形表面相关但独立于三角形“存在”的坐标空间，重心空间就是这样一个坐标空间，它在图形学中应用也十分广泛。
三角形平面中的任意点都可以表示为顶点的加权平均值，这些加权称为重心坐标。下面看看将标准笛卡尔坐标转换为重心坐标的方法。

在二维中，可以通过一组方程来解决：

而它最终可转化为子三角形面积比率的问题：

\[b_1 = \frac{A(T_1)}{A(T)},b_2 = \frac{A(T_2)}{A(T)},b_3 = \frac{A(T_3)}{A(T)} \]

在三维中，会有3个未知数和4个方程，将不能直接求解。一种办法是将三角形投影到3个基本平面之一，转化为2维计算。但不能随意投影，要考虑三角形可能出现在某平面的投影为0的情况，所以可以选择投影到具有最大绝对值的坐标所在基本平面，以保证投影面积最大化，；另一种是直接通过叉积来计算出子三角形的面积，它的计算量比前者稍大，但不需要if判断。

将重心坐标$(b_1,b_2,b_3)$与三个顶点相乘求和，就可以转换回标准笛卡尔坐标：

我们可以看看具体的例子：

不难发现，在重心空间下，三个顶点具有很简单的形式：$\vec{v_1} = (1,0,0)$、$\vec{v_2} = (0,1,0)$、$\vec{v_3} = (0,0,1)$；而在三角形之内的点坐标都在 $[0,1]$ 范围内，三角形外的任何点都至少有一个坐标。重心坐标可以将平面网格化为与原始三角形大小相同的三角形：