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.
Given a collection of surfaces representing boundaries of obstacles, considers visibility problem as determining the regions of space or the surfaces of obstacles that are visible to an observer @cite_0 @cite_20 . They model visibility as a binary notion and find the light and dark regions of a space for a point light source. Disregarding reflection, diffraction and interference of light, they assume light rays are diminished upon contact with a surface of an obstacle.
@cite_0 @cite_20
2073815206 2126572568 2129404737 1970123385
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. The authors consider the problem faced by a newborn that must explore and learn an unknown room with obstacles in it. They seek algorithms that achieve a bounded ratio of the worst-case distance traversed in order to see all visible points of the environment (thus creating a map), divided by the optimum distance needed to verify the map. The situation is complicated by the fact that the latter offline problem (optimally verifying a map) is NP-hard and thus must be solved approximately. Although the authors show that there is no such competitive algorithm for general obstacle courses, they give a competitive algorithm for the case of a polygonal room with a bounded number of obstacles in it. > This paper proposes a novel algorithm for multiview stereopsis that outputs a dense set of small rectangular patches covering the surfaces visible in the images. Stereopsis is implemented as a match, expand, and filter procedure, starting from a sparse set of matched keypoints, and repeatedly expanding these before using visibility constraints to filter away false matches. The keys to the performance of the proposed algorithm are effective techniques for enforcing local photometric consistency and global visibility constraints. Simple but effective methods are also proposed to turn the resulting patch model into a mesh which can be further refined by an algorithm that enforces both photometric consistency and regularization constraints. The proposed approach automatically detects and discards outliers and obstacles and does not require any initialization in the form of a visual hull, a bounding box, or valid depth ranges. We have tested our algorithm on various data sets including objects with fine surface details, deep concavities, and thin structures, outdoor scenes observed from a restricted set of viewpoints, and "crowded" scenes where moving obstacles appear in front of a static structure of interest. A quantitative evaluation on the Middlebury benchmark [1] shows that the proposed method outperforms all others submitted so far for four out of the six data sets. Constructing the visible and invisible regions of an observer due to the presence of obstacles in the environment has played a central role in many applications. It can also be a first step. In this paper, we adopt a visibility algorithm that can produce a variety of general information to handle the optimization of visibility information. Through the use of level set tools, gradient flow, finite differencing, and solvers for ordinary differential equations, we introduce a set of distinct algorithms for several model problems involving the optimization of visibility information.