计算机图形学基础(6)——几何

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

几何表示

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

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

  • 隐式几何表示(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 条贝塞尔曲线上的点作为控制点,绘制贝塞尔曲线。以此类推,最终得到一个贝塞尔曲面。

曲面处理

根据上述绘制算法,我们可以得到基于多边形网格的曲面。在实际应用中,我们会对曲面进行进一步的处理。常见的曲面处理操作有以下两种:

  • 网格细分(Mesh Subdivision)
  • 网格简化(Mesh Simplification)

网格细分

网格细分就是把一个多边形拆分成多个多边形。这里我们介绍两种细分算法:Loop 细分和 Catmull-Clark 细分。

Loop 细分

Loop 细分只适用于三角形面的细分,具体可以分为两步:

  • 将一个三角形拆分成四个三角形
  • 更新新顶点和旧顶点的位置,使模型变得更加光滑

三角形的拆分非常简单,连接每条边的中点,即可将拆分成四个三角形,如下图所示。

对于新顶点的更新,它会基于周围四个旧顶点求加权平均,离它近的顶点权重大,设为 3/8,离它远的顶点权重小,设为 1/8,如下所示,白点为待更新的新顶点。

对于旧顶点的更新,它会基于周围几个旧顶点求加权平均,其中各个点的权重值与待更新点的度(Degree)有关,最终可以得到如下所示的更新方法。

Loop 细分只针对三角形面进行细分,整体效果如下所示。

Catmull-Clark 细分

相比对 Loop 细分,Catmull-Clark 细分是一种更加通用的细分方法,适用于各种多边形网格曲面。Catmull-Clark 细分涉及到一个概念 奇异点(Extraordinary Vertex),即度不为 4 的点。

Catmull-Clark 细分的第一步同样是拆分多边形,主要包含以下几点:

  • 对于边,取其中点;对于面,也取其一个点(比如:重心)
  • 连接边的中点和面的中点

我们可以发现,当对非四边形进行一次细分后,所有的非四边形都消失了。不过,一次细分后,会引入两个新的奇异点。

对于新顶点的更新,可以分为两种情况,分别边上的点和面中的点,其规则如下所示。

对于旧顶点的更新,其更新规则如下所示。

Catmull-Clark 适用于任何多边形网格面,整体效果如下所示。

网格简化

网格简化与网格细分正好相反,其目的是为了减少三角形数量,从而提升性能。对于近的物体三角形多,远的物体三角形少。

网格简化是通过 边坍缩(Edge Collapse)实现的,它会减少边的数量,并更新相关顶点的位置。

那么边坍缩的底层依据是什么呢?这里涉及到 二次度量误差(Quadirc Error Metrics)的概念。二次度量误差用来表示网格简化带来的误差大小,其计算方法是新顶点与它关联的面的垂直距离的平方和,如下图所示。

当删除一条边时,我们会引入一个新的顶点,当新顶点调整至二次度量误差最小时,我们将其设置为边坍缩后的新顶点。利用这种贪心思想,就能实现网格简化。

总结

本文我们主要介绍了计算机图形学中的几何相关部分。首先,我们介绍了几何的几种表示方法:隐式几何表示和显式集合表示,两者各自又有着很多实现方法。

然后,我们介绍了曲线,特别是贝塞尔曲线,详细介绍了其绘制算法 De Casteljau's Algorithm。由此延伸值曲面的绘制,特别是贝塞尔曲面。

最后,我们介绍了曲面的两种常见的处理方式:网格细分和网格简化。

至此,几何相关的内容均已介绍完毕。后续,我们将探讨光线追踪渲染器的相关内容。

参考

  1. 《GAMES 101》