Algorithms Seminar Fall 2001

A fundamental step in any rendering algorithm is to determine whether two points are mutually visible. Rendering algorithms are notoriously slow and in fact, they spend a majority of their time on visibility computations. One approach to speeding up rendering is to store global visibility information in a data structure which can then be efficiently queried and the visibility complex has been proposed for this purpose. However, one problem with these data structures which prevents their application in practice is their potentially enormous size; the size of the visibility complex in the worst case is $\Theta(n^4)$, which is prohibitive even for relatively modest scenes.

In this talk, we show that the expected number of visibility events is linear amongst uniformly distributed unit balls which provides a linear bound on the expected size of visibility complex.