计算机图形学基础（6）——几何

发表于 2024-04-10 更新于 2024-04-11 分类于图形学 Waline：

前面我们介绍了观测变换、光栅化、着色等几个图形学中比较复杂的主题，本文我们稍微放松一下，介绍一个相对比较简单的主题——几何。

几何表示

通过图形学建模表示现实生活中的各种物体，要解决的第一个问题就是如何定义物体形状，而这就涉及到了几何。

物体的形状非常多，那么如何通过几何方法表示物体呢？对此，图形学中定义了两种几何表示方法：

隐式几何表示（Implicit Representations of Geometry）
显示几何表示（Explicit Representations of Geometry）

隐式几何表示

隐式几何表示是一种 使用数学关系式来描述几何形状 的方法，而不是直接描述其顶点和边界等元素。在隐式几何表示法中，几何形状被定义为方程的解集，即满足某些条件的一组点的集合。比如，下面的关系式定义了一个圆环结构。

\[\begin{aligned} f(x, y, z) = (2 - \sqrt{x^2 + y^2})^2 + z^2 - 1 \end{aligned}\]

隐式几何表示的常用技术有以下这些：

代数曲面（Algebraic Surface）
构造实体几何（Constructive Solid Geometry）
距离函数（Distance Function）
水平集（Level Set）
分形（Fractals）

下面，我们来介绍一下这些常用的隐式几何表示技术。

代数曲面

代数曲面是通过一组参数方程定义的曲线和表面。它适用于一些简单的，可以使用数学关系式表示的几何体。下图所示，这些几何体就比较适合使用代数曲面来表示。

构造实体几何

构造实体几何是通过布尔运算来组合不同的几何体。下图所示，一些复杂的几何体可以通过简单的几何体来组合构造。

距离函数

距离函数描述空间中任何一个点到几何体表面的最小距离。一种特殊的距离函数，符号距离函数（Signed Distance Function），其以空间中任意一个点作为输入，根据距离函数的返回值，可以进行判断：

当距离函数的值大于 0，表示点在几何体外部
当距离函数的值小于 0，表示点在几何体内部
当距离函数的值等于 0，表示点在几何体表面

水平集

对于表面规则的几何体，我们可以使用距离函数来表示；对于表面复杂的几何体，距离函数难以适用，此时，我们可以使用水平集来表示。

水平集的核心思想与距离函数一样，区别在于：距离函数使用通过输入空间点来计算该点到几何体表面的距离，水平集则存储了一系列距离值，我们可以通过插值法找到距离为 0 的位置，拟合出一条曲面用于表示几何体的表面。

分形

分形，类似于递归，即局部和整体的形状相似，如下图所示。分形通过迭代函数系统（IFS）来生成。IFS是一种迭代的过程，该过程将函数反复应用于某个起始点或起始数据。这些函数通常是缩放、旋转、平移等操作，同时保持自相似性。

显示几何表示

显式几何表示是一种 直接或间接（通过参数映射的方式）定义点、线、面等元素集合 的方法。在显式几何表示中，各元素的位置通常由坐标值直接给出，各元素之间的关系通常由数据结构来表示。比如，下面的关系式通过参数映射的方式间接定义了点的集合。

\[\begin{aligned} f: R^2 \rightarrow & R^3 \\ (u, v) \rightarrow & (x, y, z) \end{aligned}\]

显式几何表示的常用技术有以下这些：

点云（Point Cloud）
网格模型（Polygon Mesh）

下面，我们来介绍一下这两种显式几何表示技术。

点云

点云是显式几何表示中最简单的技术，其核心思想是使用大量的点来表示几何体的表面。点的密度越高，几何体的精度越高。由于点云的缺点很明显，内存占用大，因此一般会被再次转换成多边形网格。

多边形网格

多边形网格是图形学中最常用的几何表示方法，它存储点和多边形（一般是三角形或四边形），这种形式非常容易处理、模拟、采样。

在 3D 建模中，我们经常会用到 .obj 格式的模型文件，其本质上是一个文本文件，记录了顶点、法线、纹理坐标、连接关系，由此构成几何体的形状。如下所示，是一个立方体结构的表示。

v 表示顶点
vn 表示法线（多了两条是因为建模误差）
vt 表示纹理坐标
f 表示面，比如 f 5/1/1 1/2/1 4/3/1 表示三角形面是由第 5、1、4 个顶点组成，三个点的纹理坐标是第 1、2、3 对应的纹理坐标，面的法线是第 1 条法线。

曲线

曲线（Curves）在图形学中应用非常广泛，比如：相机的拍摄路径、物体的移动路径、动画曲线、矢量字体等。

贝塞尔曲线

贝塞尔曲线是通过一系列控制点进行定义的曲线。如下图所示，4 个控制点定义了一条贝塞尔曲线，起始方向沿着 \(p_0p_1\)，结束方向沿着 \(p_2p_3\)，曲线不必经过所有控制点，但必须经过起始点和结束点。

绘制算法

那么控制点是如何影响曲线的呢？贝塞尔曲线绘制算法的原理是什么呢？

贝塞尔曲线的绘制算法是 De Casteljau's Algorithm，算法的基本思想是利用线性插值的原理，将高阶贝塞尔曲线转化为一阶贝塞尔曲线的组合。对于一个 N 阶贝塞尔曲线，首先构建一系列的二维点，然后在这些点上构建线段，以此类推，直到计算出贝塞尔曲线上的一个点。重复这个过程就可以得到贝塞尔曲线上的所有点，从而绘制出完整的贝塞尔曲线。

下面，我们以 3 个控制点绘制贝塞尔曲线的例子来进行介绍。

N 个控制点绘制的贝塞尔曲线，称为 N-1 阶贝塞尔曲线。如下所示，我们定义了 3 个控制点，由此绘制的贝塞尔曲线称之为 二阶贝塞尔曲线（Quadratic Bezier）。对于这 3 个控制点，我们首先对相邻控制点进行连线。

我们定义一个变量 t，其值的范围为 [0, 1]，作为算法的输入值。当 t = 0 时，表示贝塞尔曲线起始点的输入值，当 t = 1 时，表示贝塞尔曲线结束点的输入值。随后，我们在控制点所构成的各个连线上定义一个点，这个点的位置取决于 t 的值，即一个比例值。比如：\(b_0b_1\) 连线上定义点 \(b_{0}^{1}\)，\(b_1b_2\) 连线上定义点 \(b_{1}^{1}\)。

然后，我们继续对 \(b_{0}^{1}\) 和 \(b_{1}^{1}\) 进行连线，并按照上述规则，在 \(b_{0}^{1}b_{1}^{1}\) 连线上定义点 \(b_{0}^{2}\)，如下图所示。

当新定义的点只有一个时，我们可以将 t 的值逐步从 0 变到 1。在这个过程中，\(b_{0}^{1}\)、\(b_{0}^{2}\)、\(b_{1}^{1}\) 的位置都会随着 t 的变化而变化。对于最终的贝塞尔曲线，我们只需要关注最后定义的点 \(b_{0}^{2}\) 的路径即可，如下所示。

当我们扩展至更多控制点时，比如 4 个控制点时，我们仍然按照上述规则来处理，将高阶贝塞尔曲线转化为一阶贝塞尔曲线的组合，最终绘制曲线。

代数公式

对于上述通过 3 个控制点绘制贝塞尔曲线，我们可以用代数的方式来表示，如下所示。

\[\begin{aligned} b_{0}^{1}(t) = & (1 - t)b_0 + tb_1 \\ b_{1}^{1}(t) = & (1 - t)b_1 + tb_2 \\ b_{0}^{2}(t) = & (1 - t)b_{0}^{1} + tb_{1}^{1} \\ b_{0}^{2}(t) = & (1 - t)^2b_0 + 2t(1 - t)b_1 + t^2b_2 \end{aligned}\]

由此，我们可以推导出 N 阶贝塞尔曲线的代数公式，如下所示。其中，\(n\) 表示 N 阶贝塞尔曲线，\(b_j\) 表示控制点，\(B_i^n(t)\) 为伯恩斯坦多项式（Bernstein Polynomials）。

\[\begin{aligned} b^n(t) = & b_{0}^{n}(t) = \sum_{j=0}^{n}b_jB_{j}^{n}(t) \\ B_i^n(t) = & \left( \begin{matrix} n \\ i \\ \end{matrix} \right) t^i(1-t)^{n-i} \end{aligned}\]

曲线性质

贝塞尔曲线具有以下几个特性：

一定过起点和终点。
不受仿射变换影响，受投影变换影响。
凸包（Convex Hull）性质：贝塞尔曲线在所有控制点的凸包范围内。

分段贝塞尔曲线

根据贝塞尔曲线绘制算法，我们可以知道，改变任意一个控制点的位置都会影响整个贝塞尔曲线。因此，当控制点比较多时，我们很难进行精准的控制和调整。于是就有了分段贝塞尔曲线，即采用多条贝塞尔曲线进行串联。

曲面

曲面（Surface）在图形学中应用同样非常广泛，可以用它来表示各种三维物体。

贝塞尔曲面

贝塞尔曲线控制点都是在同一平面内，由此进行扩展，贝塞尔曲面的控制点则是分部在三维空间中。下图所示，展示了空间中 4 x 4 个控制点所构成的贝塞尔曲面。

绘制算法

贝塞尔曲面的绘制算法本质上还是基于 De Casteljau's Algorithm 进行多次绘制。以下图为例，首先基于预设的所有控制点（比如：4 x 4 的控制点），绘制 4 条贝塞尔曲线。然后在与曲线垂直的平面中开始绘制曲线，按照固定间距，以 4 条贝塞尔曲线上的点作为控制点，绘制贝塞尔曲线。以此类推，最终得到一个贝塞尔曲面。