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.
In computer graphics, the visibility map refers to a planar subdivision that encodes the visibility information, i.e., which points are mutually @cite_5 . Two points are mutually visible if the straight line segment connecting these points does not intersect with any obstacle. If a scene is represented using a planar straight-line graph, a horizontal (vertical) visibility map is obtained by drawing a horizontal (vertical) straight line @math through each vertex @math of that graph until @math intersects an edge @math of the graph or extends to infinity. The edge @math is horizontally (vertically) visible from @math . A large body of works @cite_3 @cite_18 @cite_7 @cite_19 @cite_22 construct such visibility maps efficiently.
@cite_18 @cite_22 @cite_7 @cite_3 @cite_19 @cite_5
1835934527 2035823949 2094665988 1988245788 1596411313
This paper describes a robust, hardware-accelerated algorithm to compute an approximate visibility map, which describes the visible scene from a particular viewpoint. The user can control the degree of approximation, choosing more accuracy at the cost of increased execution time. The algorithm exploits item buffer hardware to coarsely determine visibility, which is later refined. The paper also describes a conceptually simple algorithm to compute a subset of the discontinuity mesh using the visibility map. We introduce a novel representation for visibility in three dimensions and describe an efficient algorithm to construct it. The data structure is a spherical map that consists of a doubly-connected edge list embedded on the surface of a sphere. Each face of the spherical map is labeled with the polygon visible in the corresponding cone. We demonstrate that the algorithm is efficient and robust by presenting the statistics of its time and space requirements for handling several classes of input. We present an algorithm that efficiently constructs a visibility map for a given view of a polygonal scene. The view is represented by a BSP tree and the visibility map is obtained by postprocessing of that tree. The scene is organised in a kD-tree that is used to perform an approximate occlusion sweep. The occlusion sweep is interleaved with hierarchical visibility tests what results in expected output sensitive behaviour of the algorithm. We evaluate our implementation of the method on several scenes and demonstrate its application to discontinuity meshing. 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. Algorithms and Theory of Computation Handbook, Second Edition provides an up-to-date compendium of fundamental computer science topics and techniques. It also illustrates how the topics and techniques come together to deliver efficient solutions to important practical problems. New to the Second EditionAlong with updating and revising many of the existing chapters, this second edition contains more than 20 new chapters. This edition now covers external memory, parameterized, self-stabilizing, and pricing algorithms as well as the theories of algorithmic coding, privacy and anonymity, databases, computational games, and communication networks. It also discusses computational topology, computational number theory, natural language processing, and grid computing and explores applications in intensity-modulated radiation therapy, voting, DNA research, systems biology, and financial derivatives. This best-selling handbook continues to help computer professionals and engineers find significant information on various algorithmic topics. The expert contributors clearly define the terminology, present basic results and techniques, and offer a number of current references to the in-depth literature. They also provide a glimpse of the major research issues concerning the relevant topics.