Computer Graphics
Computer Graphics
Spline
A long flexible strips of metal used by
draftspersons to lay out the surfaces of
airplanes, cars and ships
Ducks weights attached to the splines
were used to pull the spline in different
directions
The metal splines had second order
continuity
Computer Graphics
Lecture 14
Curves and Surfaces II
10/10/2008
Computer Graphics
Lecture 5
Computer Graphics
B-splines
B-Splines (for basis splines)
B-Splines
Another polynomial curve for modelling curves and
surfaces
Consists of curve segments whose polynomial
coefficients only depend on just a few control points
The curve does not necessarily pass through
the control points
The shape is constrained to the convex hull
made by the control points
Uniform cubic b-splines has C2 continuity
Local control
Higher than Hermite or Bezier curves
Segments joined at knots
10/10/2008
Lecture 5
Computer Graphics
Computer Graphics
Basis Functions
Generating a curve
X(t)
12
Opposite we see an
example of a shape to be
generated.
knots
We can create a long curve using many knots and B-splines
The unweighted cubic B-Splines have been shown for clarity.
These are weighted and summed to produce a curve of the
desired shape
10/10/2008
Lecture 5
Here we see the curve
again with the weighted
B-Splines which
generated the required
shape.
t
10/10/2008
Lecture 5
Computer Graphics
Computer Graphics
The basic one:
Uniform Cubic B-Splines
Cubic B-Splines
Cubic B-splines with uniform knot-vector is the
most commonly used form of B-splines
X (t ) = t T MQ (i)
ti t t i +1
for
Q (i) = ( xi 3 , ... , xi )
where :
1 3 3
1 3 6 3
M=
3
6 3 0
4
1
1
1
0
,
0
0
t T = (t ti )3 , (t ti ) 2 , t ti ,1
10/10/2008
t : knots,
i
3i
The unweighted spline set of 10 control points, 10 splines,
14 knots, and but only 7 intervals.
You can see why t3 to t4 is the first interval with a curve
since it is the first with all four B-Spline functions.
t9 to t10 is the last interval
Lecture 5
Computer Graphics
Lecture 5
t
m+1
Computer Graphics
Cubic Uniform B-Spline
2D example
Domain of the function
6
3
10/10/2008
For each i 4 , there is a knot between Qi-1 and Qi at t = ti.
Initial points at t3 and tm+1 are also knots. The following
illustrates an example with control points set P0 P9:
Order k, Degree k-1
Control points Pi (i=0,,m)
Knots : tj, (j=0,, k + m)
The domain of the function tk-1 t tm+1
Below, k = 4, m = 9,
Knot.
Control point.
domain, t3 t t10
t
m+1
10/10/2008
Computer Graphics
Lecture 5
10
Computer Graphics
Uniform Non-rational B-Splines.
Uniform Non-rational B-Splines.
First segment Q3 is defined by point P0 through P3 over the
range t3 = 0 to t4 = 1. So m at least 3 for cubic spline.
Second segment Q4 is defined by point P1 through P4 over
the range t4 = 1 to t5 = 2.
Knot.
Control point.
P1
Knot.
Control point.
P1
P3
P3
P4
Q3
P0
10/10/2008
Q4
P2
P2
Lecture 5
11
10/10/2008
Lecture 5
12
Computer Graphics
B-Spline :
A more general definition
A Bspline of order k is a parametric curve composed of a linear
combination of basis B-splines Bi,n
Pi (i=0,,m) the control points
Knots: tj, j=0,, k + m
The B-splines can be defined by
10/10/2008
p(t ) = Pi Bi , n (t )
Computer Graphics
The shape of the basis functions
Bi,2 : linear basis functions
Order = 2, degree = 1
C0 continuous
i =0
1, t t < t i +1
Bi ,1 (t ) = i
0, otherwise
t ti
t t
Bi , k (t ) =
Bi ,k 1 (t ) + i + k
Bi +1, k 1 (t )
ti + k Lecture
ti + k 1 ti
1 ti5
13
Computer Graphics
Lecture 5
14
[Link]
10/10/2008
Computer Graphics
The shape of the basis functions
The shape of the basis functions
Bi,3 : Quadratic basis functions
Bi,4 : Cubic basis functions
Order = 3, degree = 2
Order = 4, degree = 3
C1 continuous
C2 continuous
10/10/2008
Lecture 5
15
[Link]
Computer Graphics
Lecture 5
16
[Link]
10/10/2008
Computer Graphics
Uniform / non-uniform B-splines
Uniform B-splines
The knots are equidistant / non-equidistant
The previous examples were uniform B-splines
t0 , t1 , t2 ,..., t m were equidistant, same interval
Parametric interval between knots does not
have to be equal.
Non-uniform B-splines.
Blending functions no longer the same for each interval.
Advantages
Continuity at selected control points can be reduced to
C1 or lower allows us to interpolate a control point
without side-effects.
Can interpolate start and end points.
Easy to add extra knots and control points.
Good for shape modelling !
Non-uniform B-splines
10/10/2008
Computer Graphics
Computer Graphics
Controlling the shape through
control points
Controlling the shape of the curves
P0
Can control the shape through
P2
Control points
Overlapping the control points to make it pass
through a specific point
First knot shown with 4
control points, and their
convex hull.
Knots
Changing the continuity by increasing the
multiplicity at some knot (non-uniform bsplines)
P1
10/10/2008
Computer Graphics
Lecture 5
20
Computer Graphics
Controlling the shape through
control points
P0
P3
Repeated control point.
P0
P2
P4
P3
First two curve segments
shown with their respective
convex hulls.
First two curve segments
shown with their respective
convex hulls.
The curve is forced to lie on
the line that joins the 2
convex hulls.
Centre Knot must lie in the
intersection of the 2 convex
hulls.
P3
P1
10/10/2008
P1=P2
Lecture 5
21
Computer Graphics
10/10/2008
P4
Lecture 5
22
Computer Graphics
Triple control point.
P0
P4
Controlling the shape through knots
First two curve segments
shown with their respective
convex hulls.
Both convex hulls collapse
to straight lines all the
curve must lie on these lines.
P1=P2=P3
Smoothness increases with order k in Bi,k
Quadratic, k = 3, gives up to C1 continuity.
Cubic, k = 4 gives up to C2 continuity.
However, we can lower continuity order too with Multiple
Knots, ie. ti = ti+1= ti+2 = Knots are coincident and so
now we have non-uniform knot intervals.
A knot with multiplicity p is continuous to the
(k-1-p)th derivative.
A knot with multiplicity k has no continuity at all, i.e. the
curve is broken at that knot. B (t ) = 1, t t < t
i
i +1
i ,1
10/10/2008
Lecture 5
23
10/10/2008
0, otherwise
t ti
t t
Bi , k 1 (t ) + i + k
Bi +1, k 1 (t ) 24
LectureB5i , k (t ) =
t i + k 1 ti
ti + k 1 ti
Computer Graphics
Computer Graphics
B-Splines at multiple knots
Cubic B-spline
Multiplicities are indicated
Computer Graphics
Knot multiplicity
Double knot at 5,
knot ={0,1,2,3,4,5,5,6,7,8,9,10,11,12}
6 segments, continuity = 1
Computer Graphics
Knot multiplicity
Consider the uniform cubic (n=4) B-spline curve,
t={0,1, ,13}, m=9 , n=4, 7 segments
Computer Graphics
Knot multiplicity
Triple knot at 5
knot={0,1,2,3,4
,5,5,5,6,7,8,9,10
,11}
5 segments
Computer Graphics
Knot multiplicity
Quadruple knot at 5
4 segments
Summary of B-Splines.
Functions that can be manipulated by a series of control
points with C2 continuity and local control.
Dont pass through their control points, although can be
forced.
Uniform
Knots are equally spaced in t.
Non-Uniform
Knots are unequally spaced
Allows addition of extra control points anywhere in the set.
10/10/2008
Lecture 5
30
Computer Graphics
Computer Graphics
2nd Practical
Summary cont.
Do not have to worry about the continuity at
the join points
For interactive curve modelling
B-Splines are very good.
Use OpenGL to draw the teapot
You must extend your code in the first
assignment
Bonus marks for making it nice
Bump mapping
Texture mapping
Or whatever
Deadline : 10th December
10/10/2008
Lecture 5
31
Computer Graphics
Reading for this lecture
Foley at al., Chapter 11, sections 11.2.3,
11.2.4, 11.2.9, 11.2.10, 11.3 and 11.5.
Introductory text, Chapter 9, sections 9.2.4,
9.2.5, 9.2.7, 9.2.8 and 9.3.
.
10/10/2008
Lecture 5
33