0

I want to accumulate the edges of triangular model/mesh. For example a triangular cube has 18 edges.

It looks so simple and easy but literally its too complicated. I have all adjacent information of a triangle. For example I have adjacent vertices and triangles, and I know which triangles have common edge but the problem is how to extract that common edge between two triangles.

One thing that needs to consider is there should not be any duplicate index of edge's point/vertex.

First thing is how to count the total number of edges. Remember a Cube has 18 edges.

I tried a lot but gave up now. :) any idea? .

Update 1:

ok I have a triangle T[i] (index v1, index v2, index v3) which has three edges v1v2, v2v3, v3v1.

and I have a neighbor triangles of all edges.

T[i].index_of_sharedTri1_with_edge_v1v2, 
T[i].index_of_sharedTri2_with_edge_v2v3, 
T[i].index_of_sharedTri3_with_edge_v3v1; 

now which loop I need to make that can extract unique edge? What information I need to compare? Do I need to compare edge vertices, shared tri index, or what ? I tried with many ways but it so complicated.

Update 2:

GLTris *e = new GLTris[nb_Tris*3];
int n = getTotalEdges_Sorted(indices, nb_Tris, e);
cout<<n<<endl;
int ne = RemoveDublicatesFromAnSortedEdgeArray(e, n);
for(int i=0; i<ne; i++)
   e[i].Cout();

I have tried this and it works perfect but I need to figure it out whether it will work on all types of meshes and is it a efficient way?

0

3 Answers 3

2

If you have the number of triangles, and the adjacency information for each, then the number of edges is simply:

3 * num_triangles - num_shared_edges

Where num_shared_edges can be accumulated by iterating over each triangle and adding up the number of adjacent triangles. Then divide by two, as you'll have counted them all twice (this obviously assumes you have no more than two triangles per edge)

If you want to build a list of unique edges, you'll need to keep track of them, preferably in some easily indexable structure like a map.

The procedure is roughly as follows:

  1. Define an edge as being two indices (i1, i2). Order those indices such that i1 < i2. Now shared edges are guaranteed to match.
  2. Make some kind of list structure that can hold these edges. You need to be able to quickly find an existing edge by its indices, so you want a structure that is searchable, such as some kind of tree. If you were using c++, I'd suggest using a map with the i1,i2 pair as a key.
  3. Iterate over all triangles, adding 3 edges for each. Do not add the edge if it already exists.

That's all there is to it.

10
  • yea the main problem is this one, when I will add shared triangles then how will I know that this triangle I have already added or already counted. For example in a cube case, every triangles is shared with 3 triangles. When I will flag to first edge of triangle then that edge again comes when shared triangle comes into loop.
    – maxpayne
    Dec 11, 2012 at 18:02
  • I have tried to add some more detail, but it would help to expand your original question with more info about what data you actually have, in what structure, and what you actually want to end up with.
    – JasonD
    Dec 11, 2012 at 18:44
  • Thanks for your addition. I tried to understand you but still confuse. I have updated my question please check it now. I am not using linked list but just c data structure. The issue is I have everything relevant to adjacency of a triangle but which information I need to compare to extract shared edge? "you can build an ID for an edge based on the two indices of its end points." This is the problem how to give a unique ID to shared edge, in case of cube ID should 18. But how?
    – maxpayne
    Dec 12, 2012 at 6:39
  • Ok, so if you only care about the edges, your adjacency information isn't actually needed. All you need to do, is maintain a list of edges, and uniqueness is defined by the indices of the vertices. I'll try to elaborate on my answer a bit more.
    – JasonD
    Dec 12, 2012 at 6:47
  • Thanks. I don't understand how to do this. "Do not add the edge if it already exists." But I found a way from your answer. First I sort out all the edges like v1<v2. Then I remove all duplicates from an array so remaining will be Unique edges. It works perfect. Like this. GLTris *e = new GLTris[nb_Tris*3]; int n = getTotalEdges_Sorted(indices, nb_Tris, e); cout<<n<<endl; int ne = RemoveDublicatesFromAnSortedEdgeArray(e, n); for(int i=0; i<ne; i++) e[i].Cout(); How about this.. What would you say ? Is it a good way to do this. or still some issues. i tried it works well by the way.
    – maxpayne
    Dec 12, 2012 at 7:26
1

If surface is simple and closed than by Euler characteristic number of edges is E = F + V - 2. Cube in your example has V=8, F=12.

1

I have learnt a simple trick.
First ,you define a structure which is an unordered pair of vertex indices (for example, a struct{int i,j} that guarantees that i<j). Then create an std::set<UnorderedPair>. Finally, each time you encounter an edge, just insert it into this set. At the end, the number of elements in this set will give you the number of unique edges.

1
  • You mean that in case of a cube there would be 36 pair of vertices. and in each pair v1 should be less than v2 v1<v2. Then after that what I need to do ? could please explain it little in code form. :) I mean in for loop ? I have updated my question please check it now. The issue is I have everything relevant to adjacency of a triangle but which information I need to compare to extract shared edge?
    – maxpayne
    Dec 12, 2012 at 6:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.