Abstract
This paper presents new techniques for speeding up the ray tracing algorithm. By projecting the scene to be ray traced onto perpendicular planes, subdividing the planes with a 2D subdivision scheme (regular grid- and quadtree structures) and traversing these projected scenes throughout the subdividing structures, the methods reported upon exploit the advantages of the 3D voxel- and octree- based acceleration techniques, without having their disadvantage of large memory consumption. Utilizing bounding rectangular extents around the primitives constituting the scene, the techniques covered can be beneficial for many different types of primitives to be ray traced. Results given for the regular grid- and quadtree-based techniques illustrate that even on single-processor machines it becomes viable to ray trace complex scenes --we tested the algorithms presented with scenes containing up to one million primitives-- in an affordable time (i.e. in the order of minutes rather than hours or days).