I have large vectors of triangles that make up a mesh for a given model.

What I would like to do is find a way to iterate through the mesh looking for shared edges, then move on to the next triangle until I have searched every triangle in the mesh. The triangles are ordered in a vector as I read them from a file, but it may be that there's a better way to setup for this type of search.

Can anyone point to some resources that would help me figure out how to find shared edges?

Do you know if all the shared edges in the mesh will share indices also? Or could there be vertices that share position but not other attributes?

Also, what's the end goal? Are you looking to build something like a 'half-edge' representation for fast real-time operations? Or is this a preprocessing step of some sort for which a brute-force solution might suffice?

I think starting off, this is a pre-processing step where brute-force would work, and then I would eventually like to do cases where there may be small tolerances between the edges and yet still be considered shared. But for now, it's safe to say yes, the vertices share position.

You may already know some of the things I'm going to mention here, but these are just the first thoughts that come to mind.

Quote

...I would eventually like to do cases where there may be small tolerances between the edges and yet still be considered shared.

I'm assuming you actually want to correct these small distances between vertex positions, rather than leaving them as is while still considering them coincident. If so, for that you'd probably want to run a 'welding' step on the mesh first to eliminate such errors, and then move on to topological analysis with the assumption that shared positions match exactly.

For detecting shared positions, one option is to use a vector->integer map, where the vectors are vertex positions and the integers are numeric IDs. Assuming a sorted map (e.g. std::map rather than std::unordered_map in C++), you can use lexicographical comparison on x, y, and z for the comparison function. You can then associate a unique integer ID with each unique position.

I'm just winging it here, but the whole process might look something like this:

for each vertex
  if position is not already in the map
    add it to the map with a new integer ID

for each triangle
  for each vertex
    get the ID for the position and store it as part of the vertex description

At this point you now have vertex 'indices' that you can use, just as if all vertices were entirely shared to begin with.

Then:

for each triangle
  for each edge
    for each triangle
      for each edge
        check to see if the edges are shared based on vertex IDs

Obviously you can optimize that last set of loops to avoid checking triangle pairs redundantly. Also, when checking for shared edges, keep in mind that, assuming consistent winding, the indices for two coincident edges will be in opposite order with respect to one another.

Note that some of the intermediate steps described here, like the position->ID map and storing IDs as part of the vertex descriptions, aren't strictly necessary, but I think they provide some conceptual clarity, and they should make the process more performant.

Maybe this is all too obvious and I'm not telling you anything you don't know, but you can always ask further questions if I'm off base here. Also, the above examples and pseudocode are all off the top of my head - it's been a while since I've implemented these sorts of algorithms, so I may have missed something or gotten something wrong somewhere. If so, maybe someone else will jump in with corrections.

11 hours ago, SR D said:

I have large vectors of triangles that make up a mesh for a given model.

What I would like to do is find a way to iterate through the mesh looking for shared edges, then move on to the next triangle until I have searched every triangle in the mesh. The triangles are ordered in a vector as I read them from a file, but it may be that there's a better way to setup for this type of search.

Can anyone point to some resources that would help me figure out how to find shared edges?

So how exactly are they stored in the file?  For instance, generally on the GPU you have a list of vertexes and a second list of triangles, which is actually a list of sets of 3 indexes into the vertex list. Is the file like this, or do you just have a simple list of sets of 3 vertexes?

5 hours ago, Gnollrunner said:

So how exactly are they stored in the file?  For instance, generally on the GPU you have a list of vertexes and a second list of triangles, which is actually a list of sets of 3 indexes into the vertex list. Is the file like this, or do you just have a simple list of sets of 3 vertexes?

That's pretty much exactly how it is.

8 hours ago, Zakwayda said:

Maybe this is all too obvious and I'm not telling you anything you don't know, but you can always ask further questions if I'm off base here. Also, the above examples and pseudocode are all off the top of my head - it's been a while since I've implemented these sorts of algorithms, so I may have missed something or gotten something wrong somewhere. If so, maybe someone else will jump in with corrections.

All very helpful, thanks for the thoughts.

1 hour ago, SR D said:

That's pretty much exactly how it is.

Sorry I didn't get you. You quoted my whole post. Was it:

A) The two lists: one with vertexes and one with indexes.

or

B) A single list of vertex triads.

Sorry, it's like this. " ... you have a list of vertexes and a second list of triangles, which is actually a list of sets of 3 indexes into the vertex list."

So the file is stored as a list of vertices, x, y, and z. Then the next section is a list of triangles which contains a set of indices into the vertex list.

13 hours ago, SR D said:

Sorry, it's like this. " ... you have a list of vertexes and a second list of triangles, which is actually a list of sets of 3 indexes into the vertex list."

So the file is stored as a list of vertices, x, y, and z. Then the next section is a list of triangles which contains a set of indices into the vertex list.

 

In that case I'd probably just combine the pairs of indexes that represent an edge, into a single number. For instance say you have 2 32 bit indexes, you can make a 64 bit number out of them. Then you can simply insert that into some lookup data structure: hash table, red-black tree .... what have you.  I think that should pretty much take care of it.

On 7/27/2019 at 5:27 PM, SR D said:

Can anyone point to some resources that would help me figure out how to find shared edges?

This is a very good book to have for that type of information.

https://www.amazon.com/Polygon-Mesh-Processing-Mario-Botsch/dp/1568814267