Recursive subdivision without the convex hull property (Q1094860)

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. In this paper it is shown that if a recursive subdivision algorithm exists for a given curve or surface type, then uniform convergence of the subdivision polygons to the original curve or surface is guaranteed if the blending functions are continuous, form a partition of unity, and are linearly independent. The proof proposed in this paper does not make use of the convex hull property, and therefore the convex hull property is not necessary for convergence of a recursive subdivision algorithm. Moreover, it is noted that since recursive subdivision algorithms always exist for curves and surfaces generated by polynomial bases, uniform convergence is guaranteed for polynomial curves and surfaces if the basis functions sum to one. It is also shown that termination tests based on flatness and intersection algorithms based on recursive subdivision do not require the convex hull property. Examples are given of polynomial curves to which the theorems apply.