Hierarchical techniques for visibility computations.

The thesis proposes a taxonomy of visibility (vis.) problems based on the dimension of the problem-relevant line set, i.e. set of lines forming the domain of the vis. problem. The taxonomy helps to identify relationships between vis. problems from various application areas by grouping together problems of similar complexity. The thesis presents a general concept of a vis. algorithm (alg.) suitable for solution of several classes of vis. problems. The concept is based on 3 main ideas: an approximate occlusion sweep, an occlusion tree and hierarchical vis. 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 vis. culling alg. for real-time rendering acceleration. We describe an alg. for real-time vis. culling. The alg. 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 vis. culling methods and an alg. for computing vis. maps in polygonal scenes. The alg. provides a comprehensive description of the topology of the given view of the scene. We discuss an application of the alg. to discontinuity meshing. The proposed concept is applied to comput. of from-region vis. in 2D scenes. We present and evaluate an exact analytic alg. for comput. a potentially visible set for a polygonal region in the plane. We propose 2 alg. for comput. from-region vis. in 21/2D scenes. Both alg. are targeted at vis. preprocessing for walkthroughs of outdoor urban scenes. The methods are compared with another recent technique. We describe an exact analytic alg. for comput. from-region vis. in 3D scenes suitable for various applications. The alg. uses Plucker coordinates and maintains a hierarchical subdivision of 5D space. We discuss its application to vis. preprocessing, occluder synthesis and discontinuity meshing.Available from STL Prague, CZ / NTK - National Technical LibrarySIGLECZCzech Republi