Abstract

This thesis introduces new algorithms for solving curve/curve and ray/surface intersections. These algorithms introduce the concept of a geometric interval to extend the technique of Bézier clipping. A geometric interval is used to tightly bound a curve or surface or to contain a point on a curve or surface. Our algorithms retain the desirable characteristics of the Bézier clipping technique such as ease of implementation and the guarantee that all intersections over a given interval will be found. However, these new algorithms generally exhibit cubic convergence, improving on the observed quadratic convergence rate of Bézier clipping. This is achieved without significantly increasing computational complexity at each iteration. Timing tests show that the geometric interval algorithm is generally about 40-60% faster than Bézier clipping for curve/curve intersections. Ray tracing tests suggest that the geometric interval method is faster than the Bézier clipping technique by at least 25% when finding ray/surface intersections.

Degree

College and Department

Physical and Mathematical Sciences; Computer Science

Rights

http://lib.byu.edu/about/copyright/