eikonal equation | Distance Field

- combined with a threshold function, you can render text smoothly upscalable with low memory footprint
- you can dynamically make an object bolder (or thinner with Signed Distance Field)
- you can use this for ray marching
- if you interpret the image as a mesh where each pixel is a vertex linked to its neighbors by an edge, you can see an interesting generalization which has many application in geometry processing.

For each pixel we could look for the closest pixel of $A$. A breadth-first search could sound good : we look every closest pixels first in a "radial fashion". But we need to do this for every pixel. This implies a cost of $\mathcal{O}(N²)$ where $N$ is total pixel count.

An alternative way to build our distance field $B$ is, for each pixel of value $1$ in $A$, to fill the entire image $B$ with a "distance cone" or a "radial gradient", and then take the minimum value of each value.

This formulation is very similar to a convolution ! Indeed with $C$ the "distance cone" that is $C(x) = |x|$ where $x∈ℝ^n$

$$\al{ \text{convolution : } (A⊕C)(x) &=& ∫∫ dy⋅A(y)⋅C(x-y) \\ \text{distance field : } (A⊙C)(x) &=& \min_{y∈ℝ^n} A(y)⋅C(x-y) } $$ Then there is a cool property of Fourier transform that can compute convolution much quicker. $$\al{ \mathcal{F}[A]⋅\mathcal{F}[C] &= ∫∫ dx⋅e^{-ikx} A(x)∫∫ dy⋅e^{-iky} C(y) \\ &= ∫∫ dx ∫∫ dy⋅e^{-ik(x+y)}⋅A(x)⋅C(y) \\ F[A⊕C](k) &= ∫∫dx⋅e^{-ikx} ∫∫ dy⋅A(y)⋅C(x-y) \\ &= ∫∫dx ∫∫ dy⋅e^{-ikx}⋅A(y)⋅C(x-y) \\ % z+y = x &= ∫∫dx ∫∫ dz⋅e^{-ik(z+y)}⋅A(y)⋅C(z) \\ }$$ Thus $F[A⊕C](k) = \mathcal{F}[A]⋅\mathcal{F}[C]$
Thus $A⊕C = F^{-1}[\mathcal{F}[A]⋅\mathcal{F}[C]]$

Let's try the same strategy for the distance field ! $$\al{ F[A⊙C](k) &= ∫∫dx⋅e^{-ikx} \min_{y} A(y)⋅C(x-y) \\ &≠ ∫∫dx \min_{y} e^{-ikx}⋅A(y)⋅C(x-y) \\ }$$ Oh no ! we cannot move the $\min$ operator like we could with the integral operator ! This was crucial to allow the change of variable $z=x-y$ ! Moreover $\min$ on complex number is total non sens.