algorithm - 通过边缘循环分割 3D 模型

Question

我有一个 3D 模型，表示如下:

class Vertex
{
    double x, y, z;
}

class Edge
{
    Vertex *v1, *v2; // no particular order
    Face *f1, *f2; // no particular order. f2 may be null.
}

class Face
{
    List<Vertex*> vertices; // clockwise order
    List<Edge*> edges; // clockwise order
}

class Model
{
    List<Face*> faces;
    List<Vertex*> vertices;
    List<Edge*> edges;
}

当然这可以转换成任何最方便的表示。

我想沿着连接边的多个环将这个模型分割成几个不相连的部分，并创建新的面来盖住末端。一个循环的例子:

新面孔应该在相同的位置，并且除了它们与其他面孔的连接之外完全相同，但对于这个例子，我将它们分开了。我怎么能这样做？

顶点是否在原本断开的部分之间共享并不重要。

由于每条边正好连接两个面，我尝试将每条边单独拆分为两个副本(每个面一个)。这确实根据需要分离了模型，但是我看不到正确添加新面孔的方法。

这个问题被标记为图算法，因为这个问题似乎与图论有某种关系。

Answer 1

• 修正你的模型。 class Edge 应该包含指向 Face 和 Vertex 的指针，而不是值。
• 您想在class Model 中使用某种set 而不是List。这有助于查找和删除内容，并确保没有重复项。

• 提出您的函数原型(prototype)。我建议

pair<Model*, Model*> split_model( const Model* mx, const List<Edge*>& loop );

• 创建两个新的空模型，比如 ma 和 mb。将 loop 中的边添加到它们中的每一个。
• 从循环中选取一条边。我们将附加到它的两个面称为 fa 和 fb。
• 将fa 添加到模型ma 中。从 fa 开始，通过跟踪附加到 fa 的所有边以及附加到这些边的所有面等进行完整的图形搜索。必须遵循所有遇到的面和边并将其添加到模型 ma 中。如果您遇到已经是 ma 一部分的面或边，则不要跟随它们。特别是当您遇到属于 loop 的边时，就会发生这种情况，因此您永远不会越过边界。通过这种方式，您可以对一侧的所有边和面进行全面搜索，最终得到一个完整的模型 ma。最后添加代表切割的面。此处可以忽略大部分顶点，但当然最后您可能想要添加属于您添加的面的所有顶点。
• 从面 fb 开始重复此步骤以创建代表另一部分的模型 mb。