Synthetic Curves –
B-Spline Curves
Convex Hull Property
• Most desirable feature for any curve defined by a
polygon
• Property guarantees that incremental changes in
control point positions produce intuitive geometric
changes (main merit)
• A curve is said to have the convex hull property if it
lies entirely within the convex hull defined by the
polygon vertices
• Convex hull:
–In a plane: closed polygon
Convex Hull
–In 3D: polyhedron
–Upper bound on the size of the curve
2
Splines History
• Draftsman use ‘ducks’ and
strips of wood (splines) to
draw curves
• Wood splines have second- A Duck (weight)
order continuity
• And pass through the
control points
Ducks trace out curve
3
B-Spline Curves
• Piecewise curve creation is still a nuisance
– Tedious
– All points affect one another
– Preserves continuity conditions
• It would be convenient to have local control
– More intuitive how to specify shape of the curve
– Moving a point changes only a small part of the curve
– Can also reduce computation
• Degree of curve independent of number of control
points
Demo:http://www.engin.umd.umich.edu/CIS/course.des
/cis577/projects/BSP/welcome.html
4
B-Splines
•Really a family of related splines:
1. Uniform or nonuniform – how are the knots spaced
in u
2. Rational or nonrational – is it the ratio of two
polynomials or not
•These curves have the ability to interpolate or
approximate a set of given data points
•Interpolation useful in displaying design or engg
results such as stress or displacement distribution
•Segments are approximating
•Segments are C2 continuous
•Most common type of spline used 5
Find the Spline
6
Hidden Splines in Games
• Curved surfaces are an obvious use of splines
in games
• Spline curves have been long used in graphics,
including games – but not necessarily for direct
display
• A common use of spline curves is interpolation
for animation – cameras and other objects may
follow spline curve paths between key frames
7
B-Spline
• How it is like the Bézier Curve?
– Approximates control points
– Convex Hull Property
• How it differs?
– Ability to add control points without increasing the
degree of the curve, i.e., Degree of curve
independent of number of control points
– Local control over spline shape
• Local control achieved by defining blending functions
over subintervals of the total range of u
8
B-Spline
• More complex than Bézier
• Proper and powerful generalization of Bézier curves
9
B-Splines
• It’d be convenient to have local control
▪ More intuitive how to specify shape of the curve
▪ Moving a point changes only a small part of the
curve
▪ Can also reduce computation
• Local control through blending functions
• Can accommodate larger number of control points
without increasing the degree of curve
10
B-Spline Curves
• Separates the degree of resulting curve from the
number of the given control points
• Four control points:
– Always produce Cubic Bézier curve
– Can generate a linear, quadratic, or cubic B-spline
curve
• Flexibility: the blending functions are chosen
with an additional degree of freedom which
does not exist in Bernstein polynomials
11
B-Spline Curves
• B-spline curve defined by n+1 control points Pi:
n
p(u ) = pi N i ,k (u ) , 0 u u m ax
i =0
Ni,k (u) : B-spline functions
(B-spline basis)
12
Open B-Spline Curves
B-Spline Curve Definition
B-spline functions
n
p(u ) = pi N i ,k (u ) , 0 u u m ax
i =0
• Control points (or deBoor points or Cox-deBoor points):
form the vertices of the control or deBoor polygon
• Parameter k controls the degree (k-1) of the resulting
B-spline curve or
• k: Order of the blending function
• k is usually independent of the number of control
points
• Each control point affects only k curve segments
• i: index
• Maximum limit of the parameter u is no longer unity
14
Properties of B-Spline Curve
n
• Partition of unity: N
i =0
i ,k (u ) = 1
– Relationship between the curve and its defining control
points is invariant under affine transformations
• Positivity: Ni,k (u) 0
– Curve segment lies completely within the convex hull of Pi
• Local support: Ni,k (u) = 0 if u ui ,ui +k +1
– Each segment of curve is influenced by only k control points
(OR each control point affects only k curve segments)
• Continuity: N i ,k (u )is (k-2) times (as degree is (k-1)) continuously
differentiable 15
B-Spline Curve
• Recursively defined B-Spline basis function
u −ui ui + k − u
N (u ) = ui+k −1 −ui N (u ) + ui+k −ui+1 N (u )
i,k i , k −1 i +1, k −1
K controls
degree of 1 ui u ui +1
the curve N (u ) = Choose 0/0 = 0
i ,1
0 otherwise
• Ni,1: constant for k = 1: unit step function
• A general value of k produces a polynomial in u of
degree (k-1)
• ui: parametric knots or knot values
• Values of ui depends on whether the B-spline curve is
an open (non-periodic) or closed (periodic) curve
16
Open (Non-periodic) B-Spline
• If the limits of u for any Ni,1 are equal, the u range
becomes one point
• For calculating Ni,ks: i+kbasis ≯ n+kcurve (Constant for a
curve)
• ui: Parametric knots or knot values – control degree of
curve
• ui: Relate the parametric variable u to the pi control
points
• A sequence of non-decreasing integer values of ui:
Knot Vector
17
B-Spline Curve
•For an open (non-periodic) B-spline
0 j k Where 0 ≤ j ≤ n+k
Range of j
u j = j − k +1 k j n
n − k + 2 jn Range of u :
0 ≤ u ≤ n-k+2
•0 ≤ j ≤ n+k: (n+k+1) knots are needed to create a (k-1)
degree curve defined by (n+1) control points
•k is limited by number of control points: n-k+2 > 0
•These knots are evenly spaced over the range of u with
unit separation (△u = 1) between non-coincident knots
•Multiple (coincident) knots for certain values of u may
exist 18
B-Spline Blending Function
Blending Functions for n =
5, k =1 → Step Functions Blending Functions for n = 5,
k =2 → Ramp Functions 19
B-Spline Blending Function
Blending Functions for n = 5, k =3 → Quadratic Functions
20
B-Spline Curve
•Degree controlled by k
Range of u is 0 (lower limit) ≤ u ≤ n-k+2 (upper bound)
Implication: there is a limit on k that is determined by
the number of the given control points
•Limit: n-k+2 > 0
or (n+1) – (k-1) > 0
Degree of curve
Number of
control points
•Interpretation: a minimum of 2, 3, and 4 control points
are required to define a linear, quadratic, and cubic B-
spline curve respectively
21
B-Spline Characteristics
• Ability to add control points without increasing the
degree of the curve
• All polynomials are of order k and degree (k-1)
22
B-Spline Characteristics
• Local control achieved by changing the position of a
control point(s) or
• Using multiple control points by placing several
points at the same location OR
• By choosing a different degree (k-1)
4 curve segments
Changing
surrounding P3 changes one control
point affects
only k curve
segments
23
B-Spline Characteristics
• An open B-spline curve
passes through the 1st and last control points P0 and
Pn+1
and
is tangent to the 1st (P1-P0) and last (Pn+1-Pn) segments
of the control polygon – similar to Bézier curve
24
B-Spline Characteristics
• Increasing the degree of the curve tightens it
In general, the less the degree, the closer the curve gets
to the control points
25
B-Spline Characteristics
• A second degree curve is always tangent to the
midpoints of all the ‘internal’ polygon segments
This is not the case for other degrees
26
B-Spline Characteristics
• If k = n + 1 (number of control points), then the
resulting B-spline curve becomes a Bézier curve
• In this case:
• Range of u: 0 to 1
27
B-Spline Characteristics
•Multiple control points induce regions of high
curvature of a B-spline curve
•Useful for creating sharp corners in the curve
•The effect is equivalent to curve being pulled more
towards a control point by increasing its multiplicity
Curve is pulled more towards a control
point by increasing its multiplicity
28
B-Spline Characteristics
• Increasing the degree of the curve makes it more
difficult to control and to calculate accurately
• A cubic B-spline is sufficient for a large number of
applications
• The points ui where poly pieces join together are called
breakpoints, or knots
• The order of a spline is the highest degree of its poly
pieces plus 1
29
