Robust Visibility Skeleton

Florent Duguet and George Drettakis



Visibility is a central problem in computer graphics. Visibility computations are necessary in every step of image synthesis. For lighting simulations, we need visibility for shadow computations. For rendering, occlusion culling is based on  visibility tools. Visibility is also important in various other domains such as robotics.

We present techniques for visibility computations for polygonal scenes. We currently only consider polygonal scenes. This is not too restrictive since alternative representations can be meshed, and polygons are widely used.

Previous Work

The work done here is mainly based on The Visibility Skeleton of Frédo Durand et al. The Visibility Skeleton is a data structure encoding the visibility events of a 3D polygonal scene. The Skeleton as presented in 97 was the starting point of our work.


We present a generalization of the visibility skeleton, in order to overcome the limitations of the first method. We develop a framework to hande  degeneracies. With this formal approach, we can compute visibility events using linear algebra.


For the Masters thesis in French click here. An english paper will soon be available.


Here are some results of the application using the library. Detailed results are available in the thesis.

click on images to enlarge.