Curves in Computer Graphics
Fonts
Parametric Curves
Jason Lawrence Princeton University COS 426, Spring 2005
ABC
Animation
(Angel, Plate 1)
Animation paths
Shape modeling
etc
Shell
(Douglas Turnbull, CS 426, Fall99)
Implicit curves
An implicit curve in the plane is expressed as: f(x, y) = 0 Example: a circle with radius r centered at origin: x 2 + y 2 - r2 = 0
y r x
Parametric curves
A parametric curve in the plane is expressed as:
x = fx(u) y = fy(u)
Example: a circle with radius r centered at origin:
x = r cos u y = r sin u y r x
Parametric curves
How can we define arbitrary curves?
x = fx(u) y = fy(u)
Parametric curves
How can we define arbitrary curves?
x = fx(u) y = fy(u) V0 V1
Use functions that blend control points
x = fx(u) = V0x*(1 - u) + V1x*u y = fy(u) = V0y*(1 - u) + V1y*u
Parametric curves
More generally:
x(u ) = Bi (u ) *Vix
y (u ) = Bi (u ) *Vi y
i =0
Parametric curves
What B(u) functions should we use?
x(u ) = Bi (u ) *Vix y (u ) = Bi (u ) *Vi y
i =0 i =0 n n
i =0 n
x(u), y(u)
V2 V3
V1 V0
Parametric curves
What B(u) functions should we use?
x(u ) = Bi (u ) *Vix y (u ) = Bi (u ) *Vi y
i =0 i =0 n n
Parametric curves
What B(u) functions should we use?
V1
x(u ) = Bi (u ) *Vix y (u ) = Bi (u ) *Vi y
i =0 i =0 n
V1
V0
V0
V2
B0
1
B1
B0
B1
B2
0 0 1
0 0 1
0 0 1
0 0 1
Goals
Some attributes we might like to have:
o o o o Interpolation Continuity Predictable control Local control
Continuity
Parametric continuity (Cn)
o How many times differentiable is the curve at a given point
V0 V1
Continuity at joints:
Well satisfy these goals using:
o Piecewise o Parametric o Polynomials
o C0 continuity means curve is connected at joint V2 o C1 continuity means that segments V3 share same first derivative at joint o Cn continuity means that segments share same nth derivative at joint V4
V5 V6
Parametric Polynomial Curves
Blending functions are polynomials:
x(u ) = Bi (u ) *Vix y (u ) = Bi (u ) *Vi y
i =0 i =0 n n
Parametric Polynomial Curves
Derive polynomial Bi(u) to ensure properties
V0
o Example: interpolation of control vertices o What about easy of control?
V0 V1 V2 V3
Bi (u ) = a j u
j =0
V1 V2 V3
Bi
1
Advantages of polynomials
o Easy to compute o Infinitely continuous o Easy to derive curve properties
V4
-1
V4 V5 V6
V5 V6
V0
V1
V2
V3
V4
V5
V6
Piecewise Parametric Polynomial Curves
Splines:
o Split curve into segments o Each segment defined by blending subset of control vertices
Piecewise Parametric Polynomial Curves
Compute polynomial Bi(u) to ensure properties
o Example: interpolation of control vertices and C2 continuity at joints with cubics
V0 V1 V2 V3
V0 V1
Motivation:
o Provides control & efficiency o Same blending function for every segment o Prove properties from blending functions
Bi
1
V2 V3
u
Challenges
o How choose blending functions? o How guarantee continuity at joints?
V4
-1
V4 V5 V6
V5 V6
V0
V1
V2
V3
V4
V5
V6
Cubic Piecewise Parametric Polynomial Curves From now on, consider cubic blending functions
o All ideas generalize to higher degrees
Types of Splines
Splines covered in this lecture
o o o o Hermite Bezier Catmull-Rom B-Spline
In CAGD, higher-order functions are often used
o Hard to control wiggles
In graphics, piecewise cubic curves will do
o Smallest degree that allows C2 continuity for arbitrary curves
There are many others
Each has different blending functions Each has different blending functions resulting in different properties resulting in different properties
Cubic Hermite Splines
Definition:
o Each segment defined by position and derivative at two adjacent control vertices o Blending functions are cubic polynomials
Cubic Hermite Splines
Definition:
V0 V1 V2 V3 V4 V5 V6
o Each segment defined by position and derivative at two adjacent control vertices o Blending functions are cubic polynomials
V0
D0
P V1 D1
Properties:
o Interpolates control points o C1 continuity at joints
Properties:
o Interpolates control points o C1 continuity at joints
P(u) = B0(u)*D0 + B1(u)*V0 + B2(u)* V1 + B3(u)* D1
Cubic Hermite Splines
Blending functions:
Bi (u ) = a j u
j =0 m j
Types of Splines
Splines covered in this lecture
V0 V1
o Hermite ! Bezier o Catmull-Rom o B-Spline
Bi-1
1
Bi
1
V2 V3
0 1
There are many others
0 1
Bi+1
0 1 1
Bi+2
V4 V5 V6
Each has different blending functions Each has different blending functions resulting in different properties resulting in different properties
0 1
Bezier curves
Blending functions:
Bi (u ) = a j u j
j =0 m
Bzier curves
Developed simultaneously in 1960 by
V0 V1
o Bzier (at Renault) o deCasteljau (at Citroen)
Bi-3
1
Bi-2
1
V2 V3
0 1
Curve Q(u) is defined by nested interpolation:
V1 V2
0 1
Bi-1
0 1
Bi
1
V4 V0 V5 V6
Vis are control points {V0, V1, , Vn} is control polygon
Q(u)
V3
0 1
Basic properties of Bzier curves
Endpoint interpolation:
Q (0) = V0 Q (1) = Vn
Explicit formulation
Lets indicate level of nesting with superscript j: An explicit formulation of Q(u) is given by:
Vi j = (1 u )Vi j 1 + uVi +j1 1
Convex hull:
o Curve is contained within convex hull of control polygon
Case n=3 (expand recurrence):
Q (u ) = V03 = (1 u )V02 + uV12 = (1 u )[(1 u )V01 + uV11 ] + u[(1 u )V11 + uV21 ] = (1 u )[(1 u )[(1 u )V00 + uV10 ] + u[(1 u )V10 + uV20 ]......
Symmetry
Q (u ) defined by {V0 ,...,Vn } Q (1 u ) defined by {Vn ,...,V0}
More properties
General case: Bernstein polynomials
n n Q (u ) = Vi u i (1 u ) n i i =0 i
Matrix form
Bzier curves may be described in matrix form:
n n Q (u ) = Vi u i (1 u ) n i i i =0 = (1 u )3V0 + 3u (1 u )2V1 + 3u 2 (1 u )V2 + u 3V3
Degree: is a polynomial of degree n
Q ' (0) = n(V1 V0 ) Q ' (1) = n (Vn Vn 1 )
= (u 3 u 2
Tangents:
1 3 3 3 6 3 u 1) 3 3 0 1 0 0
1 V0 0 V1 0 V2 0 V3
MBezier
Display
Q: How would you draw it using line segments? A: Recursive subdivision!
V1 V2
Display
Pseudocode for displaying Bzier curves:
procedure Display({Vi}): if {Vi} flat within then output line segment V0Vn else subdivide to produce {Li} and {Ri} Display({Li}) Display({Ri}) end if end procedure
V0
V3
Flatness
Q: How do you test for flatness? A: Compare the length of the control polygon to the length of the segment between endpoints
V1 V2
Splines
For more complex curves, piece together Bziers We want continuity across joints:
o Positional (C0) continuity o Derivative (C1) continuity
Q: How would you satisfy continuity constraints?
Q: Why not just use higher-order Bzier curves?
V0
| V1 V0 | + | V2 V1 | + | V3 V2 | <1+ | V3 V0 |
V3
A: Splines have several of advantages:
Numerically more stable Easier to compute Fewer bumps and wiggles
Types of Splines
Splines covered in this lecture
o Hermite o Bezier ! Catmull-Rom o B-Spline
Catmull-Rom splines
Properties
o Interpolate control points o Have C0 and C1 continuity
Derivation
o Start with joints to interpolate o Build cubic Bzier between each joint o Endpoints of Bzier curves are obvious
There are many others
Each has different blending functions Each has different blending functions resulting in different properties resulting in different properties
What should we do for the other Bzier control points?
Catmull-Rom Splines
Catmull & Rom use:
o half the magnitude of the vector between adjacent CPs
Properties
Catmull-Rom splines have these attributes:
o C1 continuity o Interpolation o Locality of control o No convex hull property (Proof left as an exercise.)
Many other formulations work, for example:
o Use an arbitrary constant times this vector o Gives a tension control o Could be adjusted for each joint
Types of Splines
Splines covered in this lecture
o Hermite o Bezier o Catmull-Rom ! B-Spline
B-Splines
Properties:
o Local control o C2 continuity o Cubic polynomials
V0 V1
Constraints:
o Three continuity conditions at each joint j Position of two curves same V3 Derivative of two curves same Second derivatives same o Local control Each joint affected by 4 control vertices
There are many others
V2
Each has different blending functions Each has different blending functions resulting in different properties resulting in different properties
Give up interpolation :)
V5
Matrix formulation for B-splines
List mathematical constraints:
Qi (u ) = (u 3 u 2 Vi 3 V u 1)M BSPLINE i 2 V i 1 V i
Qi (1) = Qi +1 (0) Qi ' (1) = Qi +1 ' (0) Qi ' ' (1) = Qi +1 ' ' (0)
B-Splines
Blending functions:
o Local control: how can we tell? o Interpolates control points?
1
V0 V1
V3
1 0 0 0
0
V0 V1 V2 V3 V4 V5
V2
Grind through some messy math to get:
1 3 3 1 3 6 3 = 3 6 3 0 1 4 1
u
M BSPLINE
V5
Summary
Splines: mathematical way to express curves Motivated by loftsmans spline
o o o o Long, narrow strip of wood/plastic Used to fit curves through specified data points Shaped by lead weights called ducks Gives curves that are smooth or fair
Whats next?
Use curves to create parameterized surfaces Surface of revolution Swept surfaces Surface patches
Have been used to design:
o Automobiles o Ship hulls o Aircraft fuselage/wing Przemyslaw Prusinkiewicz Demetri Terzopoulos
