load 3d Mesh as C3t3

[nschloe]

I would like to apply Lloyd's method (as described in the docs) to a 3D mesh read from a file.
Is it possible to initialize C3t3 from a file or with points/cells?

[MaelRL]

How is your 3D mesh generated in the first place?

Internally, a C3T3 is a Delaunay triangulation of the convex hull of the points involved. It might thus not be possible to recover your mesh, either because your mesh was not Delaunay, or for other types of problems: for example, your mesh could have a hole shaped like a Schönhardt polyhedron and although it was not an issue for your mesher, it would not possible for the C3T3 to recover the surface facets of the hole (since there does not exist any triangulation of the hole, the facets will certainly not be in the triangulation).

To extend a bit more, the paragraph above lied a bit, it's actually a weighted Delaunay triangulation, so you could potentially fit more triangulations, but (1.) you would have to know which weights to use to get the proper combinatorics, (2.) it still likely wouldn't be strong enough to fit all random non-Delaunay 3D mesh you can generate.

Note that if your 3D mesh was generated with CGAL, or was based on a Delaunay triangulation and you have all the cells (meaning those in the domains, and those outside the domain), then we have some internal functions (see file https://github.com/CGAL/cgal/blob/04bef2b071228a9ff29e7b510ddf77594ededa8b/Mesh_3/include/CGAL/Mesh_3/tet_soup_to_c3t3.h) doing just what you are asking for.

[nschloe]

Thanks @MaelRL for the reply! Interesting points.

How is your 3D mesh generated in the first place?

All sorts of ways, they might or might not fit CGAL assumptions. I would be fine with CGAL saying "sorry, can't import that mesh because it's too weird" as long as I can import the well-behaved ones.

From looking at the code, it seem that either build_triangulation or build_triangulation_from_file are for me. Is there any documentation on how to use those? Or what file format the latter expects?

[MaelRL]

This is completely undocumented, we use it mainly to load meshes generated by the Mesh_3 package into our visualizer, the so-called "Polyhedron demo" that can be built in the Polyhedron/demo/....

From a file format point of view, it is the same as the .mesh file format used by medit (https://www.ljll.math.upmc.fr/frey/publications/RT-0253.pdf), with a twist: as I said above, a C3T3 is triangulation of the convex hull, and then some cells of the triangulation are marked as "in the domain". In that file, we expect all the cells. If you had for example meshed a sphere with a hole inside, the file still requires you to to provide the cells that are in the hole so that the triangulation is a topological ball. In theory we could ask users to only provide cells in the domain and then construct a triangulation to fill the holes (possibly using Steiner points to deal with parts like Schönhardt polyhedra), but we have had no need for it so far, so it doesn't exist.

Another thing that is undefined behavior is if you provide all these cells, but they are not Delaunay. Your triangulation is going to say it's not valid because you violate the empty ball property, and it's likely to explode when you start optimizing, simply because for some large point moves, it'll be dealt as a removal and subsequent re-insertion of that point at a new position, and things are going to get weird because the existing triangulation being Delaunay is an underlying precondition when you insert a new point in the triangulation. As said above, there might exist weights such that you can express your 3D mesh as a weighted triangulation, but I'm not sure if there always exists a solution.

[nschloe]

I said above, a C3T3 is triangulation of the convex hull [...]
If you had for example meshed a sphere with a hole inside [...]

I'd say I can do without meshes with holes for now, but convex meshes are a pretty strong restriction. Anyway, even that would be fine for the trying things out. (I want to compare CGAL's smoother to others/my own.)

It'd be awesome to have an easy-to-use function with which one could just load a c3t3 from a file, and which raises an exception for whenever this isn't possible yet (nonconvex domains).

In theory we could ask users to only provide cells in the domain and then construct a triangulation to fill the holes (possibly using Steiner points to deal with parts like Schönhardt polyhedra), but we have had no need for it so far, so it doesn't exist.

Consider this a +1 on the feature request.