前进的立方体歧义与前进的四面体

Question

我已经成功实现了行进立方体算法.我使用标准材料作为参考,但我完全从头开始重写.它有效,但我观察到导致网格中的洞的模糊性.

我正在考虑行进的四面体算法,据说这种算法不会产生歧义.我看不出这是怎么可能的.

行进四面体算法使用六个四面体代替立方体,每个四面体具有三角剖分.但是,假设我要实现行进立方体算法,但对于256个三角测量中的每一个,只需选择多维数据集四面体三角剖分的"和"(并集)？据我所知,这就是行军四面体的作用 -那为什么会神奇地修复模糊性？

我认为有16个独特的案例,其他240个只是那些16的反思/轮换.我记得在某个地方阅读一些解决含糊之处的文章,你需要33个案例.这可能与为什么行进四面体不会出现问题有关？

所以,问题:

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

我觉得我在这里错过了一些东西.谢谢.

Answer 1

好吧,我刚刚完成了我的行进四面体版本的实现,虽然我很容易看到模糊不清导致行进立方体网格中出现问题,但行进四面体的网格似乎始终在拓扑上是正确的.这里是沿着非常薄点,其中一些顶点不能完全决定他们想在鸿沟的哪一侧一些恼人的功能,但网总是滴水不漏.

在回答我的问题时:

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

如果我有时间和注意力(我都不这样做),重新对每个立方体的内部进行重新划分以使用更少的三角形可能是有益的,我认为这不会对它造成伤害.

Answer 2

回答“为什么前进四面体算法有歧义？”的问题。需要理解为什么歧义首先出现在Marching Cubes中。

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

这是Rephael Wenger的出色著作“等值面几何，拓扑和算法”的相关报价（最多只能发布2个链接，因此我已将本书中的所有相关图像合并为一个）：

多维数据集的三维等值面补丁的边界在每个多维数据集的方形小平面上定义了一个等值线。如果某个配置的等值面补丁将小平面上的负顶点分开，而相邻配置的等值面补丁将正顶点分开，则公共小平面上的等值面边缘将不对齐。图2.16中的等值面补丁未将任何小面上的正顶点分开。此外，在配置的任何旋转或反射中派生的等值面补丁也不会在任何小平面上分离正顶点。因此，任意两个相邻立方体中的等值面补丁都在其边界上正确对齐。同等有效，但组合上完全不同的

这意味着如果所有使用的歧义配置都遵循相同的模式（即始终分开的“负”顶点），则不可能生成拓扑错误的表面。如果对单个等值面使用“来自两个世界”的配置，则会出现问题。

使用相同歧义分辨率模式构造的表面仍然可能包含此类不必要的错误（摘自Thomas Lewiner Helio Lopes，Antonio Wilson Vieira和Geovan Tavares的“有效执行带有拓扑保证的Marching Cubes案例”），但是如您所说，将是水密的。

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

现在，最后回到最初的问题-行军四面体为什么不遭受歧义之苦？出于同样的原因，如果按照上述说明进行，行进多维数据集将不会有歧义-因为您可以随意选择使用模棱两可的配置分辨率的两个可用变体之一。在Marching Cubes中，这甚至不是一个选项（至少对我来说，必须做很多挖掘工作）是完全不明显的，但是在Marching Tetrahedrons中，它是由算法本身为您完成的。这是Rephael Wenger的书中的另一句话：

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

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

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

我强烈建议阅读Rephael Wenger的书“等值面几何，拓扑和算法”的相关章节，以更好地理解这些算法的性质，存在的问题，问题的根源以及如何解决。

正如李小生所指出的那样，首先仔细检查行军广场算法可以更好地理解基础知识。实际上，整个答案是由李小生确定的，我只是在扩大了一些解释。