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.