This section contains a brief description of my diploma thesis.

Introduction

The topic of my diploma thesis are subdivision algorithms. These are local operators that may be applied to meshes in order to smooth them. The interesting thing about subdivision algorithms is that they are conceptually very simple, but their analysis is rather complicated.

In my thesis, I present (and use) a framework for the smoothness analysis of subdivision algorithms. The framework has been developed by Jörg Peters and Ulrich Reif, who also performed the first analysis of the most common subdivision schemes.

Here is a nice example figure demonstrating subdivision algorithms. The figure was rendered by Blender using input data from psalm (see below).

psalm

In order to understand and visualize the algorithms I was examining, I developed psalm, which is a mesh compiler for some common 3D mesh formats (namely, OBJ, OFF, and PLY). psalm is short for pretty subdivision algorithms on meshes.

psalm is released under a BSD licence. See the source files for more information.

Abstract & thesis

In computer graphics, subdivision algorithms are common tools for smoothing down irregularly shaped meshes. Of special interest, due to their simple formulations, are algorithms that generalize B-spline subdivision. Their conceptual simplicity is in stark contrast to the complexity of analysing their results. A complete formal examination of smoothness properties for subdivision schemes was only recently performed by Jörg Peters and Ulrich Reif.

This thesis presents a precise and detailed introduction to the analysis of subdivision algorithms. For this purpose, first of all, the necessary background in B-spline theory is established. Building on this, two of the most common subdivision algorithms, the Doo-Sabin and the Catmull-Clark scheme, are motivated. Their treatment is followed by an in-depth description of methods for analysing smoothness properties of subdivision schemes, as developed by Peters and Reif. Afterwards, these methods are applied to the two aforementioned algorithms, thereby establishing smoothness for both algorithms in their original form. Last, in order to demonstrate the effects of choosing unsuitable weights, a number of degenerate weights, which produce irregular shapes in almost all cases, are derived for both schemes—these have hitherto not been published.

If you are interested, you may download the complete thesis as a PDF. Do not be deterred by the few German words I had to include to satisfy the formal requirements for a diploma thesis in Germany. If you are interested in the LaTeX source code for my thesis, please drop me a line.

Resources