Weak Refinement for Uniform Subdivision

Authors: 

Steven Kilthau
Torsten Möller
Thomas C. Shermer
F. David Fracchia

A subdivision surface is a surface that, starting with an initial polygon mesh, can be repeatedly refined to generate finer and finer meshes. In the limit, this refinement produces a surface with known properties (e.g. smoothness), but in practice only a few refinements are necessary to produce a surface which closely approximates the limit surface (i.e. subdivision converges quickly).

In recent years, subdivision surfaces have come to the forefront of geometric modeling and design. They are currently in use in many production houses, and are slowly becoming commonplace in the computer gaming industry. Furthermore, subdivision surfaces are used extensively in the solution of partial differential equations using the finite element method. However, practitioners wishing to use subdivision surfaces are faced with choosing a scheme to suit their needs from the relatively small set of existing subdivision schemes.
In this thesis, we create a technique whereby subdivision schemes with arbitrary properties can be easily generated. Our focus is on the creation of uniform piecewise subdivision schemes of varying extent and smoothness. To facilitate the creation of new subdivision schemes, we derive a new mathematical relationship called the weak refinement relationship. This new relationship drastically reduces the number of open parameters in the equation system describing a given uniform piecewise subdivision scheme, and hence enables the system to be solved quickly.

After deriving the weak refinement relationship, we apply it to the creation of a new solution method which we use to generate several new subdivision schemes with piecewise-polynomial subdivision functions. To simplify the study of our new schemes, we define the notion of a it family of subdivision schemes and categorize all of our results accordingly. All of the subdivision functions of our new schemes are then analyzed according to their frequency spectra, which helps to give an understanding of their spatial domain properties. For the two new schemes which our analysis suggests are the most important, we generate their two dimensional versions via tensor products, and generalize them to arbitrary topologies. In the regular case, our first generalized subdivision scheme produces C1 continuous surfaces, while our second generalized subdivision scheme produces C2 continuous surfaces.