diff options
Diffstat (limited to 'analysis/analysis.tex')
-rw-r--r-- | analysis/analysis.tex | 336 |
1 files changed, 336 insertions, 0 deletions
diff --git a/analysis/analysis.tex b/analysis/analysis.tex new file mode 100644 index 0000000..d1386f3 --- /dev/null +++ b/analysis/analysis.tex @@ -0,0 +1,336 @@ +\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^3$$ +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^3$ 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 = \sum_{i=1}^n (\nabla f)_i^2 = ||\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 $n^2$ 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 lemma which i didnt end up using +% \begin{lemma} +% \label{x-y-delta} +% Let $f:\bb R^m\to\bb R^n$ be continuous. +% If for all $\vec x,\vec y\in\bb R^m,\delta > 0$ there exist +% $\vec a\in B(\vec x;\delta),\vec b\in B(\vec y;\delta)$ such that +% $||f(\vec a)-f(\vec b)|| < K||\vec a-\vec b||$, then $f$ is $K$-Lipschitz. +% \begin{proof} +% Let $\ve > 0$, and select $\delta<\ve/K$ such that $f$ varies by less than $\ve$ in both +% $B(\vec x;\delta)$ and $B(\vec y;\delta)$. Take $\vec a,\vec b$ as given by our assumption, then +% \begin{align*} +% ||f(\vec x)-f(\vec y)|| &\leq ||f(\vec x) - f(\vec a)|| + ||f(\vec a) - f(\vec b)|| + ||f(\vec b) - f(\vec y)||\\ +% &\leq \ve + K||\vec a-\vec b|| + \ve\\ +% &\leq 2\ve + K(||\vec a - \vec x|| + ||\vec x - \vec y|| + ||\vec y-\vec b||)\\ +% &\leq 2\ve + K(2\delta + ||\vec x - \vec y||)\\ +% &< 4\ve + K||\vec x-\vec y|| +% \end{align*} +% The $4\ve$ term can be made arbitrarily small, so $||f(\vec x)-f(\vec y)|| \leq K||\vec x-\vec y||$. +% \end{proof} +% \end{lemma} + + +\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. +One such rule is: + +\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} +\begin{align*} +|h(\vec x)-h(\vec y)| &= | \min\{f(\vec x),g(\vec x)\} - \min\{f(\vec y),g(\vec y)\}| +\end{align*} +$\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$). + +% i don't know about this section +% it's pretty long and maybe not very helpful +% \section{twisty function} +% One function which might look interesting is +% $$f(x,y,z) =(x\cos(\theta(z)) + y\sin(\theta(z)), y\cos(\theta(z)) - x\sin(\theta(z)), z)$$ +% where $\theta:\bb R\to\bb R$ is some function. +% This can only work for $(x,y)$ bounded: +% we want $\theta$ to only be dependent on $z$, since we want the plane $z=c$ to be rotated +% all by the same angle, but then taking $(x,y)$ large enough, moving $z$ up by a tiny bit will drastically +% change $x,y$. +% So let's take $||(x,y)|| \leq 1$ for now. +% We'll abbreviate $\theta(z)$ as just $\theta$. +% +% $$f(x,y,z) =(x\cos\theta + y\sin\theta, y\cos\theta - x\sin\theta, z)$$ +% $$\frac{\partial f_1}{\partial x} = \cos\theta$$ +% $$\frac{\partial f_1}{\partial y} = \sin\theta$$ +% \begin{align*} +% \frac{\partial f_1}{\partial z} &= -x\sin\theta\dd4\theta z + y\cos\theta\dd\theta z\\ +% &= u\theta'~~~~~\text{where $u=-x\sin\theta + y\cos\theta$} +% \end{align*} +% $$\frac{\partial f_2}{\partial x} = -\sin\theta$$ +% $$\frac{\partial f_2}{\partial y} = \cos\theta$$ +% \begin{align*} +% \frac{\partial f_2}{\partial z} &= -y\sin\theta\pp\theta z - x\cos\theta\pp\theta z\\ +% &= v\theta'~~~~\text{where $v=-x\cos\theta - y\sin\theta$} +% \end{align*} +% Of course $\pp {f_3} x=\pp{f_3}y=0,\pp{f_3}z=1$. This gives us the derivative +% $$Df = \begin{pmatrix} +% \cos\theta&\sin\theta&u\theta'\\ +% -\sin\theta&\cos\theta&v\theta'\\ +% 0&0&1 +% \end{pmatrix}$$ +% $$(Df)(r,s,t) = \begin{pmatrix} +% r\cos\theta + s\sin\theta + u\theta't\\ +% s\cos\theta - r\sin\theta + v\theta't\\ +% t +% \end{pmatrix}$$ +% \begin{align*} +% ||(Df)(r,s,t)||^2 &= +% (r\cos\theta)^2 + (s\sin\theta)^2 + (u\theta't)^2\\ +% &~~+ 2rs\cos\theta\sin\theta + 2rtu\theta'\cos\theta +% + 2stu\theta'\sin\theta\\ +% &~~+(s\cos\theta)^2 + (-r\sin\theta)^2 + (v\theta't)^2\\ +% &~~- 2rs\cos\theta\sin\theta + 2stv\theta'\cos\theta +% - 2rtv\theta'\sin\theta + t^2\\ +% &= (r^2+s^2)(\cos^2\theta + \sin^2\theta) + (u^2+v^2)(\theta't)^2\\ +% &~~+2t\theta'((ru+sv)\cos\theta + (su-rv)\sin\theta)\\ +% &= ||(r,s)||^2 + ||(u,v)||^2 +% + 2t\theta'((ru+sv)\cos\theta + (su-rv)\sin\theta) + t^2 +% \end{align*} +% Now let's take $||(r,s,t)||,||(u,v)||\leq 1$. Note +% that $ru+sv = (r,s)\cdot (u,v) \leq ||(r,s)||$ and likewise +% $su-rv\leq ||(s,-r)||=||(r,s)||$. So then +% \begin{align*} +% ||(Df)(r,s,t)||^2 &\leq 2 + 2\theta't||(r,s)||(\cos\theta + \sin\theta) + t^2\\ +% &\leq2 + 2\theta't||(r,s)||\sqrt2 + t^2\\ +% \end{align*} +% {\Large\bf TODO} +% +\end{document} |