L-system specification of knot-insertion rules for non-uniform B-spline subdivision (Q419478)

The background of this paper is related to a problem from geometric modeling and computer graphics, namely the representation of smooth objects by parametrization with B-spline generated splines. For the knots in parameter space (the vertices of the definition domain for each polynomial spline) a set of control points in object space is associated in order to allow the control of the object's shape locally. By inserting new knots and successively computing new nets of the control points, subdivision schemes are obtained with the aim of drawing smooth objects starting from given nets of control point, given knots and degree for B-spline basis. Hence, subdivision schemes are based on a hierarchy of knot grids in parameter space. If the density provided by successively inserted knots is suitable, the control net converges to the smooth object. Most of the used subdivision schemes are uniform subdivision schemes based on a regular grid of the knots having the new knots inserted at midpoints. A univariate grid hierarchy is regular if all knots are equidistant on each level and irregular otherwise. In this paper, the authors address the non-uniform case with univariate schemes and they propose subdivision schemes for B-spline parametrized curves with irregular but controlled knot intervals. The authors use L-systems to describe the sequences of irregular knots in the context of a wide class of non-uniform subdivision schemes with knots sequences more irregular than uniform or affine bisection, but with a small set of the subdivision process which doesn't depend on the subdivision step and using fixed coefficients that can be computed in advance. Moreover, they give sufficient conditions for an L-system such that the subdivision scheme, based on a non-uniform B-spline of known degree defined on the initial knot grid is uniformly convergent. An implementation of proposed schemes using the \texttt{Sage} software is also presented.