BibTeX
@inproceedings{SemwalKvarnstrom-gi97, title = {Directed safe zones and the dual extent algorithms for efficient grid traversal during ray tracing}, author = {Sudhanshu Kumar Semwal and Hakan Kvarnstrom}, booktitle = {Proceedings of the Graphics Interface 1997 Conference, May 21-23, 1997, Kelowna, BC, Canada}, year = {1997}, month = {May}, pages = {76--87}, url = {http://graphicsinterface.org/wp-content/uploads/gi1997-9.pdf} }Supplementary Media
Abstract
Ray tracing is inherently a very time consuming process. There have been a variety of techniques developed for reducing the rendering time. While using space subdivision techniques, the object space is divided into a set of disjoint voxels; and only those objects are checked for intersection with the ray which pierce the voxels along the path of the ray. As the grid size is increased in an attempt to reduce the number of objects encountered along the path of the ray, more empty voxels are encountered along the path. In other words, considerable rendering time could be invested in moving from one empty voxel to another empty voxel. The proximity clouds method uses distance transformations to identify the empty regions, and combined with the 3DDA grid traversal (SEADS) technique, has been shown to be the fastest grid traversal technique available today. In this paper, we present two further improvements to the proximity clouds method -- called the Directed Safe Zones (DSZ) and the Dual Extents (DEs). We have implemented four methods for our comparison: SEADS (3DDA), proximity clouds, Directed Safe Zones (DSZs), and Dual Extents (DEs). We present both the theoretical and statistical analysis of the four methods. We show that DSZs and DEs surpass the performance of both the proximity clouds and SEADS implementations. The DSZs method em usually outperforms the Dual Extents implementation, except when the topology of the scene favors the Dual Extent method.