W Randolph Franklin home page
... (old version)
Research/ home page Login

Here are some random notes on splines.

  1. Here is an intro paper by an author I usually agree with: 77-bezier.pdf
  2. Mathematica has some good spline demos, playable with the free MathematicaPlayer.
  3. 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.
  4. 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) $}
  5. 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.
  6. 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} $}
  7. 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.
  8. 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.
  9. 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.
  10. 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''.
  11. BSplineCurveWithKnots.nbp shows many things about B-splines.
    1. Set the degree to 1.
      1. Observe that the curve is just the control polygon.
      2. The basis functions show that each point depends on the 2 closest control points.
    2. Set the degree to 2.
      1. See the the midpoint of each edge of the control polygon has a new red point, called a joint at its middle.
      2. The B-spline curve is a sequence of curves.
      3. Each segment curve is a Bezier curve. Its control points are a knot and the two adjacent joints.
      4. The end segments are a special case, as you can see.
      5. 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 C1 at the joints and C2 elsewhere.
      6. 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 G1. This is visibly just as smooth as C1 and gives the designer an extra degree of freedom.
      7. Move control points 3 and 4 together, but not collinear with 2 and 5. The spline will not be C1 there. Every extra coincident control point lowers the degree of continuity there by 1. This is called a nonuniform B-spline.
      8. Move a control point and see that only the nearby part of the spline moves.
      9. Finally, look at the basis functions. Each point on the spline depends on the 3 closest control points.
      10. 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.
      11. Putting everything together, we have a Non-Uniform Rational B-Spline, i.e., a NURBS.
      12. The control polygon could be closed, tho this demo doesn't show it. Then there are no end conditions.
    3. 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.
    4. Set the degree to 3.
      1. The joints are determined with a procedure like de Castelau interpolation.
  12. 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.
    1. A space curve may look better.
    2. If the curve is modelling a robot arm, then a sequence of quadratic curves will cause the arm to move unevenly.
  13. 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).
  14. 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.
  15. 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.
  16. Computing the cubic B-spline from the control polygon:
    1. Find control polygon of each Bezier piece.
    2. Cut each edge into thirds with 2 extra points.
    3. Join new points adjacent to each old vertex, and add a new point in middle of that new edge.
  17. When interpolating a curve with a B-spline, choosing the knot set is important.
  18. Given the knot set, we also need the tangents at those points. Two choices (at least):
    1. Infer them from the adjacent knots, or
    2. Compute them from the curve
  19. Properties:
    1. Affine invariance
    2. linear precision
    3. convex hull
    4. variation diminishing
  20. Differential geometry considerations
    1. parametric vs geometric continuity. Parametric is easier, geometric is better.
    2. arc-length (or natural) paramaterization: good but hard.
    3. Frenet coords
  21. tensor product surface: de Castelau
    1. matrix form
  22. The twist at the corner of a patch is the deviation from planarity. It's relevant but hard to visualize.
  23. 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.
  24. 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.
    1. Interpolate between top and botton curves.
      {$r_c = (1-v) x(u,0) + v x(u,1) $}
    2. Interpolate between left and right curves.
      {$r_d = (1-u) x(0,v) + u x(1,v) $}
    3. 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} $}
    4. Then
      {$x(u,v) = r_c + r_d - r_{cd} $}
    5. 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.
  25. Bicubic Coons: also match derivatives across the edges.
  26. This can be combined with some other method to create a skeleton grid of lines, filled in with Coons patches.
  27. Triangular patches: better than tensor-product, but harder, therefore rarer.
  28. Constructive Solid Geometry (CSG): Build an object from boolean operations (union, intersection, difference) of a set of primitive objects, like blocks and cylinders.
    1. This idea starts nicely; visualization is easy. Finding approximate volume is easy.
    2. However there are limits, like explicitly finding the resulting object, and especially its edges.
    3. The boolean ops are regularized.