c++ - 重建三角形网格中的所有边

Question

我有一个包含数百万个三角形的三角形网格。目前在我的数据结构中只存储了三角形和顶点。我想重建所有边缘并将它们存储在数据容器中。想法可能是这样的:遍历所有的三角形，得到它的每两个顶点，并在它们之间创建一条边。问题是共享边可能创建了两次。所以为了克服这个问题，我需要一个数据容器EdgeContainer存储边，它应该有一个功能来检查这条边是否已经被创建。所以它就像一个有多个键的 map ，但根据我的问题，这个 map 应该还具有以下功能:

1. EdgeContainer(v1, v2)应返回与 EdgeContainer(v2, v1) 相同的结果, 其中v1和 v2是指向两个顶点的指针。
2. EdgeContainer应该有类似 EdgeContainer::Remove(v1) 的功能, 这将删除所有与顶点 v1 相关的边.
3. 实现应尽可能高效。

是否有任何现有的库可以处理这个问题？

Answer 1

首先我建议你看一下的概念半边http://www.flipcode.com/archives/The_Half-Edge_Data_Structure.shtml meshes 它在 CGAL 和 OpenMesh 中使用，你应该知道你将要使用它们中的任何一个的概念。我自己推荐 OpenMesh http://openmesh.org/Documentation/OpenMesh-2.0-Documentation/tutorial_01.html它是免费和开源的，您可以轻松地从一组顶点和索引创建网格，并且在创建网格后您可以轻松地遍历所有边。