Adapting search structures to scene characteristics for ray tracing
Kalpathi R. Subramanian · 1991
Ray tracing is an important and popular rendering technique in computer graphics for synthesizing photorealistic images. However, ray tracing, if not carefully done, can be a computationally expensive technique. A great deal of research has focused on discovering efficient ways to perform ray tracing. An important approach to controlling the computational expense has been the use of geometric search structures to prevent needless ray-object intersection calculations. Search structures in current use take advantage of scene characteristics in a variety of ways to enhance ray tracing performance. Constraints in their construction can cause inefficiencies and consequent degradation in performance. Performance comparisons between search structures using timing benchmarks have shown that no single existing search structure performs best on all scene models. A knowledge of search structure performance prior to rendering is therefore important to selecting a search structure for a given scene. A thorough understanding of the ways in which search structures succeed in enhancing performance on various types of scenes can also be expected to lead to improvements in existing techniques. We present new results in adapting search structures to scene characteristics for improving the performance of ray tracing. A cost model is developed for evaluating search structures currently being used in ray tracing. The model has been successfully used to terminate search structure construction, thus making it unnecessary to set termination parameters in advance. The model has also been used with limited success to compare the performance of different search structures for a given scene. A detailed experimental study of some of the important properties of search structures has been performed. This has resulted in a new adaptive search structure that is based on k-d trees, a multi-dimensional binary search structure which outperforms existing methods. Its high performance is primarily due to the fact that it combines the advantages of such structures based on space partitioning and those based on bounding volumes. The greater flexibility of this search structure allows it to terminate automatically at a point where further subdivision would result in no additional benefits. Finally, this search structure has been used to render volume models from scientific applications such as medical imaging and molecular modeling. Its advantages over traditional volume rendering techniques have been demonstrated.