geometric algorithms, computer-aided design, rational curves and surfaces, tessellation, flatness, derivative bounds, step size, projection distance
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.
BYU ScholarsArchive Citation
Sederberg, Thomas W. and Zheng, Jianmin, "Estimating Tessellation Parameter Intervals for Rational Curves and Surfaces" (2000). Faculty Publications. 1111.
Physical and Mathematical Sciences
© 2000 ACM. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in the ACM Transactions on Graphics, 19, 1, (2000), http://doi.acm.org/10.1145/343002.343034.
Copyright Use Information