Recent advances in 3D modeling provide us with real 3D datasets to answer queries, such as "What is the best position for a new billboard?" and "Which hotel room has the best view?" in the presence of obstacles. These applications require measuring and differentiating the visibility of an object (target) from different viewpoints in a dataspace, e.g., a billboard may be seen from two viewpoints but is readable only from the viewpoint closer to the target. In this paper, we formulate the above problem of quantifying the visibility of (from) a target object from (of) the surrounding area with a visibility color map (VCM). A VCM is essentially defined as a surface color map of the space, where each viewpoint of the space is assigned a color value that denotes the visibility measure of the target from that viewpoint. Measuring the visibility of a target even from a single viewpoint is an expensive operation, as we need to consider factors such as distance, angle, and obstacles between the viewpoint and the target. Hence, a straightforward approach to construct the VCM that requires visibility computation for every viewpoint of the surrounding space of the target, is prohibitively expensive in terms of both I Os and computation, especially for a real dataset comprising of thousands of obstacles. We propose an efficient approach to compute the VCM based on a key property of the human vision that eliminates the necessity of computing the visibility for a large number of viewpoints of the space. To further reduce the computational overhead, we propose two approximations; namely, minimum bounding rectangle and tangential approaches with guaranteed error bounds. Our extensive experiments demonstrate the effectiveness and efficiency of our solutions to construct the VCM for real 2D and 3D datasets.
The notion of visibility is actively studied in different contexts: computer graphics and visualization @cite_5 @cite_22 and spatial databases @cite_15 @cite_12 @cite_13 . Most of these techniques consider visibility as a binary notion, i.e., a point is either visible or invisible from another point.
@cite_22 @cite_5 @cite_15 @cite_13 @cite_12
1988245788 2073815206 2122710056 1497599070
Visibility computation was crucial for computer graphics from its very beginning. The first visibility algorithms in computer graphics aimed to determine visible surfaces in a synthesized image of a three-dimensional scene. Nowadays there are many different visibility algorithms for various visibility problems. We propose a new taxonomy of visibility problems that is based on a classification according to the problem domain. We provide a broad overview of visibility problems and algorithms in computer graphics grouped by the proposed taxonomy. We survey visible surface algorithms, visibility culling algorithms, visibility algorithms for shadow computation, global illumination, point-based and image-based rendering, and global visibility computations. Finally, we discuss common concepts of visibility algorithm design and several criteria for the classification of visibility algorithms. We investigate the problem of determining visible regions given a set of (moving) obstacles and a (moving) vantage point. Our approach to this problem is through an implicit framework, where the obstacles are represented by a level set function. The visibility problem is formally formulated as a boundary value problem (BVP) of a first order partial differential equation. It is based on the continuation of values along the given ray field. We propose a one-pass, multi-level algorithm for the construction of the solution on a grid. Furthermore, we study the dynamics of shadow boundaries on the surfaces of the obstacles when the vantage point moves along a given trajectory. In all of these situations, topological changes such as merging and breaking occur in the regions of interest. These are automatically handled by the level set framework proposed here. Finally, we obtain additional useful information through simple operations in the level set framework. One of the more powerful impressions created by vision is that of a coherent, richly detailed world where everything is present simultaneously. Indeed, this impression is so compelling that we tend to ascribe these properties not only to the external world, but to our internal representations as well. But results from several recent experiments argue against this latter ascription. For example, changes in images of real-world scenes often go unnoticed when made during a saccade, flicker, blink, or movie cut. This “change blindness” provides strong evidence against the idea that our brains contain a picture-like representation of the scene that is everywhere detailed and coherent. How then do we represent a scene? It is argued here that focused attention provides spatiotemporal coherence for the stable representation of one object at a time. It is then argued that the allocation of attention can be co-ordinated to create a “virtual representation”. In such a scheme, a stable object representation is formed... A number of psychophysical studies concerning the detection, localization and recognition of objects in the visual field have suggested a two-stage theory of human visual perception. The first stage is the “preattentive” mode, in which simple features are processed rapidly and in parallel over the entire visual field. In the second, “attentive” mode, a specialized processing focus, usually called the focus of attention, is directed to particular locations in the visual field. The analysis of complex forms and the recognition of objects are associated with this second stage.1 The computational justification for such a hypothesis comes from the realization that while it is possible to imagine specific algorithms performing tasks such as shape analysis and recognition at specific locations, it is difficult to imagine these algorithms operating in parallel over the whole visual scene, since such an approach will quickly lead to a combinatorial explosion in terms of required computational resources.2 This is essentially the major critique of Minsky and Papert to a universal application of perceptrons in visual perception.3 Taken together, these empirical and theoretical studies suggest that beyond a certain preprocessing stage, the analysis of visual information proceeds in a sequence of operations, each one applied to a selected location (or locations).