# Identifying connected triangles in a triangular mesh

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

## 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 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 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 on other sites
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 on other sites
Quote:
 Original post by scientiphicI 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 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.

1. 1
2. 2
3. 3
Rutin
22
4. 4
5. 5

• 10
• 16
• 14
• 9
• 9
• ### Forum Statistics

• Total Topics
632928
• Total Posts
3009272
• ### Who's Online (See full list)

There are no registered users currently online

×