# Geometry（几何）

在图形学中几何被分为了两类，一种是隐式几何（Implicit Geometry），另一种是显式几何（Explicit Geometry）。也就是说，我们有不同的方式来表示几何。

所谓隐式几何，即不会告诉你几何上具体的点在哪，而是告诉你这些点满足的一些关系，或者说满足特定关系的一些点都在一些什么样的表面上。

隐式几何有优点也有缺点，缺点就是我们不能直观的知道哪些点是满足这些条件的。也就是说，从式子上我们很难看出来它具体表示的结构。

而它的优点就是，我们通过表达式很容易就能判断一个给定的点在不在这个表面上以及判断它与几何之间的内外关系。

另外一种显式几何的表达方法，一种方式就是直接把表面上所有的点都表示出来，而另一种则是通过参数映射的方式定义的表面，例如上面定义了 uv 坐标，并且这个坐标系上的点都会映射到空间中某一个点，也就是说把 uv 坐标系下的点都走一遍之后，就可以得到空间中对应的所有的 (x,y,z)。

这里便是一个用到参数映射的一个例子。

但对于显式几何，用于判断某一点是在表面内还是在表面外就非常的困难了。

也就是说，几何并没有一个最好的表示的方式，而是根据我们实际任务的需要选出最合适的表示方式。

# More Implicit Representations in Computer Graphics

几何的表述方法远远不止上述提到的那些，我们先从隐式几何的表示方法来介绍。

最直接的方式便是用数学公式来表示，这种表示方式最严重的问题就是非常不直观。而且，对于相对简单的形状我们可以用数学公式来表达，但是如果像奶牛这种复杂的形体，用数学公式来表示好像就十分困难了。

当然几何的隐式表示也不止是通过代数方式来描述，其中一种叫 Constructive Solid Geometry，简称 CSG。它是通过一些基础几何的布尔运算来定义新的几何，例如这里的圆柱和球就是基本的几何。通过这种方式我们可以生成一些很复杂的几何，例如上图中的镂空筛子就是通过这些基础几何和布尔运算得到的。这种方式得到了非常广泛的应用，各种 DCC 软件基本都支持。

还有一种隐式的表达方法叫做 Distance Functions（距离函数）。对于任意一个几何，我们都不直接描述它的表面，而是描述任意一个点到这个表面的最近距离。上图中我们可以看到两个球，当这个两个球逐渐靠近以至于发生了形状上的融合，它们的拓扑结构会发生一些变化，实际上就是对几何的距离函数做了融合而形成的一个结果。

我们来看一个具体的例子。假设 A、B 两张图是表示某种几何的一个边界，有一个物体挡住了所能看到的视口的左侧的$1\over3$ 形成图 A，这个物体经过移动之后挡住了左侧的$2\over3$ 形成图 B。我们想要求出这个物体从左到右运动时的中间状态。如果我们仅仅只是把只是把两张图线性的 blend，得到便是右上角图的效果，这不是我们想要的结果，因为它不能表示运动的信息。要想得到正确的结果，我们要先求出图 A 和图 B 的符号距离函数，然后把这两张图再做一个 blend 操作，由于两张图在中间区域的正负性是相反的，最中间的地方 blend 后的结果为 0，再把这张图恢复成物体所表示的形状，值为 0 的地方是它的边界。通过 blend 两张图对应的 SDF，就相当于在 blend 它们的边界。

对于一些特定的情况，例如距离函数不太好写成解析的形式，也就是不太容易用式子去表示 SDF 的时候，这个距离函数只要能通过某种方法表示出来就可以了。这里便用到了一个叫做水平集的方法，思路和距离函数一样，只不过函数的表述写在了格子上，在格子上不同的位置表示了不同的值，我们只需要找到中间函数值为 0 的一些地方便可以把整个函数试图描述的一些地方的物体表面给提取出来。其实在地理上早就使用了这种概念，例如等高线。

水平集不一定要定义在二维空间的格子上，还可以定义在三维空间的格子上，而这就和我们之前所说的纹理联系上了。如果我们有一个三维的纹理表示了人体不同位置的密度，那么我们通过在水平集上查找相同密度的位置我们就可以找到一个表面。

同理，水花四溅时，水花之间结合在一起的这种关系我们如何描述也可以通过水平集或者距离函数的方式来得到融合之后的表面长什么样。

几何还有一种特殊的描述方法，叫做 Fractals（分形），分形指的是一种自相似的结构，物体的某个会和它的整体结构非常相似，跟计算机里面的递归属于同一种性质。

隐式的函数通常表述起来都很容易，要么拿一个函数直接来表示，要么是通过一些并不是特别明显的方式定义的，例如我们定义距离函数的时候。它不是明确的把表面上表示的点给写出来，也就是隐式的，这对于存储来说是非常有利的事情，通常用一个公式就能描述出物体的形状。同时，它还支持查询一个点在几何的里面还是外面。后面我们还会了解到，用隐函数描述的隐式表面是很容易做光线和它的求交的。还有一些拓扑结构也很适合用隐式方法来描述。当然，在面临一些复杂形体时用隐式方法描述起来就会有困难。

# Explicit Representations in Computer Graphics

显式的几何同样也有各种各样的方法去表示，例如三角形面、贝塞尔曲面、细分曲面、点云等等...

其中，最简单的一种物体表示方法就是点云。所谓点云，就是我们不考虑这个物体是一个表面，而是它表面的一堆点，当我们把这些点表示的足够细的时候，我们就看不到点和点之间的缝隙，就能看到表面这样一个概念。表示点云的方式也非常的简单，只需要一个记录各点 (x,y,z) 的一个列表。它的优缺点都已在上图列出。

我们用的最多的一种显式方法就是多边形面，这也是在图形学中应用的最多的一种几何的表示方法。任何面可以被拆成很多小的三角形或者四边形。当然这种方式就涉及到顶点之间的连接关系，自然就需要更复杂的数据结构来表示。

我们平时会用到.obj 格式的文件来存储由三角形面形成的模型，这种文件格式也被称作 Wavefront Object File，文件名后缀为.obj，是一个文本文件。它实际上只是把空间中的顶点、法线、纹理坐标的信息分开表示，然后再把它们组织起来形成一个模型。例如上图中 v 表示顶点信息，vn 代表各个面的法线信息，vt 代表纹理坐标，f 定义了各个信息之间的联系。这样一来我们就可以完美的定义一个模型所拥有的各种信息。

# Curves

# Bézier Curves（贝塞尔曲线）

贝塞尔曲线是用一系列控制点去定义某一个曲线，而这些控制点再定义曲线时满足一些性质，例如在上图中，曲线一开始从$p_0$ 点开始要沿着$p_0p_1$ 为切线方向往前走，同理，这个曲线要在$p_3$ 点结束，并且结束时是沿着$p_2p_3$ 这个方向往外走。至于这里为什么会有一个系数 3，我们在后面部分再来解释。总之，通过这个定义我们可以得到一个唯一的曲线。

# Evaluating Bézier Curves (de Casteljau Algorithm)

那么，我们用任意多个控制点，如何画出一条贝塞尔曲线？接下来我们要介绍的便是 de Casteljau 算法。

我们现在给定 3 个控制点，它生成的贝塞尔曲线叫做 Quadratic Bezier（二次贝塞尔曲线）。那么，怎么来画这样的一条线呢？首先，它一定要从$b_0$ 开始，并且要在$b_2$ 结束，并且$b_1$ 能决定曲线的弯曲程度，事实上就是这么回事，只不过我们需要一个更加精准的方法来控制它。假设我们可以定义这个曲线它的起点是在时间 0，然后它的终点是在时间 1，那么我们想要画出这条曲线，实则就是要把它的任意一个时间 t 这个点对应在曲线的哪个位置给找出来。怎么找到这个点呢？我们现在$b_0b_1$ 上找到相对于整个线段$t\over1$ 的位置，同样的在$b_1b_2$ 上也找相对于这个线段$t\over1$ 的位置，这样一来，我们便得到了$b_0^1$ 和$b_1^1$ 这两个点，再把这两个点连起来找相对于这条线段的$t\over1$ 的位置，得到了点$b_0^2$ 这样一个点。这一个点就是这条贝塞尔曲线在时间 t 形成的点的位置。看到这里可能会有这样一个疑问，为什么贝塞尔曲线算是显式表示的呢？显式定义要么是直接定义要么是通过参数定义，这里的 t 就是一个参数。我们想要画出一条完整的曲线，只要枚举所有的时间 t，只要能画出一个点，那么我们就能画出任意其它的点。

这听上去是一个递归的一个算法，我们每段找一个点，知道最后只剩下一个点，算法结束。上图这个例子给定了四个点，用这四个点定义一条贝塞尔曲线，我们同样用这样一个递归的方式来做，可以得到最后形成的曲线。

# Evaluating Bézier Curves Algebraic Formula

我们可以把贝塞尔曲线通过代数的形式给写出来。最后可以贝塞尔曲线在给定时间 t 是的函数表达给写出来，也就是$b_0^2(t)$。仔细观察会发现，这个式子实际上就是 1 的平方的展开式，准确的来说是 ((1-t)+t) 的平方。

贝塞尔曲线实际上就是一个多项式，给你 n+1 个控制点，我们可以得到一个 n 阶的贝塞尔曲线，这个贝塞尔曲线在任意时间 t 它都是之前给定的这些控制点的线性组合，它组合的系数就是一个多项式，这个多项式是跟时间有关的一个多项式，这个多项式叫做伯恩斯坦多项式（Bernstein Polynomial），这个多项式实际上就是描述二项分布的一个多项式。

这里有一个例子，这个例子想说明的是通过这样的一个推导，我们可以得到一些很多不错的性质，例如我们完全没有必要限制我们这些控制点在平面内，在空间中我们仍然能得到贝塞尔曲线，那么我们只需要把这些控制点输入成三维的坐标即可，我们同样还是用伯恩斯坦多项式去对它进行插值。这样我们成功的把 de Casteljau 算法用数字表示了出来。

伯恩斯坦多项式相对于对 1 自己的 n 阶展开，所以这个多项式在同一阶上把几个多项式的值加起来一定都等于 1，并且多项式存在两两对称的关系。通过定义一系列跟时间有关的多项式，来对不同的控制点进行插值，然后得出一个新的点，这个点就是曲线上的点。

贝塞尔曲线有一些独特的性质。首先，它必须过起点和终点，对于有 4 个控制点的贝塞尔曲线，还定义了起始和结束的切线方向和大小。其次，贝塞尔曲线可以直接对不同的顶点做仿射变换，然后对变换之后的顶点画一条曲线出来，这条曲线和之前的曲线是一样的，但对于投影就没有这个性质了。还有一条性质就是，最后形成的贝塞尔曲线一定在所有的控制点形成的凸包内。

所谓凸包，指的就是能够包围一系列给定的几何形体的最小的凸多边形。

# Piecewise Bézier Curves（逐段的贝塞尔曲线）

这里给了 11 个控制点，n=10，形成了 10 个线段，每个线段都取时间 t，一直做到只剩一个线段，最后找到了 1 个点，虽然很费时，但是我们最终还是能画出这条贝塞尔曲线。但是这种方式并不直观，而且不太利于控制。

我们其实不需要用这么多的控制点去定义一条贝塞尔曲线，我们其实还可以每次用很少的控制点去定义一段贝塞尔曲线，在把每段贝塞尔曲线给连起来，也就是逐段定义的贝塞尔曲线。人们常常会用每 4 个控制点来定义一段贝塞尔曲线（Piecewise cubic Bézier）。

这里画出来的就是分段的三次贝塞尔曲线。要想保证整个贝塞尔曲线是光滑（连续）的，我们就得保证分段处的切线方向共线，并且外侧的两个控制点到中间的控制点要是等距离的，我们就说这两段区域是连续的。

其实连续性有更准确的定义。如果有前一段的终止点等于后一段的起点，我们就把这种连续叫做$C^0$ 连续。

如果切线方向共线，并且上图标出的两段红色的线段距离是一样的，我们就称这种连续性为$C^1$ 连续。

图形学上还有一些别的曲线表示方法，例如 Spline（样条）。简单来说，一条可控的曲线就叫做样条。

样条里面用到比较多的叫做 B - 样条，指的就是基函数样条。基函数可以理解成例如用伯恩斯坦多项式在时间 t 它的几个不同的项对不同的控制点做一个加权平均，也可以理解成用控制点的位置对伯恩斯坦多项式进行一个加权求和，那么伯恩斯坦多项式就是一个基函数。就相当于由不同的函数通过不同的方式组合起来，可以形成别的函数，这些函数就是基函数。B - 样条是对贝塞尔曲线的扩展，它比贝塞尔曲线的能力更强。我们刚刚看到拥有 11 个控制点的贝塞尔曲线，如果我们动了一个点，整个曲线在任何一个位置都会发生变化，而这在设计上都是我们不太想要的一个性质。我们有时觉得曲线的大多数部分都挺好的，就只有一个地方需要改一改，也就是说我们想要局部性。所谓局部性指的是改变一个点，我们能知道这个控制点至多能影响这条曲线在哪个范围内。B - 样条就有这样的功能，我们前面讲的分段贝塞尔曲线也能做到这种事情，但是 B - 样条不需要分段。

# Bézier Surfaces

作为概念上的延伸，我们不仅可以定义贝塞尔曲线，还可以定义贝塞尔曲面。

我们现在要考虑的事情是如何用贝塞尔曲线得到贝塞尔曲面。对于上图的曲面来说，可以理解成它原本是一个平面，中间有一个力把它给拉上去了。这个曲面实际上是通过 4×4 个控制点得到的。

如何得到这个曲面，还是可以结合我们之前双线性插值的理解来理解它。在两个方向上我们分别应用贝塞尔曲线就可以了。首先，我们现在平面上定义 4×4 的控制点，把它看成 4 行，每一行拿出 4 个控制点得到一条贝塞尔曲线，我们可以得到这样的 4 条贝塞尔曲线，这些曲线在不同的时间 t 会对应曲线上不同的点，我们再把这些得到的 4 个点认为是在另外一条贝塞尔曲线上的控制点我们又可以得到一条贝塞尔曲线，当我们把时间 t 内的点都扫过一遍之后就可以得到一个贝塞尔曲面。

# Evaluating Bézier Surfaces

我们想找到贝塞尔曲面上任意的一个点，我们通过刚才的过程来看需要两个不同的时间 t，也就是我们要一个二维的控制，这里我们把它叫做 uv。

最后在曲面上找出的点就是曲面在 uv 这个参数下的位置，也就是说我们可以把在范围 0~1 的参数 uv 映射到了曲面上任意一个点，这也同样说明了为什么贝塞尔曲线是显式的表示，因为它是通过参数映射过去的。

我们一开始就提到，用来表示空间中的面或者说几何形体，用的最多的还是 Mesh（网格），无论是用三角形网格还是四边形网格，既然我们用网格来描述空间中的表面，自然而然我们对它也会有一系列操作，例如网格的细分、网格的简化、网格的规格化（最后一张图）等。

# Mesh Subdivsion（细分）

我们在之前讲位移贴图时也提到过细分，位移贴图需要用很多的三角形满足纹理上对各个顶点的移动，所以我们需要细分，而且是可以做一个动态的细分的。如何引入更多的三角形就是我们之后要提到的各种各样的算法。我们所说的细分一般分为两个部分。第一，分出更多的三角形；第二，让这些三角形的位置发生一点变化使得原来的模型变得更光滑。

以 Loop 细分为例，我们连接三角形的三个中点形成一个新的三角形，而且这个中间的三角形又把原本的三角形分出了 3 个三角形，总共形成了 4 个三角形。这就是 Loop 细分的拆分方法。接着我们需要调整三角形顶点的位置，Loop 细分把三角形顶点分为了新的顶点和旧的顶点，新的顶点指的就是细分之后产生的顶点，其余的顶点为旧的顶点。Loop 细分分别来改变这两种顶点的位置。注意，这里的 Loop 和循环没有关系，仅仅是一个名称而已。接下来我们来看看如何如何来分别调整这两类顶点的位置。

我们先来看怎么更新新的顶点的位置，这里以上图中间的白点为例，这个点的位置会被调整到${3\over8}*(A+B)+{1\over8}*(C+D)$，这里做了一个加权平均。

对于旧的顶点，这里同样以图中的白点为例，首先，这个点肯定和周围的点有关系，周围这就旧的顶点也会有所贡献。Loop 细分认为一部分相信周围这些旧的顶点的平均值，另外一部分会相信自己（保留自己的位置属性）。这里我们会定义顶点的度 n（和数据结构中的图论类似）以及另外一个数 u。如果这个白点连了很多个三角形，那么它其实完全就可以依赖周围的点来决定各种各样的信息来更新它自己，也就是说这个点自身的那一部分就不太重要了。如果这个白点只连了两个三角形，那么就说明这个白点非常的重要，如果要更新它的话，更多的就要相信它自己。

我们现在来介绍另外一种细分方法，叫做 Catmull-Clark 细分，我们刚刚所说的 Loop 细分只能对三角形网格做细分，而对于更加一般的情况，我们就要使用 Catmull-Clark 细分。先定义一些概念，我们定义 Quad Face（四边形面）、Non-quad Face（非四边形面）以及 Extraordinary Vertex（奇异点，度不为 4 的点都叫奇异点）。上图中紫色的点都是奇异点。怎么做细分呢？每一条边都取它的中点，每一个面也取它中间的一个点，并且把边上的中点和面上的点连起来。

经过了一次细分之后现在还有多少个奇异点呢？我们发现在三角形中点上的点，由于它要和三条边分别相连，因此有两个点的度数都是 3，也就是我们引入了两个新的奇异点，现在就总共有了 4 个奇异点。我们会发现这样一个特点，在非四边形内新增的一个点，由于要和周围的每条边相连，所以形成的这个点一定是个奇异点。而经过了这样的一次细分之后，我们发现四边形面全部都消失了。

之后的每一次细分，我们发现都不会增加奇异点的数量了。

我们现在已经知道怎么通过 Catmull-Clark 细分增加新的点了，现在要知道该怎么调整它。Catmull-Clark 把顶点分成了 3 类：Face Point（在面的中间的点）、Edge Point（边的中心的点）、Vertex Point（以前那些旧的点）。

# Mesh Simplification

曲面的简化，即减少三角形的数量。通常这么做是为了提高程序的性能，有时为了照顾例如移动端的计算我们不得不用简化的模型。还有一些情况，例如模型离我们很远时我们并不需要那么精细的模型，离我们比较近的时候用比较精细的模型。也就是有时候我们会根据距离的远近选择不同精度的模型，这同样也涉及到曲面的简化。

其中一种简化的方法叫作边坍缩（Edge Collapse）。找到一条边，把这条边所连的两个顶点往中间一捏，把它捏成一个顶点，这个边就不存在了，这种操作就叫做边坍缩。

边坍缩在实际的做法中并没有那么容易，比如我要坍缩哪些边？我们需要判断哪些边是重要的，哪些边不重要可以进行坍缩。这个问题我们就需要用到 Quadric Error Metrics（二次误差度量）。我们先看左下角这幅图，假设我们想要把中间的三个顶点简化成一个顶点，把这个顶点放在哪才能保证蓝色的三角形和原本灰色的多边形基本保证它们轮廓形状的一致。如果做平均（求 5 个点的平均）我们发现效果并不好，即使用中间 3 个点也没有太大的改善。于是，人们引入了二次误差度量，我们想要把这个点放在某个位置上可以最小化二次误差，这个新的点和原本的几个面都有关系，现在就求这个点到原本这几个面它们距离的平方和，我们希望把这个点放置在一个位置，使得这个点到它相关联面的距离平方和达到最小，这便是二次误差度量。

有了二次误差度量，我们要如何取坍缩这条边是我们现在要讨论的事情。如果我们有一条边，把它坍缩成一个点之后，我们可以移动这个点的位置，使得坍缩对原本的这些面造成的影响最小，即求出一个最小的二次度量误差。对于整个模型有那么多条边，我们都假设如果坍缩这条边并且把坍缩形成的点放在最佳的位置上，记录得到的二次度量误差。每一条边我们都记录得到的这个值。现在我们就有一个算法，我们每次都选这个二次度量误差最小的这个边进行坍缩，然后坍缩第二小、第三小以此类推。这种方式也会存在一些问题，当我们坍缩一条边之后，有一些边会跟着这条边受到影响，这个时候，这些边的二次度量误差就得重新计算了。也就是我们现在做的是这样一种操作：我们要在所有的边当中选出二次度量误差最小的那个边，当我们坍缩完这条边之后要对它所影响的这些边的二次度量误差更新，也就是说，我们需要一种数据结构能够保证我们能够取到最小值，又可以动态的以最小的代价更新其它这些受影响的元素，这个时候我们很容易就会想到 “堆（也叫优先队列）” 这种数据结构。

我们希望找到其实是全局上能够表示原本的这个物体它的轮廓的简化表示，而现在我们是在任意一个局部，任意一个边附近找它的最优值，我们在试图不断的对局部做最优解来找到一个全局的最优解，这种做法实际上是一个典型的贪心算法。这并不是一个能保证全局最优性的一种做法，但实际上我们这种做法得到的效果挺不错的，于是就这么做了。毕竟图形学第一定律告诉我们：这个东西如果看上去是对的，那么它就是对的。