Please Steal my Meshing Algorithm Idea
Recommended pre-requisites: read my earlier posts on 2D Contouring and Quadratic Error Functions, or have familiarity with implicit surface meshing. This is a relatively dense post intended for people with experience in the field.
Meshing implicit surfaces is a hard problem that I've been thinking about for many years. Ideally, you want an algorithm that is guaranteed to output a mesh with a bunch of desirable properties:
- Manifold
- Correctly reproducing sharp features (corners and edges)
- Correctly reproducing thin features
- Not self-intersecting
- Density scaling with complexity (i.e. flat surfaces have fewer triangles)
- Not terrible triangle quality
(Some of these are optional: you can always take a self-intersecting mesh and pass it through TetWild, or take a fully dense mesh and decimate it; still, a man can dream)
I'm typically operating in a regime where I can evaluate the function at arbitrary points and receive two values:
- A signed distance value (with C0 continuity but no higher guarantees, e.g. not necessarily Lipschitz continuous)
- Gradients (through automatic differentiation)
In libfive and Fidget, I implemented Manifold Dual Contouring, which is a local maxima in the solution space. It uses Quadratic Error Functions to positions vertices on sharp features, and guarantees manifold output by construction.
However, the resulting meshes may have self-intersections, and thin features are only captured if they happen to lie on the sampling grid. There are also scale-invariant adversarial models, which can bite you depending on how your model aligns with the sampling grid.
I have a vague idea for a meshing algorithm – which I have told a bunch of people in person – but wanted to post for a wider audience.
Here's the sketch:
- Sample your function on a grid, tagging points as inside or outside
- On every edge with different endpoints, perform binary search to find a surface point
- Use dual contouring-style QEFs to compute sharp feature points. Evaluate the function at the feature point and tag them as inside or outside
- Build a tetrahedralization of all of these tagged points (Delaunay or similar)
- If any edges in the tetrahedralization connect an inside and outside point directly, perform binary search to find a surface point, then add it to the tetrahedralization
- Repeat until the system stabilizes
- Your triangulation is all of the faces of tetrahedrons where all three corners are tagged as surface, and the additional vertices in the two tets sharing the triangle have different signs (to prevent zero-thickness walls)
You may note that steps 1-3 are basically the same as Dual Contouring. That is intentional – the core idea here is to separate "generating surface points" from "building a manifold mesh". Using a tetrahedralization means that the mesh will be manifold and free from self-intersections; using QEFs to locate points means that we will capture sharp features.
The cool part about separating point generation from meshing is that we could mix in other strategies for finding surface points:
- Check triangles in the tetrahedralization and inject additional QEF-generated points if their normals are sufficiently divergent, per Kobbelt '01
- Generate additional points by detecting thin features, per Schaefer '05
- Find most or all surface intersections along grid edges, per Baktash '26
There's also a bunch of room for experimentation. A few quick variations:
- Tag the QEF points as surface points directly, instead of tagging them as inside / outside (which forces a local binary search and may lead to clusters of very-near vertices). More efficient, but less rigorous!
- If a QEF launches a point out of its containing cell, inject Steiner points based on its eventual location (e.g. one per cell encountered on a DDA walk to the new location)
- Use probabilistic QEFs instead
There are two reasons why I haven't implemented this myself:
- The first is simply time – this is a big project, and I only have so many hours
- The second is that this requires a bulletproof implementation of incremental Delaunay Tetrahedralization, which is a significant research project in its own right. I implemented Constrained Delaunay Triangulation a few years ago, which was already quite a challenge – and it was neither 3D nor incremental!
There may also be edge cases that this doesn't handle well; whoever implement it first gets to find out! After writing everything up, I'm tempted to throw together a 2D implementation myself...
As always, please send me a note if you've got comments or citations that I should check out.