Visibility computation is crucial for computer graphics from its very
beginning. The first visibility algorithms aimed to determine visible
lines or surfaces in a synthesized image of a 3D scene. Nowadays there
is a plethora of visibility algorithms for various applications. The
thesis proposes a taxonomy of visibility problems based on the
dimension of the problem-relevant line set, i.e. set of lines forming
the domain of the visibility problem. The taxonomy helps to identify
relationships between visibility problems from various application
areas by grouping together problems of similar complexity. The thesis
presents a general concept of a visibility algorithm suitable for
solution of several classes of visibility problems. The concept is
based on three main ideas: an approximate occlusion sweep, an
occlusion tree, and hierarchical visibility tests. The central idea of
the concept is the occlusion tree representing an aggregated occlusion
map by means of a hierarchical subdivision in line space. The thesis
presents several applications of the concept. The major focus is
placed on visibility culling algorithms for real-time rendering
acceleration. First, we describe an algorithm for real-time visibility
culling. The algorithm is used to accelerate rendering of large
densely occluded scenes. It improves previous results by efficiently
performing occluder fusion in real-time. We propose several techniques
exploiting temporal and spatial coherence applicable to most existing
hierarchical visibility culling methods. Second, we propose an
algorithm for computing visibility maps in polygonal scenes. The
algorithm provides a comprehensive description of the topology of the
given view of the scene. We discuss an application of the algorithm to
discontinuity meshing. Third, the proposed concept is applied to
computation of from-region visibility in 2D scenes. We present and
evaluate an exact analytic algorithm for computing a potentially
visible set for a polygonal region in the plane. Fourth, we propose
two algorithms for computing from-region visibility in 2.5D
scenes. Both algorithms are targeted at visibility preprocessing for
walkthroughs of outdoor urban scenes. The methods are compared with
another recent technique. Finally, we describe an exact analytic
algorithm for computing from-region visibility in 3D scenes suitable
for various applications. The algorithm uses Pluecker coordinates and
maintains a hierarchical subdivision of 5D space. We discuss its
application to visibility preprocessing, occluder synthesis and
discontinuity meshing.