A Multiresolution Framework for Variational Subdivision

Subdivision is a powerful paradigm for the generation of curves and surfaces. It is easy to implement, computationally efficient, and useful in a variety 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 minimize a fairness functional (variational design). In the context of subdivision, fairing leads to special schemes requiring the solution of a banded linear system at every subdivision step. We present several examples of such schemes including one that reproduces non-uniform interpolating cubic splines. Expressing the construction in terms of certain elementary operationswe are able to embed variational subdivision in the lifting framework, a powerful technique to construct wavelet filter banks given a subdivision scheme. This allows us to extend the traditional lifting scheme for FIR filters to a certain class of IIR filters. Consequently we show how to build variationally optimal curves and associated, stable wavelets in a straightforward fashion. The algorithms to perform the corresponding decomposition and reconstruction transformations are easy to implement and efficient enough for interactive applications.