algorithm - 分离网

Question

我在分离网格方面遇到了问题。有一个组合网格，它有 1 个顶点缓冲区和 1 个三角形索引缓冲区。但网格至少有 2 个独立的对象。例如，有 2 个没有共享顶点的四边形(当然也没有共享索引)，它们的几何图形位于 1 个单个网格中(1 个顶点缓冲区，1 个索引缓冲区)。那么如何从它们创建 2 个网格。有什么算法吗？

我尝试在新网格中添加第一个顶点，然后寻找指向该顶点的索引，然后我将三角形的该索引及其相关的 2 个索引(和顶点)添加到新网格中，但必须更改索引。

很抱歉遗漏了有关我的问题的信息。我认为逻辑上分开。例如在编程中。如果下面的单个网格像图片中那样具有未共享的子网格。我希望它分成 2 个网格类。我想要一个算法，一个数学解决方案，而不是一个为我做这件事的工具。

Answer 1

首先，用顶点数初始化一个联合查找数据结构。然后找到所有连接的组件如下:

for each triangle index i1, i2, i3 in indices
    union-find.union(i1, i2)
    union-find.union(i1, i3)

然后初始化一个空映射(或字典)，将旧顶点索引映射到新顶点索引:

Dictionary<int, int> indexMap;

此外，我们需要新的顶点列表:

Dictionary<int, List<Vertex>> vertices;
Dictionary<int, List<int>> indices;

然后按如下方式将顶点分配到正确的列表中:

for i from 0 to vertex count -1
    componentRepresentative := union-find.find(i)
    if(!vertices.ContainsKey(componentRepresentative))
        vertices.Add(new List<Vertex>());
        indices.Add(new List<int>());
    var list = vertices[componentRepresentative];
    list.Add(vertexBuffer[i]);
    indexMap.Add(i, list.Count - 1)

此时我们已经分离了顶点缓冲区。我们仍然需要类似地分离索引缓冲区。

for i from 0 to index count - 1
    componentRepresentative := union-find.find(indexbuffer[i])
    var list = indices[componentRepresentative]
    list.Add(indexMap[indexBuffer[i]])

总体时间复杂度接近 O(n)(对于理想的联合查找结构)。