Data Structures and Algorithms for Navigation in Highly Polygon-Populated Scenes

We present the visibility octree, a new data structure to accelerate 3D navigation through very complex scenes. Our approach employs a conservative visibility technique to compute an approximation to the visibility space partition. This approximation is computed and stored hierarchically at a preprocessing stage. We believe its main contribution to be its ability to provide an effective control over the coarseness of the approximation. A preliminary test with some randomly generated indoor scenes seems to show that the visibility octree will perform well on densely occluded scenes. 1 Introduction This work is focused on the interactive navigation through polygonal models. There is a wide range of applications nowadays whose requirements surpass even the most expensive high-end graphics workstations. To name a few, ship design, architectural design and virtual reality applications have hundreds of thousands or even millions of polygons. Current graphics hardware is not able to cope wit..