Signed distance function

In mathematics and its 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 Ω.[1] However, the alternative convention is also sometimes taken instead (i.e., negative inside Ω and positive outside).[2]

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).

Definition

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

${\displaystyle 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 ${\displaystyle \partial \Omega }$ denotes the boundary of ${\displaystyle \Omega }$. For any ${\displaystyle x\in X}$,

${\displaystyle 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

${\displaystyle |\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 Ω.[3] In particular, on the boundary f satisfies

${\displaystyle \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

${\displaystyle \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.[4]

Algorithms

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

Applications

Signed distance fields stored as raster images can be used to represent shapes.

Signed distance functions are applied, for example, in real-time rendering[6] and computer vision.[7][8]

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.[9] 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.[10]

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

See also

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

Notes

1. Chan, T.; Zhu, W. (2005). Level set based shape prior segmentation. IEEE Computer Society Conference on Computer Vision and Pattern Recognition. doi:10.1109/CVPR.2005.212.
2. Malladi, R.; Sethian, J.A.; Vemuri, B.C. (1995). "Shape modeling with front propagation: a level set approach". IEEE Transactions on Pattern Analysis and Machine Intelligence. 17 (2): 158–175. CiteSeerX 10.1.1.33.2443. doi:10.1109/34.368173.
3. Gilbarg 1983, Lemma 14.16. sfn error: no target: CITEREFGilbarg1983 (help)
4. Gilbarg 1983, Equation (14.98). sfn error: no target: CITEREFGilbarg1983 (help)
5. Zhao Hongkai. A fast sweeping method for eikonal equations. Mathematics of Computation, 2005, 74. Jg., Nr. 250, S. 603-627.
6. Tomas Akenine-Mo ̈ller; Eric Haines; Naty Hoffman (6 August 2018). Real-Time Rendering, Fourth Edition. CRC Press. ISBN 978-1-351-81615-1.
7. Perera, S.; Barnes, N.; He, X.; Izadi, S.; Kohli, P.; Glocker, B. (January 2015). "Motion Segmentation of Truncated Signed Distance Function Based Volumetric Surfaces". 2015 IEEE Winter Conference on Applications of Computer Vision: 1046–1053. doi:10.1109/WACV.2015.144. ISBN 978-1-4799-6683-7.
8. Izadi, Shahram; Kim, David; Hilliges, Otmar; Molyneaux, David; Newcombe, Richard; Kohli, Pushmeet; Shotton, Jamie; Hodges, Steve; Freeman, Dustin (2011). "KinectFusion: Real-time 3D Reconstruction and Interaction Using a Moving Depth Camera". Proceedings of the 24th Annual ACM Symposium on User Interface Software and Technology. UIST '11. New York, NY, USA: ACM: 559–568. doi:10.1145/2047196.2047270. ISBN 9781450307161.
9. Green, Chris (2007). Improved alpha-tested magnification for vector textures and special effects. ACM SIGGRAPH 2007 Courses on - SIGGRAPH '07. p. 9. CiteSeerX 10.1.1.170.9418. doi:10.1145/1281500.1281665. ISBN 9781450318235.
10. https://www.youtube.com/watch?v=7tHv6mcIIeo

References

• Stanley J. Osher and Ronald P. Fedkiw (2003). Level Set Methods and Dynamic Implicit Surfaces. Springer. ISBN 9780387227467.
• 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.)