平滑体素地形，第2部分（2012年）

上一次，我们提出了等值面提取问题，并在较高级别上讨论了一些通用方法。今天，我们将变得非常具体，特别是网格。

为了具体起见，让我们假设我们已经通过以某个固定分辨率将其采样到立方网格上来近似势场。为了获得中间值，我们将使用标准三线性插值在网格点之间进行插值。这就像Minecraft样式体素曲面的一般化。本文的目标是弄清楚如何提取隐式曲面的网格（或的零交叉点）。特别是，我们将研究解决此问题的三种不同方法：

到目前为止，提取等值面最著名的方法是行进立方体算法。实际上，它是如此流行，以至于术语“前进立方体”比术语“等值面”更受欢迎（至少根据Google而言）！当算法变得比解决的问题更受欢迎时，这真是一项壮举！此方法的历史非常有趣。它最初在SIGGRAPH 87中发布，然后由Lorensen和Cline获得了专利。这一事实引起了很多愤慨，被广泛引用为阻碍创新的专利的经典例子之一。幸运的是，行军立方体的专利于2005年到期，因此今天您可以在美国自由使用此算法，而不必担心诉讼。

如今，行军的流行很大程度上归功于保罗·伯克（Paul Bourke）撰写的著名文章。早在1994年，他制作了一个名为“多边形化标量场”的网页，该网页介绍了行进立方体的简短，自包含的参考实现（摘自Cory Gene Bloyd的早期工作。）C程序的这一小片段可能是一直是大多数复制粘贴的代码。在我看过的每一个行进多维数据集实现中，我都看到了Bloyd / Bourke代码的一些变体，无一例外。至少有两个原因：

保罗·伯克（Paul Bourke）的展览真是太好了。即使在今天，有关该技术的文章和教程也很多，但似乎都没有人对此做充分的解释。 （而且我没有任何错觉，我会做得更好！）

而且它们的实现非常小且快速。它使用了一些巧妙的技巧，例如预先计算的边表，以加快顶点生成。很难想到任何非平凡的方法来改进它。

最后一点需要一些解释。从概念上讲，前进立方体非常简单。它的作用是沿网格对隐式函数进行采样，然后在每个点（+/-）上检查潜在函数的符号。然后，对于具有符号变化的立方体的每个边缘，它找到该边缘与体积相交的点并添加一个顶点（这就像射线在每对网格点之间投射一堆微小的小段一样）。困难的部分是弄清楚如何在这些交叉点之间缝一些表面。直到零交叉点的位置，都有不同的可能性，每种可能性都由立方体的8个顶点处的函数的符号决定：

更糟糕的是，其中一些情况是模棱两可的！解决此问题的唯一方法是基于个案分析在某种程度上任意打破表格的对称性。真是一团糟！幸运的是，如果您只是下载Bloyd / Bourke的代码，则不必担心任何这些，一切都将正常工作。难怪它被大量使用了！

等值面提取的重要性和行进立方体的缺点都促使人们寻找替代方案。最受欢迎的作品之一是Doi和Koide推出的行进四面体。除了行军四面体没有专利的历史优势外，它还有一些技术优势：

行进四面体与行进立方体不同，它没有模棱两可的拓扑。结果，四面体行进产生的表面总是多面体。

每个四面体生成的几何图形的数量要小得多，这可能使其更适合用于几何图形着色器。

最后，行进四面体只有一些情况，考虑到对称性，这个数目可以进一步减少为3种特殊情况。这足以使您可以手工解决它们。

练习：尝试找出自己行进四面体的情况。 （真的不错）。

行进四面体的总体思路与行进立方体相同，只是行进使用四面体细分。再次，实际实现的标准参考是Paul Bourke（与以前相同的页面，请向下滚动一点。）尽管行进四面体有很多优点，但确实有一些缺点。特别是，从行进的四面体获得的网格通常比行进的立方体大约4倍。这使得算法和渲染速度都降低了约4倍。如果您主要考虑性能，那么使用三次方方法可能会更好。另一方面，如果您确实需要流形网格，则行进四面体可能是一个不错的选择。另一个好处是，如果您固执己见并且喜欢自己编写所有代码，那么进行四面体操作可能会比较容易，因为不需要检查太多情况。

到目前为止，行进的立方体和四面体都已经很老了。但是，等面萃取的研究在1980年代几乎没有停止。在随后的几年中，已经开发了许多新技术。一种被证明非常有效的通用方法是所谓的“双重”方案。 Sarah Frisken Gibson在1999年提出了第一种对偶方法，即表面网：

顺丰吉布森（Gibson），（1999年）“约束弹性表面网”，三菱电机研究实验室，技术报告。

对偶方法和原始方法（例如行进立方体）之间的主要区别是它们生成表面拓扑的方式。在这两种算法中，我们都从相同的输入开始：一个由我们的样本确定的体积网格，由于缺乏更好的术语，我将自由地调用一个样本复合体。如果您以前从未听说过“单元复合物”一词，可以将其视为三角形网格的n维概括，其中“单元”或小平面不必是简单的。

在样本复合物中，顶点（或0像元）对应于样本点。边缘（1个单元）对应于附近的样本对；面（2个单元）绑定的边缘等：

这是这种复杂情况的说明。我绘制了顶点，其中势函数为负黑色，而顶点为正白色。

原始方法和对偶方法都遍历样本复合物，寻找与潜在功能的0级交叉的单元。在上图中，这将包括以下面孔：

原始方法（例如，行进立方体），尝试使用以下配方将越过边界的细胞转变为等值面：

为我们的样本复合体构造原始网格的一种方法如下：

这很不错，因为很容易沿边缘找到相交点。当然，此构造中存在一些拓扑歧义。对于跨越边界的非简单单元，并不总是清楚如何将单元粘合在一起：

如我们所见，这些歧义导致了许多特殊情况的成倍增加，并且通常很难解决。

另一方面，对偶方法对曲面网格使用非常不同的拓扑。像原始方法一样，它们仅考虑与边界相交的单元格，但用于构造表面单元格的规则却大不相同：

这种构造的好处在于，与原始方法不同，双等值面网格的拓扑结构完全由样本复合物确定（因此没有歧义）。缺点是您有时可能会得到非流形顶点：

第二项是棘手的部分，对双重方法的许多研究都集中在探索可能性上。有趣的是，这与原始方法相反，在原始方法中，找到顶点非常容易，但始终将它们粘合在一起非常困难。

这是一个整洁的难题：如果将双重配方应用于规则的立方网格会怎样？好吧，事实证明，您会获得与Minecraft游戏（从拓扑上来说）相同的方型立方体网格！

左：顶点位置对齐到整数坐标的双网格。右：具有平滑顶点位置的双网格。

因此，如果您知道如何生成Minecraft网格，那么您已经知道如何制作平滑形状！您要做的就是以某种方式将顶点压缩到等值面上。多么酷啊？

这项技术称为“曲面网”（记得我们之前提到过它们吗？）当然，诀窍是弄清楚放置顶点的​​位置。在吉布森（Gibson）的原始论文中，她将顶点放置的过程描述为一种全局能量最小化的方法，并将其应用于任意平滑函数。从对表面上的点（通常只是盒子的中心）的一些初步猜测开始，她的想法是干扰它（使用梯度下降），直到最终撞到某个地方的表面。她还添加了一个春季能量术语，以保持表面美观和整体光滑。虽然这个想法在理论上听起来不错，但在实践中可能有点慢，并且要正确地找到能量项之间的平衡并不总是那么容易。

当然，如果对功能进行一些假设，我们通常会做得更好。还记得我一开始说过要假设我们通过三线性过滤近似吗？好吧，我们可以利用这一事实来得出顶点在每个单元格中的最佳位置-无需进行任何迭代的根查找！实际上，如果我们扩展三线性滤波函数的定义，那么我们可以看到0集始终是一个双曲面。这表明如果我们正在寻找0交叉，那么一个很好的选择就是选择双曲面的顶点。

不幸的是，计算该值可能会有些麻烦，所以让我们做些更简单的事情：与其查找最佳顶点，不如寻找最佳顶点，而是仅计算边缘交叉（就像我们在行进立方体中所做的那样），然后将其质心作为顶点对于每个立方体。出乎意料的是，此方法效果很好，并且从此过程中获得的网格看起来与行进立方体相似，但顶点和面较少。这是一个并排比较：

这种方法的另一个优点是它非常容易编码（就像生成Minecraft网格的朴素/剔除算法一样）。我以前没有看过这种技术的发表或提及（可能是因为它太琐碎了），但是我有毫无疑问，其他人已经想到了。也许你们中的某个读者知道引用或在实践中使用该引用的地方？无论如何，随时可以窃取这个想法或在您自己的项目中使用它。我还有一个JavaScript实现，您可以看一下。

假设您对带有斜角的网格不满意。也许您想要在表面上具有尖锐的特征，或者您只是想要一些更严格的方式来放置顶点。好吧，我的朋友，那么您应该看一下双重轮廓：

T. Ju，F。Losasso，S。Schaefer和J. Warren。 （2004）“ Hermite数据的双重轮廓” SIGGRAPH 2004

对于在双网格中的何处放置顶点的​​问题，双轮廓是非常聪明的解决方案。但是，这是一个很大的假设。为了使用双重轮廓，您不仅需要知道势函数的值，还需要知道其梯度！也就是说，对于每个边，您必须计算相交点和法线方向。但是，如果您知道的那么多，那么就有可能将找到一个好的顶点的问题重新构造为一种线性最小二乘问题。该技术可产生可以保留清晰特征的非常高质量的网格。据我所知，它仍然是从潜在场中生成高质量网格物体的最佳方法之一。

当然也有一些缺点。第一个问题是您需要拥有Hermite数据，并且要从任意函数中恢复该数据需要使用数值微分或应用一些笨拙的自动微分器。这些工具在理论上很好，但是在实践中可能很难使用（特别是对于诸如噪声函数或内插数据之类的东西）。第二个问题是，解决一个预先确定的线性最小二乘问题比获取几个浮点数倒数要昂贵得多，并且当精度不够用时，也更容易发生意外爆炸。本文中有一些有关如何处理这些问题的讨论，但是这可能会变得非常棘手。结果，我没办法在javascript中实现此方法（也许以后，一旦我找到了一个好的线性最小二乘法求解器……）

像往常一样，我制作了一个WebGL小部件来尝试所有这些东西（警告：此浏览器有点繁琐）：

这个工具箱可让您比较行军立方体/四面体和我上面描述的（原始）表面网。 Perlin噪声示例使用Kas Thomas编写的javascript代码。行进立方体和行进四面体算法都是Bloyd / Bourke C实现的直接端口。这是一些并排比较。

MC：15268个顶点，7638个面。 MT：58580个顶点，17671个面。 SN：3816个字，3701个面。

MC：1140个顶点，572个面。 MT：4200个顶点，1272个面。 SN：272个顶点，270个面。

MC：80520点，40276面MT：302744 verts，91676 faces。 SN：20122个版本，20130个面孔。

MC：172705个顶点，88071个面。 MT：639522个顶点，192966个面。 SN：41888个版本，40995个面。

控件为：鼠标左键旋转，鼠标右键平移，鼠标中键缩放。我不知道这在Mac上如何运作。

这次我决定尝试一些不同的方法，并放置一个小计时部件，以便您可以看到每种算法需要多长时间。当然，您确实需要对这些数字表示怀疑，因为它正在浏览器中运行，并且时间可能会根据完全任意的外力而随机波动。但是，它确实可以帮助您对每种方法的相对性能有所了解。

在行进的四面体示例中，经常有许多黑色三角形。我不确定这是因为端口中有错误还是在three.js中出现问题。似乎该问题可能与以下事实有关：我的实现在网格中混合了四边形和三角形，并且three.js不能很好地处理这种情况。

我也没有实现双重轮廓。它与曲面网没有太大区别，但是要使其正常工作，您需要获取Hermite数据并解决一些线性最小二乘问题，由于缺少工具，在Javascript中很难做到这一点。

为了比较每种方法的相对性能，我采用了我以前的文章中描述的实验方案。和以前一样，我在样品正弦波上测试了实验，并随时间变化了频率。也就是说，我生成了一个

到目前为止，四面体是最慢的方法，主要是因为它产生了更多数量级的三角形。另一方面，行进多维数据集尽管生成了几乎两倍的原语，但仍然相当快。对于较小的几何形状，行进立方体和曲面网的性能相当。但是，随着等值面变得越来越复杂，最终由于仅创建较少的图元而最终获得了面网。当然，这有点像将苹果与橙色进行比较，因为行进的多维数据集生成三角形，而表面网生成四边形，但是即使如此，表面网生成的面仍然略小于基准面的一半。要查看它们如何堆叠，下面是每种方法为基准测试生成的原语数量的并排比较：

每种等值面提取方法都有其相对的优点和缺点。基于免费且易于使用的实现，行进多维数据集非常不错，而且运行速度也非常快。 （更不用说它也是最广为人知的）。行进四面体解决了行进立方体的一些问题，但代价是速度慢得多并且创建了更大的网格。另一方面，表面网要快得多，并且可以使用更复杂的顶点选择算法进行扩展以生成高质量的网格。它也很容易实现，并会产生较小的网格。唯一的缺点是它可以创建非流形顶点，这对于某些应用程序可能是个问题。不幸的是，我一直未能正确实现双重轮廓，主要是因为我想避免必须用JavaScript编写健壮的线性最小二乘法求解器。如果您有任何读者想接受挑战，我很想知道您获得了什么结果。

最近，我一直在谈论wordpress主题。无论出于何种原因，看来我使用的旧版本会不断使Chrome崩溃。我一直在尝试寻找一些美好而简约的东西。希望这个可以解决。