Reconstruct all the edges in a triangle mesh

2
votes

I have a triangle mesh which contains millions of triangles. Currently in my data structure only the triangles and the vertices are stored. I want to reconstruct all the edges and stored them in a data container. The idea may be like this: Traverse all the triangles, get each two of its vertices, and create an edge between them. The question is the shared edge maybe created twice. So to overcome this problem, I need a data container EdgeContainer to store the edges and it should have a function to check whether this edge has been already created. So it is like a map with multiple keys, but according to my question, this map should also have the following functions:

  1. EdgeContainer(v1, v2) should return the same result as EdgeContainer(v2, v1), where v1 and v2 are the pointers to two vertices.
  2. EdgeContainer should have a function like EdgeContainer::Remove(v1), which will remove all edges incident to vertex v1.
  3. The implementation should be as efficient as possible.

Is there any existing library which can handle this?

3
c++graphicshashmapmesh
Why won't a simple map<Vertex, vector<Vertex>> not suffice? – Nico Schertler
@NicoSchertler, Edge must be explicitly stored for further use, i.e. stores its length or some other attributes. Your proposal cannot handle it, can it? – C. Wang
Then make it map<Vertex, vector<Edge*>>. – Nico Schertler
If you are able to use sparse matrix multiplication, like in Matlab, then here's an algorithm: mathproblems123.wordpress.com/2015/04/21/… – Beni Bogosel

3 Answers

1
votes

First i suggest you have a look at the concept of half-edge http://www.flipcode.com/archives/The_Half-Edge_Data_Structure.shtml meshes it is used in CGAL and also in OpenMesh and you should be aware of the concept of you are going to use any of them. I my slef recommend OpenMesh http://openmesh.org/Documentation/OpenMesh-2.0-Documentation/tutorial_01.html it is free and open source, you can easily create mesh from set of vertices and indices, and after creating mesh you can easily iterate over all edges.

0
votes

Your easiest bet would be to use the Cgal library, which is basically designed for doing this.

http://doc.cgal.org/latest/Triangulation_2/index.html

It provides natural iterators for iterating over faces, edges and vertices.

Notice that in Cgal, they do not actually store the edges explicitly, they are generated each time the structure is iterated. This can be done efficiently using some clever rules that stop you from counting things twice: looking at the code, it appears that each face is iterated once, and an edge is added for each neighbouring face to the current face, that comes earlier in the list of faces than the current face.

Note that visiting the edges in this fashion only requires constant time per edge (depending on how you store your faces) so that you are unlikely to benefit from storing them separately. Also note that the edge is defined by two adjacent faces, rather than two adjacent vertices. You can transform them in constant time.

0
votes

Simple solution is to use sorted pair of indices:

struct _edge_desc : public std::pair<int,int> {
    _edge_desc(int a, int b): std::pair<int,int>(a<b?a:b, a<b?b:a) {}
};
std::set<_edge_desc> Edges;

If additional info about edges is needed than it can be store in separate vector, and instead of using set for storing edges, use map that maps to index in vector.

std::vector<some_struct> EdgesInfo;
std::map<_edge_desc, int> EdgesMap;