Home | Blog | GitHub

Lipschitz continuity and sphere tracing

Date: 2020-04-28, Author: Nenad Markuš

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:

\[\vert f(\mathbf{x}) - f(\mathbf{y})\vert \leq \lambda \vert\vert\mathbf{x} - \mathbf{y}\vert\vert\]

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

\[\vert f_S(\mathbf{x})\vert\leq \min_{\mathbf{y}\in f_S^{-1}(0)}\vert\vert\mathbf{x} - \mathbf{y}\vert\vert_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

\[\vert\vert\mathbf{x} - \mathbf{z}\vert\vert_2= \min_{\mathbf{y}\in f_S^{-1}(0)}\vert\vert\mathbf{x} - \mathbf{y}\vert\vert_2\]

we have

\[\vert f(\mathbf{x})\vert\leq \lambda^*\vert\vert\mathbf{x} - \mathbf{z}\vert\vert_2= \lambda^*\min_{\mathbf{y}\in f_S^{-1}(0)}\vert\vert\mathbf{x} - \mathbf{y}\vert\vert_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 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://nenadmarkus.com/lambda:

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:

lam=4

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):

lam=3

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$.

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:
\[\vert f(x)+g(x) - (f(y)+g(y))\vert \leq \vert f(x) - f(y)\vert + \vert g(x) - g(y)\vert \leq \lambda_f\vert x - y\vert + \lambda_g\vert x - y\vert= (\lambda_f + \lambda_g)\vert x - y\vert\]
  1. If $\vert f\vert$ and $\vert g\vert$ are bounded by some constant $M$, then the product $fg$ is Lipschitz continuous:
\[\vert f(x)g(x) - f(y)g(y)\vert\leq \vert f(x)g(x) - f(x)g(y)\vert + \vert f(x)g(y) - f(y)g(y)\vert\leq M\cdot( \vert g(x) - g(y)\vert + \vert f(x) - f(y)\vert )\]
  1. 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:
\[\vert f'(x)\vert= \lim_{h\rightarrow0}\left\vert \frac{f(x+h) - f(x)}{h} \right\vert\leq \lim_{h\rightarrow0}\lambda_f\left\vert \frac{x+h - x}{h} \right\vert= \lambda_f\]

The other implication follows from the mean value theorem. There exists $c$ between $x$ and $y$ such that

\[\vert f(x) - f(y)\vert\leq \vert f'(c)\vert\cdot\vert x - y\vert\]

If we assume that $\vert f'(c)\vert\leq M$, then it follows that $f$ is Lipschitz continuous.

  1. The composition $f\circ g$ is Lipschitz continuous:
\[\vert f(g(x)) - f(g(y))\vert\leq \lambda_f\vert g(x) - g(y)\vert\leq \lambda_f\lambda_g\vert x - y\vert\]

Resources