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.

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.

I think with
3D Convex Hull algorithm you can generate the surface triangles.

But i am not sure. You can give a try.

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!

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.

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]