CS 184: COMPUTER GRAPHICS
PREVIOUS
< - - - - > CS
184 HOME < - - - - > CURRENT
< - - - - > NEXT
Lecture #24 -- Tu: 11/23, 2004
Introduction to Splines
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.
Bicubic Bezier Patches
Now we have 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!).
Construction of Bezier Curves
DeCasteljau
construction algorithm: (Construction by three iterations of linear
interpolation)
The role of the control points.
-- How to draw a Bezier curve from its control points:
-- Subdivision of a Bezier curve into two pieces
that together are identical to the original one.
How
to put two Bezier segments together with G1 or with C1 continuity.
How
to approximate a given smooth curve with Bezier segments.
Intermezzo: Remarks on Final Projects
REMINDER: Send your partner information for the final project to Pushkar before 8pm tonight !
Some general points: You have only three week ...
- Keep it simple (KISS principle)!
- Build it incrementally (get something to work, then add to it).
- Tackle only one or
two new techniques (don't try to do inverse kinematics, collision
detection, flocking behavior, ... all at once).
- Keep it modular (try to reuse a technique that you have implemented in more than one instance).
B-Spline Curves
An easy way to make a smooth C2-continuous space curve 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 the text book.
In a nutshell, one segment depending on the 4 control points A,B,C,D,
is given by the polynomial:
Q = A(1 -3t +3t^2 -t^3)/6 + B(4 -6t^2 +3t^3)/6 + C(1
+3t +3t^2 -3t^3)/6 + D(t^3)/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!
Use of Splines in your Final Projects
Smooth camera paths.
Rollercoaster tracks.
Snake bodies.
Curved smooth bodies and shells.
A good introductory booklet on Splines with interactive demos:
"Interactive Curves and Surfaces," (with Multimedia Tutorial on CAGD),
A. Rockwood and P. Chambers, Morgan Kaufman Publishers, Inc.
Reading Assignment:
Study: 2ndEd: Ch 10.1-10.4, 10.6 -10.7, 10.9, 10.12 -10.14, 11.6 -11.7
Study: 3rdEd: Ch 10.1-10.4, 10.6 -10.7, 10.9, 10.12 -10.14,11.6 -11.7
Current Homework Assignment:
ASG#10
Final Project
CAN BE DONE WITH YOUR PARTNER OF CHOICE !
The normal default is to do this project in pairs.
If you have good reason to want to do this alone or in a group of three,
you need to send a petition to Prof. Sequin before Sunday, Nov. 21, midnight.
In any case, everybody will have to mail their partner information to Pushkar before Tuesday, Nov. 23, 8pm.
Project Due Date is Monday, December 13, 7:59pm.
PREVIOUS
< - - - - > CS
184 HOME < - - - - > CURRENT
< - - - - > NEXT
Page Editor: Carlo H. Séquin