如何生成Marching Cubes三角形表？

Question

如何生成 marching cubes 三角形表？我知道可以使用预先计算好的表，但我想知道这些表是如何生成的。

似乎最初的作者是通过手工绘制来进行三角剖分的，但是否有一种方法可以在代码中生成呢？

边缘表很简单，但我看不出是否有一种简单的方法来获取三角形表，即使忽略模糊的情况。

- allo

Answer 1

这里有一种方法：

从顶点和边点开始。现在，如果一个顶点被选中，则将三个相邻的边点放置在该顶点旁边。对于每个顶点都要这样做。

现在，注意连接选中顶点的边缘。删除位于它们上面的边点。

利用这些边点制作一个三角形数组。

通过使用循环256次来制作三角形表，实际上，使用此方法，您甚至可能不需要循环。

为了测试它：

• 你可以在谷歌上搜索“Marching Cubes Combination”，

• 或者看看这个链接： https://www.researchgate.net/profile/Zhongjie_Long/publication/282209849/figure/fig2/AS:362916613246979@1463537471898/Type-of-surface-combinations-for-the-marching-cube-algorithm-The-black-circles-means.jpg

试试我告诉你的方法。它是有效的。 只有一件事，当我测试时，由于绘制方式，我有些困惑。无论如何，享受吧！ :)

编辑：使用这种方法，您可以使用任何三角形渲染方式。 人们使用不同的三角形表格。 使用这种方法，您不必弄清楚边缘点的编号是什么。您可以按照自己的方式使用它，以便您不必浪费时间弄清楚。

- Kino Bacaltos

---

我不确定这是否完全回答了我的问题。您描述了从顶点的距离函数到边界点的步骤，这是算法的一部分。之后，找到的边界点需要通过三角形连接（如您图像所示）。现在我想知道生成三角形表的*算法，该表将边缘组合映射到像http://paulbourke.net/geometry/polygonise/](此处)的三角形。您能详细说明这一部分吗？ - allo

好的，这可以用来生成它。遍历角点，并使用该方法。 - Kino Bacaltos

嗯，我知道这太晚了，但看看这个。 您可以用有效的点编号所有边 然后采用此模式0，1，2，1，3，2，2，3，4，3，5，4，4，5，6，5，7，6 其中每个数字表示点或边号。 然后你就有了它。 但什么是有效点？如果一个点只被计算一次，则它是有效点。 如果至少两个，则无效。 - Kino Bacaltos

兄弟，我可以再回答这个问题吗？（目前我正在编辑它） - Kino Bacaltos

我明天可以给你另一个解决方案。我还在准备考试。 - Kino Bacaltos

Answer 2

这里是算法的原始解释：http://paulbourke.net/geometry/polygonise/

- abenci

Answer 3

另一种解决方案 (在我告诉你之前不要看这个) (否则你会看到我的未完成的混乱，因为我没有时间完成它)

我不会真正引用代码。

Marching Cube Triangle List从一个立方体开始。

如果您有一个立方体，或者可以制作一个立方体，我建议您使用一个立方体，仅出于方便。使用笔或标记器整齐地编号其角落和边缘。 请不要不规则地计数。使计数“可编程”。

一个立方体有8个角。让我们将每个角想象成一个灯泡。 因此，三角形列表为打开和关闭的每个灯泡组合生成三角形。 也就是说，256种组合。（（2个灯泡条件）^（8个灯泡）= 256种组合） 但是如何生成三角形列表？

对于每个组合，我们都有一个独特的立方体。 让我们从这样的组合开始

 /7.on-----8.off
/ |           /|
3.off----4.on/ |
| 5.on ------| 6.off
| /          | /
|/           |/
1.on------2.off

我们可以制作一个角落或灯泡的列表。 灯泡1，灯泡2，灯泡3-灯泡8 然后告诉它们是开着还是关着 开，关，关...关 你编号的方式取决于你想要什么。虽然我建议有组织地进行。有40,320种点序的组合。 对于这个例子，我使用我习惯的顺序。

我们可以将这个灯泡状态列表转换为二进制数。关闭表示0，打开表示1。 10011010在二进制中=表格的第154个索引

可能你都知道这些:P

2. 创建一个12元素的边缘点数组。 对于新手（没有冒犯），边缘点->位于边缘上的点。

int[] edgePoints = new int[12] {0,0,0,0,0,0,0,0,0,0,0,0} //12 elements

然后我们启用边缘点。对于每个角点，启用其相邻的边缘点。 如果完成此迭代，请检查某个点是否已启用多次。如果是，则禁用它。如果没有启用，则禁用它。

现在您有了有效的边缘点。将其存储在数组或列表中。现在让我们制作三角形。

这里有一些我们可以使用的数组。

List<int> validVertexIndices = new List<int>(); //add the valids
List<int> usedVertices = new List<int>();
List<int> oldVertices = new List<int>();
List<int[]> usedTris = new List<int[]>();

让我们先画一个三角形。 程序并不知道如何连接这些点（以形成三角形）。所以，我们从一个随机点开始。（最好从最低的索引开始）

usedVertices.Add(your random point index);

然后检查距离起点最近的点。 为此，遍历除了起始点以外的所有点。检查起点和每个其他点之间的距离。（假设每个点的x、y、z位置是0.5的完美倍数）（例如0、0.5、1.0）

如果起点和另一个点之间的距离是所有其他距离中最短的，则这两个点是第一个三角形的前两个点。

usedVertices.Add(That second point to be used);

然后获取离第二个点最近的不是第一个点也不是第二个点的点。那就是第三个点。

usedVertices.Add(The third point);

然后您可以注册三角形。

usedTris.Add(usedVertices.ToArray());
oldVertices.Add(usedVertices);
usedVertices = new List<int>();

现在来谈谈其他三角形。有许多规则可以遵循。你可以简单地重复第一个三角形的过程，只不过这一次，你必须重置迭代并更改点，如果它违反了规则。你可以将第一个点改为下一个未使用的点。然后如果失败，再更改第二个点和第三个点。

三个主要规则是： 1. 三角形不应与先前的三角形相同。 2. 三角形不应相交。 有一些相交算法，但我不能在这里放出来，因为它们太长了。 3. 检查是否覆盖了启用的角点。 - 获取所有相邻的启用角点的平均距离，并查看其是否与当前三角形的法线平行并具有相同的方向。

这很复杂，可能不会成功，但你已经有了一套规则。

一直做下去，直到达到n(n-1)/2次。你就有了三角形。（其中n=启用边缘点的数量）

然后，对于每个三角形，创建一个克隆，以使其法线相反。

这样你就做到了。也许不是很好，所以最好找一个源。

哈哈，另外，请不要制作和训练神经网络来制造这样的事情，那只是折磨。

- Kino Bacaltos