1.4.3 Algorithms for B-spline curves

• Evaluation and subdivision algorithm: A B-spline curve can be evaluated at a specific parameter value using the de Boor algorithm, which is a generalization of the de Casteljau algorithm introduced in Sect. 1.3.5. The repeated substitution of the recursive definition of the B-spline basis function (1.59) into (1.62) and re-indexing leads to the following de Boor algorithm [175]
  
  
  where
  
  
  with
  
  
  For , the B-spline basis function reduces to for , and coincides with the curve
  
  
  The de Boor algorithm is shown graphically in Fig. 1.12 for a cubic B-spline curve ( ). If we compare Figs. 1.6 and 1.12, it is obvious that the de Boor algorithm is a generalization of the de Casteljau algorithm. The de Boor algorithm also permits the subdivision of the B-spline curve into two segments of the same order. In Fig. 1.12, the two new polygons are and .

• Knot insertion: A knot can be inserted into a B-spline curve without changing the geometry of the curve [34,314]. The new curve is identical to the old one, with a new basis where
  

  becomes (1.74)

  over over

  
  when a new knot is inserted between knots and . The new de Boor points are given by
  
  
  where
  
  
  The above algorithm is also known as Boehm's algorithm [34,35]. A more general (but also more complex) insertion algorithm permitting insertion of several (possibly multiple) knots into a B-spline knot vector, known as the Oslo algorithm, was developed by Cohen et al. [63]. Both algorithms due to Boehm and Cohen et al. have found wide application in CAD/CAM systems since the early 1980's.

  Figure 1.13: Boehm's algorithm

  A B-spline curve is continuous in the interior of a span. Within exact arithmetic, inserting a knot does not change the curve, so it does not change the continuity. However, if any of the control points are moved after knot insertion, the continuity at the knot will become , where is the multiplicity of the knot. Figure 1.13 illustrates a single insertion of a knot at parameter value , resulting in a knot with multiplicity one.

  The B-spline curve can be subdivided into Bézier segments by knot insertion at each internal knot until the multiplicity of each internal knot is equal to .

• Knot removal: Knot removal is the reverse process of knot insertion. It is used for approximation and data reduction [243], and for data reduction in cases the curve or surface does not change neither geometrically nor parametrically [420].

  We briefly review the latter knot removal algorithm developed by Tiller [420]. To demonstrate the process, this example uses a cubic B-spline curve given by control points and knot vector where , and as shown in Fig. 1.14. As the basis functions only guarantee continuity at , the first derivative may or may not be continuous there. Using the continuity condition (1.52), the first derivative will be continuous if and only if
  

  
  Since ,
  
  
  Since and ,
  
  
  

  A similar reasoning yields the fact that a knot can be removed a second time, if and only if the second derivative is continuous, yielding
  

  
  and a knot can be removed a third time if and only if the third derivative is continuous, yielding
  
  
  Note that there are no unknowns in (1.79), one unknown, , in (1.80) and two unknowns, and , in (1.81).

  For the knot removal process, first the right hand side of (1.79) is computed and compared to . If they are equal within a given tolerance, the knot and are removed.

  If the first knot removal is successful, equations (1.80) are solved for and compared:
  

  
  If the two values for are the same, then the knot and control points and are removed and control point is inserted.

  If the second knot removal is successful, the third step is to solve the first and third equations of (1.81) for
  

  
  The two values are then substituted into the second equation of (1.81). If the result is within tolerance of , then the knot is removed and control points , and are replaced by and .

  Figure 1.14: Knot removal (adapted from [420])

  This can be generalized to apply to any number of removals of any particular knot. For the th removal, there will be a system of equations with unknowns. If is even, two values of the final unknown control point will be calculated and compared. If they are within tolerance, the knot removal is successful. If is odd, all new control points are computed and the final two are substituted into the middle equation. If the result is within the tolerance, the knot removal is successful. If the th removal is successful, control points will be replaced by control points.

  Knot removal from a surface is performed on the rows or columns of control points. However, the knot removal is successful only if the knot can be successfully removed from each row or column. Therefore, the result must be checked for each row or column before any control points are removed.