Description
Adaptive subdivision is a method of creating polygonal approximations to spline surfaces. An adaptive subdivision algorithm takes as input a spline surface and a tolerance epsilon, and outputs a piecewise planar approximation to the surface that is guaranteed to differ from the actual surface by a distance no greater than epsilon. These algorithms proceed by recursively "splitting" the surface into smaller subsurfaces, ultimately approximating subsurfaces with planar polyhedra. These algorithms are therefore characterized by the mathematics behind the splitting of a surface, the test that is used to determine when to stop the recursion, and the method by which a subsurface is approximated by polyhedra. Algorithms of this type are currently known for spline techniques such as Bezier and B-splines.
The purpose of this paper is two-fold. First, we describe the Beta-spline curve and surface technique and derive the equations governing the splitting of Beta-spline curves and surfaces. Second, we present a very general adaptive subdivision algorithm that can be used with a variety of surface techniques. It incorporates splitting criteria based on flatness and prevents cracks from occurring between approximating polyhedra. The testing required to determine when surface splitting can stop can be very expensive and methods for reducing these costs are examined. The tolerance controlling the splitting process may itself be adaptive, so that as an object moves farther away the tolerance is automatically increased. These ideas have all been used in the implementation of a surface design and rendering system.