Jump to content
  • Advertisement
Sign in to follow this  
vegi

Border of a Mesh

This topic is 3337 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, i´m trying to find an efficient algorithm for finding the border-vertices(segments) of a Mesh in 2D. The information i have: - muuuuuuch vertices with their ID an Coordinates - a list of the triangles of the mesh ( with the 3 vertex-ID´s) The idea is to loop the triangles and search for another triangle with 2 same Vertices. So i have to do this for Vertice 1 and 2, 2 and 3, 1 and 3. If there is a second triangle it is not an edge of the mesh, otherwise i add those two vertices to my border-vertice-list. But i think this is not very efficient. Maybe anyone already has a solution for c# ?

Share this post


Link to post
Share on other sites
Advertisement
This seems like a very easy problem to solve if you can use an associative container. I don't know any C#, but if you still can't figure it out I'll try to give you some sample code (probably in C++).

Share this post


Link to post
Share on other sites
No, i´m not searching for the convex hull, i´m searching for the edge(vertice)s of a mesh.

@alvaro: jeah i think you are right. I will try it with hash arrays.

Share this post


Link to post
Share on other sites
In pseudo-code (assuming your triangles are oriented, it works for any dimension):
for each edge (v1, v2) {
if (v1<v2)
count[v1][v2]++;
else
count[v2][v1]--;
}

for each index i in count {
for each index j in count {
if (count[j]!=0) {
border_vertices.insert(i);
}
}
}

Share this post


Link to post
Share on other sites
this is my current code and it works:

ArrayList al_border = new ArrayList();
Hashtable ht_Triangle = new Hashtable();
foreach (Triangle item in this.Triangles)
{
ht_Triangle.Add(" " + item.ID_1 + " " + item.ID_2 + " ", item);
ht_Triangle.Add(" " + item.ID_2 + " " + item.ID_3 + " ", item);
ht_Triangle.Add(" " + item.ID_3 + " " + item.ID_1 + " ", item);
}
foreach (Triangle item in this.Triangles)
{
String key1 = " " + item.ID_2.ToString() + " " + item.ID_1.ToString()+ " ";
String key2 = " " + item.ID_3.ToString() + " " + item.ID_2.ToString() + " ";
String key3 = " " + item.ID_1.ToString() + " " + item.ID_3.ToString() + " ";
if (!ht_Triangle.ContainsKey(key1))
al_border.Add(new Segment(item.ID_1, item.ID_2));
if (!ht_Triangle.ContainsKey(key2))
al_border.Add(new Segment(item.ID_2, item.ID_3));
if (!ht_Triangle.ContainsKey(key3))
al_border.Add(new Segment(item.ID_1, item.ID_3));
}






But would be nice if someone could find an optimization for this problem.

Share this post


Link to post
Share on other sites
On little note: if your mesh is texture mapped, there is a chance that there are vertices with same position but different texture co-ordinates, so you need to adapt the above to handle when two different vertex ID's refer to the same geometric position.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!