Here are some random notes on splines.

- Here is an intro paper by an author I usually agree with: 77-bezier.pdf
- Mathematica has some good spline demos, playable with the free MathematicaPlayer.
- RungesPhenomenon.nbp shows approximating a
smooth function by selecting N points on it and interpolating
an (N-1)-degree polynomial through the points. This is
called
*Lagrangian interpolation*However this function is tricky. Although it is infinitely differentiable, it has nearby complex poles. Therefore, e.g., a Taylor series would have a very small radius of convergence, and very slow convergence within that radius. In any case, with this function as more equally spaced points are added, the approximation quickly gets*worse*!. However, if unequally spaced Chebyshev points are used, then the approximation slowly gets better. The lesson is that using a single hi-degree polynomial is wrong. Instead, use multiple lo-degree curves (splines) joined smoothly together. - Lagrangian interpolation math: The {$n+1$} input points are {$(x_i,y_i)$}. {$f(x)$}, the resulting polynomial has degree {$n$}. {$ L_i(x) = \prod_{j=0, j\ne i}^{j=n} \frac{x-x_j}{x_i-x_j}.$} {$f(x) = \sum_{i=0}^{n} y_i L_i(x) $}
- SimpleSplineCurves.nbp demonstrates cubic Bezier
parametric curve changes as the endpoints are moved. The
curves goes through the two endpoints, but not through the
two middle control points. However, it is completely inside
the four control points' convex hull. This means that you
know how curvy the curve will be.
This also shows
*interpolating*a curve through all four control points. This requires that the curve swing outside the convex hull by an amount that is not completely predictable. Therefore interpolating the control points is not used much. This also shows that you should be careful what you wish for. - Bernstein polynomial math:
*x*is the parameter. {$ 0\le x \le 1 $}. {$n$} is the degree. {$n+1$} is the number of control points.

{$ B_i(x) = {n \choose i} x^i (1-x)^{n-i} $} - Bezier curve math: {$P_i$} are the control points. {$P(x)$} is the output curve. {$ P(x) = \sum_{i=0}^n P_i B_i(x) $}. Here the curve is an explicit function of x. However, x and y could just as easily be explicit functions of parameter t.
- BezierCurveByDeCasteljausAlgorithm.nbp shows how to compute any point on a Bezier curve by a sequence of linear interpolations. Thid also shows how to subdivide a Bezier curve into two smaller Bezier curves, with their control points. Since the new curves are straighter, repeating this a few times approximates the curves by a sequence of straight lines.
- BernsteinPolynomials.nbp shows the Bernstein weighting polynomials for different degrees. Each point on the curve depends on all control points, though it depends more on the closer control points.
- BSplineBasisFunctions.nbp shows the B-spline basis functions. Each point on curve depends only on the closest control points. IOW, changing one control point changes only part of the curve. That is called ''local control''.
- BSplineCurveWithKnots.nbp shows many things
about B-splines.
- Set the degree to 1.
- Observe that the curve is just the control polygon.
- The basis functions show that each point depends on the 2 closest control points.

- Set the degree to 2.
- See the the midpoint of each edge of the control polygon
has a new red point, called a
*joint*at its middle. - The B-spline curve is a sequence of curves.
- Each segment curve is a Bezier curve. Its control points are a knot and the two adjacent joints.
- The end segments are a special case, as you can see.
- Since the derivative of the endpoint of a Bezier curve is
proportional to the line connecting the last two control
points, and since the joint is in the middle between the
two control points, the two Bezier curves at the joint
have matching derivatives. The spline is C
^{1}at the joints and C^{2}elsewhere. - The joints can be anywhere along the edge; they don't
have to be in the middle (tho you can't change them in
this demo). If a joint is not in the middle, then the
two Bezier curves will have matching tangents but not
derivatives. That is called G
^{1}. This is visibly just as smooth as C^{1}and gives the designer an extra degree of freedom. - Move control points 3 and 4 together, but not collinear
with 2 and 5. The spline will not be C
^{1}there. Every extra coincident control point lowers the degree of continuity there by 1. This is called a*nonuniform*B-spline. - Move a control point and see that only the nearby part of the spline moves.
- Finally, look at the basis functions. Each point on the spline depends on the 3 closest control points.
- Here,
*x*and*y*are functions of a parameter*u*. We could use homogeneous coordinates and make*w*also to be a function of*u*. That makes a*rational*B-spline. - Putting everything together, we have a
**N**on-**U**niform**R**ational**B**-**S**pline, i.e., a**NURBS**. - The control polygon could be closed, tho this demo doesn't show it. Then there are no end conditions.

- See the the midpoint of each edge of the control polygon
has a new red point, called a
- Think about a sequence of Bezier curves forming a spline. Because of continuity constraints at the joints, each extra curve adds only one free control point.
- Set the degree to 3.
- The joints are determined with a procedure like de Castelau interpolation.

- Set the degree to 1.
- Advantage of cubic segments over quadratic segments:
A quadratic Bezier curves is planar even if the control polygon
is in 3D (since with only 3 points, the polygon is planar).
However, a cubic Bezier curve with a nonplanar control polygon
is a space curve. This gives the designer more freedom.
- A space curve may look better.
- If the curve is modelling a robot arm, then a sequence of quadratic curves will cause the arm to move unevenly.

- Hermite form of cubic Bezier curve: Instead of 4 control points, we have 2 control points and their parametric derivatives. The number of d.f. matches. As before, going from the inputs to the coefficients of the cubic polynomials is just a matrix multiplication (with a different matrix).
- Advantage of splitting a Bezier curve into two smaller curves that, together are identical to the original Bezier curve: Then the designer can move the control points of one of the curves. This lets him add local details to the curve.
- Hermite form of spline: Instead of computing control points for each Bezier piece of the spline, compute control points and parametric derivatives for each Hermite piece.
- Computing the cubic B-spline from the control polygon:
- Find control polygon of each Bezier piece.
- Cut each edge into thirds with 2 extra points.
- Join new points adjacent to each old vertex, and add a new point in middle of that new edge.

- When interpolating a curve with a B-spline, choosing the
*knot set*is important. - Given the knot set, we also need the tangents at those
points. Two choices (at least):
- Infer them from the adjacent knots, or
- Compute them from the curve

- Properties:
- Affine invariance
- linear precision
- convex hull
- variation diminishing

- Differential geometry considerations
- parametric vs geometric continuity. Parametric is easier, geometric is better.
- arc-length (or natural) paramaterization: good but hard.
- Frenet coords

- tensor product surface: de Castelau
- matrix form

- The
*twist*at the corner of a patch is the deviation from planarity. It's relevant but hard to visualize. - Trimmed patches:
You may want to cut a patch where it intersects another patch.
That
*trim line*may be a paramaterized curve in the local coordinate systems of the two patches. Those two versions will be slightly different, leading to a gap or overlap. - Coons patch:
Given a square patch defined by 4 parametric curves for the 4
sides, this interpolates the interior of the patch. The curves
can be anything.
- Interpolate between top and botton curves. {$r_c = (1-v) x(u,0) + v x(u,1) $}
- Interpolate between left and right curves. {$r_d = (1-u) x(0,v) + u x(1,v) $}
- A correction: {$ r_{cd} = \begin{bmatrix} 1-u & , & u \end{bmatrix} \begin{bmatrix} x(0,0) & x(0,1) \\ x(1,0) & x(1,1) \end{bmatrix} \begin{bmatrix} 1-v \\ v \end{bmatrix} $}
- Then {$x(u,v) = r_c + r_d - r_{cd} $}
- The {$ \begin{bmatrix}1-u&,& u\end{bmatrix} $} interpolator can be replaced with other things, like {$ \begin{bmatrix} 1-3t^2+2t^3 & , & 3t^2-2t^3\end{bmatrix} $} That makes the derivative 0 at the edges, so patches will join smoothly. However there is a twist.

- Bicubic Coons: also match derivatives across the edges.
- This can be combined with some other method to create a skeleton grid of lines, filled in with Coons patches.
- Triangular patches: better than tensor-product, but harder, therefore rarer.
- Constructive Solid Geometry (CSG): Build an object from boolean
operations (union, intersection, difference) of a set of
primitive objects, like blocks and cylinders.
- This idea starts nicely; visualization is easy. Finding approximate volume is easy.
- However there are limits, like explicitly finding the resulting object, and especially its edges.
- The boolean ops are
*regularized*.