{{Short description|Distance from a point to the boundary of a set}} [[Image:Signed distance1.png|right|thumb|The graph (bottom, in red) of the signed distance between the points on the ''xy'' plane (in blue) and a fixed disk (also represented on top, in gray)]] right|thumb|A more complicated set (top) and the graph of its signed distance function (bottom, in red).
In mathematics and its applications, the '''signed distance function''' or '''signed distance field''' ('''SDF''') is the orthogonal distance of a given point ''x'' to the boundary of a set Ω in a metric space (such as the surface of a geometric shape), 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 Ω.<ref>{{cite conference | title=Level set based shape prior segmentation | author1=Chan, T. | author2=Zhu, W. | year=2005 | conference=IEEE Computer Society Conference on Computer Vision and Pattern Recognition | doi=10.1109/CVPR.2005.212 }}</ref> However, the alternative convention is also sometimes taken instead (i.e., negative inside Ω and positive outside).<ref>{{cite journal | title=Shape modeling with front propagation: a level set approach | author1=Malladi, R. | author2=Sethian, J.A. | author3=Vemuri, B.C. | journal=IEEE Transactions on Pattern Analysis and Machine Intelligence | volume=17 | issue=2 | pages=158–175 | year=1995 | doi = 10.1109/34.368173 | bibcode=<!-- useless bibcode 1995ITPAM..17..158M --> |url=https://math.berkeley.edu/~sethian/2006/Papers/sethianmalladivemuripami.pdf }}</ref> The concept also sometimes goes by the name '''oriented distance function/field'''.
==Definition==
Let {{math|Ω}} be a subset of a metric space {{math|''X''}} with metric {{math|''d''}}, and <math>\partial\Omega</math> be its boundary. The distance between a point {{mvar|x}} of {{math|''X''}} and the subset <math>\partial\Omega</math> of {{mvar|X}} is defined as usual as
<math display="block"> d(x, \partial \Omega) = \inf_{y \in \partial \Omega}d(x, y),</math>
where <math>\inf</math> denotes the infimum. The ''signed distance function'' from a point {{mvar|x}} of {{mvar|X}} to <math>\Omega</math> is defined by
<math display="block">f(x) = \begin{cases} d(x, \partial \Omega) & \text{if } x \in \Omega \\ -d(x, \partial \Omega) & \text{if }\, x \notin \Omega\\ 0 & \text{if }\, x \in \partial \Omega. \end{cases}</math>
==Properties in Euclidean space==
If Ω is a subset of the Euclidean space '''R'''<sup>''n''</sup> with piecewise smooth boundary, then the signed distance function is differentiable almost everywhere, and its gradient satisfies the eikonal equation
<math display="block">|\nabla f|=1.</math>
If the boundary of Ω is ''C''<sup>''k''</sup> for ''k'' ≥ 2 (see Differentiability classes) then ''d'' is ''C''<sup>''k''</sup> on points sufficiently close to the boundary of Ω.{{sfn|Gilbarg|Trudinger|1983|loc=Lemma 14.16}} In particular, '''''on''''' the boundary ''f'' satisfies
<math display="block">\nabla f(x) = N(x),</math>
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''<sub>''x''</sub> 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
<math display="block">\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,</math>
where {{math|det}} denotes the determinant and ''dS''<sub>''u''</sub> indicates that we are taking the surface integral.{{sfn|Gilbarg|Trudinger|1983|loc=Equation (14.98)}}
==Algorithms== Algorithms for calculating the signed distance function include the efficient fast marching method, fast sweeping method<ref>Zhao Hongkai. [https://www.ams.org/mcom/2005-74-250/S0025-5718-04-01678-3/S0025-5718-04-01678-3.pdf A fast sweeping method for eikonal equations]. Mathematics of Computation, 2005, 74. Jg., Nr. 250, S. 603-627.</ref> and the more general level-set method.
For voxel rendering, a fast algorithm for calculating the SDF in taxicab geometry uses summed-area tables.<ref>{{Cite web |last=Nilsson |first=Tobias |date=2019 |title=Optimization Methods for Direct Volume Rendering on the Client Side Web |url=https://www.diva-portal.org/smash/get/diva2:1330460/FULLTEXT01.pdf |access-date=2022-07-08 |website=Digitala Vetenskapliga Arkivet}}</ref>
== Applications == thumb|right|Signed distance fields stored as raster images can be used to represent shapes. Signed distance functions are applied, for example, in real-time rendering,<ref name="̈llerHaines2018">{{cite book|author1=Tomas Akenine-Möller|author2=Eric Haines|author3=Naty Hoffman|title=Real-Time Rendering, Fourth Edition|url=https://books.google.com/books?id=0g1mDwAAQBAJ|date=6 August 2018|publisher=CRC Press|isbn=978-1-351-81615-1}}</ref> for instance the method of SDF ray marching, and computer vision.<ref>{{Cite book|last1=Perera|first1=S.|last2=Barnes|first2=N.|last3=He|first3=X.|last4=Izadi|first4=S.|last5=Kohli|first5=P.|last6=Glocker|first6=B.|title=2015 IEEE Winter Conference on Applications of Computer Vision |chapter=Motion Segmentation of Truncated Signed Distance Function Based Volumetric Surfaces |date=January 2015 |pages=1046–1053 |doi=10.1109/WACV.2015.144 |isbn=978-1-4799-6683-7 |url=https://www.microsoft.com/en-us/research/wp-content/uploads/2016/11/pbhikg_wavc2014.pdf }}</ref><ref>{{Cite book |last1=Izadi |first1=Shahram |last2=Kim |first2=David |last3=Hilliges |first3=Otmar|last4=Molyneaux|first4=David|last5=Newcombe|first5=Richard|last6=Kohli|first6=Pushmeet|last7=Shotton|first7=Jamie|last8=Hodges|first8=Steve|last9=Freeman|first9=Dustin |title=Proceedings of the 24th annual ACM symposium on User interface software and technology |chapter=KinectFusion: Real-time 3D Reconstruction and Interaction Using a Moving Depth Camera |date=2011 |series=UIST '11 |location=New York, NY, USA |publisher=ACM |pages=559–568 |doi=10.1145/2047196.2047270 |isbn=9781450307161 |url=https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/kinectfusion-uist-comp.pdf }}</ref>
SDF has been used to describe object geometry in real-time rendering, usually in a raymarching context, starting in the mid 2000s. By 2007, Valve was using SDFs to render large pixel-size (or high DPI) smooth fonts with GPU acceleration in its games.<ref>{{cite book | doi = 10.1145/1281500.1281665 | pages=9–18 | date=2007 | first=Chris | last=Green| title=ACM SIGGRAPH 2007 courses | chapter=Improved alpha-tested magnification for vector textures and special effects | isbn=9781450318235 | url=https://valvearchive.com/archive/Other%20Files/Publications/SIGGRAPH2007_AlphaTestedMagnification.pdf }}</ref>{{Primary source inline|date=July 2025}} Valve's method is not perfect as it runs in raster space in order to avoid the computational complexity of solving the problem in the (continuous) vector space. The rendered text often loses sharp corners. In 2014, an improved method was presented by Behdad Esfahbod. Behdad's GLyphy approximates the font's Bézier curves with arc splines, accelerated by grid-based discretization techniques (which culls too-far-away points) to run in real time.<ref>{{cite AV media|author= Behdad Esfahbod | url-status = live| archive-url = https://ghostarchive.org/varchive/youtube/20211211/7tHv6mcIIeo| archive-date = 2021-12-11| url = https://www.youtube.com/watch?v=7tHv6mcIIeo| title = GLyphy: high-quality glyph rendering using OpenGL ES2 shaders [linux.conf.au 2014] | website=YouTube}}{{cbignore}} [https://github.com/behdad/glyphy Source Code]</ref>{{Primary source inline|date=July 2025}}
A modified version of SDF was introduced as a loss function to minimise the error in interpenetration of pixels while rendering multiple objects.<ref>{{cite arXiv|last1=Jiang|first1=Wen|last2=Kolotouros|first2=Nikos|last3=Pavlakos|first3=Georgios|last4=Zhou|first4=Xiaowei|last5=Daniilidis|first5=Kostas|date=2020-06-15|title=Coherent Reconstruction of Multiple Humans from a Single Image|class=cs.CV|eprint=2006.08586}}</ref> 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.
<math display="block">f(x) = \begin{cases} 0 & \text{if }\, x \in \Omega^c\\ d(x, \partial\Omega) & \text{if }\, x \in \Omega \end{cases}</math>
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.<ref>{{cite web |last1=Engine |first1=Godot |title=Godot 4.0 gets SDF based real-time global illumination |url=https://godotengine.org/article/godot-40-gets-sdf-based-real-time-global-illumination/ |website=Godot Engine |language=en}}</ref>{{Primary source inline|date=July 2025}}
In 2023, the authors of the Zed text editor announced a GPUI framework that draws all UI elements using the GPU at 120 fps. The work makes use of Inigo Quilez's list of geometric primitives in SDF, Figma co-founder Evan Wallace's Gaussian blur in SDF, and a new rounded rectangle SDF.<ref>{{cite web |last1=Scandurra |first1=Antonio |title=Leveraging Rust and the GPU to render user interfaces at 120 FPS - Zed Blog |url=https://zed.dev/blog/videogame |website=Zed |date=7 March 2023}}</ref>{{Primary source inline|date=July 2025}}
==See also== * Distance function * Level-set method * Eikonal equation * Parallel curve (also known as offset curve) * Signed arc length * Signed area * Signed measure * Signed volume
==Notes==
{{reflist}}
==References==
*{{cite book | author=Stanley J. Osher and Ronald P. Fedkiw | title=Level Set Methods and Dynamic Implicit Surfaces | publisher=Springer | year=2003|url=https://books.google.com/books?id=i4bfBwAAQBAJ |url-access=limited |isbn=9780387227467 |doi=10.1007/b98879 }} *{{cite book | author1-last=Gilbarg |author1-first=D. | author2-last=Trudinger |author2-first=N. S. | year=1983 | edition=2nd | title=Elliptic Partial Differential Equations of Second Order | publisher=Springer-Verlag | volume=224 | series=Grundlehren der mathematischen Wissenschaften | doi=10.1007/978-3-642-61798-0 }} (or the Appendix of the 1977 1st ed.)
Category:Applied mathematics Category:Distance Category:Sign (mathematics) Category:Implicit surface modeling