Subdivision schemes for physical problems
Doctor of Philosophy
Geometric modeling is concerned with the description and manipulation of geometric shapes. Recursive subdivision is a particularly simple and efficient way of representing shapes as the limit of a sequence of recursive refinement operations, applied to a simple initial shape. The properties of this limit shape depend on the subdivision rules that are used to build the next finer shape at any step in the recursion. In this thesis, I present a methodology for constructing subdivision rules. Starting from a variational energy functional, this method constructs subdivision rules in a systematic manner. The shapes modeled by these schemes are guaranteed to minimize the given energy functional. Applications of this method are as simple as the modeling of a bending piece of metal, and as far reaching as the efficient animation of a realistic fluid flow. This thesis consists of four major parts. Part one, the introduction, contains just one chapter. There, I presents subdivision as an efficient way for describing functions. The second part, focussing on exact subdivision schemes for physical problems, consists of chapters two, three and four. In chapter two, I will establish a natural link between the modeling of physical problems and subdivision by working through a concrete example. The result is a dethodology for building a subdivision scheme that captures the physical modeling problem. In chapter three, this methodology is generalized to a large class of curves and surfaces defined over regular grids. Chapter four finally links more traditional definitions of subdivision schemes, based on convolution, with this approach. Part three, consisting of chapters five and six, extends subdivision for physical problems to the case where approximation is necessary to obtain locally supported schemes. Chapter five presents the various approaches that can be taken to find local approximations of globally supported subdivision schemes. In chapter six, these methods are used to capture several interesting physical modeling problems for curve networks and for various classes of surfaces on irregular domains. Part four, consisting of chapter seven, develops analytic basis functions for the subdivision schemes derived using the methodology of this thesis. To summarize, this thesis provides a link between multi-resolution modeling and the modeling of physical problems. A methodology for building subdivision schemes that model given physical principles is derived, analyzed, applied to various interesting modeling problems.