I am reading a paper entitles "Sphere Tracing: a Robust Antialiased Rendering of Distance Based Implicit Surfaces", written by John C. Hart.
Here are some definitions:
Surfaces/shapes can be defined implicitly.
An implicit function is a continuous mapping $f$: $R^n \rightarrow R$ that describes the set $A \subset R^n$ as the locus of points: $A \equiv \{ x : f(x) \le 0\}.$
The boundary of the surface may be denoted $f^{-1}(0)$.
Distance to a set. The distance $d(x,A)$ from a point $x \in R^3$ to a closed set $A \subset R^3$ is given by $d(x,A) = \min_{y \in A}||x - y||.$
Then Hart writes that if you have $|f(x)| = |d(x, f^{-1}(0))|$ (eq. 1) then you have what he calls a distance implicit function or DIF. And if you have $|f(x)| \le |d(x, f^{-1}(0))|$ then you have distance underestimate implicit function or DUF.
I don't want to get into the details of why he is interested in the DUF type of function but in short within the context of ray-tracing (in computer graphics) this helps the process of finding if a ray (defined by an origin and a direction) intersects surfaces (which can be defined implicitly in this case). The property of DUF functions is that they guarantee to return a distance to the surface from a given point $x$ within which the ray "cannot interest the surface or can intersect the surface (where the intersection point is exactly on the surface)" but in no circumstance can overshoot the surface. That's just to provide some context to my questions.
Then he goes on defining Lipschitz implicit functions or LIF.
It is an implicit function such that $|f(x) - f(y)| \le \lambda ||x-y||$ (eq. 2) for some positive constant $\lambda$. This constant is denoted the Lipschitz constant and is written as $Lip \; f$. Any LIF can be made into a DUF. Let $f$ be a LIF with Lipschitz constant $\lambda$. Let $y \in f^{-1}(0)$ be one of the points such that: $||x -y|| = d(x, f^{-1}(0))$ (eq. 3).
Then by eq. 2 $|f(x)| \le Lip \; f \; d(x, f^{-1}(0)).$
Hence, $f(x)/ Lip \; f$ is a DUF for any LIF $f$.
QUESTIONS:
I believe that Hart's point is to show that if an implicit function is a Lipschitz function, then it has a DUF, and thus this DUF can be used later on to compute the "underestimate" distance of a ray's origin to a given surface. Okay I get that. The proof from his paper is something I hope I understand as well:
$\lambda ||x-y|| \ge |f(x) - f(y)|\\$
then replace $||x-y||$ by $d(x,f^{-1}(0))$ (eq. 3)
$\lambda \; d(x,f^{-1}(0)) \ge |f(x) - f(y)|\\$
$f(y)=0$ in this particular case since $y \in A$ thus we can re-write:
$\lambda \; d(x,f^{-1}(0)) \ge |f(x)|\\$
and finally:
$ \dfrac {f(x)}{\lambda} \le d(x,f^{-1}(0))$
- If this correct?
Finally, this is the part where I am the most interested in an explanation. Hart writes:
The Lipschitz constant of a continuous function is its maximum slope. The maximum slope can be found by setting the function's second derivative equal to zero and solving for x. Since x is a vector, these derivatives can be the squared magnitude of the gradient.
- Could someone explain me this part with possibly an example? (using a real function)
PS: as a helper later on in the paper Hart uses the function:
$C(r) = 2 r^3/R^3 - 3r^2/R^2 + 1$
then he computes the first and second derivative:
$C'(r) = 6r^2/R^3 - 6r/R^2$
and
$C''(r) = 12r/R^3 - 6/R^2.$
Setting C''(r) = 0 yield the max slope, which occurs at the midpoint r=R/2, which is C'(R/2) = -3/2R = Lip C(r).
I really don't understand this at all. Could someone please explain?
EDIT
I believe I understand most of it myself now.
- The paper says the Lipschitz constant is equal to the maxima of the function which you can find if you know the second derivative of that function and solve for f''(x) = 0. So it would be great to learn/know how I can explain this property.
- So I understand how Hart finds the value of $r=R/2$ for C''(r) but why do we re-inject this value in C'(r) ($C'(R/2)$) in order to find about the value of Lip C(r)? Is that because:
$\lambda = \dfrac{|f(x) - f(y)|}{||x - y||}.$
Can be assumed as the first order derivative of the function f(x)?
If a function is differentiable, and the absolute value of the derivative is bounded by a constant $L$, then this function is also Lipschitz with constant $L$ (this is a stronger condition than Lipschitz).
If the maximum of the derivative is a local maximum and the derivative is again differentiable, then it can be be found by inspecting the points where the second derivative of the original function vanishes.
The paper is rather imprecise when it is talking about derivatives of continuous functions