Signed distance function

A disk (top, in grey) and its signed distance function (bottom, in red). The x-y plane is shown in blue.

A more complicated set (top) and its signed distance function (bottom, in red).

In mathematics and applications, the signed distance function (or oriented distance function) of a set Ω in a metric space determines the distance of a given point x from the boundary of Ω, with the sign determined by whether x is in Ω. The function has positive values at points x inside Ω, it decreases in value as x approaches the boundary of Ω where the signed distance function is zero, and it takes negative values outside of Ω.

Definition

If Ω is a subset of a metric space, X, with metric, d, then the signed distance function, f, is defined by

$f(x) = \begin{cases} d(x, \partial \Omega) & \mbox{ if } x\in\Omega \\ -d(x, \partial \Omega)& \mbox{ if } x\in\Omega^c \end{cases}$

where $\partial \Omega$ denotes the boundary of $\Omega$. For any $x \in X$,

$d(x, \partial \Omega) := \inf_{y \in \partial \Omega}d(x, y)$

where inf denotes the infimum.

Properties in Euclidean space

If Ω is a subset of the Euclidean space Rⁿ with piecewise smooth boundary, then the signed distance function is differentiable almost everywhere, and its gradient satisfies the eikonal equation

$|\nabla f|=1.$

If the boundary of Ω is C^k for k≥2 (see differentiability classes) then d is C^k on points sufficiently close to the boundary of Ω.^[1] In particular, on the boundary f satisfies

$\nabla f(x) = N(x),$

where N is the inward normal vector field. The signed distance function is thus a differentiable extension of the normal vector field. In particular, the Hessian of the signed distance function on the boundary of Ω gives the Weingarten map.

If, further, Γ is a region sufficiently close to the boundary of Ω that f is twice continuously differentiable on it, then there is an explicit formula involving the Weingarten map W_x for the Jacobian of changing variables in terms of the signed distance function and nearest boundary point. Specifically, if T(∂Ω,μ) is the set of points within distance μ of the boundary of Ω (i.e. the tubular neighbourhood of radius μ), and g is an absolutely integrable function on Γ, then

$\int_{T(\partial\Omega,\mu)} g(x)\,dx = \int_{\partial\Omega}\int_{-\mu}^\mu g(u+\lambda N(u))\, \det(I-\lambda W_u) \,d\lambda \,dS_u,$

where det indicates the determinant and dS_u indicates that we are taking the surface integral.^[2]

Algorithms

Algorithms for calculating the signed distance function include the efficient fast marching method , fast sweeping method^[3] and the more general level set method.

Applications

Signed distance functions are applied, for example, in computer vision.

They have also recently been used in a method (advanced by Valve Software) to render smooth fonts at large sizes (or alternatively at high DPI) using GPU acceleration.^[4] Valve's method computed signed distance fields in raster space in order to avoid of the computational complexity of solving the problem in the (continuous) vector space. More recently piece-wise approximation solutions have been proposed (which for example approximate a Bezier with arc splines), but even this way the computation can be too slow for real-time rendering, and it has to be assisted by grid-based discretization techniques to approximate (and cull from the computation) the distance to points that are too far away.^[5]

See also

• Distance function
• Level set method
• Eikonal equation
• Parallel (aka offset) curve

Notes

1. Gilbarg 1983, Lemma 14.16.
2. Gilbarg 1983, Equation (14.98).
3. [ZHAO, Hongkai. A fast sweeping method for eikonal equations. Mathematics of computation, 2005, 74. Jg., Nr. 250, S. 603-627.
4. Green, Chris (2007). "Improved alpha-tested magnification for vector textures and special effects". ACM SIGGRAPH 2007 courses on - SIGGRAPH '07: 9. doi:10.1145/1281500.1281665. ISBN 9781450318235.
5. https://www.youtube.com/watch?v=7tHv6mcIIeo

References

• Stanley J. Osher and Ronald P. Fedkiw (2003). Level Set Methods and Dynamic Implicit Surfaces. Springer.
• Gilbarg, D.; Trudinger, N. S. (1983). Elliptic Partial Differential Equations of Second Order. Grundlehren der mathematischen Wissenschaften 224 (2nd ed.). Springer-Verlag. (or the Appendix of the 1977 1st ed.)