2
$\begingroup$

As described by Shirley in his computer graphics book,

Cubic curves provide the minimum-curvature interpolants to a set of points. That is, if you have a set of n + 3 points and define the “smoothest” curve that passes through them (that is the curve that has the minimum curvature over its length), this curve can be represented as a piecewise cubic with n segments.

Could you please give some hints or references about its proof?

$\endgroup$
  • $\begingroup$ Could you mention which specific computer graphics book by Shirley you are quoting from? (There are several.) $\endgroup$ – trichoplax Sep 7 '19 at 18:52
  • $\begingroup$ It is the third version of "Fundamentals of computer graphics" published by CRC Press. $\endgroup$ – 8cold8hot Sep 8 '19 at 2:58
2
$\begingroup$

For a function $y = f(x)$ the (signed) curvature at $x$ is given by: $$ \kappa(x) = \frac{f''(x)}{(1+f'^2(x))^{\frac{3}{2}}} $$

If you assume that the slope is very small compared to $1$: $ f'^2<\!<1 $, then:

$$ k(x) \approx f''(x)$$

Suppose you are given data points ($x_0<x_1<\cdots<x_N$):

$$(x_0,y_0), (x_1,y_1), ..., (x_N, y_N)$$

You want to find an interpolating function $f$, such that:

$$f(x_k) = y_k$$

And we'll additionally require that it minimizes the energy:

$$E[f] = \int_{x_0}^{x_N}\left(f''(x)\right)^2\,dx$$

Let $f(x_k) = y_k \wedge \exists f''(x) \wedge f''(x_0)=f''(x_N) = 0$, and let $f$ be piece-wise cubic, then: $$\forall g \ne f : g(x_k) = y_k \wedge \exists g''(x) \implies $$ $$ E[g] = \int_{x_0}^{x_N}\left(g''(x)\right)^2\,dx > \int_{x_0}^{x_N}\left(f''(x)\right)^2\,dx = E[f]$$

Proof:

$$E[g] - E[f] = \int_{x_0}^{x_N}\left(g''(x)\right)^2\,dx - \int_{x_0}^{x_N}\left(f''(x)\right)^2\,dx = $$

$$ \int_{x_0}^{x_N}\left(g''(x)\right)^2\,dx -2\int_{x_0}^{x_N}g''(x)f''(x)\,dx + \int_{x_0}^{x_N}\left(f''(x)\right)^2\,dx$$ $$- 2\int_{x_0}^{x_N}\left(f''(x)\right)^2\,dx + 2\int_{x_0}^{x_N}g''(x)f''(x)\,dx = $$

$$\int_{x_0}^{x_N}\left(g''(x)-f''(x)\right)^2\,dx + 2\int_{x_0}^{x_N}(g''(x)-f''(x))f''(x)\,dx $$

Clearly if $g \ne f$ almost everywhere then $\int_{x_0}^{x_N}\left(g''(x)-f''(x)\right)^2\,dx > 0$, then to prove $E[g]-E[f]>0$ it remains to show that: $2\int_{x_0}^{x_N}(g''(x)-f''(x))f''(x)\,dx \geq 0$.

Integrating by parts yields:

$$2\int_{x_0}^{x_N}(g''(x)-f''(x))f''(x)\,dx = 2\int_{x_0}^{x_N}f''(x)\,d[g'(x)-f'(x)] = $$

$$ 2(g'(x_N)-f'(x_N))f''(x_N) - 2(g'(x_0)-f'(x_0))f''(x_0)$$ $$-2\int_{x_0}^{x_N}(g'(x)-f'(x))f'''(x)\,dx = $$

Since $f''(x_N) = f''(x_0) = 0$ the first two terms are 0, and we are left with:

$$- 2\int_{x_0}^{x_N}(g'(x)-f'(x))f'''(x)\,dx = $$

Since $f$ was chosen to be piece-wise cubic, then $f(x) = a_kx^3 + b_kx^2 + c_kx + d_k, x \in [x_k,x_{k+1})$ and consequently $f'''([x_k,x_{k+1})) = 6a_k = \operatorname{const}$, and we can take it out of the integral and integrate in each interval $[x_k,x_{k+1}]$:

$$-2\sum_{k=0}^{N-1}f'''([x_k,x_{k+1}))\int_{x_k}^{x_{k+1}}(g'(x)-f'(x))\,dx = $$

$$-2\sum_{k=0}^{N-1}6a_k[g(x_{k+1})-f(x_{k+1}) - (g(x_k) - f(x_k))] = $$

Using the interpolation constraint $f(x_k) = g(x_k) = y_k$:

$$-2\sum_{k=0}^{N-1}6a_k[y_{k+1} - y_{k+1} - (y_k-y_k)] = 0$$

Thus:

$$E[g] - E[f] = \int_{x_0}^{x_N}\left(g''(x)-f''(x)\right)^2\,dx > 0$$

And consequently:

$$E[g] > E[f]$$

Which proves the fact that an interpolating C2 cubic spline with natural end conditions minimizes the squared (approximate) "curvature" energy:

$$ E[f] = \int_{x_0}^{x_N}\left(f''(x)\right)^2\,dx $$

| improve this answer | |
$\endgroup$
  • $\begingroup$ Minor nit: you don't need $g \neq f$ almost everywhere; you just need that to be true more than almost nowhere (i.e. on a set of strictly positive measure). $\endgroup$ – Nathan Reed Sep 7 '19 at 22:49
  • $\begingroup$ @NathanReed I am not sure 'almost nowhere' is a term but I got what you mean. You are correct, since I require the functions to not agree only a measurable subset of the interval for $>$ to hold. Good catch. I won't edit it, since it may become confusing me trying to explain what almost nowhere is. I hope interested readers will see your comment below. $\endgroup$ – lightxbulb Sep 7 '19 at 22:55
  • $\begingroup$ As a matter of fact, since $f$ and $g$ are required to be continuous, I think it suffices to require $g \neq f$ somewhere. That would automatically imply $g \neq f$ on a nonzero interval around that point. $\endgroup$ – Nathan Reed Sep 7 '19 at 23:01
  • $\begingroup$ @NathanReed Which brings us to another point - that it's $f'' \ne g''$ which is required and not $f \ne g$ (though this is sufficient). There's no continuity constraint on $g''$ on the other hand, so the "almost nowhere" constraint is valid for this. I wonder whether it's beneficial including that in the answer however. $\endgroup$ – lightxbulb Sep 8 '19 at 0:40
2
$\begingroup$

Splines confuse me which is one reason I asked somebody else to write that chapter.

But I like this explanation: https://www.johndcook.com/blog/2009/02/06/the-smoothest-curve-through-a-set-of-points/

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the answer. I really like this book and also the ray tracing in weekends series. $\endgroup$ – 8cold8hot Sep 8 '19 at 3:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.