An Adaptive Subdivision Method with Crack Prevention for Rendering Beta-Spline Objects.

Adaptive subdivision is a method of creating polygonal approximations to spline surfaces. An adaptive subdivision algorithm takes an 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. This paper describes the Beta-spline curve and surface technique and derive the equations governing the splitting of Beta-spline curves and surfaces. It presents 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 occuring between approximating polyhedra. The tolerance controlling the splitting process may itself be adaptive, so that as an object moves farther away the tolerance is automatically increased.