Analysis of non-uniform subdivision schemes

Subdivision is an indispensable algorithmic part of computer animation and computer games. It provides fast and ecient algorithms for generation of animation characters with fast motion response. The animation characters consist of smooth surface patches as well as sharp features. The main goal of this project is to address a challenging mathematical task of designing and analysis of subdivision algorithms that generate surfaces that posses simultaneously desired topological, geometrical and smoothness properties. 1

This project explored how to use a simple algorithm, called subdivision schemes, to create complex yet smooth structures needed in areas such as computer graphics, simulation, or signal processing. Subdivision schemes are a type of interpolation algorithm that generates new points by averaging nearby points. In this way, a small set of initial points can be repeatedly refined into curves or surfaces that become smoother and smoother. A new and particularly challenging aspect concerns anisotropic schemes, which interpolate at different speeds in different directions. This is important because many applications in nature and technology are direction-dependent. In this project, methods were developed for the first time that make it possible to determine the smoothness of such anisotropic schemes exactly. A central tool for this purpose is the Joint Spectral Radius (JSR). Behind this complicated-sounding term lies a quantity that describes how certain computational steps, more precisely products of matrices, develop over the long run. Put simply: it measures whether a process becomes "calm" or "chaotic" over time. This quantity directly determines how smooth the curves and surfaces produced by subdivision will be. Until now, it was often impossible to compute the JSR exactly. We combined existing algorithms (invariant polytope methods, tree methods) and thus obtained a hybrid algorithm that works in more cases than earlier approaches and is both faster and more robust. In particular, we were able to use it to prove the so-called Finiteness Conjecture for all pairs of 33 binary matrices - a long-standing open problem in mathematics. The results are not only of theoretical importance. They also have direct practical impact: in computer graphics, complex shapes can be computed faster and more precisely; in signal processing, the behavior of filters can be predicted more reliably; in engineering, stability analyses can be carried out with greater confidence. In addition, the new methods open up ways to construct extremely smooth functions with a small "footprint," which can serve as building blocks for high-quality image rendering or for specialized mathematical tools such as wavelets. Beyond that, practical programming patterns for parallel CPU/GPU programming were developed, as well as testing methods for hard-to-maintain code, in order to make the implementation of such mathematical algorithms easier.