# Signed distance function

Last updated

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

## Definition

If Ω is a subset of a metric space X with metric d, then the signed distance functionf 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 Rn 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 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

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

${\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 denotes the determinant and dSu 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.

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

## Applications

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

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 is using SDFs to render large pixel-size (or high DPI) smooth fonts with GPU acceleration in its games. [10] 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. [11]

A modified version of SDF was introduced as a loss function to minimise the error in interpenetration of pixels while rendering multiple objects. [12] 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.

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

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. [13]

In 2023, a "GPUI" UI framework was released to draw all UI elements using the GPU, many parts using SDF. The author claims to have produced a Zed code editor that renders at 120 fps. The work makes use of Inigo Quilez's list of geometric primitives in SDF, Evan Wallace (co-founder of Figma)'s approximated gaussian blur in SDF, and a new rounded rectangle SDF. [14]

## 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  . doi:10.1109/34.368173.
3. Gilbarg & Trudinger 1983, Lemma 14.16.
4. Gilbarg & Trudinger 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. Nilsson, Tobias (2019). "Optimization Methods for Direct Volume Rendering on the Client Side Web" (PDF). Digitala Vetenskapliga Arkivet. Retrieved 2022-07-08.
7. Tomas Akenine-Möller; Eric Haines; Naty Hoffman (6 August 2018). Real-Time Rendering, Fourth Edition. CRC Press. ISBN   978-1-351-81615-1.
8. 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.
9. 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.
10. Green, Chris (2007). "Improved alpha-tested magnification for vector textures and special effects". ACM SIGGRAPH 2007 Courses on - SIGGRAPH '07: 9. CiteSeerX  . doi:10.1145/1281500.1281665. ISBN   9781450318235. S2CID   7479538.
11. Behdad Esfahbod. GLyphy: high-quality glyph rendering using OpenGL ES2 shaders [linux.conf.au 2014]. YouTube . Archived from the original on 2021-12-11.
12. Jiang, Wen; Kolotouros, Nikos; Pavlakos, Georgios; Zhou, Xiaowei; Daniilidis, Kostas (2020-06-15). "Coherent Reconstruction of Multiple Humans from a Single Image". arXiv: [cs.CV].
13. Engine, Godot. "Godot 4.0 gets SDF based real-time global illumination". Godot Engine.
14. Scandurra, Antonio (7 March 2023). "Leveraging Rust and the GPU to render user interfaces at 120 FPS - Zed Blog". Zed.

## Related Research Articles

The Navier–Stokes equations are partial differential equations which describe the motion of viscous fluid substances, named after French engineer and physicist Claude-Louis Navier and Anglo-Irish physicist and mathematician George Gabriel Stokes. They were developed over several decades of progressively building the theories, from 1822 (Navier) to 1842-1850 (Stokes).

In mathematics, mathematical physics and the theory of stochastic processes, a harmonic function is a twice continuously differentiable function where U is an open subset of that satisfies Laplace's equation, that is,

In mathematics, the Laplace operator or Laplacian is a differential operator given by the divergence of the gradient of a scalar function on Euclidean space. It is usually denoted by the symbols , (where is the nabla operator), or . In a Cartesian coordinate system, the Laplacian is given by the sum of second partial derivatives of the function with respect to each independent variable. In other coordinate systems, such as cylindrical and spherical coordinates, the Laplacian also has a useful form. Informally, the Laplacian Δf (p) of a function f at a point p measures by how much the average value of f over small spheres or balls centered at p deviates from f (p).

In the theory of partial differential equations, elliptic operators are differential operators that generalize the Laplace operator. They are defined by the condition that the coefficients of the highest-order derivatives be positive, which implies the key property that the principal symbol is invertible, or equivalently that there are no real characteristic directions.

In mathematics, the total variation identifies several slightly different concepts, related to the (local or global) structure of the codomain of a function or a measure. For a real-valued continuous function f, defined on an interval [a, b] ⊂ R, its total variation on the interval of definition is a measure of the one-dimensional arclength of the curve with parametric equation xf(x), for x ∈ [a, b]. Functions whose total variation is finite are called functions of bounded variation.

Geometrical optics, or ray optics, is a model of optics that describes light propagation in terms of rays. The ray in geometrical optics is an abstraction useful for approximating the paths along which light propagates under certain circumstances.

In mathematics, the Newtonian potential or Newton potential is an operator in vector calculus that acts as the inverse to the negative Laplacian, on functions that are smooth and decay rapidly enough at infinity. As such, it is a fundamental object of study in potential theory. In its general nature, it is a singular integral operator, defined by convolution with a function having a mathematical singularity at the origin, the Newtonian kernel Γ which is the fundamental solution of the Laplace equation. It is named for Isaac Newton, who first discovered it and proved that it was a harmonic function in the special case of three variables, where it served as the fundamental gravitational potential in Newton's law of universal gravitation. In modern potential theory, the Newtonian potential is instead thought of as an electrostatic potential.

Euler–Bernoulli beam theory is a simplification of the linear theory of elasticity which provides a means of calculating the load-carrying and deflection characteristics of beams. It covers the case corresponding to small deflections of a beam that is subjected to lateral loads only. By ignoring the effects of shear deformation and rotatory inertia, it is thus a special case of Timoshenko–Ehrenfest beam theory. It was first enunciated circa 1750, but was not applied on a large scale until the development of the Eiffel Tower and the Ferris wheel in the late 19th century. Following these successful demonstrations, it quickly became a cornerstone of engineering and an enabler of the Second Industrial Revolution.

In mathematics, Harnack's inequality is an inequality relating the values of a positive harmonic function at two points, introduced by A. Harnack (1887). Harnack's inequality is used to prove Harnack's theorem about the convergence of sequences of harmonic functions. J. Serrin (1955), and J. Moser generalized Harnack's inequality to solutions of elliptic or parabolic partial differential equations. Such results can be used to show the interior regularity of weak solutions.

In mathematics, a real or complex-valued function f on d-dimensional Euclidean space satisfies a Hölder condition, or is Hölder continuous, when there are real constants C ≥ 0, α > 0, such that

In mathematics, a locally integrable function is a function which is integrable on every compact subset of its domain of definition. The importance of such functions lies in the fact that their function space is similar to Lp spaces, but its members are not required to satisfy any growth restriction on their behavior at the boundary of their domain : in other words, locally integrable functions can grow arbitrarily fast at the domain boundary, but are still manageable in a way similar to ordinary integrable functions.

In mathematics, a (real) Monge–Ampère equation is a nonlinear second-order partial differential equation of special kind. A second-order equation for the unknown function u of two variables x,y is of Monge–Ampère type if it is linear in the determinant of the Hessian matrix of u and in the second-order partial derivatives of u. The independent variables (x,y) vary over a given domain D of R2. The term also applies to analogous equations with n independent variables. The most complete results so far have been obtained when the equation is elliptic.

In probability theory, random element is a generalization of the concept of random variable to more complicated spaces than the simple real line. The concept was introduced by Maurice Fréchet (1948) who commented that the “development of probability theory and expansion of area of its applications have led to necessity to pass from schemes where (random) outcomes of experiments can be described by number or a finite set of numbers, to schemes where outcomes of experiments represent, for example, vectors, functions, processes, fields, series, transformations, and also sets or collections of sets.”

In mathematics, Bochner spaces are a generalization of the concept of spaces to functions whose values lie in a Banach space which is not necessarily the space or of real or complex numbers.

In mathematics, Weyl's lemma, named after Hermann Weyl, states that every weak solution of Laplace's equation is a smooth solution. This contrasts with the wave equation, for example, which has weak solutions that are not smooth solutions. Weyl's lemma is a special case of elliptic or hypoelliptic regularity.

In the mathematical theory of harmonic analysis, the Riesz transforms are a family of generalizations of the Hilbert transform to Euclidean spaces of dimension d > 1. They are a type of singular integral operator, meaning that they are given by a convolution of one function with another function having a singularity at the origin. Specifically, the Riesz transforms of a complex-valued function ƒ on Rd are defined by

An adjoint equation is a linear differential equation, usually derived from its primal equation using integration by parts. Gradient values with respect to a particular quantity of interest can be efficiently calculated by solving the adjoint equation. Methods based on solution of adjoint equations are used in wing shape optimization, fluid flow control and uncertainty quantification. For example this is an Itō stochastic differential equation. Now by using Euler scheme, we integrate the parts of this equation and get another equation, , here is a random variable, later one is an adjoint equation.

In mathematics, the Schauder estimates are a collection of results due to Juliusz Schauder concerning the regularity of solutions to linear, uniformly elliptic partial differential equations. The estimates say that when the equation has appropriately smooth terms and appropriately smooth solutions, then the Hölder norm of the solution can be controlled in terms of the Hölder norms for the coefficient and source terms. Since these estimates assume by hypothesis the existence of a solution, they are called a priori estimates.

Geometrical acoustics or ray acoustics is a branch of acoustics that studies propagation of sound on the basis of the concept of acoustic rays, defined as lines along which the acoustic energy is transported. This concept is similar to geometrical optics, or ray optics, that studies light propagation in terms of optical rays. Geometrical acoustics is an approximate theory, valid in the limiting case of very small wavelengths, or very high frequencies. The principal task of geometrical acoustics is to determine the trajectories of sound rays. The rays have the simplest form in a homogeneous medium, where they are straight lines. If the acoustic parameters of the medium are functions of spatial coordinates, the ray trajectories become curvilinear, describing sound reflection, refraction, possible focusing, etc. The equations of geometric acoustics have essentially the same form as those of geometric optics. The same laws of reflection and refraction hold for sound rays as for light rays. Geometrical acoustics does not take into account such important wave effects as diffraction. However, it provides a very good approximation when the wavelength is very small compared to the characteristic dimensions of inhomogeneous inclusions through which the sound propagates.

In applied mathematics, the fast sweeping method is a numerical method for solving boundary value problems of the Eikonal equation.

## 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. Vol. 224 (2nd ed.). Springer-Verlag. (or the Appendix of the 1977 1st ed.)