Keywords

geometric algorithms, computer-aided design, rational curves and surfaces, tessellation, flatness, derivative bounds, step size, projection distance

Abstract

This paper presents a method for determining a priori a constant parameter interval with which a rational curve or surface can be tessellated such that the deviation of the curve or surface from its piecewise linear approximation is within a specified tolerance. The parameter interval is estimated based on information about the second order derivatives in the homogeneous coordinates, instead of using affine coordinates directly. This new step size can be found with roughly the same amount of computation as the step size presented in [Cheng 1992], though it can be proven to always be larger than Cheng's step size. In fact, numerical experiments show the new step is typically orders of magnitude larger than the step size in [Cheng 1992]. Furthermore, for rational cubic and quartic curves, the new step size is generally twice as large as the step size found by computing bounds on the Bernstein polynomial coefficients of the second derivatives function.

Original Publication Citation

J. Zheng and T. W. Sederberg, "Estimating tessellation parameter intervals for rational curves and surfaces," ACM Transactions on Graphics, 19, 1, 56-77, 2.