5. 几何
5. 几何
鲸拓工作室本系列的主要目的是复盘并总结计算机图形学这个学科常用算法与原理，会从基本的数学理论讲起，同时会附带部分算法的代码实现，由浅入深，只需初中的数学基础就行。主要参考了GAMES101-现代计算机图形学入门这门课（具体引用见文章末尾），同时附加上自己的理解。有兴趣的也可直接看视频。
几何
学完了上面这些东西之后，我们已经能够把一些简单模型渲染出来了。但是你可能也想过，如果模型都是三角形组成的话，那不会有瓶颈么？对于一些复杂或特殊的模型怎么办呢？比如下图，还是用三角形硬刚吗？
很明显，这玩意很难用三角形组装起来。这个时候，我们就可以引入一些几何方法了。
隐式表达
隐式表达，也就是字面意思，你并不知道实际的点在哪里，只知道点与模型之间的关系。就比如说一个球的隐式表达式是这样的：
隐式表达有好处也有坏处，你可以很容易的判断一个点是否在表面，内部或者外部，但是想对它采样却很困难。
显式表达
与之相对的是显式表达，它会用uv的方式，告诉你模型上的所有的点，但是与之相应的，你很难知道其他的点是在模型内还是模型外
几何这一块，目前还真没有什么完美的解决办法，只能根据场景来选择合适的模型
距离方程
啥是距离方程呢？我们先来看看它的应用。假如我们要模拟这个过程，应该怎么做呢？
这是一个融合的过程，大致思路是判断它们之间的距离，然后融合在一块。理解起来蛮简单，但是似乎不好用数学方法表达出来。这个时候就要用到距离方程了，距离方程说白了就是记录了空间中的某个点到物体表面的距离。来看下图
说起来复杂，但是看起来是不是还挺好理解的。距离方程中，0所在的区域就是物理的表面，+表示该点在物体外面，-代表该点在物体内部。我们只需要把混合后的距离方程还原出来，就能得到融合之后的模型了。
其实，距离方程除了能用在物体融合上，它还有很强的表现力。两个简单模型的融合就能得到复杂的效果，如下图，基本你能看到的东西都是用距离方程搞出来的
距离方程的本质是一个隐式表达，除了用公式，还可以用水平集的方式，如下图
很直观，就是用一个网格来记录距离
贝塞尔曲线
曲线的作用自不必说，不论是静态的图片，还是三维动画，都需要绘制无数曲线。这里就介绍一种典型的曲线定义方法，贝塞尔曲线
我们先来直观的了解一下贝塞尔曲线是个啥，见下图
曲线的起点和终点我们都知道，贝塞尔曲线中的核心其实就是那两个控制点，那么它们是怎么控制一个曲线的呢？我们先来看只有一个控制点的情况
图中的
通过上面的方法确定了
理解了上面一个控制点的原理，那再加一个控制点就也没问题了，无非就是多做一次插值而已
下面的动画可以用来帮助理解（如果是pdf看不了的话，可以去网页上看）
了解了几何原理之后，我们需要用数学公式表达出来，也不难，就是插值的不断叠加
将其拓展到n阶的话，就是下面这样
其中
举个小例子，大家可以自行验算
下面是贝塞尔曲线的几个性质
- 必须经过起点和终点
- 曲线的方向永远朝向终点
- 仿射变换下保持不变
- 永远在控制点形成的凸包内
至于凸包是什么：就是几个控制点围成的最小多边形
几段不同的贝塞尔曲线可以连接成一个逐段曲线，如下图
但是可以发现，连接点的那一块会显得比较突兀。如果想要连续性的话，就需要两个控制点在同一条线上，且他们之间的距离要相等
曲面
了解了怎么形成曲线之后，是不是觉得曲线也不远了？其实曲面，无非就是不同的曲线的合集嘛，见下面的动图，你会秒懂的
原理就是先画出几条曲线，然后再在几个曲线之间做插值
几何处理
所谓几何处理，就是把现有模型做一些优化。比如说我们可以通过模型细分，给模型更加更多细节；简化则可以降低复杂度；而正则化就是优化三角形，使之变得规整（正则化的原理暂时先不讲，了解概念就行）
细分
细分的核心思想就是引入更多的三角形，使模型变得更加光滑。
有这么一种细分的方法，叫Loop Subdivision（虽然叫loop，但和循环可没有关系）。它是通过区分新、老顶点，采用先细分后调整的方法来做的。具体是这么个操作：
对于新顶点，我们一般是在一条边上选取一个新点，然后根据它周围的点来做加权平均，以此更新他的位置
对于老顶点，我们需要同时考虑老顶点本身所在的位置，和其他邻居的位置，从而确定最终更新的位置，具体的更新算法如下
下图是细分的结果，看起来还是很不错的
我们除了对三角形进行细分外，还能对网格进行细分，下面来介绍一种典型的网格细分方法，叫Catmull-Clark Subdivision
在此之前先定义一个概念，叫奇异点，所谓奇异点，就是度不为4的点
通过上图所示的细分过程，我们仅需要做一次细分，就会神奇的发现所有的非四边形都消失了，而奇异点的数量有所增加
再做一次细分，会发现依旧不会出现非四边形，并且奇异点的数量也不会再有变化
多次细分之后，模型会变得越来越光滑
Catmull-Clark Subdivision的数学表示方法如下，也很容易理解，这里就不做详细分析
这种细分方法可用于多种不同的面，来看看它的效果，还是非常不错的
简化
说完细分就该说简化了，简化的目的也很明确。很多时候我们不需要模型的密度那么高，只用能辨别这是个啥就OK。就比如打游戏的时候，我们其实并不关心远处某一个桌子上的摆件一样，扫一眼，知道那里有个东西就行了。
下图是具体的简化效果，三角形从30000到3000，其实也没有很多变化。哪怕是300，我们也能清晰的分辨出这是个头骨
简化的方法也很形象，叫边坍缩
看起来很直观，但是我们需要考虑两个问题：
- 我们该坍缩哪条边呢？
- 坍缩后的顶点放在哪里呢？
如果按照直观的想法，坍缩后的点，自然要根据它周围几个点来做平均。确实很直观，但是问题也很明显
如上图，我们会看到平均之后，这个面，会直接缩下去。这不是我们想要的。
于是就引入了二次度量误差来一次解决这两个问题
这里采用了机器学习的思想，所谓二次度量误差，就是取一个点，让这个点到其他面的距离最小
我们需要计算每一条边坍缩之后的点，及其这个点所带来的二次度量误差，然后取误差最小的点进行坍缩；随后更新其他受影响的点，再接着继续坍缩其他误差最小的点。
很明显这里用到了贪心的思想，可能最终解并不是最优的，但是通过观察结果，发现简化的结果还是相当不错的
