Sign in to follow this  
scientiphic

Identifying connected triangles in a triangular mesh

Recommended Posts

Hi All, I have a list of triangles (with vertices) that I obtained by using the marching cubes algorithm on a 3d data field. I would like to generate a (linked) list of connected triangles for subsequent processing (not all triangles may be connected to each other, so there may be several closed polygons in the data field). Could someone pl suggest any algorithm that can do this efficiently (pseudocode will also be great)?

Share this post


Link to post
Share on other sites
The quick and dirty way would be to see if two triangles share two vertices (and thus an edge).

Of course, when a vertex is shared by two triangles there may be a small numerical discrepancy in its position from one triangle to the next. That is, using == to compare them will not work, and so you should consider them to be equal if the distance between them is very small (e.g: 1e-5 or whatnot, depending on the size of the triangles).

Since you're using marching cubes, you won't have to wait until the final mesh is complete before beginning the tests. For instance, when comparing one triangle with the others, you only have to consider the triangles within that marching cube and its neighbouring cubes (there are 26 neighbours, some may be unnecessary to check since some would only allow for one shared vertex right where the cube corners meet).

It seems then that it might be a good idea to keep track of which cube each triangle belongs to.

Share this post


Link to post
Share on other sites
It's pretty simple. Run a DFS (http://en.wikipedia.org/wiki/Depth_first_search) several times, each time starting from an unvisited triangle. Each triangle visited by a DFS run is marked as visited and as belonging to the same component. Continue this until there aren't any unvisited triangles left.

Only connectivity information needed is the neighbouring triangles of each triangles. This can be either triangles sharing a vertex, or only those sharing an edge depending on your needs.

Share this post


Link to post
Share on other sites
[quote]Original post by _swx_
It's pretty simple. Run a DFS (http://en.wikipedia.org/wiki/Depth_first_search) several times, each time starting from an unvisited triangle. Each triangle visited by a DFS run is marked as visited and as belonging to the same component. Continue this until there aren't any unvisited triangles left.

Thanks let me check that out.

I have a follow-up query. Say I start with a triangle, store its vertices (which are in double precision) in a data structure, then pick the next triangle. To check if the new triangle has any vertices shared with the first one, is it standard to check each new vertex with the first three vertices using the coordinate locations, or are there smarter ways to check for neighbors? Checking floating point numbers can be really time consuming, I would imagine.

I am wondering if I can generate a unique integer based on a vertex coordinate (since all non-overlapping vertices have unique coordinates). So, when I pick a new vertex - and if this vertex coordinate co-oincides with an earlier one - this unqiue integer will immediately tell me that this is a duplicate vertex and is thus shared by an earlier triangle.

Share this post


Link to post
Share on other sites
Quote:
Original post by scientiphic
I am wondering if I can generate a unique integer based on a vertex coordinate (since all non-overlapping vertices have unique coordinates). So, when I pick a new vertex - and if this vertex coordinate co-oincides with an earlier one - this unqiue integer will immediately tell me that this is a duplicate vertex and is thus shared by an earlier triangle.


A std::set would work for generating unique 3D points, providing that you code the required sort operator so that it takes small numerical discrepancy into account.

Share this post


Link to post
Share on other sites
I would simplify your problem first before connecting the triangles.

Build an unique list of vertices first, then build an unique list of edges. Then from there you have enough good data to link triangles very fast
with no problems.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this