Towards interactive ray tracing in two- and three-dimensions
One of the main goals of computer graphics is to generate photorealistic images at high frame rates. This thesis presents techniques for generating ray traced images in a 2D environment at interactive rates, and closely approximating ray traced images in a 3D environment at near interactive rates. In the two dimensional case, our technique is based on the visibility complex data structure [48]. The visibility complex is a data structure in a dual space whose faces correspond to contiguous sets of rays in the primary space that share the same forward and backward views. Sweeping a viewing ray around a viewpoint corresponds to walking along a trajectory on the visibility complex. Producing a ray traced image is equivalent to walking along and maintaining a set of trajectories. Generating ray traced images with the visibility complex is very efficient since the coherence among the rays is effectively captured. We have developed a novel algorithm for the construction of the visibility complex which is based on the randomized incremental paradigm. The history of the incremental construction yields an efficient ray query data structure, which is required for spawning new reflected and refracted rays. The performance of our rendering algorithm is analyzed and the rendering speed of our algorithm is experimentally compared with the rendering speed of a conventional ray tracer. 
For the three dimensional case, we have developed a technique called extended environment mapping which is based on the environment mapping algorithm but produces much more accurate images. An extended environment map records the depth information of the scene along with the radiance information stored as an environment map. This technique is based on the observation that capturing the radiance along the wrong direction from the right point produces much more accurate rendering than capturing the radiance along the right direction from the wrong point, which is how an ordinary environment map generates images. The accuracy of our technique is demonstrated by presenting difference images computed between ray traced images and the images rendered using extended environment mapping. The extended environment map produces images up to an order of magnitude faster than a conventional ray tracer.