Fast approximate quantitative visibility for complex scenes

Abstract

Ray tracing and Monte-Carlo based global illumi- nation, as well as radiosity and other finite-element based global illumination methods, all require re- peated 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 prepro- cessing stage. Once this data structure has been com- puted, it allows us to quickly compute approximate an- swers to visibility queries. Because visibility queries are computed using a discretization of the space, the execution time is effectively decoupled from the num- ber of geometric primitives in the scene. A potential hazard with the proposed approach is that it might re- quire large amounts of memory, if the data structures are designed in a naive fashion. We discuss ways for substantially compressing the discretization, while still allowing rapid query evaluation. Preliminary results obtained via a partial implementation demonstrate the effectiveness of the proposed approach.