Enhanced Dual Contouring

[TaoliShen]

Taoli Shen GSoC 2025 Submission

Project description

The main objective of this project is to enhance Dual Contouring (DC) in CGAL so that the generated meshes are guaranteed to be 2-manifold. Classical DC is known to produce nonmanifold surfaces, which leads to topological inconsistencies and computational challenges.

Implementation Steps

1. Dual Marching Cubes (DMC) baseline
   I began by implementing the Dual Marching Cubes (DMC) algorithm, which generates dual vertices derived from patches in the marching cubes lookup table. Dual vertices are placed either at the cell-centroid method or computed using the quadratic error function (QEF) from the patch corners.

2. Integration of Topologically-Correct Marching Cubes (TMC)
   To address ambiguous face configurations (e.g. MC case 105), I incorporated the Topologically-Correct Marching Cubes (TMC) rules into DMC. This resolves some of the nonmanifold surfaces.

3. Nonmanifold Edge Resolution (based on Zint, Grosso, and Gürtler)
   Even with TMC integration, DMC can still produce nonmanifold edges (nme) (edges shared by more than two quads) in the case when a tunnel is generated with the TMC look-up table.
   To resolve these, I implemented the method described in
   Resolving Non-Manifoldness on Meshes from Dual Marching Cubes (D. Zint, R. Grosso, P. Gürtler).

Result examples

Before (left) and after (right) applying Zint–Grosso–Gürtler:
three neighboring non-manifold edges (red) are resolved, and the corresponding three tunnels are recovered.

Final report

For more implementation and documentation details, please see my final report:
final report

To-Do

Currently, all nonmanifold edges are resolved, but nonmanifold vertices remain.
The method of Zint–Grosso–Gürtler suggests padding an additional layer of cells,
which addresses nonmanifold vertices on the boundary but does not resolve those in the interior.

List of commits:

7f110ccb984 cleaned up comments
3c69b16a1c4 pad cells to resolve nonmanifold vertices
d68837c6bb4 function overload for dmc_tmc with resolving nonmanifoldness
7235000263d forced operation only on nonmanifold edges with exactly 4 incident quads; otherwise mesh generation may fail
cee58a1ba0b debugging basically done. now works (almost) as expected. just need a bit housekeeping
93ecf9a2d3d now it compiles
18fdd847bc7 implementation of resolving nonmanifold is complete. now need to debug
ed91f6fd1c6 compressed some output messages
13fc33e4b09 added features that detect whether a nonmanifold edge is generated from tunnel reconstruction of p_slice (tmc post-processing)
9165fdfed8c added some debug cases and invalid points filtering
6eda0008dde there's error in the the gradient computation by finite difference--null gradient vectors created by nan points, possibly out of bound. Investigating...
a38abcfa275 fixed tmc generate holes bug
68c2f39ab95 some more debugging message for tmc_dmc
5422304fafc implemented topologically correct dual marching cube, though subsequent debug may be needed
c3dfa7fb39c some debug call and cleaned up the code
9e0ac4b7f2a added dual vertex strategy--patch centroid
8cc36ee04b5 added the rotate sin wave layer function