A multiresolution framework for variational subdivision

Subdivision is a powerful paradigm for the generation of curves and surface s. It is easy to implement, computationally efficient, and useful in a vari ety of applications because of its intimate connection with multiresolution analysis. An important task in computer graphics and geometric modeling is the construction of curves that interpolate a given set of points and mini mize a fairness functional (variational design). In the context of subdivis ion, fairing leads to special schemes requiring the solution of a banded li near system at every subdivision step. We present several examples of such schemes including one that reproduces nonuniform interpolating cubic spline s. Expressing the construction in terms of certain elementary operations we are able to embed variational subdivision in the lifting framework, a powe rful technique to construct wavelet filter banks given a subdivision scheme . This allows us to extend the traditional lifting scheme for FIR filters t o a certain class of IIR filters. Consequently, we show how to build variat ionally optimal curves and associated, stable wavelets in a straightforward fashion. The algorithms to perform the corresponding decomposition and rec onstruction transformations are easy to implement and efficient enough for interactive applications.