The visibility octree: a data structure for 3D navigation

This paper describes the visibility octree, a data structure to accelerate 3D navigation through very complex scenes. A conservative visibility algori thm that computes and hierarchically stores the structure at a preprocessin g stage is presented. The Visibility Octree is used during navigation and i ts main contribution is its ability to provide an effective control over th e coarseness of the visibility approximation. Tests with indoor ship scenes show that the visibility octree performs well on densely occluded environm ents. (C) 1999 Elsevier Science Ltd. All rights reserved.