Technical Reports

The ICICS/CS Reading Room

UBC CS TR-94-36 Summary

Chebyshev Polynomials for Boxing and Intersections of Parametric Curves and, January 31, 1994 Alain Fournier and John Buchanan, 17 pages

Surfaces Computer Graphics and Computer Aided Design. Ray-tracing is a versatile and popular rendering technique. There is therefore a strong incentive in developing fast, accurate and reliable algorithms to intersect rays and parametric curves and surfaces. We propose and demonstrate the use of Chebyshev basis functions to speed up the computation of the intersections between rays and parametric curves or surfaces. The properties of Chebyshev polynomials result in the computation of better and tighter enclosing boxes. For surfaces they provide a better termination criterion to decide on the limits of subdivision, and allow the use of bilinear surfaces for the computation of the intersection when needed. The efficiency of the techniques used depends on the relative magnitude of the coefficients of the Chebyshev basis functions. We show from a statistical analysis of the characteristics of several thousands surfaces of different origin that these techniques will result most of the time in significant improvement in speed and accuracy over other boxing and subdivision technqiues.

If you have any questions or comments regarding this page please send mail to