1

我有一个 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;
}

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

我想将这个模型分割成几个断开的部分，沿着连接边缘的多个循环，并创建新的面来覆盖末端。一个循环的例子：

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

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

由于每条边都恰好连接两个面，因此我尝试将每条边分别分成两个副本（每个面一个）。这确实根据需要分离了模型，但是我看不到正确添加新面孔的方法。

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

4

1 回答 1

2
  • 修复你的模型。 class Edge应该保存指向Face而Vertex不是值的指针。
  • 你想在你set的. 这有助于查找和删除内容，并确保没有重复项。Listclass 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代表另一部分的模型。
于 2014-02-25T15:00:09.027 回答