Fast approximate quantitative visibility for complex scenes

Ray tracing and Monte-Carlo based global illumination, as well as radiosity and other finite-element based global illumination methods, all require repeated evaluation of quantitative visibility queries, such as (i) what is the average visibility between a point (a differential area element) and a finite area or volume; or (ii) what is the average visibility between two finite areas or volumes. In this paper, we present a new data structure and an algorithm for rapidly evaluating such queries in complex scenes. The proposed approach utilizes a novel image-based discretization of the space of bounded rays in the scene, constructed in a preprocessing stage. This data structure makes it possible to quickly compute approximate answers to visibility queries. Because visibility queries are computed using a discretization of the space, the execution time is effectively decoupled from the number of geometric primitives in the scene. A potential hazard with the proposed approach is that it might require large amounts of memory, if the data structures are designed in a naive fashion. We discuss ways for representing the discretization bl a compact manner, while still allowing rapid query evaluation. Preliminary results demonstrate the effectiveness of the proposed approach.