tetrahedrizing a mesh

Question

I am looking for an algorithm that receives a 3d surface mesh (i.e comprised of 3d triangles that are a discretization of some manifold) and generates tetrahedra inside the mesh's volume.

i.e, I want the 3d equivalent to this 2d problem: given a closed curve, triangulate it's interior.

I am sorry if this is unclear, it's the best way I could think of explaining it.

For the 2d case there's Triangle. For a 3d case I could find none.

Copra

You want to break it up in pieces later? Like in physics simulation? If yes, it seems very interesting! And, oh, I believe plural form is tetrahedra (based on en.wikipedia.org/wiki/Tetrahedron). – Keeley

I believe the 2 terms used more frequently are tetrahedralization and 3d triangulation. Check out this talk for a good overview: archive.org/details/lecture_10309 – Transcontinental

A quite interesting problem. I even have a hard time coming up with the brute force exhaustive algorithm. Does "for every triangle, pick another vertex in the mesh to add a new tetrahedron (by trying all vertices) that does not intersect a previous one" even work? I think this does not even work in 3d without additional vertices in the general case. – Mahon

Is the original mesh convex or arbitrary? Can the tetrahedra in the interior be arbitrary in size, or are there angle / size / volume constraints on them? – Oletaoletha

@Oletaoletha - the mesh is not convex. There are no constraints - I think even state of the art algorithms can give very little guarantees as the ones you mention. But I am looking for a package, not a suggested algorithm. – Copra

Answer 1

I found GRUMMP which seems to answer all the needs mentioned in the question, and more...

Copra

Were you able to download GRUMMP onto a windows computer? – Telegenic

Answer 2

pygalmesh (a project of mine based on CGAL) can do just that.

pygalmesh-volume-from-surface elephant.vtu out.vtk --cell-size 1.0 --odt

https://github.com/nschloe/pygalmesh/#volume-meshes-from-surface-meshes

Sandy

I am using marching cubes to identify objects. I then create a triangular mesh. I see from your package that it is possible to calculate volume from a surface mesh. I see that your elephant file is in the form '.vtu'. Do I need to convert my mesh into this form? Also, very impressed at your project. – Telegenic

pygalmesh understands all formats that meshio does -- many. – Mcinerney

Nico, I've been trying to download pygalmesh, but it doesn't see where Eigen\Dense is.. Do you have any idea how to resolve this? – Telegenic

Schlomer I've done that. I am using a Windows machine. This is very complicated and not working. I do not know how to change the setup.py for pygalmesh. My problem is very similar to github.com/nschloe/pygalmesh/issues/64 – Telegenic

Answer 3

I haven't had any experience using GRUMMP, but as far as a 3D version of triangle there is tetgen. If you know the triangle switches it is built to resemble it. It also has fairly decent documentation and a python wrapper for it and triangle.

http://wias-berlin.de/software/tetgen/

http://mathema.tician.de/software/meshpy/

Telling