Signed distance function

In mathematics and its applications, the signed distance function (or oriented distance function) is the orthogonal distance of a given point ''x'' to the boundary of a set Ω in a metric space, with the sign determined by whether or not ''x'' is in the interior of Ω. 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 Ω. However, the alternative convention is also sometimes taken instead (i.e., negative inside Ω and positive outside).

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 d(x, \partial \Omega) & \mbox\, x \in \Omega \\ -d(x, \partial \Omega) & \mbox\, x \in \Omega^c \end$

where $\partial \Omega$ denotes the boundary of For any

: $d(x, \partial \Omega) := \inf_d(x, y)$

where denotes the infimum.

Properties in Euclidean space

If Ω is a subset of the Euclidean space R^''n'' 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 Ω. 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_ g(x)\,dx = \int_\int_^\mu g(u+\lambda N(u))\, \det(I-\lambda W_u) \,d\lambda \,dS_u,$

where denotes the determinant and ''dS''_''u'' indicates that we are taking the surface integral.

Algorithms

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

For voxel rendering, a fast algorithm for calculating the SDF in taxicab geometry uses summed-area tables.

Applications

Signed distance functions are applied, for example, in real-time rendering, for instance the method of SDF ray marching, and computer vision.

A modified version of SDF was introduced as a loss function to minimise the error in interpenetration of pixels while rendering multiple objects. In particular, for any pixel that does not belong to an object, if it lies outside the object in rendition, no penalty is imposed; if it does, a positive value proportional to its distance inside the object is imposed.

$f(x) = \begin 0 & \text\, x \in \Omega^c\\ d(x, \partial\Omega) & \text\, x \in \Omega \end$

They have also been used in a method (advanced by Valve) to render smooth fonts at large sizes (or alternatively at high DPI) using GPU acceleration. Valve's method computed signed distance fields in raster space in order to avoid 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 Bézier 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.

In 2020, the FOSS game engine Godot 4.0 received SDF-based real-time global illumination (SDFGI), that became a compromise between more realistic voxel-based GI and baked GI. Its core advantage is that it can be applied to infinite space, which allows developers to use it for open-world games.

See also

* Distance function
* Level-set method
* Eikonal equation
* Parallel (aka offset) curve
* Signed arc length

Notes

References

*
*{{cite book , author1=Gilbarg, D. , author2=Trudinger, N. S. , year=1983 , edition=2nd , title=Elliptic Partial Differential Equations of Second Order , publisher=Springer-Verlag , volume=224 , series=Grundlehren der mathematischen Wissenschaften (or the Appendix of the 1977 1st ed.)

Applied mathematics
Distance