Next, we would like to illustrate a few computational algorithms.
first algorithm is about inserting additional knots. Adding new knots
to the original knot sequence will make the original one a proper
of the new one. The process of adding new knots without changing any
of the original knots is called knot refinement. There are many
of knot insertion, for example, refining a knot sequence, subdividing
a B-spline curve, and converting a B-spline curve to Bézier, and so
on. Consider a cubic curve with uniform knots. Suppose somehow we
would like to insert an additional knot at this position without
the shape of this curve. Inserting an additional knot here, we
the original four control vertices in black by the newly calculated
five control vertices in white such that we end up with exactly the
same curve except with two segments now.
One motivation to insert such a new knot is to create an extra
of freedom to design the shape of the curve. Another motivation is to
split this curve into two segments. But the splitting is not clean
these two segments still have knots and control vertices overlapped
so that they may not be processed independently. One way to
separate them is to keep adding extra knots until the multiplicity at
this knot position is equal to the order. Now we have a pair of
separated curves, each has its own control polygon and knot sequence,
and they do not overlap.
The next application of knot insertion is to convert a B-spline to
a Bézier. Consider a cubic B-spline curve with uniform
The conversion can be done by adding new knots at both ends of the
evaluation interval, up to multiplicity equal to the order. Let us
add one first. Notice that the basis function is eventually pushed
out of the evaluation interval. Therefore, the vertex is no longer
contributing. Now we add another one. Notice that the
basis function is also pushed out of the evaluation interval.
the vertex is no longer contributing. Now we have added a third
one. Not only the basis function is also pushed out (so that
the vertex is not contributing), we also have another vertex
sitting on top of the first vertex. We are done with one end. We
repeat the process for the other end. This process effectively
six more control vertices, such that the outermost ones are no
contributing to the curve definition. These irrelevant vertices can
be ignored. So can the irrelevant knots. This is exactly the same
as the original curve which was a cubic B-spline with uniform
now it is a genuine cubic Bézier curve.
If we change the sequence of new knots to be inserted, the result
is the same. For example, we could insert knots at one end first.
Then the other end. Or, we could have one inserted at each end at a
Similar operations can be applied to convert a curve with open end
condition to a Bézier curve. Consider a cubic B-spline curve
end condition, but it has interior knots. It is not a Bézier
of these interior knots. But if we add new knots to each interior
knot up to the order, we can convert it into Bézier
segments. In general,
we should have N Bézier segments if we have N evaluation
to begin with. We can break it into segments as long as we know how
to dissect the control polygon and to re-group control vertices.
would one convert a B-spline to Bézier? We don't have to
the knot sequence for Bézier curves because the only knots
have are the K multiple knots at the ends, where K is the order.
it is relatively easier to code the algorithms for Bézier
the algorithms are in general more efficient.
a Bézier Curves
For instance, the next computational algorithm is about
a point on a Bézier curve based on a very simple corner
Here is a Bézier curve. To obtain the point on the curve
to a parameter t, say, t is one half. We find the half way to each
edge of the polygon and connect them to form a secondary polygon.
Repeat the same process, find points half way to the polygon,
them and finally its mid-point is the point on the curve. As we
a moment ago, this scheme works for every point on the curve.
The cutting corner scheme has a more sophisticated version for
curves. It is a numerically stable algorithm for evaluating
The algorithm was based on a recurrence relation of spline basis
It was also revealed as a geometric construction scheme for
Consider a cubic B-spline curve with uniform knots. Let
focus on the control polygon and its parameter t. Instead of
with a fixed ratio all the way through, we start with these three
ratios determined by the order, knot sequence and, of course, the
current parameter t. We find a point on the first edge of the
polygon corresponding to the first ratio. Second point on the
edge with the second ratio. And so on. This will produce a
polyline. We now apply a different set of ratios. Find points on
secondary polyline and produce another secondary polyline. Finally,
we have a last ratio determined on evaluation interval. The point
with this ratio is the point on the curve. This scheme works
on the curve. Furthermore, the points derived from the first step
of this algorithm can be collected for knot insertion. This new set
of control points is exactly the same one if we inserted a new knot
at this position.
More interesting is the fact that a set of vertices generated during
this process can be collected for subdividing a Bézier curve.
subdivide anywhere on the Bézier this way. The result is
same as if we inserted multiple knots to subdivide. If we apply
recursively, we effectively break the original curve into pieces,
on how deep into the recursive level we want. Level l has two
Level 2 has four sub-pieces. Level 3 has eight sub-pieces. And so on.
us repeat the process. We can see that the control polygon converges
to the curve rather rapidly.
a Bézier Curves
Raising the degree of a Bézier curve will also make its
converge to the curve. Let us see how we could raise the degree of
a Bézier curve. Again, let us start with a cubic
Bézier curve. We
would like to create a quartic Bézier curve such that it is
to the original, cubic Bézier curve. Here is how it works.
each edge of the control polygon evenly into K pieces, where K is
the original order. We step along the control polygon and pick up
every (K-l)-st vertex. Along with the original end vertices, we
(K+1) vertices that form a new control polygon for a quartic
that produces exactly the same point set as the original cubic
curve. Similarly, from this control polygon for the quartic
we pick up vertices to create a new control polygon for a quintic
Bézier that defines exactly the same point set as the
Bézier curve. If we keep raising its degree, we can see that
polygon converges to the curve.
There are also algorithms to raise the degree of a B-spline curve.
Here we have a cubic B-spline curve with open end condition. We
just raised its degree to quartic. It is interesting to see that
we raise its degree by one, the continuity at each knot position is
also increased by one. To compensate that side effect, the
also increases the multiplicity of each knot by one. Similarly,
we further raise its degree by one to quartic, knot multiplicity at
each knot position is also increased by one. If we keep raising the
degree of a B-spline curve, its control polygon will also converge
to the curve, just like a Bézier curve does.