Intersection Algorithms Based On Geometric Intervals Intersection Algorithms Based On Geometric Intervals

by North, Nicholas Stewart

Abstract (Summary)
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.
Bibliographical Information:


School:Brigham Young University

School Location:USA - Utah

Source Type:Master's Thesis

Keywords:bézier curve surface intersection ray clipping implicitization interval arithmetic geometric


Date of Publication:10/17/2007

© 2009 All Rights Reserved.