Analysis of Algorithms Generalizing B-Spline Subdivision (Q4389151)

The authors address the question when the indefinite refining of control polyhedra of B-splines yield a smooth surface. The algorithms considered are supposed to be affine invariant, linear and stationary; that means that the matrix \({\mathbf B}_{n+1}\) formed by the control points added in step \(n+1\) are given by \({\mathbf B}_{n+1}= A{\mathbf B}_n\). All convergence properties depend on the spare matrix \(A\). The largest eigenvalue of \(A\) is \(1\) and the important case is that in which the next largest eigenvalue is double. A main tool is the characteristic map, introduced earlier by the second author [Comput. Aided Geom. Des. 12, No. 2, 153-174 (1995; Zbl 0872.65007)] that is an annular domain patched together by images of an \(L\)-shaped domain defined by the generalized eigenvectors of the double eigenvalue. If that domain is schlicht, the second author had proved that the limit surface is regular for almost all choices of \({\mathbf B}_0\). Here it is proved that if it is not schlicht, the limit surface is not regular at all points. A subdivision algorithm is called symmetric if it is invariant in a shift and an inversion of the labelling of the vectors of \({\mathbf B}_n\). It is shown that a condition for regularity is that the double subdominant eigenvalue also be an eigenvalue of the finite Fourier transform \(\widehat A\) of \(A\) and on \(\widehat A^{n-1}\). A further investigation of the characteristic map then leads to rules that show that the Doo-Sabin algorithm of symmetric weights \((\alpha^j_n, j= 1,\dots,n)\) leads almost always to smooth limit surfaces if \(\lambda= \alpha^1_n= \alpha_n^{n-1}\) satisfies \(1> \lambda> \max(1/4,| \alpha^j_n|, j=2,\dots, n-2)\) and \(128\lambda^2(1- \lambda)- 7\lambda- 2+ 9\lambda\cos(2\pi/n)= 0\). For the Catmull-Clark algorithm, regularity follows if, for \(c= \cos 2\pi k/n\), \(\lambda= [c+ 5+ \sqrt(c+ 1)(c+ 9)]/16\).