16

我已经成功实现了行进立方体算法。我使用标准材料作为参考，但我完全从头开始重写。它有效，但我正在观察导致网格中出现孔洞的歧义。

我正在考虑行进四面体算法，据说它不会受到歧义的影响。我看不出这是怎么可能的。

行进四面体算法使用六个四面体代替立方体，每个四面体都有三角剖分。但是，假设我要实现行进立方体算法，但是对于 256 个三角剖分中的每一个，只需选择立方体四面体三角剖分的“总和”（并集）吗？据我所知，这就是行进四面体所做的——那么为什么这能神奇地解决歧义呢？

我认为有 16 个独特的案例，其他 240 个只是这 16 个案例的反映/旋转。我记得在某处读过一些论文，为了解决歧义，你需要 33 个案例。这可能与为什么行进的四面体不会出现问题有关吗？

所以，问题：

  1. 为什么行进的四面体不会出现歧义？
  2. 如果没有，为什么人们不使用行进立方体算法，而是使用四面体的三角剖分呢？

我觉得我在这里遗漏了一些东西。谢谢。

4

3 回答 3

9

好的，我刚刚完成了我的行进四面体版本，虽然我很容易看到歧义会导致行进立方体的网格出现问题，但行进四面体的网格似乎在拓扑上始终是正确的。沿着非常细的点有一些烦人的特征，其中一些顶点无法完全决定他们想要在分界线的哪一侧，但网格始终是水密的。

回答我的问题：

  1. 为了解决行进立方体算法中的歧义，据我所知，人们在单元格中更仔细地评估了函数。在四面体算法中，明确地对单元的中心进行采样并将其多边形化。我怀疑因为四面体网格特别包括这个顶点，所以隐含地处理了歧义。侧面的其他额外顶点可能也与它有关。作为一个关键点，当你去细化它时，实际上是在更多的地方对函数进行采样。
  2. 我很确定他们会。我的行进四面体算法就是这样做的，我认为，在内部，它与经典的行进四面体算法做同样的事情。在我的实现中，所有可能的立方体都列出了四面体的三角形，我怀疑这比单独为每个单独的四面体找出一个或两个三角形更快。

如果我有时间和注意力（我都没有），重新划分每个立方体的内部以使用更少的三角形可能是有益的，我认为这不会伤害它。

于 2012-06-18T03:40:28.917 回答
8

回答“为什么行进四面体算法有歧义？”这个问题。需要了解为什么在 Marching Cubes 中首先会出现歧义。

当立方体中有两个对角相对的“正”顶点和两个对角相对的“负”顶点时，可能会出现歧义。我花了一些时间来思考它，但含糊不清的问题是它们理论上允许为彼此不兼容的相邻立方体创建等值面补丁。这是显而易见的部分。有趣的是，如果（且仅当）其中一个分隔“负”顶点，而另一个分隔“正”顶点，则来自两个模棱两可配置的两个相邻等值面补丁是不兼容的。

这是来自 Rephael Wenger 的巨著“等值面几何、拓扑和算法”的相关引述（不能发布超过 2 个链接，因此我将书中的所有相关图像合并为一个）：

立方体的 3D 等值面片的边界在立方体的每个方形面上定义了一个等高线。如果某个配置的等值面贴片将小平面上的负顶点分开，而相邻配置的等值面贴片将正顶点分开，那么公共小平面上的等值面边将不会对齐。图 2.16 中的等值面补丁不会分离任何面上的正顶点。此外，在配置的任何旋转或反射中派生的等值面曲面片也不分离任何面上的正顶点。因此，任何两个相邻立方体中的等值面块在它们的边界上正确对齐。一个同样有效但组合不同的，

这意味着如果所有使用的模棱两可的配置都遵循相同的模式（即总是分开的“负”顶点），那么就不可能产生拓扑不正确的表面。如果您对单个等值面使用“来自两个世界”的配置，则会出现问题。

使用相同的歧义分辨率模式构建的表面仍然可能包含像这样的不需要的错误（取自Thomas Lewiner Helio Lopes、Antonio Wilson Vieira 和 Geovan Tavares的“Efficient implementation of Marching Cubes' case with topologies”文章），但它正如你所说，将是无懈可击的。

为此，您需要使用基于图 2.16 所示的 22 种独特配置（不是标准的 14 或 15 种）的查找表。

现在，最后回到最初的问题——为什么 Marching Tetrahedrons 不会出现歧义？出于同样的原因，如果按照上述方法完成，Marching Cubes 中不会有歧义 - 因为您任意选择使用歧义配置解析的两种可用变体之一。在 Marching Cubes 中，这甚至是一种选择并不明显（至少对我来说，不得不做很多挖掘），但在 Marching Tetrahedrons 中，它是由算法本身为您完成的。这是 Rephael Wenger 书中的另一句话：

规则网格立方体具有不明确的配置，而四面体分解则没有。模棱两可的配置怎么了？这些配置是通过选择三角测量来解决的。例如，在图 2.31 中，第一个三角剖分给出了一个等值面补丁，其中两个分量对应于图 2.22 中的 2B-II，而第二个三角剖分给出了一个等值面补丁，其中一个分量对应于 2B-I。

请注意图 2.31 中立方体是如何以两种不同的方式切割成四面体的。这种切片或另一种切片的选择是解决歧义的秘诀。

有人可能会问自己——如果可以通过对所有立方体使用相同的模式来解决歧义问题，那么为什么会有这么多关于更复杂解决方案的书籍和论文呢？为什么我需要渐近决策者和所有这些东西？据我所知，这一切都取决于您需要实现的目标。如果拓扑正确性（例如，没有漏洞）对您来说就足够了，那么您就不需要所有高级的东西。如果您想解决上面显示的“行进立方体的有效实施”文章中所示的问题，那么您需要更深入地研究。

我强烈建议阅读 Rephael Wenger 的《Isosurfaces Geometry, Topology & Algorithms》一书中的相关章节，以更好地了解这些算法的本质、问题是什么、问题从何而来以及如何解决。

正如李小生所指出的，首先仔细研究行进广场算法可以更好地理解基础知识。其实整个答案都是李小生写的，我只是稍微扩展了一下。

于 2015-04-07T10:38:39.930 回答
2

以下面的二维示例（引入歧义）为例：

01

10

如果我们把这个正方形分成两个三角形，我们会在我们选择分割正方形的对角线上得到不同的结果。沿着 0-0 对角线，我们得到三角形 (010,010)，而对于 1-1 对角线，我们得到三角形 (101,101)。显然，不同的平方分解会导致不同的结果。两者都是正确的，对于 3D 立方体也是如此。

MT 实际上并没有解决歧义，但它可以通过为所有立方体选择相同的分解策略来产生拓扑一致的结果。这样就摆脱了模棱两可的痛苦。

于 2013-06-24T10:09:24.767 回答