Combi2k2

What is a curve?

A parameterized curve is a map btw each point $t$ an interval of the real line to some point $x(t)$ in the plane
Note that: the same geometrical curve admit many parameterizations...
- basically corresponds to a change of "velocity" along the curve
- canonical: unit-speed curve $\|x'(t)\|=1$
- we can get this unit-speed curve by choosing the right parameterization:
A measure of the curve is called geometric if it is invariant to the choice of parameterization:
- e.g: length, tangent direction, normal direction, curvature
- some are not intuitive from the formula. E.g: curvature

Given a curve $x(t)=\begin{pmatrix}x(t)\\ y(t)\end{pmatrix}$

The length of this curve between $t_0$ and $t$ is:

l(t) = \int_{t_0}^t \sqrt{x'(s)^2+y'(s)^2} ds = \int_{t_0}^t\|x'(u)\|du

note that $l(t)$ is strictly increasing
thus, it has an inverse $l^-1(t)$
$x(l^-t(t))$ is exactly the unit-speed curve we are looking for

Local Frames of Curves (Frenet–Serret basis (or TNB basis))

Given an unit-speed curve.

The tangent, normal, and binormal unit vectors, often called T, N, and B make up the Frenet–Serret basis (or TNB basis), together form an orthonormal basis that spans $\mathbb{R}^3$ are defined as follows:

T is the unit vector tangent to the curve, pointing in the direction of motion.
N is the normal unit vector, the derivative of T with respect to the arclength parameter of the curve, divided by its length.
B is the binormal unit vector, the cross product of T and N.

In math word:

$T = x'(s)$
$N = x''(s)$
$B = T\times N$

Because we have $<x'(s),x'(s)>=1$ , one has $<x'(s), x''(s)>=0$ , so $x''(s) is normal of the curve$

The maginitude of $x''(s)$ $x^{''} (s)$ is the absolute value of the curvature $\kappa$ $κ$
- $x''(s)=\kappa(s)n(s)$
- inverse of osculating radius

\frac{d}{ds}\begin{pmatrix} t(s)\\ n(s)\\ b(s) \end{pmatrix} = \begin{pmatrix} 0 & \kappa(s) & 0\\ -\kappa(s) & 0 & \tau(s)\\ 0 & -\tau(s) & 0 \end{pmatrix} \begin{pmatrix} t(s)\\ n(s)\\ b(s) \end{pmatrix}

Fundamental theorem of Curves

In 2D, the curvature $\kappa(t)$ fully determines a planar curve up to rigid motion (translation, rotation)
In 3D, the curvature $\kappa(t)$ and torsion $\tau(t)$ fully determine a curve up to rigid motion.

But now what, how to explain the curve to the computer?

The simplest form could be through a function: $y=f(x)$

Or through $2$ functions we saw earlier.

Or ... through interpolation between ordered points:

linear interpolation: easy, but look boring, and not smooth
linear combination of smooth functions

Winding number

Winding number (winding index) of a closed curve in the plane around a given point is an integer representing the total number of times that the curve travels counterclockwise around the point, i.e., the curve's number of turns. For certain open plane curves, the number of turns may be a non-integer. The winding number depends on the orientation of the curve, and it is negative if the curve travels around the point clockwise.


-2	-1	0

1	2	3

Turning number theorem:

\oint_C \kappa ds = k2\pi \text{ with }k\text{ being turning number.}

Generic Interpolation

Given points $(x_i,y_i)$ and basis functions $\{\phi_i(x)\}$ , find a function:

f(x) = \sum_{i=1}^N a_i\phi_i(x) \text{ s.t. }f(x_i)=y_i

Solution step-by-step:

Construct the Vandermonde-like matrix:

W = \begin{pmatrix} \phi_1(x_1) & \phi_2(x_1) & \ldots & \phi_N(x_1)\\ \phi_1(x_2) & \phi_2(x_2) & \ldots & \phi_N(x_2)\\ \vdots & \vdots & \ddots & \vdots \\ \phi_1(x_N) & \phi_2(x_N) & \ldots & \phi_N(x_N) \end{pmatrix}

Solve for the vector $a = W^{-1}y$
Done

So the problem come back to the choice of the basis function $\phi_i$ .

Polynomial Interpolation

simple, but can easily go bad:

Runge phenomenon
local changes affect global shape
may not converge
terrible condition number for W.

Spline Interpolation

Idea: although globally, there is no interpolating low-degree polynomial, locally, we may find a good one.

Goal: construct a set of local, piecewise expressions that result in a smooth, global curve:

simpler is better, so let's keep it of low-order
but too simple is bad: linear should be avoided for example

cubic polynomial is the first order having inflections (change of curvature)

To formularize the problem again:

Given pairs of coordinates $\{x_i,y_i\}$ , construct a function $f$ s.t. $f(x_i)=y_i \forall i$ that is cubic in each interval $[x_i,x_{i+1}]$ .

We have:

\begin{alignat*}{7} &f_i(x_i) &&= y_i &&\iff a_i &&+ b_ix_i &&+ c_ix_i^2 &&+ d_ix_i^3 &&= y_i\\ &f_i(x_{i+1}) &&= y_{i+1} &&\iff a_i &&+ b_ix_{i+1} &&+ c_ix_{i+1}^2 &&+ d_ix_{i+1}^3 &&= y_{i+1}\\ \end{alignat*}

This ensures that $f$ interpolates the points and is continuous.

But we also need smoothness:

\begin{alignat*}{4} f_i'(x_i) = f_{i-1}'(x_i) &\iff &&b_i &&+ 2c_ix_i &&+ 3d_ix_i^2\\ & = &&b_{i-1} &&+ 2c_{i-1}x_i &&+ 3d_{i-1}x_i^2 \end{alignat*}

I am not so sure why, but my lecture also requires second derivative at the end of each interval to be equalized.

And finally, we need to ensure $f'(x_1)=s_1$ and $f'(x_N)=s_N$ with $s_1, s_N$ being the direction of the curve at the very last points.

Thus we have a $4(n-1)$ linear equation with $4(n-1)$ variables. And this approach has some particular benefits:

easier to solve numerically (sparse solvers)
more stable solutions (lower condition number)
is guaranteed to converge as sampling density increases.

Note: This is so much better compare to Lagrange interpolation (polynomial version) because among all $C^2$ functions that interpolate a given set of points, spline interpolate minimizes:

\int_{x_1}^{x_N}f''(x)^2 dx

which is closely related to curvature minimization!

Variant of Cubic Splines

Hermite splines: The tangent at each endpoints is provided by users.
Catmull-Rom splines: tangent based on previous/next points

Other Ways to Design Splines

Find a more expressive basis:

\begin{align*} Q(u) &= a_0 + a_1u + a_2u^2 + a_3u^3\\ &= p_0b_0(u) + p_1b_1(u) + p_2b_2(u) + p_3b_3(u) \end{align*}

This works for arbitrary order $k=2,3,\dots$
$(p_i)_{i\le n}$ are the control points
$u\in[0,1]$ is the parameterization variable.

\begin{cases} b_i(u) \ge 0\\ \sum_{i=1}^k b_i(u) = 1 \end{cases}

A few more key-word to look at:

de Casteljau Algorithm: Repeated subdivision converges to curve
B Splines
Chaiken’s Algorithm: This idea is the basis of subdivision surfaces

Duc Nguyen

Shape Analysis #2: Curve Representation