11

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.

olamundo
  • 23,991
  • 34
  • 108
  • 149
  • 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 http://en.wikipedia.org/wiki/Tetrahedron). – Bartek Banachewicz Aug 12 '12 at 11:57
  • I believe the 2 terms used more frequently are tetrahedralization and 3d triangulation. Check out this talk for a good overview: http://archive.org/details/lecture_10309 – Eric Aug 18 '12 at 18:32
  • 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. – starmole Sep 27 '12 at 09:48
  • 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? – Mikeb Sep 27 '12 at 19:18
  • @Mikeb - 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. – olamundo Sep 28 '12 at 21:51

3 Answers3

3

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

enter image description here

Nico Schlömer
  • 53,797
  • 27
  • 201
  • 249
  • 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. – McM Apr 26 '20 at 21:10
  • 1
    pygalmesh understands all formats that [meshio](https://github.com/nschloe/meshio) does -- many. – Nico Schlömer Apr 26 '20 at 21:31
  • 1
    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? – McM May 02 '20 at 08:00
  • 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 https://github.com/nschloe/pygalmesh/issues/64 – McM May 02 '20 at 08:40
1

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

olamundo
  • 23,991
  • 34
  • 108
  • 149
0

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/

fatalaccidents
  • 192
  • 1
  • 2
  • 13