1 Ground truth and SDF samples
We start from a closed curve (loaded from an SVG) and sample its signed distance function D, negative inside and positive outside. This is what our algorithm takes as input. Each sample (\mathbf{x}_i, d_i) is drawn as a circle of radius |d_i|: red outside, blue inside.
The disk of each circle lies entirely on one side of the curve, and the circle touches the curve at the sample's closest point \mathbf{a}_i = \mathbf{x}_i - d_i \nabla D(\mathbf{x}_i). So every sample implies a second, zero-valued constraint somewhere on its circle: its tangent point. We do not know where it is, because we do not know \nabla D. Finding it is the heart of the method. Hover over a sample to see its true tangent point.
2 Optional Power diagram and exposed arcs
A tangent point cannot be inside another sample's disk, since that disk contains no surface. The part of a circle not covered by other disks is its exposed region, here visualized as a set of exposed arcs. They are exactly the boundary of the union of all disks. We compute them with the power diagram, whose dual is the regular triangulation. The cell of sample i is where |\mathbf{x}-\mathbf{x}_i|^2 - d_i^2 is smallest. Each circle's exposed arcs are the parts of the circle inside its own cell. So we clip each circle against the edges of its cell.
Sometimes the exposed region collapses to (nearly) a single point. This happens at sharp corners, where the circle is squeezed by its neighbors, or when two circles are internally tangent, as with collinear grid samples near a flat edge. Then the tangent point is determined by geometry alone and is fixed there. Sometimes these samples disappear from the power diagram (dashed circles); we clip it against the neighbors of the cell that contains it, and an infinitesimal arc remains. This step is optional: turn off Exposed-arc step above to skip it.
3 Interpolate the samples with an RBF
We interpolate the samples with a radial basis function using the cubic kernel \varphi(r) = r^3 and a linear polynomial:
The coefficients come from one symmetric linear system. The zero level set interpolates the samples' values, but with the samples alone it floats off the true curve and rounds off sharp features, because nothing tells it where the surface actually is.
One dense solve costs O(n^3), so by default we use a partition of unity (turn it off above for a single global RBF): a k-d tree splits the constraints at the median of the longest axis until each leaf holds at most 50. Each leaf becomes a disk patch, centered at the leaf's mean with the leaf's radius inflated by 1+\lambda so neighbors overlap. A local RBF f_j interpolates the constraints inside each disk, and the local interpolants are blended with Wendland weights:
Every constraint lies inside every patch whose weight is nonzero there, so \tilde D still interpolates all of them. The partition is rebuilt at every solve, because the tangent points move. Lower the leaf and patch sizes under Advanced to see more patches.
4 Find tangent points by projected descent
For each sample we look for the point \mathbf{y} = \mathbf{x} - d\,\mathbf{g} on its circle (\mathbf{g} a unit direction) that reaches farthest past the current zero level set into the region of opposite sign. That is, we minimize
Dividing by d handles both signs and makes the gradient simply \nabla f = -\nabla \tilde D(\mathbf{y}). At a minimum, \mathbf{g} is parallel to the level set's normal at \mathbf{y}, exactly the tangency condition. We start from the best of 64 directions, then take projected gradient steps: step along the tangent, then renormalize onto the circle. Samples whose circle touches no other circle are deferred to the next iteration. With exposed arcs enabled, points that land outside their exposed region are culled. Click a sample to plot f around its circle.
5 Re-interpolate with the tangent points
Every accepted tangent point becomes an extra interpolation constraint with value 0. We solve for the RBF again. Near-duplicate points are merged first to keep the system well conditioned. The new level set is pulled onto the tangent points and moves toward the true curve; the previous level set is shown dashed. Pick an iteration to see that iteration's interpolant against the stage before it.
6 Iterate
With a better \tilde D, the tangent directions improve, which improves \tilde D. Each iteration warm-starts every sample's descent from its previous direction. Scrub through the iterations and watch the level set settle onto the ground truth, including corners the initial interpolant could not represent.
Notes
The full 3D method uses the same ideas with spheres instead of circles. See the paper for details.
Drag to pan, scroll to zoom, double-click to reset any figure. On a touch screen, pinch or drag with two fingers to zoom and pan, tap a sample to select it, and double-tap to reset. Uploaded SVGs are interpreted with the even-odd fill rule; all closed paths, polygons, rects, circles, and ellipses are used.