Recursive subdivision without the convex hull property

Recursive subdivision is a standard technique in computer aided geometric design for intersecting and rendering curves and surfaces. The convergence of recursive subdivision is critical for its effective use. Bézier and B-spline curves and surfaces have recursive subdivision algorithms that are known to converge. We show more generally that if a recursive subdivision algorithm exists for a given curve or surface type, then convergence is guaranteed if the blending functions are continuous, form a partition of unity, and are linearly independent. Thus, convergence of recursive subdivision does not depend on the convex hull property. We also show that even in the absence of the convex hull property, it is possible to define termination tests based on the flatness of control polygons, and to construct intersection algorithms based on recursive subdivision. Examples are given of polynomial curves to which our theorems apply.