从《我的世界》了解“体素”引擎的工作，----网格优化算法的比较
一. 写在之前
目前正在制作一个3D体素类的项目，大量的模型带有大量面数的模型在Unity中直接跑不动，FPS在15以下，考虑到一个场景中不仅有一个模型需要显示，想要提高游戏流畅度，必须对这些模型的网格面数进行深度优化，至少优化到5000面以下。先在网上调研了很多的资料，发现了一个确实很实用，但是不那么容易理解的优化算法----贪心网格规划算法（GreedyMesh，翻译过来的）。
二. Meshing
《我的世界》这种现象级游戏，最为创新的点之一就是游戏使用大量的多边形渲染空间体积。使用多边形的主要挑战是弄清楚如何有效地将体素转换为多边形。此过程称为网格划分。本文章会提供三种方法划分网格。在此之前，我们首先需要明白什么是“网格规划”，什么才是好的网格。
多边形的渲染大致分为两部分：1.）图元装配（Primitive Assembly），以及2.）扫描线填充（也称为多边形填充）。通常情况下，没有任何方法可以更改需要绘制的像素/片段的数量；因此，出于渲染的目的，我们可以将其视为固定成本，这样一来，原始装配操作的成本严格地取决于网格中面和顶点的数量。而降低成本的唯一方法是减少网格中多边形的总数，因此我们对Minecraft网格可以得出下面的结论：网格数量越小越好。
当然，上面的分析还远远不够，虽然更新网格块的频率不高，然而一旦需要更新网格块的时候，我们还是希望能快速的更新完，用户是不愿意看到形状更新要等上两帧或以上，所以我们可以得出评估网格算法好坏的第二个标准：计算网格的耗时不能过高。
对于以上两个标准，有一个好的解决方案：对于一个很复杂的网格，我们可以先不对其进行规划，而是标记，然后在另外一个线程中的某个时间将其进行网格化算法处理，一旦处理成功，就可以将那个复杂的低质量网格替换成这个规划后的网格。在理论上完美的解决了上述的问题。
网格规划的一些算法：
上述的两个标准中，其中第一个标准最为重要，因此，我们将网格规划算法的重点放在其输出的多边形上的质量上。
1. 笨办法（StupidMethod）
当然这是最笨的也是最直接的办法，体素与体素依次迭代，并为每个实体体素生成一个6面立方体。如下图所示：
该方法是线形复杂度，同样的，使用的四边形数量为总体素数量的6倍，如果是 8*8*8的网格块，那么总的四边形数 8*8*8*6 = 3072，这样的结果明显是很不合理的，大量的四边形是重复冗余的。严格来说这不算个方法，就是就是所有的体素垒起来，不做任何网格优化的结果，显然不符合我们的要求。
2. 剔除法（Culling）
该方法是剔除了网格内部没有用的表面，只留下表面的四边形，如下图所示：
很明显，该算法的网格规划最后生成8 * 8 * 6 = 384的四边形数，是原来数量的1/8，但从本质上来说，这两个方法是一样的。
3. 贪心算法
该算法将相邻的四边形合并到更大的区域中，以减小几何的总大小。例如，我们可以尝试通过将每边的所有面融合在一起来对上一个立方体进行网格划分：
这样得到的网格只有6个四边形（在这种情况下，实际上也是最佳算法！）显然，这种算法的计算结果又是第二种算法的1/64。该算法有两个创新点，首先，仅考虑为某些2D横截面生成四边形网格的问题就足够了。也就是说，我们可以在每个方向上一次扫过网格体，然后分别对每个横截面进行网格划分：
这样可以将3D问题简化为2D。第二步是如何对每个2D切片进行网格划分的问题。这（即最少的四边形）是贪婪算法最核心也最难的地方。为了容易理解，我们换一种方式表述这个问题，将在所有可能的四边形的集合上定义某种类型的总阶，然后选择该集合的最小元素作为网格。为此，我们将首先在每个四边形上定义一个顺序，然后将其扩展到所有网格的集合上的顺序。一种简单的排序两个四边形的方法是将它们从上到下，从左到右排序，然后按它们的长度进行比较。更具体地，使用元组（x，y，w，h）表示一个四边形，其中（x，y）是左上角，（w，h）是四边形的宽度/高度，我们可以通过以下方式表示四边形：
所谓二维四边形网格，是指将某些集合S划分为四边形Qi的集合。现在，在给定（x0，y0，w0，h0），（x1，y1，w1，h1）的情况下，我们定义这些四边形的总阶数：
或者，用伪代码的方式，我们可以这样写：
接下来我们要做的是，将四边形上的排序扩展为网格上的排序，一种非常简单的方式是，给定两个四边形的排序序列（q0，q1，...），（p0，p1，...），这样qi \ leq q {i + 1}和pi \ leq p {i + 1}，我们可以只需按字典顺序比较它们即可。同样，此新排序实际上是总大小，这意味着它有一个最小的元素。在贪婪网格划分中，以这个最小元素作为初始网格，这就是贪婪网格划分算法。如下图，是这些字典最小的网格之一的示例：
你可能会问，这种新顺序找到最少的元素总是会产生更好的四边形网格。例如，不能保证此新顺序中的最少元素也是具有最少四边形的网格。考虑使用以下方法对T形网格进行四边形网格规划时的情况：
此外，我们可以说，贪婪网格规划算法中的每个四边形始终完全覆盖该区域周边上的至少一个边缘，这始终是正确的。因此，我们可以证明以下几点：贪婪网格中的四边形数量严格小于该区域的边缘中的边数量。
这意味着在最坏的情况下，我们应该期望贪婪网格的大小与边的数量大致成比例。通过启发式/尺寸分析，可以合理地估计出贪婪网格通常比球形几何形状（其中n是球体的半径）小的网格大约小O（\ sqrt（n））倍。但是我们可以更加精确地了解贪婪网格的实际质量：贪婪网格规划后的四边形不超过最佳网格的8倍。
这就是最佳因素！为了证明这一点，我们需要先引入一些术语。如果顺时针绕网格旋转时向右转，我们将在该区域的外围上称为顶点，否则，将其称为凹入。这是一张图片，凸顶点为红色，凹顶点为绿色：
关于这些数字有一个明显的规律：对于任何在周长上具有V+凸顶点和V-凹顶点的简单连接区域，V +V_ = 4。
推导：具有E边周长的任何已连接属G区域至少需要个四边形进行网格划分。
最后，代码实现。（后面附有源码）
由于计算量较大，使用Unity的ThreadedJob，具体构造如下：
每一个线程是一个网格生成器 GreedyMeshGenerator，本算法需要三个网格生成器，前后方向、左右方向、上下方向分别切片之后，对这三个方向的切片结果进行计算，是算法逻辑真正实现的地方。
- 初始化网格生成器：首先过滤到该切片上，那些不在边缘上的、被其他的网格片遮挡住的点，然后根据这个点的颜色，将其分类存储到一个字典中，字典的key是颜色，value是相同颜色的所有点集合List。后期的所有计算都是围绕这个字典进行。
- 对每个方向上的切片进行网格规划计算，以水平方向切片为例，假设水平方向是xy平面，逐点判断能否作为边缘点成为新网格的顶点。具体详见代码。这里需要注意的是，水平方向上，判断某点的标准是垂直水平面方向上，上下各1单位的点是否落在整个网格的内部还是外部。
- 符合所有上述条件的顶点会添加到新的网格中，该网格在迭代中不断的扩大。
引用文章来源：https://0fps.net/2012/06/30/meshing-in-a-minecraft-game/
如果有问题，欢迎邮箱联系，共同学习探讨。感谢
email：[email protected]