Generalized Lane–Riesenfeld algorithms

The Lane–Riesenfeld algorithm for generating uniform B-splines provides a prototype for subdivision algorithms that use a refine and smooth factorization to gain arbitrarily high smoothness through efficient local rules. In this paper we generalize this algorithm by maintaining the key property that the same operator is used to define the refine and each smoothing stage. For the Lane–Riesenfeld algorithm this operator samples a linear polynomial, and therefore the algorithm preserves only linear polynomials in the functional setting, and straight lines in the geometric setting. We present two new families of schemes that extend this set of invariants: one which preserves cubic polynomials, and another which preserves circles. For both generalizations, as for the Lane–Riesenfeld algorithm, a greater number of smoothing stages gives smoother curves, and only local rules are required for an implementation.

► New subdivision algorithms that use a refine stage and repeated local smoothing.
► The new algorithms extend the class of shapes that are invariant under subdivision.
► We show two examples: the first preserving cubic polynomials, and the second circles.
► Like the Lane–Riesenfeld algorithm, using more smoothing stages gives smoother curves.