Jump to content
  • Advertisement
Sign in to follow this  
rajesh_nest

Surface triangles from tetrahedral mesh

This topic is 2988 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 need to extract the surface triangles from a large tetrahedral mesh.
My current method is not optimal( Since my graphics knowledge is very limited).
Method I adopted is finding non-overlapping triangles of entire tetrahedrons.
(Surface triangles will not overlap with other triangles.).i.e For each tetrahedron, I extract their 4 triangles and compare with the triangles of each other tetrahedrons (comparison is done by checking whether the indices of trianlges are same,if so they are overlapping).I am storing the extracted triangles in a hashmap. In the end of processing hashmap will store surface triangles.

Now I want to completely replace the current method.I am not interested in replacing the data structure with some other data structures such as list,tree etc and achieve better performance. Rather I am looking for alternative algorithms in Computational Geometry or Graphics,which can extract surface triangles.

Share this post


Link to post
Share on other sites
Advertisement
Are you generating the tetrahedron mesh yourself?

If so, add in the adjacency information while generating the mesh. This is how it's done in the real world. This information is like gold. Not saving it while it's handy is criminal.

If not, then it looks like you're kind of going in the right direction: the tets that have less than 4 neighbours are the tets that have at least 1 face along the surface of the mesh (e.g., faces on surface = 4 - number of neighbours). It's that simple if you have the adjacency information. So yep, enumerate all those vertices, edges, faces and tets, and you've got what you need. You might want to speed things up by chopping things up into an octree or using BSP (e.g., no sense in comparing a pair vertices to see if they're duplicates when they are both on completely opposite ends of the mesh!!).

Finally, these two statements are entirely contradictory:

- I am not interested in replacing the data structure with some other data structures such as list,tree etc and achieve better performance.

- Rather I am looking for alternative algorithms in Computational Geometry or Graphics,which can extract surface triangles.

Share this post


Link to post
Share on other sites
What format is the data you have? Just a big list of indices?

If so I think the algorithm you describe is optimal.

Start with an empty set.
For each tetrahedron:
For each triangle of the tetrahedron:
Look up the triangle in the set
If the triangle is in the set, delete it
If the triangle is not in the set, insert it

At the end your set will contain any triangle that is adjacent to only one tetrahedron, which should be the boundary triangles.

I don't see how you can do any better, since this algorithm is O(n) and you have to visit each tetrahedron at least once.

Share this post


Link to post
Share on other sites
Quote:
Original post by Pragma
What format is the data you have? Just a big list of indices?

If so I think the algorithm you describe is optimal.

Start with an empty set.
For each tetrahedron:
For each triangle of the tetrahedron:
Look up the triangle in the set
If the triangle is in the set, delete it
If the triangle is not in the set, insert it

At the end your set will contain any triangle that is adjacent to only one tetrahedron, which should be the boundary triangles.

I don't see how you can do any better, since this algorithm is O(n) and you have to visit each tetrahedron at least once.


Brilliant!

Share this post


Link to post
Share on other sites

Thanks to all for the suggestions. I had earlier implemented the algorithm suggested by Pragma.Of course format of my mesh data is list of indices, vertices,physical parameters.

The algorithm is very compute intensive for large mesh data.

My two meshes one with 10 Million tetrahedrons(Data file size 1.5 GB) and other 100 million tetrahedrons (Data file size 48 GB),needs 3 minutes and 48 minutes respectively to compute the surface triangles.Algorithm is running on Intel Quad core machine with 8 GB RAM. (This Time taken does not include File Reading part).

I am looking for a much better performance which can given a speed of atleasr 20x.

How can I optimize and achieve desired speed up.






Share this post


Link to post
Share on other sites
Quote:
Original post by taby
You might want to speed things up by chopping things up into an octree or using BSP (e.g., no sense in comparing a pair vertices to see if they're duplicates when they are both on completely opposite ends of the mesh!!).



If I chop the mesh into a tree,I may have to compare the surface triangles between the chops, inorder to esnure that no one surface triangle are in two differnt Partitions. But won't it be more time consuming?

[Edited by - rajesh_nest on July 19, 2010 4:34:41 AM]

Share this post


Link to post
Share on other sites
I don't see how spatial partitioning will help. The problem as stated is purely topological and doesn't depend on the position of the vertices at all; he shouldn't even need to read that data to figure out the indices of the surface triangles.

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!