A function $f:D\rightarrow \mathbb{R}$ (with $D$ a subset of $\mathbb{R}^n$) is called **Lipschitz continuous** if there exists a constant $\lambda \geq 0$ such that for all $\mathbf{x}, \mathbf{y}\in D$ the following inequality holds:
$$
|f(\mathbf{x}) - f(\mathbf{y})| \leq \lambda ||\mathbf{x} - \mathbf{y}||
$$
Let us denote smallest such $\lambda$ as $\lambda^\*$ and call it the **Lipschitz constant**.
## Importance for sphere tracing
As explained by J. C. Hart, sphere tracing requires Lipschitz continuity to work correctly.
Morever, the associated $\lambda^\*$ has to be smaller than or equal to $1$.
If this is not the case, we cannot take $f(\mathbf{x})$ as the step size along the ray without the risk to "overshoot" the surface.
To see this, recall that $f\_S$ is a signed distance bound of $S$ if and only if for all $\mathbf{x}\in\mathbb{R}^3$ we have
$$
|f\_S(\mathbf{x})|\leq
\min\_{\mathbf{y}\in f\_S^{-1}(0)}||\mathbf{x} - \mathbf{y}||\_2
$$
where $f\_S^{-1}(0)=\\{\mathbf{z}: f\_S(\mathbf{z})=0\\}$.
If we assume that $f\_S$ is Lipschitz continuous with Lipschitz constant $\lambda^\*$, then for any point $\mathbf{x}$ and $\mathbf{z}$ such that
$$
||\mathbf{x} - \mathbf{z}||\_2=
\min\_{\mathbf{y}\in f\_S^{-1}(0)}||\mathbf{x} - \mathbf{y}||\_2
$$
we have
$$
|f(\mathbf{x})|\leq
\lambda^\*||\mathbf{x} - \mathbf{z}||\_2=
\lambda^\*\min\_{\mathbf{y}\in f\_S^{-1}(0)}||\mathbf{x} - \mathbf{y}||\_2
$$
Thus, to mitigate overestimating the distance, in which case sphere tracing can "overshoot" the surface and penetrate the shape, we must have $\lambda^\*\leq 1$.
This is a **sufficient condition** to avoid the mentioned problem.
If $\lambda^\*$ is greater than $1$, we can replace $f\_S$ by $f\_S/\lambda^\*$.
The resulting function has an optimal Lipschitz constant, $1$.
In the context of the [lambdaCAD](https://lambdacad.gitlab.io) tool, we can get holes in the generated mesh if $\lambda^\* > 1$.
This is demonstrated in the next section.
## An illustrative example
Let us consider a shape defined by a implicit function $F(x, y, z) = x^2 + y^2 + z^2 - 4 = 0$.
It is not hard to see that this is a sphere of radius $2$ centered at the origin.
The function $F$ is not Lipschitz continuous on $\mathbb{R}^3$ since it's derivative is not bounded (more on that later).
However, if we constrain ourselves to a region $[-2, +2]^3$, then we can construct a signed distance bound $f(x, y, z)=F(x, y, z)/\lambda$ for $\lambda=4$.
The following snippet is an implementation of $f$ for [https://lambdacad.gitlab.io](https://lambdacad.gitlab.io):
```
return function (x, y, z) {
const r = 2;
const lam = 4;
return (x*x + y*y + z*z - r*r)/lam;
};
```
Setting `size=4` and `resolution=100` produces the following mesh:
The above representation looks as expected.
However, if we change $\lambda$ from $4$ to $3$ (set `lam=3` in the code snippet), we get holes in the model (some triangles are missing):
This is due to sphere tracing occasionally "missing" the surface of the shape and immediately "jumping" in its interior.
A consequence of overestimating some distances because of wrong $\lambda$.
## Useful properties related to Lipschitz continuity
We assume that $f$ and $g$ are Lipschitz continuous with associated constants $\lambda\_f$ and $\lambda\_g$, respectively.
1. The sum $f+g$ is Lipschitz continuous:
$$
|f(x)+g(x) - (f(y)+g(y))| \leq
|f(x) - f(y)| + |g(x) - g(y)| \leq
\lambda\_f|x - y| + \lambda\_g|x - y|=
(\lambda\_f + \lambda\_g)|x - y|
$$
2. If $|f|$ and $|g|$ are bounded by some constant $M$, then the product $fg$ is Lipschitz continuous:
$$
|f(x)g(x) - f(y)g(y)|\leq
|f(x)g(x) - f(x)g(y)| + |f(x)g(y) - f(y)g(y)|\leq
M\cdot( |g(x) - g(y)| + |f(x) - f(y)| )
$$
3. A continuous and differentiable function $f$ is Lipschitz if and only if its derivative $f'$ is bounded.
To prove the first implication, we assume that $f$ is Lipschitz continuos and work with the definition of the derivative:
$$
|f'(x)|=
\lim\_{h\rightarrow0}\left|
\frac{f(x+h) - f(x)}{h}
\right|\leq
\lim\_{h\rightarrow0}\lambda\_f\left|
\frac{x+h - x}{h}
\right|=
\lambda\_f
$$
The other implication follows from the [mean value theorem](https://en.wikipedia.org/wiki/Mean_value_theorem).
There exists $c$ between $x$ and $y$ such that
$$
|f(x) - f(y)|\leq
|f'(c)|\cdot|x - y|
$$
If we assume that $|f'(c)|\leq M$, then it follows that $f$ is Lipschitz continuous.
4. The composition $f\circ g$ is Lipschitz continuous:
$$
|f(g(x)) - f(g(y))|\leq
\lambda\_f|g(x) - g(y)|\leq
\lambda\_f\lambda\_g|x - y|
$$
## Resources
* J. C. Hart. Sphere tracing: A geometric method for the antialiased ray tracing of implicit surfaces. The Visual Computer, 1994.
* [https://en.wikipedia.org/wiki/Lipschitz_continuity](https://en.wikipedia.org/wiki/Lipschitz_continuity)
* [https://math.stackexchange.com/questions/2823582/sum-of-lipschitz-functions](https://math.stackexchange.com/questions/2823582/sum-of-lipschitz-functions)
* [https://math.stackexchange.com/questions/1028974/sum-and-product-of-lipschitz-functions](https://math.stackexchange.com/questions/1028974/sum-and-product-of-lipschitz-functions)
* [https://math.stackexchange.com/questions/1165431/is-a-function-lipschitz-if-and-only-if-its-derivative-is-bounded](https://math.stackexchange.com/questions/1165431/is-a-function-lipschitz-if-and-only-if-its-derivative-is-bounded)