Mesh Reconstruction Algorithms Specifications

Explanation of the algorithms for converting a point cloud into a mesh.

CGAL documentation link : Documentation

---

Table of Contents

• Algorithms Parameters Description
• Poisson Algorithm
• Frontal Surface Reconstruction Algorithm
• Scale Space Surface Reconstruction Algorithm

---

Algorithms Parameters Description

Scale Space Surface Reconstruction - scale_space

Parameter Name	Description	Default Value
-i, --iterations	Number of smoothing iterations. The higher the number is, the smoother the constructed mesh will be (fewer faces)	4

Advancing Front Reconstruction - advancing

No parameters

Poisson Reconstruction - poisson

Parameter Name	Description	Default Value
-d, --detail	Controls the level of detail. A high number removes small structures. Conversely, a low number means the algorithm pays attention to small details, but is more sensitive to noise.	6
-s, --smoothing	Controls the mesh smoothing factor. A higher value results in a smoother mesh; a lower value results in a more detailed mesh.	24

Poisson Algorithm

CGAL documentation : Poisson Algorithm

Input: Points P with normals N

1. Construct a Delaunay triangulation (3D);
2. Refine the triangulation;
3. Construct the vector field V from the normals;
4. Assemble the linear system (Δf = div(V));
5. Solve to obtain f;
6. Extract the isosurface f = λ;
7. Generate the mesh;

Output: Triangulated mesh

---

Detailed Explanation :

1. Construct the Delaunay triangulation (3D)

   • We divide the space into small tetrahedra from the points

2. Refine the triangulation

   • We improve this structure to avoid anomalous shapes (too flat or stretched)
   • We add points if necessary

3. Construct the vector field V from the normals

   • Each point has a normal
   • We use these directions to "fill the space" with consistent directions

4. Assemble the linear system (Δf = div(V))

   • We construct a large mathematical equation that connects everything
   • Simple idea : We look for a function f that best follows the normals
   • We obtain a system of equations to solve

5. Solve to obtain f

   • We solve this system
   • We obtain a function f defined everywhere in space

6. Extract the isosurface f = λ

   • We choose a value (λ)
   • We Retrieves all points where f equals this value
   • This results in a surface

7. Generate the mesh

   • This surface is transformed into triangles (a format usable in 3D)

---

Advantages

• Automatically generates a closed surface (complete object)
• Produces smooth and visually clean surfaces
• Robust to moderate noise (small errors filtered out)
• Capable of filling gaps in the data
• Global method → ​​consistent result across the entire object
• Good quality for organic and complex shapes

Disadvantages

• Requires properly oriented normals
• Sensitive to outliers (aberrant points)
• Smooths details → loss of sharp edges
• Requires a dense cloud for good results
• High memory cost (large datasets)
• Parameters sometimes difficult to adjust

---

Frontal Surface Reconstruction Algorithm

CGAL documentation : Advancing Front Surface Algorithm

def : CGAL::advancing_front_surface_reconstruction()

Input: points P

1. Construct a Delaunay triangulation (3D);
2. Select an initial triangle (smallest radius);
3. Initialize the front (edge ​​of the surface);
4. Add neighboring candidate triangles to a priority queue;
5. While the queue is not empty:
    - Take the most plausible triangle
    - Check that it is valid (correct topology)
    - Add it to the surface
    - Update the front
    - Add new candidate triangles
6. Repeat until all candidates are exhausted;

Output: triangulated mesh

---

Detailed Explanation :

1. Construct the Delaunay triangulation (3D)

2. Select an initial triangle (smallest radius)

   • We choose a reliable (well-formed) first triangle
   • This triangle serves as the starting point for the reconstruction

3. Initialize the front (edge ​​of the surface)

4. The front corresponds to the current edge of the surface being constructed, that is, the edges on which new triangles can be added.

5. Add neighboring candidate triangles to a priority queue

   • We retrieve the neighboring triangles from the front
   • They are stored with a "quality" (plausibility) score

6. While the queue is not empty:

   • Take the most plausible triangle
   • We choose the best candidate based on its size and orientation
   • Verify that it is valid (correct topology)
   • We avoid errors (inconsistent holes, non-manifold surface)
   • Add it to the surface
   • The triangle is integrated into the mesh
   • Update the front
   • The edge of the surface changes (some edges disappear, others appear)
   • Add new candidate triangles
   • Add the new neighbors from the front

7. Repeat until all candidates are exhausted

8. We therefore obtain a complete (or maximum possible) surface.

Simple summary: we start with an initial triangle and we "grow" the surface by progressively adding the most coherent triangles around the current edge.

---

Advantages

• Fast and efficient
• Does not require normals
• Local construction → good control
• Good accuracy on details
• Works on non-uniform data

Disadvantages

• Sensitive to noise and outliers
• Difficulty with large holes
• Parameter dependent
• Can produce incomplete surfaces
• Does not always guarantee a perfect topology
• Can freeze if data are insufficient

---

Scale Space Surface Reconstruction Algorithm

CGAL documentation : Scale Space Surface Algorithm

def : CGAL::Scale_space_surface_reconstruction_3

Input: Points P

1. Estimate the neighborhood (radius / local density);
2. Construct the scale-space (multi-scale space);
3. Scale up (smoothing of points);
4. Repeat the smoothing over several iterations;
5. Reconstruct the surface on the smoothed points;
6. Reproject the points to their initial position;

Output: Triangulated mesh

---

Detailed Explanation :

1. Estimate the neighborhood (radius/local density)

   • We determine which points are close to each other
   • This allows us to define an “influence zone” for each point

2. Construct the scale space (multi-scale space)

   • We consider several versions of the point cloud
   • Each version corresponds to a different level of detail

3. Increase the scale (smoothing of points)

   • The points are slightly shifted to smooth out the noise
   • Small irregularities gradually disappear

4. Repeat the smoothing over several iterations

   • The more iterations is, the smoother the model becomes
   • We simplify the overall geometry

5. Reconstruct the surface on the smoothed points

   • We create a mesh from the simplified point cloud
   • The reconstruction is more stable (less noise)

6. Reproject the points to their initial position

7. We maintain the mesh connectivity
8. But we place the points back in their original positions
9. This results in a surface that accurately reflects the data

Simple summary: we progressively smooth the point cloud to remove noise, we build a mesh on this simplified version, then we apply this mesh to the original points.

---

Advantages

• Handles noise and outliers well
• Works with unstructured clouds
• Suitable for real-world data (scans, photogrammetry)
• Allows control over the level of detail (via iterations)
• Can handle irregular sampling patterns
• Good overall stability

Disadvantages

• Can lose fine details (due to smoothing)
• Sensitive parameters (radius, iterations)
• Can create topological artifacts
• Does not always guarantee a manifold surface
• Can produce double surfaces (interior/exterior)
• More complex to configure correctly