Hybrid Scene Structuring with Application to Ray Tracing
Dieter W. Fellner, Gordon Müller · 1999
The handling of highly complex 3D scenes is one of the major challenges in computer graphics. Several data structures were proposed in the past to address this problem. Many of these schemes are only suited for specific spatial distribution of objects in 3D space, making it difficult for a developer to select the appropriate data structure for the scene and/or application. Further, the selection of initialization parameters is typically a non-trivial task. Using a ray casting environment this paper presents an algorithm that automatically builds a hybrid data structure combining bounding volume hierarchies and uniform spatial subdivisions for a given scene. Our data structure is built by first creating a cost function based volume hierarchy, subsequently detecting regions of uniformly distributed objects using the scene hierarchy, and, as the last step, locally integrating uniform spatial subdivisions into the scene tree. We will show that the data structure can be built with low costs, both with regard to space and to run-time. Finally, we present rendering times that demonstrate the usefulness of the new approach compared to standard techniques by comparing run-time efficiency. The memory requirements of the new data structure are, on average, linear in the number of scene objects. Further applications of the hybrid approach are also proposed.