ITR: Making 3D Visibility Practical

University Of Illinois At Urbana-Champaign, Urbana IL

Investigators

Abstract

Efficient reasoning about three-dimensional visibility is a challenging problem in many research areas and applications, including computer graphics (radiosity, virtual reality walkthroughs), robotics (sensor-based navigation, visual surveillance), computer vision (recognition, model building), architecture, urban planning, and visualization in computational biology. Visibility issues have been considered for four decades in these areas however, most early work has focused on computing visibility from a single viewpoint, while modern techniques require more global visibility information. Global visibility describes the visibility relationships etween objects that are more complex than points: visibility from a volumetric region of space, limits of umbra and penumbra with respect to an extended light source, mutual visibility etween pairs of objects, and loci of structural changes of visibility. Although great strides have een made in understanding visibility through the introduction of visibility space partitions and the visibility complex, they have so far had little impact on applications. This is due to several reasons: 1) worst-case theoretical complexity bounds are discouraging 2) there are many degenerate cases that must be handled, making it difficult to make robust implementations 3) equivalences in visibility lead to a four-dimensional cell decomposition, which is difficult to visualize 4) cells can be extremely complicated (some include holes). This work will make 3D visibility computations practical by approaching the problem in two parallel, integrated tracks. One involves the investigation of several key issues that will make 3D visibility algorithms more attractive and practical in applications: 1) performing practical complexity analysis that captures the expected performance for models that are typically used in applications, as opposed to theoretical worst-case ounds derived from uncommon pathological cases 2) rather than taking a generic "precompute and return everything" approach, we would like the amount of precomputation, information stored in data structures, and extraction algorithms to be nicely tailored to the number of queries and the type of information arises in a particular application 3) traversal through the space of visibility rays will be facilitated through the development of decomposition algorithms based on critical events and Morse theory 4) we will develop techniques for reasoning about the evolving shadow space (set of points not visible), which is required for many problems that involve moving viewpoints. The second track involves the development of a 3D visibility library ased on robust visibility primitives. We expect to make an immediate impact on applications by making this library available for free to other researchers. The library will serve both as a helpful visualization and evaluation tool during the development of the research, and as a way to stimulate other interest and applications of 3D visibility after the work is completed. This effort, combined with the understanding gained from investigating the key visibility issues, is expected to make a broad impact on a wide array of applications that depend on efficient processing of visibility information.