A Quadtree Approach to Subdivision and Triangulation of Bezier Patches

One of the approaches to computer display of a parametric surface is to subdivide the surface adaptively in parametric space and triangulate the resulting subdivision so that the surface is represented by a network of triangles. The conventional rendering techniques can thus be employed for the individual triangles. In this paper, the method of adaptively subdividing a bicubic Bezier patch is introduced with the quadtree data structure used to represent the hierarchical subdivision mechanism. An algorithm for triangulation of the resulting subdivision is then presented. The algorithm prevents the potential cracks caused by adaptive subdivision.