Signed distance function

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
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 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]

Definition[edit]

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

where denotes the boundary of . For any ,

where inf denotes the infimum.

Properties in Euclidean space[edit]

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

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

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 Wx 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

where det indicates the determinant and dSu indicates that we are taking the surface integral.[4]

Algorithms[edit]

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[edit]

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, 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.[citation needed]

See also[edit]

Notes[edit]

  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.
  4. ^ Gilbarg 1983, Equation (14.98).
  5. ^ Zhao Hongkai. A fast sweeping method for eikonal equations. Mathematics of Computation, 2005, 74. Jg., Nr. 250, S. 603-627.
  6. ^ Tomas Akenine-Mö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. S2CID 16811314.
  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. S2CID 3345516.
  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. S2CID 7479538. Missing or empty |title= (help)
  10. ^ https://www.youtube.com/watch?v=7tHv6mcIIeo

References[edit]

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