Intersection Algorithms Based On Geometric Intervals

<p>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.</p>

Name thesis:degree_name

MS

Grantor dc:publisher

Brigham Young University - Provo

Author dc:creator

• North, Nicholas Stewart

• Bézier curve
• Bézier surface
• curve intersection
• ray surface intersection
• Bézier clipping
• implicitization
• interval arithmetic
• geometric interval
• Computer Sciences

Language dc:language

English

Repository record dc:identifier

https://scholarsarchive.byu.edu/etd/1207

OAI identifier oai:identifier

oai:scholarsarchive.byu.edu:etd-2206