Knot Insertion

Evaluation

Subdivision

Degree Raising

 


Knot Insertion

Next, we would like to illustrate a few computational algorithms. The first algorithm is about inserting additional knots. Adding new knots to the original knot sequence will make the original one a proper sub-sequence of the new one. The process of adding new knots without changing any of the original knots is called knot refinement. There are many applications 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 changing the shape of this curve. Inserting an additional knot here, we effectively replaced 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 degree 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 because these two segments still have knots and control vertices overlapped so that they may not be processed independently. One way to completely 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 completely separated curves, each has its own control polygon and knot sequence, and they do not overlap.

Bézier Conversion

The next application of knot insertion is to convert a B-spline to a Bézier. Consider a cubic B-spline curve with uniform knots. 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. Therefore, 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 can repeat the process for the other end. This process effectively created six more control vertices, such that the outermost ones are no longer 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 knots, 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 time. Similar operations can be applied to convert a curve with open end condition to a Bézier curve. Consider a cubic B-spline curve with open end condition, but it has interior knots. It is not a Bézier because 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 intervals 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. Why would one convert a B-spline to Bézier? We don't have to worry about the knot sequence for Bézier curves because the only knots they can have are the K multiple knots at the ends, where K is the order. Furthermore, it is relatively easier to code the algorithms for Bézier curves and the algorithms are in general more efficient.

Evaluation

a Bézier Curves

For instance, the next computational algorithm is about calculating a point on a Bézier curve based on a very simple corner cutting scheme. Here is a Bézier curve. To obtain the point on the curve corresponding 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, connect them and finally its mid-point is the point on the curve. As we said a moment ago, this scheme works for every point on the curve.

a B-Splines

The cutting corner scheme has a more sophisticated version for B-spline curves. It is a numerically stable algorithm for evaluating B-splines. The algorithm was based on a recurrence relation of spline basis functions. It was also revealed as a geometric construction scheme for B-splines. Consider a cubic B-spline curve with uniform knots. Let focus on the control polygon and its parameter t. Instead of cutting 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 control polygon corresponding to the first ratio. Second point on the second edge with the second ratio. And so on. This will produce a secondary polyline. We now apply a different set of ratios. Find points on this 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 everywhere 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.

Subdivision

More interesting is the fact that a set of vertices generated during this process can be collected for subdividing a Bézier curve. One can subdivide anywhere on the Bézier this way. The result is exactly the same as if we inserted multiple knots to subdivide. If we apply subdivision recursively, we effectively break the original curve into pieces, depending on how deep into the recursive level we want. Level l has two subpieces. Level 2 has four sub-pieces. Level 3 has eight sub-pieces. And so on. Let us repeat the process. We can see that the control polygon converges to the curve rather rapidly.

Degree Raising

a Bézier Curves

Raising the degree of a Bézier curve will also make its control polygon 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 identical to the original, cubic Bézier curve. Here is how it works. We divide 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 have (K+1) vertices that form a new control polygon for a quartic Bézier that produces exactly the same point set as the original cubic Bézier curve. Similarly, from this control polygon for the quartic Bézier, we pick up vertices to create a new control polygon for a quintic Bézier that defines exactly the same point set as the original quartic Bézier curve. If we keep raising its degree, we can see that the control polygon converges to the curve.

a B-Splines

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 have just raised its degree to quartic. It is interesting to see that when we raise its degree by one, the continuity at each knot position is also increased by one. To compensate that side effect, the algorithm also increases the multiplicity of each knot by one. Similarly, when 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.