2 - Subdivision schemes in geometric modelling

Summary

Subdivision schemes are efficient computational methods for the design and representation of 3D surfaces of arbitrary topology. They are also a tool for the generation of refinable functions, which are instrumental in the construction of wavelets. This paper presents various flavours of subdivision, seasoned by the personal viewpoint of the authors, which is mainly concerned with geometric modelling. Our starting point is the general setting of scalar multivariate nonstationary schemes on regular grids. We also briefly review other classes of schemes, such as schemes on general nets, matrix schemes, non-uniform schemes and nonlinear schemes. Different representations of subdivision schemes, and several tools for the analysis of convergence, smoothness and approximation order are discussed, followed by explanatory examples.

Introduction

The first work on a subdivision scheme was by de Rahm (1956). He showed that the scheme he presented produces limit functions with a first derivative everywhere and a second derivative nowhere. The pioneering work of Chaikin (1974) introduced subdivision as a practical algorithm for curve design. His algorithm served as a starting point for extensions into subdivision algorithms generating any spline functions. The importance of subdivision to applications in computer-aided geometric design became clear with the generalizations of the tensor product spline rules to control nets of arbitrary topology. This important step has been introduced in two papers, by Doo and Sabin (1978) and by Catmull and Clark (1978). The surfaces generated by their subdivision schemes are no longer restricted to representing bivariate functions, and they can easily represent surfaces of arbitrary topology.