# ==Dual Contouring==
<p class="doc-sub">// status: seedling</p>
If [[Marching Cubes]] is the "smooth blob" algorithm, Dual Contouring is the "keep the sharp edges" algorithm. Introduced by Ju, Losasso, Schaefer & Warren in 2002, it's the iso-surface extractor you want when you're carving with a flat brush and want the flat bits to stay flat.
# The dual trick
Marching Cubes is _primal_: it puts vertices _on_ the edges of cells. Dual Contouring is _dual_: it puts one vertex _inside_ each cell, then connects vertices of the four cells sharing a sign-crossing edge into a quad.
That flip gives DC two superpowers:
1. **Adaptive resolution is natural** — since each cell has one vertex, you can have an octree with cells of different sizes and still connect them cleanly.
2. **Sharp features are recoverable** — if you have _normals_ at the sign-crossing points (not just positions), you can place the interior vertex at the location where those planes meet.
# Hermite data
DC doesn't work from just the scalar field. You need ==Hermite data==: for each edge that crosses the iso-surface, both the crossing _position_ and the _normal_ of the surface there. For analytic SDFs you get both trivially. For sampled data (a CT scan, noise-based terrain) the gradient gives you the normal.
# The QEF
For each cell, collect all its edges that cross the surface. Each crossing gives you a point `p_i` and a normal `n_i` — implicitly a plane `n_i · (x − p_i) = 0`. Place the cell vertex at the point that minimises the sum of squared distances to all these planes:
$E(x) = \sum_i (n_i \cdot (x - p_i))^2$
This is a ==Quadratic Error Function== (QEF). Expand it and it's a linear least squares problem in 3 unknowns. Solve with SVD — not a normal equation — because many cells are underdetermined (one plane, a flat feature) and SVD gives you the minimum-norm solution with graceful degradation.
```c
// Pseudo: minimise || A x - b ||^2 with SVD, clamp x into the cell bounds.
Mat3 A; // rows are n_i
Vec3 b; // b_i = n_i . p_i
for (crossing in edges) {
A.addRow(crossing.normal);
b.addRow(dot(crossing.normal, crossing.pos));
}
Vec3 x = svdSolve(A, b, massPoint); // mass point = average of p_i as a fallback
x = clampToCell(x); // keep the vertex inside the cell
```
The mass point is a regularisation trick: bias the solution toward the average of the crossing points so that underdetermined cells give sensible results.
Clamp the final vertex to the cell bounds. Without this, sharp features can place vertices arbitrarily far outside their cell, creating self-intersecting geometry.
# Building the mesh
Once every cell has a vertex, the mesh is implicit in adjacency:
- For every cell _edge_ that crosses the surface, the four cells sharing that edge each have a vertex — connect them into a quad.
- Orient consistently using the sign of the edge crossing.
In an octree with different cell sizes, the "four cells sharing an edge" become potentially `2×` or `4×` smaller cells on one side. The same adjacency logic still works, you just walk the tree to find the neighbours at each scale.
# Variants and fixes
The classic DC paper has a few known problems that later work addressed:
- **Non-manifold output** — a single cell can have multiple disjoint surface patches inside it. Vanilla DC places _one_ vertex, which welds them together. **Manifold Dual Contouring** (Schaefer & Warren) detects this and splits the cell into multiple vertices.
- **Self-intersections** — particularly on thin features. Clamping to the cell and constraining the QEF helps; more robust variants add explicit checks.
- **Intersection-free contouring** (Ju et al., 2006) — extensions that guarantee no self-intersection.
# DC vs Marching Cubes — when to reach for each
| Property | Marching Cubes | Dual Contouring |
|----------|----------------|-----------------|
| Sharp features | No — rounds edges | Yes, with Hermite data |
| Adaptive LOD | Ad hoc (Transvoxel) | Native via octree |
| Input needed | Scalar values | Values + edge normals |
| Mesh regularity | Triangles, higher count | Quads, fewer elements |
| Topological robustness | Ambiguity cases | Non-manifold cases |
| Implementation effort | Low | Medium–high (SVD, octree plumbing) |
Rule of thumb: if you're building Minecraft-style sculpting with flat walls and 90° corners, DC. If you're rendering a medical scan or organic terrain, MC (or Surface Nets) is simpler and fine.
# Things that tripped me up
- **SVD on the small matrix** — rolling your own 3×3 SVD is fiddly. I've used the Givens-rotation variant from the DC reference code. Don't use the normal equations (`A^T A`), they square the condition number.
- **Cell clamping is not optional** — without it, outputs look plausible but self-intersect under stress.
- **Hermite data quality** — the whole algorithm stands on the accuracy of your normals. A finite-difference gradient at a lousy step size ruins sharp features.
- **Octree neighbour walks** — the part that takes the longest to write. The DC mesh is only as clean as your adjacency logic.
# References
- Ju, T., Losasso, F., Schaefer, S., & Warren, J. — _Dual Contouring of Hermite Data_ (SIGGRAPH 2002)
- Schaefer, S., & Warren, J. — _Dual Contouring: "The Secret Sauce"_
- Lin Reid's blog has an approachable implementation walk-through; Nick Gildea's "Dual Contouring the Easier Way" is the other one I reread often.
---
Back to [[Index|Notes]] · see also [[Marching Cubes]] · [[Sparse Voxel Octrees]] · [[Spatial acceleration structures]]