A new class of algorithms for the processing of parametrically defined curves is presented. All the algorithms are based on the 'divide and conquer ' (subdivision) paradigm. An important feature which marks out this class of algorithms from earlier subdivision-based algorithms is that the curve is characterized algebraically and not geometrically. Curve shape properties needed for the processing tasks are derived from the algebraic form of the curve. As long as the necessary properties can be derived, any mathematical from of the curve may be used. In particular this paper considers polynominal curves represented in the rational quadratic, cubic or rational cubic form. 5hope properties such as linearity and Euclidean bounds ere derived and algorithms for drawing and curve-curve intersection are described.
parametric curves, curve splitting, algebraic forms
Recently increasing attention has been given to the modelling of geometric shapes within a computer. Curves are needed in a variety of computer graphics applications ranging from graphic arts to CADCAM. Two curve forms predominate: the conic section (planar) and the parametric vector-valued cubic polynomial. The rational or twisted cubic curve offers the possibility of combining two curve types in a single mathematical form I . A number of methods have been proposed for the processing of curves. Typical processing tasks are rendering (or drawing) and detecting intersections, if any, between two curves. Many of the methods are based on the 'divide and conquer' paradigm, that is, they use the curve subdivision technique. Unfortunately there is no single computationally efficient technique that can be used for the processing of all three types of curves.
Catmull 2 proposed a binary subdivision technique for the processing of surfaces, particularly for rendering surfaces with hidden regions removed, on a frame buffer display. This technique can also be used for the rendering of curves. Subdivision is carried out up to the required resolution, usually the device screen resolution (raster unit). The process of subdivision is speeded up by the use of a correction term which in conjunction with the end values can be used to calculate the mid value. The correction term is faster to evaluate than the function itself.