(Smooth) CURVES and SURFACES

Lecture #1  for CS 274

Monday  3/14, 2005 -- 12:40-2:00pm, -- 203 McLaughlin

Introduction to Splines

Motivational task:  How to construct a spiral ?
    -- piecewise  linear - yields connectivity;
    -- composed of circular arcs - yields G1 (tangent-) continuity;
    -- composed of elliptical arcs - yield G2 (curvature-) continuity.

How do you represent straight lines, planes ?
How do you generalize that to curves, curved surfaces ?
    -- parametric representations.

What are "splines" ? -- Wood strips used in ship building that yield nice smooth curves,
because nature is trying to minimize overall bending energy (= arc-length integral of curvature squared).
Depending on what fixtures are being used one can apply different constraints to those strips
    -- Position Constraints are implemented with pegs, and
    -- Tangent Constriants can be realized with clamps.
Mathematical "splines" are linearized approximations to the above difficult optimization problem.

When making smooth shapes by piecing together smooth curves, consider the
degrees of smoothness at the joints:
    -- Parametric Continuity: differentiability of the parametric representation (C0, C1, C2, ...)
    -- Geometric Continuity: smoothness of the resulting displayed shape (G0=C0, G1=tangent-cont., G2=curvature-cont. )

Distinguish between:
    -- Interpolating splines (pass through all the data points; example Hermite splines), and
    -- Approximating splines (only come close to data points; example B-Splines).
 

Cubic Bezier Curves

These very handy curves are a mixture of the above two "pure" schemes.
Cubic Bezier Curve is defined by:
    -- 2 interpolated endpoints, and
    -- 2 approximated intermediary control points that define the tangent directions at the endpoints.
Cubic polynomials: ==> allow to make inflection points and true space curves in 3D.

Basic underlying math;
(Cubic) Polynomial: infinitely differentiable --> Continuity = C-infinity
Cubic Hermite Spline: 2 endpoints, 2 tangent directions.
Cubic Bezier Curve: 2 endpoints, 2 approximated intermediary control points.
    -- (P1,P2) = 1/3 of starting velocity vector
    -- (P3,P4) = 1/3 of ending velocity vector
Influence of parameters (qualitative view).
DOF's.

Properties of Bezier Curves

  • Cubic polynomial, ==> true space curves;
  • Interpolates endpoints;
  • Approximation of other two control points;
  • End tangents defined by pairs of control points;
  • Convex hull property;
  • Invariant under affine transformations;
  • Start-to-end symmetry;
  • Infinitely differentiable;
  • May have loops, cusps.

    • Construction of Bezier Curves

    DeCasteljau construction algorithm: (Construction by three iterations of linear interpolation)  
    How to draw a Bezier curve from its control points:
        -- the geometrical construction.
        -- the polynomial resulting from the repeated interpolations.
    Subdivision of a Bezier curve into two pieces that together are identical to the original one.

    Higher-order Bezier Curves and Patches

    It is hard to make "interesting" curves with high-order Bezier curves.
        -- points in the middle of the curve get influenced by every control point!
    But 5th degree (quintic) Bezier curves are very useful if you also want to get control over curvature at the ends.

    Stitching Bezier Curves Together

  • Aiming for more control over complicated curves.
  • Making Interpolating Curves from several Bezier segments.
  • Tangent Continuity Conditions at the joints.
  • Curvature Continuity Conditions at the joints.
  • Counting Degrees of Freedom (DoF)
    •      -- Each control point in 2D has 2 DoF.
         -- Each constraint imposed removes one DoF.
         -- How many DoF are remaining ?
  • How to use these DoF's ?
    •      ---> Optimize the curve !
  • Global Optimization (approximation)
    •      -- Define a cost function:
         -- E.g., Strain Energy = arc-length integral of square of curvature.

    How to approximate a given smooth curve with Bezier segments.

    Bicubic Bezier Patches  (Two-Manifolds)

    Use two parameters (u,v). Apply the above principle twice:
        -- Step one: make a few control curves (say as a function of v);
        -- Use these control curves to define a whole familiy of curves in the u-direction.
    All this forms a two-parameter patch.

    Putting patches together with G1- or G2- continuity is not trivial
    (same issues as for curves -- only more of them!).

    To make curvature-continuous (G2 or C2) surfaces, use biquintic Bezier patches.
    (but even more of a hassle to get all the control points in the right place!).
     

    B-Splines

    (a better way to make extensive smooth curves and surfaces)

    An easy way to make a smooth C2-continuous space curve, e.g.,  for a path of an airplane or for a camera path,
    is to sprinkle a few control points through space that define the coarse topology and geometry of the curve
    and then let them be approximated by a cubic B-spline.
    Assuming for the moment a closed curve with N=6 control points, such a curve would be described as
    a sequence of N=6 cubic curve segments, each one of which is controlled by four consecutive control points,
    but producing a curve segment that is only about as long as the distance between the two middle control points.
    Because a subsequent curve segment reuses three of the control points of the previous segment,
    they blend together in a very smooth (C2-continuous) way.

    The interpolation function is given in all relevant text books:
    One segment depending on the 4 control points A,B,C,D, is given by the polynomial:

    Q = A(1 -3t +3t2 -t3)/6 + B(4 -6t2 +3t3)/6 + C(1 +3t +3t2 -3t3)/6 + D(t3)/6

    thus the point at t=0 is given by  A/6 + 4B/6 + C/6,
    and the point at t=1 is given by  B/6 + 4C/6 + D/6.

    Properties of Cubic B-Splines

  • Piecewise cubic polynomial;
  • Does NOT interpolate control points;
  • Convex hull property;
  • Construction by 3-fold linear interpolation
  • Invariant under affine transformations;
  • Start-to-end symmetry;
  • Twice differentiable (C2) at joints;
  • Infinitely differentiable everywhere else;
  • May have cusps, thus may not be G2 everywhere;
  • Good to make smooth closed loops.
    •  

    B-Spline Surfaces

    Apply B-Spline machinery in two different directions.
    Creates a small patch near the central "mesh" of the control point grid.
    Will create smooth surfaces if the control points are properly reused (overlaped) for adjacent patches.
    Much easier than stitching together Bezier patches -- but creates an approximating surface!

    REFERENCES -- TO LEARN MORE:

    "Interactive Curves and Surfaces," (with Multimedia Tutorial on CAGD), A. Rockwood and P. Chambers, Morgan Kaufman Publishers, Inc.

    Page Editor: Carlo H. Séquin