GAMES101 系列总结（五）：图形学中是如何表达几何体的

上一篇关于如何使用贴图的博客中我们讲了如何从贴图中提取我们想要的数据。

这篇博客我们先简单讲一下贴图的应用，然后从位移贴图过渡到集合体的表达。

几何体的应用方式

在GPU编程中，贴图就等于我们CPU编程中内存+范围查询，可以用贴图存储我们计算过程中的需要的数据并对数据进行范围查询。

所以贴图中不仅仅可以用来存储物体本身上点的颜色信息，还可以存储诸如环境信息，法线信息，位移信息等。

环境贴图

如下图所示，本来这个茶壶上对环境的反射需要是实时计算的，但是环境时无限远的，所以茶壶相对环境位置不变，这个反射结果也是不变的，所以我们可以提前计算好，然后保存在贴图中，在做渲染的时候，将茶壶本身的颜色贴图和环境贴图的采样结果进行混合就好。

凹凸贴图（法线贴图）

如果我们的几何体本身比较平滑，我们想要在平滑的表面山制造出凹凸感，比如在一个平面上制造出柏油马路的观感，可以采用凹凸贴图的方式，因为本身我们看到的所谓的凹凸感也是因为光线反射的角度不同导致的，我们可以直接在计算反射角的时候通过凹凸贴图加以干预就好。

位移贴图

刚才我们说可以通过凹凸贴图的方式来改变光滑表面的每个点的反射角度来制造凹凸感，那我们其实也可以直接通过位移贴图的方式，在渲染的时候真的就改变点的位置来改变渲染效果。

这种方式和凹凸贴图的区别是，凹凸贴图不改变点的位置，只是改变法线方向，而唯一贴图是直接改变点的位置，它存储的是对应点基于原本位置的位置。

那这里就涉及一个问题，我改变了位置，如何计算新的法线？

这里的位移贴图其实是一种几何体的表示方式，是一种显式表示方式

几何体的表示方式

我们有很多中不同的表示几何体的方式，但是主要分为两种，一种是显式的，一种是隐式的。

隐式的表示方式

所谓的隐式的方式，它表示的是集合体上的点所满足的关系，理论上我们找到所有满足关系的点，就可以得到这个几何体。

常见的隐式表示方式有：

• algebraic surface
• level sets
• distance functions

algebraic surface

对于隐式的表示方式来说，它表示的是集合上的点所满足的关系，所以它可以很简单的判断一个点是不是在几何体的面上，而他的缺点在于，你很难看出来它表示的是个什么东西，如下图

这里我们可能会产生一个疑问，那就是这种事方式是否只能表示比较简单且有规律的图形？

其实隐式的方式可以表示非常复杂的图形的，这里提供两个思路：

第一个思路是，如果我们学过高等数学，任何函数都可以傅立叶展开多个函数相加的方式，同样的，我们可以通过足够多的函数相加拟合出任何函数，只要你有这个知识储备且愿意花时间就好。

第二个思路，比较像我们在做图表时候的思路，用多个简单的图形的拼接或者剔除等方式(即布尔运算)来做，如下图所示：

distance functions

如图所示，这种方式是刚才我们说的第二个思路布尔运算的一种变体

符号距离函数（Signed Distance Function，简称 SDF）是一种在计算机图形学和几何处理中常用的数学表示方法。它用于描述一个点到某个形状表面的最短距离，同时包含了该点相对于形状表面的位置信息。SDF 的值可以是正数、负数或零：

1. 当点位于形状表面上时，SDF 的值为零。
2. 当点位于形状内部时，SDF 的值为负数，表示点到形状表面的最短距离。
3. 当点位于形状外部时，SDF 的值为正数，表示点到形状表面的最短距离。

SDF 在许多应用中都有广泛应用，如光线追踪、碰撞检测、流体模拟等。它的优点在于可以高效地计算点与形状之间的距离，同时保留了点相对于形状的位置信息。

上图中我们在融合两个球的过程中，首先计算出空间中的任意点分别相对于两个球表面的距离函数，然后加权，结果为0的点留下

如果三维的比较难理解，我们可以用二维的一个图看看：

level sets

这种方式也是一种变体，针对的是我们没法写出SDF的情况，只能写出一个大致的表格映射的情况下，我们大概如何获得融合后的结果，以一条线为例：

显式的表示方式

而显式的表示方式，就是直接给出点面的信息，或者通过参数映射的方式，比如我们非常常见的Mesh。我们刚才说的位移贴图其实就是一种映射方式，所以我们刚才说它是一种显式的几何体表示方式。

常见的显式表示方式有：

• point cloud: 点云
• polygon mesh：我们常见Mesh
• Subdivision, simplification, regularization：细分，简化，规范化

而显式的表示方式，缺点就是比较难判断一个点是否在几何体的面上。如下图所示：

点云

这种比较好理解，就是大量的点，这些点之间也不需要连线，只要足够多，就能看不到缝隙。

因为它是一系列的点，所以用一个数组存储就好，只不过这个数据量非常大

多边形网格

具体的使用场景

贝塞尔曲线

贝塞尔曲线是由几个点来决定曲线的一种方法，有着非常常见的应用，比如如果我们用过xmind，在不同标签之间建立连线的时候，会给我们四个点，其中两个点固定是需要连接的两个标签的位置，另外给了我们两个点可以拖动，拖动之后就可以改变曲线的形状，这个曲线就是一个三次贝塞尔曲线。

贝塞尔曲线可以有n次（n大于等于2），我们以二次贝塞尔曲线为例来解释，其他的依次类推就好

如图，假设我们有三个点，我们这三个点决定了我们曲线从$b_0$开始，$b_1$结束，起点的切线方向需要是$\vec{b_0b_1}$，终点的切线方向需要是$\vec{b_1b_2}$

具体求解这曲线，我们可以采用如下方式，假设我们有一个点在时间内从$b_0$移动到$b_1$，那么在任意一个时间点t，它的位置应该是：

图中的$b_0b_0^1$与$b_0^1b_1$的比值,$b_1b_1^1$与$b_1^1b_2$的比值，$b_0^1b_0^2$与$b_0^2b_1^1$的比值都为t/（1-t）

二次贝塞尔曲线其实就是先用三个点按比例得到了两个新的点，然后再在新的两个点的连线上按照比例得到一个点

三次的贝塞尔曲线其实就是四个点来决定曲线，相通的方式，从四个点逐步变成1个点

再高次的贝塞尔曲线其实就是不断递归上述过程：

我们刚才只讲述贝塞尔曲线的是怎么得到的，那么如何用公式表达这个过程呢？如下是二次贝塞尔曲线的结果

这结果其实我们把等式右边的系数拿出来，是$(1 - t + t) ^ 2$的展开式

对于高阶的贝塞尔曲线，其公式如下，其中的B表示的是二项分布的展开式，即每次得到结果的概率是t，那么n次独立重复实验出现j次结果的概率：

贝塞尔曲线的拼接

当我们一个曲线是非常高阶的贝塞尔曲线的时候，其实是很难控制的，如下图所示：

所以我们可以采取多个低阶贝塞尔曲线拼接的方式：

贝塞尔曲面

贝塞尔曲面是由4*4=16个点来控制的曲面：

如下图所示，首先水平每一行的四个点可以得到一个贝塞尔曲线，此时我们得到了四条贝塞尔曲线，然后我们再想象有一个平面竖直切下去，和四个贝塞尔曲线得到四个点，这四个点再能确定一个贝塞尔曲线，我们移动这个数值面的过程中就可以得到一个贝塞尔曲面：

这个过程其实还是个递归的过程：

Mesh 细分

所谓mesh细分，指的是，将mesh中的多边形进行拆分，以获得更加光滑的效果

从定义中我们就可以看出，这个mesh细分其实有两件事情要做，第一件事是把多边形拆分，第二部要对拆分后的多边形进行调整，不然单纯的拆分并不会得到更加光滑的效果，就比如我们把一个三角形三条边中点连起来得到四个三角形，但是这四个三角形还是在一个面上，不会有更光滑的效果出来

Loop Subdvision

叫Loop只是因为发明者算法的人叫Loop

算法第一步就是把三角形的三条边的顶点连起来，我们就得到了四个三角形。

接下来我们要更新点的位置来使拆分后的面有更光滑的效果：

对于三个新的点，我们采取以下方式更新坐标

对于原本的三个点，我们更新方式如下：

Catmull-Clark Subdivision

Loop细分的限制很明显，只能拆分三角面，那么对于多边形我们如何拆分呢？

可以看出来，只有第一次拆分才会增加奇异点的数量，也就是只有第一次把三角形拆分成三个四边形之后，四边形怎么拆分得到的都是四边形了。

那么我们在如何使用更新新的四边形的位置呢？

Mesh 简化

边坍缩

其实就删掉一个边，或者说把边的两个顶点合并成一个。

、

这个方案听起来简单，但是有两个问题，删除哪个边，合并之后的点的位置在哪里才能引入最小的误差。

注意，在图形学中，很多所谓的最，只是效果上可以接受的意思

这里我们引入一个新的概念，叫做二次度量误差，即距离被删除的面L2距离和最小时候的L2距离

我们只需要计算出所有面的二次度量误差，然后依次选取最小的删除就好。

这里其实有个问题，就是每次删除后，都会影响一些点的位置，从而影响其二次度量误差，我们需要重新计算并重新排序获得最小的进行删除。这里我们就要用到优先级队列这个数据结构，每次获取队头进行删除，然后更新被影响到的二次度量误差，再从队头获取就好。