Marching Cubes 实现 - 网格中缺失三角形

Question

我目前正在使用C++实现Marching Cubes算法，并通过在OpenGL中渲染样本数据集来理解它。

我遇到的问题是，我渲染的网格缺少三角形。如下图所示，我看到大约有一半的三角形缺失。

填充三角形并创建四边形是否是解决该问题的正确方法，或者我漏掉了什么明显的东西？

我使用的边交叉表来自以下链接： http://paulbourke.net/geometry/polygonise/

我没有使用12位条目的边标志数组，而是使用了12个if语句（其中2个已显示）。 我使用3D数组中的索引来确定基于边值（0-11）的x、y、z值。

    if ((edge.point1 == 0 && edge.point2 == 1) ||
        (edge.point1 == 1 && edge.point2 == 0))
    {
        p1.x = x;   p1.y = y; p1.z = z;
        p2.x = x+1; p2.y = y; p2.z = z;
    }
    else if ((edge.point1 == 1 && edge.point2 == 2) ||
             (edge.point1 == 2 && edge.point2 == 1))
    {
        p1.x = x+1; p1.y = y;   p1.z = z;
        p2.x = x+1; p2.y = y+1; p2.z = z;
    }

此外，插值函数如下。

point interpolate(point p1, point p2, unsigned char isovalue)
{
    point p;

    unsigned char d1 = getDataValue(p1.x, p1.y, p1.z);
    unsigned char d2 = getDataValue(p2.x, p2.y, p2.z);

    if (abs(double(isovalue)-double(d1)) == 0)
        return(p1);
    if (abs(double(isovalue)-double(d2))  == 0)
        return(p2);
    if (abs(double(d1)-double(d2))  == 0)
        return(p1);

    double val = double(isovalue - d1) / double(d2 - d1);

    p.x = p1.x + val * (p2.x - p1.x);
    p.y = p1.y + val * (p2.y - p1.y);
    p.z = p1.z + val * (p2.z - p1.z);

    return p;
}

更新:

在找到一个例子后，我修改了我的代码并能够渲染所有三角形。现在，我发现当我旋转物体时，物体开始倒置z轴，并显示物体内部。

为什么在旋转过程中物体会倒置z值？

- Vahe

---

它们是丢失了还是顺序相反了？你尝试过禁用剔除吗？或者，你的Element/ElementArray缓冲区数据类型是什么？如果你使用GLushort，并放入超过64k个索引，奇怪的事情开始发生。 - 3Dave

没有看到代码，很难提出建议。我想代码可能相当冗长，所以在Code Review上发布您的问题可能会更好？ - Peter Bloomfield

David，感谢您的回复。我会看看是否可能是剔除或计算错误。我使用的数据类型是无符号字符（0-255）-1字节。每个3D数组单元格最多达到255，数据为255宽，255高，240深。而且，Peter，我以前没有尝试过代码审查，但会尝试一下。感谢您的帮助。 - Vahe

@PeterR.Bloomfield：这个问题在代码审查中是不相关的。如果问题是关于解决问题的，最好在这里提问。CR仅适用于可工作的代码。 - Jamal

Answer 1

对于这种空间分割算法，您可能希望使用一个非常简单的模型（如球体或立方体），然后逐步调试实现并检查每个阶段的输入/输出。有时候忽略一个小细节就会影响结果。作为一个想法，找到以下问题的答案：

• 您的单元格配置是否计算正确？
• 您是否正确地执行了单元格配置和输出三角形之间的一对一映射？
• 您的所有三角形顺序是顺时针还是逆时针？

- Pourya

---

我进一步调查了缺失三角形的原因，并了解到存在歧义的情况会导致缺失三角形。我偶然发现了一种叫做渐近决策分辨率的技术，但所有的例子都是在二维情况下提供的。那么，我该如何在存在歧义的立方体中实现这个解析器呢？谢谢。 - Vahe

对于存在歧义的立方体，您需要从中心抽取另一个样本。请查看我的发表文章：http://webhome.cs.uvic.ca/~blob/publications/egpgv12.pdf - Pourya

感谢您的帮助和文件。我想提出另一个观察结果。我尝试了运行没有任何歧义解决方案（从标准查找表）的代码，并观察到了一些缺失的三角形。我还将http://afni.nimh.nih.gov/pub/dist/src/SUMA/MarchingCubes/中的代码整合到我的代码中，使用了具有子情况的LookupTable.h和MarchingCubes.c，但仍然观察到了一些缺失的三角形。如果可以查看我的更新代码，我将不胜感激。我已经将代码上传到https://gist.github.com/anonymous/9056336。 - Vahe

我尝试的另一种修改方法是通过从直角三角形创建四边形来“填充”缺失的三角形。当然，我假设这些三角形都是直角三角形。但是，我也没有成功使用这种方法。 - Vahe