cse3431-lecture15-paramcurves
Curves and Surfaces
Curve Design
Representing curves
Explicit: y = f(x), z=g(x)
• Cannot get multiple values for single x, infinite slopes
• E.g. cannot represent a circle
Implicit (2D): f(x,y) = 0
• Cannot easily compare tangent vectors at joints
• Above/below test, normals from gradient
Parametric: x=fx(t), y = fy(t), z= fz(t)
• Often the most convenient formulation
• Tangent of curve (f(t),g(t),h(t)) is (f’(t), g’(t),h’(t)) where ’
indicates derivative wrt to t
Describing curves by means of
polynomials
Reminder:
Lth degre polynomial
Parametric and implicit forms are linear
x(t) = at +b
y(t) = ct +d
F(x,y) = kx + ly+m
Polynomial Curves of Degree 1
x
y(x)
t
y(t)
x(t)
Polynomial Curves of Degree 2
Parametric
x(t) = at2+2bt+c
y(t) = dt2+2et+f
t in R
For any choice of constants
a,d,c,d,e,f →parabola
Implicit
F(x,y) = Ax2+2Byx+Cy2+Dx+Ey+G
Let d = AC-B2
d > 0 → F(x,y) = 0 is an ellipse
d = 0 → F(x,y) = 0 is a parabola
d < 0 → F(x,y) = 0 is a hyperbola
1. Parabola
2. Circle and Ellipse
3. Hyperbola
Courtesy of Pbroks13, Wikipedia
http://commons.wikimedia.org/wiki/User:Pbroks13
Polynomial curves of degree 2
Common Vertex form:
Rational Quadratic Parametric
Curves
w < 1 ellipse
w = 1 parabola
w > 1 hyperbola
Other kinds of curves
Sinusoidal
Exponential
Complex
Fractals
Differential Geometry Concepts
Tangent vector
• Given a parameterized curve
p(t): τ(t) = p’(t) = dp(t)/dt
defines the forward orientation of the curve and the
parametric velocity
• Notice that it is a function of t and that it is a vector
• It defines locally (instantaneously) the shape of the
curve at each point and can be used for interactive
design tools
• Unit tangent: T(t) = τ(t) / ||τ(t)||
Differential Geometry Concepts
Normal vector (AKA curvature vector)
• Given the unit tangent vector T(t):
•
• Indicates how far from a straight line the curve is
(Line has 0 curvature)
• Normal to the tangent vector T
e2(t) = p
00(t)� (p00(t) ·T(t))T(t)
N(t) =
e2(t)
||e2(t)|| N
T
Differential Geometry Concepts
Binormal
• Normal to both tangent and normal vectors
• In 3D:
B = T ⊗ N
Frenet frame
The three vectors together form the Frenet
frame
Osculating plane
defined by N,T
Curve design in graphics and
animation
• In graphics we often want to interpolate or
approximate a set of values in an efficient and
predictable way
• We use parametric polynomials and constrain them to
create desired types of curves
Geometric approach
P0, …,PL→ → P(t)
Constraints Polynomial Curve
Parametric polynomial curve
design in graphics
Curve
generation
Any t
Interpolation vs
Approximation
P0
P3
P1
P2
P0
P1
P2
P4
P5
P6
Geometric approach
P0, …,PL→ → P(t)
Constraints Polynomial Curve
Pi control points
P0 …PL control polygon
Parametric polynomial curve
design in graphics
Curve
generation
Any t
Interpolation vs
Approximation
P0
P3
P1
P2
P0
P1
P2
P4
P5
P6
Tweening
Two points=line
A(t) = (1-t)P0 + tP1
De Casteljau Algorithm
P0
P1
A(t)
Tweening
Three points
A(t) = (1-t)P0 + tP1
B(t) = (1-t)P1 + tP2
De Casteljau Algorithm
P0
P1
P2
A(t)
B(t)
Tweening
Three points
(parabola)
A(t) = (1-t)P0 + tP1
B(t) = (1-t)P1 + tP2
P(t) = (1-t) A(t) + tB(t) = (1-t)2P0 +2t(1-t)P1+t2P2
De Casteljau Algorithm
A(t)
B(t)
P(t)
P0
P1
P2
Tweening
Three points
(parabola)
A(t) = (1-t)P0 + tP1
B(t) = (1-t)P1 + tP2
P(t) = (1-t) A(t) + tB(t) = (1-t)2P0 +2t(1-t)P1+t2P2
De Casteljau Algorithm
A(t)
B(t)
P(t)
P0
P1
P2
De Calsteljau (cont)
Tweening with four points
P(t) = (1-t)3P0+3(1-t)2tP1+3(1-t)t2P2+t3P3
P0
P1
P2
A(t)
B(t)
P(t)
P3
One of the most fundamental concepts in
curve design
P(t) = (1-t)3P0+3(1-t)2tP1+3(1-t)t2P2+t3P3
Bezier Curves
P0
P1
P2
P(t)
P3
Visualization
• Courtesy of Phil Tregoning, Wikipedia
Coefficients of Bezier Curves:
Berstein polynomials
P(t) = (1-t)3P0+3(1-t)2tP1+3(1-t)t2P2+t3P3
B30 (t) = (1- t)3
B31 (t) = 3(1- t)2t
B32 (t) = 3(1-t)t2
B33 (t) = t3
Expansion of [(1- t) + t]3 = (1- t)3 +3(1- t)2t + 3(1- t)t2 +t3 →
Σ B3k (t) = 1, k = 0,1,2,3
Affine combination of points
L + 1 control points, Pk
Expansion of [(1-t) + t]L
Berstein Polynomials of L
degree
P (t) =
LX
k=0
BLk (t)Pk where
BLk (t) =
✓
L
K
◆
(1� t)L�ktk
✓
L
K
◆
=
L!
k!(L� k)!
, for L � k
A�ne combination:
LX
k=0
BLk (t) = 1, for all t
Other Berstein Polynomials
Properties
Allways positive
Zero only at t =0 or 1
Degree 3
Properties of Bezier curves
• End point interpolation
• Affine Invariance:
• Invariance under affine transformation of the
parameter
• Convex Hull property
for t in [0,1]
• Linear precision by collapsing convex hull
• Variation Diminishing property: No straight line cuts
the curve more times than it cuts the control polygon
Derivatives of Bezier curves
It can be shown that:
Any derivative also a Bezier curve of lower degree
Which degree is best?
Cubic curves
• Lower order not enough flexibility
• Higher order too many wiggles and computationally
expensive
• Cubic curves are lowest degree polynomial curves
that are not planar in 3D
More complex curves
• Piecewise cubics
The general case for Cubic
Parametric Curves (piece)
• Bezier Cubic Curves are only one possible family of
cubic curves.
• We want more control of the constraints on the curves
– location
– shape
•
General form of Cubic
parametric curves
Matrix Form
Derivative of Cubic Parametric
Curves – tangent vector
Where the curve goes for
some t
How the curve is shaped
for some t
For a given set of constraints we get a family
of curves
Constraints
Endpoints and a tangent at midpoint
Setting up the curve
Constraints
Solving for A
Constraints
Final form
Basis matrix
For the example
Blending functions
T*M
For the example
Each blending function
weights the contribution
of one of the constraints
Hermite Curves
Constraints
Two points and two tangents
Hermite Curves
Blending functions
What does the magnitude of the
tangent do?
Interactive demo
Bezier Curves
Special case of Hermite
curves
Bezier Curves
Special case of Hermite
curves
Bezier Curves
Special case of Hermite
curves
Bezier Curves
Special case of Hermite
curves
Transforming between
representations
Just like Bezier and Hermite curves can be
transformed into each other with a matrix
multiplication, other families of curves can
do so as well
Bezier to Interpolating curves
• Curve must interpolate
Pi0,Pi1,Pi2,Pi3
Pi0
Pi3
Pi1 Pi2
Bezier to Interpolating curves
• Curve must interpolate
Pi0,Pi1,Pi2,Pi3
• How can we find the
Bezier points Pb from the
Pis so that the resulting
Bezier curve interpolates
the Pi points?
Pi0
Pb1
Pb2
Pi3
Pi1 Pi2
Bezier to Interpolating curves
For the next three slides
points are row vectors!!
Pb1
Pb2
Pi1 Pi2
Pi0
Pi3
Bezier to Interpolating curves
Pb1
Pb2
Pi1 Pi2
Pi0
Pi3
Bezier to Interpolating curves
Pi0
Pb1
Pb2
Pi3
Pi1 Pi2
Piecewise cubic curves
Connection?
C1
C2
C3
Continuity
Geometric Gk-continuity
P(i)(t-) = ciP(i)(t+) ∀t in [a,b]
for i = 0,…,k and
for some ci positive
constants
(P(i) is the i-th derivative)
Parametric Ck-continuity
P(i) exists and is continuous ∀t
in [a,b], for i = 0,…,k
Terminology:
P is k-smooth
P has kth-order continuity
Is a Ck-continuous function GK continuous as well?
Examples
C1
C2
C3
C1
C2
C3
Piecewise Cubic Hermite Curves
What are the conditions for G1 continuity?
Piecewise Cubic Hermite Curves
R’1 = kR4
P1’= P4
Catmull-Rom splines
Fit a piece wise cubic curve to the points
• Pi, i = 0,1,…,n-1
P0
P1xt
Pn-1xt
P2xt
Catmull-Rom splines
Fit a piece wise hermite curve to the points
• Pi, i = 0,1,…,n-1
Second order accurate tangents
• Ti = (Pi+1 – Pi-1)/2.0 for i = 1,…,n-2
• T0 = 2(P1 – P0) – (P2-P0)/2, similarly for Tn-1
P0
P1xt
Pn-1xt
P2xt
Uniform BSplines
Matrix form
For a bspline curve with:
• m+1 control points P0, …, Pm
• m-2 segments Q3,…, Qm
• t in [3,…,m]
Properties
C2 continuous
Convex hull property
NO invariace under perspective projection!
NURBS: Nonuniform Rational B-
splines
X(t) = X(t) / W(t)
Y(t) = Y(t) / W(t)
Z(t) = Z(t) / W(t)
• Exact conic sections
• Invariance under perspective projection
Summary: General problem
P0, …,PL→ → P(t)Curve generation
P (t) =
3X
i=0
Bi(t)Pi, t 2 [a, b], a, b 2 < where Bi(t) : Blending functions Pi, i = 1, · · · , L : Control Points Blending functions Weight the influence of each constraint (e.g. control point) on the curve created. B1 B2 B3 t Wish list for blending functions • Easy to compute and stable • Sum to unity for every t in [a,b] • Support over portion of [a,b] • Interpolate certain control points • Sufficient smoothness P (t) = LX k=0 BLk (t)Pk where BLk (t) = ✓ L K ◆ (1� t)L�ktk ✓ L K ◆ = L! k!(L� k)! , for L � k A�ne combination: LX k=0 BLk (t) = 1, for all t Example: Bezier curves • Sum up to unity • Smooth • Interpolate first and last • Expensive to compute for large L • No local control Rendering parametric curves Transform into primitives we know how to handle • Line segments Single cubic segment C(t): t in [0,1] C(0) C(1) Converting to Lines Straightforward Uniform subdivision Evaluate C(t) at n points spaced by dt=1/(n-1) C(0), C(dt), C(2dt),…,C((n-1)*dt=1) Draw as lines C(0) C(1) C(0) C(dt) C(2dt) Converting to Lines Straightforward Uniform subdivision Evaluate C(t) at n points spaced by dt=1/(n-1) C(0), C(dt), C(2dt),…,C((n-1)*dt=1) Here n = 2 and dt = 1/(n-1) = 1 C(0*dt = 0) C((n-1)*dt=1) Two points Converting to Lines Straightforward Uniform subdivision Evaluate C(t) at n points spaced by dt=1/(n-1) C(0), C(dt), C(2dt),…,C((n-1)*dt=1) Here n = 3 and dt = 1/(n-1)= 0.5 C(0*dt = 0) C((n-1)*dt=1) Three points C(1*dt = 0.5) Converting to Lines Straightforward Uniform subdivision Evaluate C(t) at n points spaced by dt=1/(n-1) C(0), C(dt), C(2dt),…,C((n-1)*dt=1) Here n = 4 and dt = 1/(n-1) = 0.33 Four points C(0) C((n-1)*dt=1) C(0.66) C(0.33) Converting to Lines Straightforward Uniform subdivision Evaluate C(t) at n points spaced by dt=1/(n-1) C(0), C(dt), C(2dt),…,C((n-1)*dt=1) All together for comparison Many points Three points Four points C(0) C((n-1)*dt=1) C(dt) C(2dt) Two points How many evaluation points are enough for Bezier curves? Not too few Not too many Ok, how many? Subdivision schemes Uniform Non-uniform • Adaptive Error metrics that define how much information we are losing An example... Adaptive Subdivision of Bezier Curves de Casteljau subdivision One Bezier curve becomes 2 flatter curves Original points 1,2,3,4 à Midpoints 12, 23, 34 Midpoints of midpoints: 123, 234 Midpoints of midpoints of midpoints, 1234 Remember: tweening for t = 0.5 Can chose any t we want Ok, how many times do we subdivide? Images courtesy of Maxim Shemanarev Error metrics Examples: Point distance Tangent distance Images courtesy of Maxim Shemanarev