Remeshing

Remeshing

Geogram has a remesher for smooth surface, well adapted to post-process the output of reconstructions. It is implemented in geogram/mesh/mesh_remesh.h.

If you want to know the gritty details: The algorithm is based on the notion of Centroidal Voronoi Tesselation, that optimizes the placement of a set of points on a surface in such a way that it minimizes a certain objective function (called the quantization noise power) [1,2]. The algorithm in Geogram is based on a Newton solver, that exploits the C2 smoothness of the objective function [3,4]. The anisotropic mesher works in 6D, and obtains an anisotropic 3D mesh as the projection of a 6D anisotropic one [5,6]. It exploits the "security radius" theorem [6], that lets one obtain a restricted Voronoi diagram without needing to compute a full Delaunay triangulation (which would be prohibitive in 6D !).

Isotropic remeshing (with equilateral triangles)

The simplest form of the algorithm produces an isotropic mesh (with mostly equilateral triangles) from the input mesh:

   Mesh remesh;
   GEO::remesh_smooth(mesh, remesh, nb_points);

where nb_points corresponds to the desired number of points in the remesh. The result is shown in the first column of the figure at the beginning of this page.

One can use an attribute to steer the density of the mesh. If an Attribute<double> named "weight" is attached to the vertices of the mesh, then it will be taken into account.

A natural choice is the so-called "Local Feature Size" (LFS), that measures both the curvature and the thickness of the shape. It can be computed by the LocalFeatureSize class and with the compute_sizing_field() utility function in geogram/mesh/mesh_geometry.h.

  compute_sizing_field(mesh, factor);

where factor is the exponent applied to LFS. The effect is shown in the figure (top of this page).

Instead of calling compute_sizing_field(), one can use instead his own attribute to steer mesh density, as follows:

   Attribute<double> weight (mesh.vertices.attributes(), "weight");
   for(index_t v: mesh.vertices) {
      weight[v] = ...;
   }

Anisotropic remeshing (with curvature-adapted triangles)

For anisotropic meshing, one needs to prepare the input mesh as follows:

   compute_normals(mesh);
   simple_Laplacian_smooth(mesh, nb_iter, true); // true: smooth normals
   set_anisotropy(mesh, anisotropy*0.02);

• the first step computes the normal to the vertices, and appends them to the coordinates of the vertices. Each vertex has then x,y,z,nx,ny,nz
• the second step smooths the normal coordinates. Doing so is important if the mesh is very irregular, as for instance meshes obtained from surface reconstruction
• the third step scales the coordinates of the normal with an anisotropy factor. The effect is shown on the second row of the figure.

One then calls GEO::remesh_smooth(mesh, remesh, nb_points) to remesh the surface.

References

[1] Least squares quantization in PCM, Stuart Lloyd, 1982, IEEE Transactions on Information Theory, 1982

[2] Centroidal Voronoi Tessellations: Applications and Algorithms,_Qiang Du, Vance Faber and Max Gunzburger, SIAM review, 1999 PDF

[3] On centroidal voronoi tessellation - energy smoothness and fast computation, Yang Liu, Wenping Wang, Bruno Lévy, Feng Sun, Dong-Ming Yan, Lin Lu and Chenglei Yang, ACM Transactions on Graphics, 2009 HAL

[4] Isotropic Remeshing with Fast and Exact Computation of Restricted Voronoi Diagram, Dong-Ming Yan, Bruno Lévy, Yang Liu, Feng Sun and Wenping Wang, Computer Graphics Forum, 2009, HAL

[5] Anisotropic and feature sensitive triangular remeshing using normal lifting, Vincent Nivoliers, Bruno Lévy and Christophe Geuzaine, Journal of Computational and Applied Mathematics, 2015, HAL

[6] Variational Anisotropic Surface Meshing with Voronoi Parallel Linear Enumeration, Bruno Lévy, Nicolas Bonneel, IMR, 2012, HAL