Development of a fast ray-tracing algorithm

Tan, Ming (1995) Development of a fast ray-tracing algorithm. Masters thesis, Memorial University of Newfoundland.

[English] PDF - Accepted Version Available under License - The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. Download (10MB)

Abstract

Ray-tracing is one of the best rendering techniques for the creation of high quality and realistic computer synthesized 2D images of the 3D world. It has been successfully applied in many graphics packages. However, while the technique renders realistic images by simulating the behavior of real light rays, a ray tracing algorithm also imposes a heavy computational burden. As the most time-consuming part of a ray tracer is to check the intersections between imaginary rays and object surfaces, an efficient algorithm is crucial. Thus, many efficient acceleration algorithms have been invented. Bounding volume techniques are the most popular among the many acceleration techniques for ray/object intersection testing. Although a few bounding volumes have been proposed, spheres are the simplest. In this thesis, two ray/sphere intersection algorithms, i.e. the traditional algebraic solution and the efficient geometric solution, are first discussed. Then, a new ray tracing algorithm is introduced that features a fast ray/sphere interaction. By homogeneously transforming the definition world to a ray, the new algorithm simplifies the expensive 3-D surface intersection problem into a 2-D enclosure check. The speed-up of image rendering is derived theoretically in the thesis from complexity analysis and is also demonstrated in an implementation with experimental results.

Actions (login required)

View Item