按边缘循环分割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 而不是价值观。
• 你想用某种 set 而不是 List 在你的 class Model.这有助于查找和删除内容，并且您确保没有重复项。

• 拿出你的函数的原型。我建议

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

• 创建两个新的空模型，比如说 ma 和 mb.添加边缘从 loop 给他们每个人。
• 从 loop.让我们称附在它上面的两张脸 fa 和 fb.
• 添加 fa 到模型 ma.从 fa, ，通过遵循附加到的所有边进行完整的图搜索 fa, ，以及附着在那些边缘上的所有面，等等。必须遵循遇到的所有面和边并将其添加到模型中 ma.如果遇到已经是 ma 你不遵循他们。特别是当你遇到一个属于 loop 所以你永远不会越过边界。这样你就可以对一侧的所有边和面进行完整的搜索，最终得到一个完整的模型 ma.最后你添加一个代表切割的脸。顶点可以在这里大部分被忽略，但当然最后你可能想添加属于你添加的面的所有顶点。
• 从脸部开始重复此步骤 fb 创建模型 mb 代表另一部分。