path: root/analysis/analysis.tex

\documentclass{article}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\newcommand\bb\mathbb
\newcommand\ve\varepsilon
\renewcommand\vec\textbf
\renewcommand\l\left
\renewcommand\r\right
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newcommand\pp[2]{\frac{\partial #1}{\partial #2}}
\newcommand\dd[2]{\frac{d#1}{d#2}}
\newcommand\transpose{^\top}
\title{Randomly generating signed distance functions}
\author{pommicket}
\date{}
\begin{document}
\maketitle

\section{introduction}

In general, an $n$-dimensional {\em signed distance function} (SDF) is a function
$f:\bb R^n\to\bb R$ representing the distance to a set $A$: for $\vec p\notin A$,
$f(\vec p)$ is the distance from $\vec p$ to $A$. For $\vec p\in A$, $f(\vec p)$ is the
negative of the distance from $\vec p$ to the boundary of $A$.

This means that if $A$ is closed then
$A = \{\vec x\in\bb R^n:f(\vec x)\leq 0\}$.

(I'm not gonna go over the ray marching algorithm, there are better resources out there on
the internet.)

Ray marching doesn't need a {\em true} SDF, it still usually works
for a function which just bounds the true SDF.
From now on I'm just gonna use the term ``SDF'' for something that {\em can} be used with raymarching,
not necessarily a true SDF.

When generating random SDFs,
we just want something that behaves nicely, and where we'll end up drawing the set
$\{\vec x\in\bb R^n:f(\vec x) \leq 0\}$.

\section{constraints on SDFs}
Suppose we're doing ray marching starting from 
some point $\vec p$ and traveling in the direction $\vec d$.

When designing an SDF $f$, what we want to avoid is the possibility
that $f(\vec p)$ is too  large, and so we ``skip'' over
the object when moving from $\vec p$ to $\vec p + f(\vec p) \vec d$.
Specifically, we have the following requirement:

For all $\vec p,\vec d\in \bb R^n$
with $||\vec d||=1$ and $f(\vec p)\geq 0$,
and for any point $\vec x$ on the line segment between
$\vec p$ and $\vec p + f(\vec p) \vec d$, $f(\vec x) \leq 0$.
This is equivalent to saying that for any two points $\vec x,\vec y$,
\begin{equation*}
\tag{1}
f(\vec x)\geq ||\vec x-\vec y|| \implies f(\vec  y) \geq 0
\end{equation*}

But this property is a bit annoying to deal with
so we'll instead use ``1-Lipschitz continuity'',
$$|f(\vec x) - f(\vec y)| \leq ||\vec x - \vec y||~~~\forall \vec x,\vec y\in\bb R^n$$
If $f$ is 1-Lipschitz, then $f$ satisfies (1),
since in particular
$$f(\vec y) \geq f(\vec x) - ||\vec x-\vec y||$$

In general an arbitrary function $g:A \to\bb R^n$ is
$K$-Lipschitz if for all $\vec x,\vec y\in A$,
$$||g(\vec x) - g(\vec y)|| \leq K||\vec x-\vec y||$$

(This last definition is useful for us since if $g$ is $K$-Lipschitz
then $x\mapsto g(x)/K$ and $x\mapsto g(x/K)$ are 1-Lipschitz.)

And any {\em true} SDF $f$ (i.e. $f$ actually represents
the distance to an object) is 1-Lipschitz, since the difference
between the distance from $\vec x$ to the object and the distance
from $\vec y$ to the object should be at most the distance between
$\vec x$ and $\vec y$ (triangle inequality).

Still, it's hard to say whether any particular function is
1-Lipschitz. The following characterization is useful for this:

\begin{theorem}
\label{diff-lipschitz}
Let $f:A\to\bb R^n$ be differentiable for $A\subseteq \bb R^m$ open and convex.
If $||Df(\vec x)||\leq K$ then $f$ is $K$-Lipschitz.\footnote{Here
$||\cdot||$ is the operator norm, $||M|| = \max_{\vec u} \frac{||M\vec u||}{||\vec u||}$.}
The converse is also true if $f$ is $C^1$.
\begin{proof}
($\implies$) Suppose $f$ is not $K$-Lipschitz, i.e. there exist $\vec x,\vec y\in A$ such that
$||f(\vec x)-f(\vec y)|| >  K ||\vec x-\vec y||$. By the mean value theorem there is a point $\vec c$
on the line segment between $\vec x$ and $\vec y$ such that
$$Df(\vec c)\cdot (\vec x-\vec y) = f(\vec x) - f(\vec y)$$
So
$$||Df(\vec c)|| \geq  \frac{||f(\vec x) - f(\vec y)||}{||\vec x-\vec y||} > K$$

($\impliedby$) Now suppose $f$ is $C^1$ and $||Df(\vec x)|| > K$.
Let $||\vec r|| = 1$ with $Df(\vec x)\cdot \vec r > K$.
Since $f$ is $C^1$ there is a closed ball $B(\vec x;\ve)$ around $\vec x$ such that
$Df(\vec a)\cdot \vec r > K$ for all $\vec a\in B(\vec x;\ve)$.
By the mean value theorem there exists $\vec c$ on the line segment between $\vec x$ and $\vec x+\ve\vec r$
such that
$$Df(\vec c)\cdot (\ve\vec r) = f(\vec x+\ve\vec r) - f(\vec x)$$
$$\ve (Df(\vec c)\cdot \vec r) = f(\vec x+\ve\vec r) - f(\vec x)$$
$$K\ve < f(\vec x+\ve\vec r) - f(\vec x)$$
and so $f$ is not $K$-Lipschitz.
\end{proof}
\end{theorem}

(It might seem weird to talk about general functions from $\bb R^m$ to $\bb R^n$ since
raymarching basically only deals with SDFs from $\bb R^m$ to $\bb R$, but this will be useful,
for example when creating SDFs by composing functions.)

The normal definition of the operator norm doesn't really help us calculate it (it's a pain
to consider all $\vec u$ with $||\vec u|| = 1$). Helpfully, wikipedia tells us that
$||M||$ is the square root of the largest eigenvalue of $M\transpose M$.
This is especially nice for functions $f:\bb R^n\to \bb R$, since $Df$ is just the transpose of the ``gradient''
vector
$$\nabla f = \begin{pmatrix}
\pp f{x_1}\\ \pp f{x_2}\\\cdots\\\pp f{x_n}
\end{pmatrix}$$
So
$$(Df)(Df)^T = (\nabla f)^T(\nabla f) = ||\nabla f||^2$$
So in fact
$$||Df|| = ||\nabla f||.$$

This gives us a very easy way of determining $||Df(\vec x)||$: just compute each of the
partial derivatives, and take the square root of the sum of their squares.

Finding the total derivative $Df$ can be annoying (requires finding $nm$ partial derivatives),
so it's nice to have some tools to reduce the dimension of the domain/codomain of $f$:
\begin{theorem}
\label{component-wise}
If $f:\bb R^n\to\bb R^n$, $f(\vec x) = (f_1(x_1) , f_2(x_2), \dots, f_n(x_n))$
and $f_i:\bb R\to\bb R$ is $K$-Lipschitz for all $i$ then $f$ is $K$-Lipschitz.
\begin{proof}
\begin{align*}
||f(\vec x) - f(\vec y)||^2 &= \sum_{i=1}^n (f_i(x_i) - f_i(y_i))^2\\
&\leq \sum_{i=1}^n (K|x_i - y_i|)^2\\
&= K^2\sum_{i=1}^n (x_i - y_i)^2\\
&= K^2||\vec x - \vec y||^2
\end{align*}
\end{proof}
\end{theorem}


\begin{theorem}
\label{dim-reduction}
Let $f:\bb R^m\to\bb R^n$. $f$ is $K$-Lipschitz if and only if
the function $g_{\vec p,\vec u}:\bb R\to\bb R^n,
g_{\vec p,\vec u}(x) = f(\vec p + x \vec u)$ is $K$-Lipschitz for all $\vec p,\vec u\in\bb R^n,||\vec u||=1$.
\begin{proof}
$(\implies)$
\begin{align*}
||g_{\vec p,\vec u}(x) - g_{\vec p,\vec u}(y)|| &= ||f(\vec p + x\vec u) - f(\vec p + y\vec u)||\\
&\leq K||(\vec p + x\vec u) - (\vec p + y\vec u)||\\
&= K|x-y|
\end{align*}

$(\impliedby)$
Let $\vec x,\vec y\in\bb R^m$. Let $\vec u = \frac{\vec y-\vec x}{||\vec y-\vec x||}$.
\begin{align*}
||f(\vec x)-f(\vec y)|| &= ||f(\vec x) - f(\vec x + ||\vec y-\vec x||\vec u)||\\
&= ||g_{\vec x,\vec u}(0) - g_{\vec x,\vec u}(||\vec y-\vec x||)||\\
&\leq K||\vec y-\vec x||
\end{align*}
\end{proof}
\end{theorem}

Here is a useful theorem which shows a limit
of differentiable functions $\{f_n\}$ with $||Df_n|| \leq 1$ is 1-Lipschitz
(even though the limit isn't necessarily differentiable).
\begin{theorem}
\label{limit}
Let $f:\bb R^m\to\bb R^n$, $f(\vec x) = \lim_{n\to\infty} f_n(\vec x)$, where each
$f_n$ is $K$-Lipschitz. Then $f$ is $K$-Lipschitz.
\begin{proof}
Let $\vec x,\vec y\in\bb R^m$. For any $\ve>0$, there exists $n\in\bb N$ such that
$$||f_n(\vec x) - f(\vec x)|| < \ve, ||f_n(\vec y) - f(\vec y)|| < \ve$$
And now,
\begin{align*}
||f(\vec x) - f(\vec y)|| &\leq ||f(\vec x)-f_n(\vec x)|| + ||f_n(\vec x) - f_n(\vec y)|| + ||f(\vec y)-f_n(\vec y)||\\
&< K||\vec x-\vec y|| + 2\ve
\end{align*}
Since $\ve$ can be made arbitrarily small, $||f(\vec x)-f(\vec y)|| \leq K||\vec x-\vec y||$.
\end{proof}
\end{theorem}

\section{examples of 1-Lipschitz functions}

\begin{itemize}
\item $f:\bb R^n\to \bb R$, $f(\vec x) = ||\vec x||$.
\item $f:\bb R^n\to \bb R^n$, $f(\vec x) = \vec x + \vec p$ for any fixed $\vec p\in\bb R^n$.
\item $f:\bb R^n\to \bb R^n$, $f(\vec x) = (|x_1|,\dots,|x_n|)$. This one isn't differentiable.
\item $f:\bb R^n\to\bb R^n$, $f(\vec x) = (\sin x_1,\dots,\sin x_n)$ --- by Theorem \ref{diff-lipschitz},
$\sin:\bb R\to\bb R$ is 1-Lipschitz so by Theorem \ref{component-wise}, $f$ is 1-Lipschitz.
\item Any isometry.
\end{itemize}

\section{basic closure properties}

To procedurally generate 1-Lipschitz functions, we need rules about how to combine 1-Lipschitz
functions to produce new 1-Lipschitz functions.

For example,

\begin{theorem}
\label{composition}
If $f : \bb R^m \to \bb R^n$ is $K$-Lipschitz and $g:\bb R^n\to\bb R^l$ is $L$-Lipschitz then
 $f\circ g:\bb R^m\to\bb R^l$ is $KL$-Lipschitz.
\begin{proof}
Let $\vec x,\vec y\in\bb R^m$.
$$||f(g(\vec x)) - f(g(\vec y))|| \leq K||g(\vec x) - g(\vec y)|| \leq KL||\vec x - \vec y||$$
\end{proof}
\end{theorem}

\begin{theorem}
\label{mixing}
If $f : \bb R^m \to \bb R^n,g:\bb R^m\to\bb R^n$ are 1-Lipschitz and $t\in[0,1]$ then
$h(\vec x) = tf(\vec x) + (1-t)g(\vec x)$ is 1-Lipschitz.
\begin{proof}
Let $\vec x,\vec y\in\bb R^n$.
\begin{align*}
||h(\vec x) - h(\vec y)|| &= ||tf(\vec x) + (1-t)g(\vec x) - tf(\vec y) - (1-t)g(\vec y)||\\
&= ||t(f(\vec x) - f(\vec y)) + (1-t)(g(\vec x) - g(\vec y))||\\
&\leq t||f(\vec x) - f(\vec y)|| + (1-t)||g(\vec x) - g(\vec y)||\\
&\leq t + 1 - t = 1
\end{align*}
\end{proof}
\end{theorem}

\begin{theorem}
\label{minmax}
If $f,g:\bb R^m\to\bb R$ are 1-Lipschitz then
$$\vec x\mapsto \min\{f(\vec x),g(\vec x)\},~~\vec x\mapsto \max\{f(\vec x),g(\vec x)\}$$
are too.
\begin{proof}
By Theorem \ref{dim-reduction} it suffices to consider the case where $m=1$.
Suppose that $f,g$ are 1-Lipschitz and
$$|\min\{f(\vec x),g(\vec x)\} - \min\{f(\vec y),g(\vec y)\}| > ||\vec x-\vec y||$$
If $f(\vec x) \geq g(\vec x)$ and $f(\vec y) \geq g(\vec x)$, or if $f(\vec x) \leq g(\vec x)$ and $f(\vec y) \leq g(\vec y)$,
the contradiction is immediate. There are only two cases left, and they're symmetric:
suppose without loss of generality that $f(\vec x) \geq g(\vec x)$ and $f(\vec y)\leq g(\vec y)$. Then
we have
$$|g(\vec x) - f(\vec y)| > ||\vec x-\vec y||$$
And if $g(\vec x)-f(\vec y) \geq 0$ then $|f(\vec x) - f(\vec y)| \geq |g(\vec x) - f(\vec y)| > ||\vec x-\vec y||$,
and if $g(\vec x)-f(\vec y) < 0$ then $|g(\vec x) - g(\vec y)| \geq |g(\vec x) - f(\vec y)| > ||\vec x-\vec y||$.

$\max$ follows from $\max\{a,b\} = -\min\{-a,-b\}$ (negating a 1-Lipschitz function gives
a 1-Lipschitz function).
\end{proof}
\end{theorem}


\section{products?}
Unfortunately given differentiable 1-Lipschitz functions $f,g$, the product function $x\mapsto f(x)g(x)$
is not necessarily Lipschitz continuous. However we can define a modified product which does
preserve 1-Lipschitz continuity.

Given $f,g:\bb R^n \to \bb R$ 1-Lipschitz and differentiable, define
$$h(\vec x) = \sin (f(\vec x))\cos(g(\vec x))$$
Clearly $h$ is also differentiable, we will show that it is 1-Lipschitz.
$$\pp h{x_i} = \cos(f(\vec x))\cos(g(\vec x)) \pp{f(\vec x)}{x_i}- \sin(f(\vec x))\sin(g(\vec x))  \pp{g(\vec x)}{x_i}$$
so letting $f(\vec x) = a,~g(\vec x)= b,~p = \cos a\cos b,~q = \sin a\sin b,~\pp{f(\vec x)}{x_i} = s_i,~\pp{g(\vec x)}{x_i} = t_i$, we have
\begin{align*}
||Dh(\vec x)||^2 &= \sum_{i=1}^n \left[ps_i - qt_i\right]^2\\
&=p^2\l(\sum_{i=1}^n  s_i^2\r) +  q^2\l(\sum_{i=1}^n  t_i^2\r)- 2pq\l(\sum_{i=1}^n s_it_i\r)\\
&=p^2||\vec s|| + q^2||\vec t||- 2pq(\vec s\cdot \vec t)\\
&\leq p^2||\vec s|| + q^2||\vec t||+ 2pq||\vec s||\,||\vec t||\\
\intertext{Note that $\vec s = Df(\vec x)^T,\vec t=Df(\vec x)^T$ and so $||\vec s||,||\vec t|| \leq 1$:}
&\leq p^2 + q^2 + 2pq\\
&= (p+q)^2\\
&= (\cos a\cos b + \sin a\sin b)^2\\
&= \cos^2(a-b) \leq 1
\end{align*}

And this bound is as strict as possible: we can definitely imagine $f,g$ satisfying
$f(\vec x) = 0,g(\vec x)=\pi/2, Df(\vec x)\cdot Dg(\vec x) = -1$ for example (you can verify that this
makes $||Dh(\vec x)|| = 1$).

\end{document}