Jump to content
  • Advertisement
Sign in to follow this  
GameLad

Select Connected Triangles

This topic is 866 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

I have a file exported from a 3d application like Blender or Maya. I am able to read the files. I end up with indices describing each triangle and a vertex list.

The file can have more than one connected mesh, two spheres for example. I want to select individual meshes by finding connected triangles (sharing at least one connected vertex). What is the best way to do this? What geometric algorithms can I use? Any examples? Can it be multi threaded?

Share this post


Link to post
Share on other sites
Advertisement

Is storing sub meshes in the actual file an option? It would be the easiest option to do this from your modelling application. Otherwise, this sounds like some nasty brute force work to me. Perhaps there is a better way but first you build neighbouring information for each face (if two faces share an index then they are neighbours but sharing only edges might be an option too), that in itself is quite heavy.

 

Then it gets very brute force heavy, have a list of all your faces (doesn't need to be a list as such, just some way of storing which faces have been done), pick the first one and move it to your first sub mesh list, then look at all it's neighbours and add them to the sub mesh list too. Then go to the next triangle in the sub mesh list, add all it's neighbours triangles to the sub mesh list if they aren't already in there. Repeat for the next triangle in the sub mesh list until eventually you are at the end of the sub mesh list. The sub mesh list then should contain one sub mesh.

 

Check the triangles still in the main list that haven't been used yet, pick the first and add that to your next sub mesh list and repeat the previous process. Keep going until all the triangles have been used.

 

That is very brute force heavy, involves a great deal of searching which could perhaps be alleviated by storing a value for each triangle saying which sub mesh it is in. Initially it could be -1, then as you add them to sub meshes you would set it to 0, 1, 2 etc. That way you don't have to go through the long process of checking if the triangle is already in the sub mesh, you just check that value isn't -1 (and a sanity check to make sure it is in the correct sub mesh that you are working on). What you are doing there is starting at a point and branching out of every possibility until you come to leaves, creating what is in effect a bunch of tree graphs. This must have been tackled previously so I'm sure there's a better solution to it.

 

I don't think my suggestion lends itself very well to multi threading at all.

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!