Good-visibility computation using graphics hardware

• Autores: Narcís Madern
• Directores de la Tesis: Narcís Coll (dir. tes.) , J. A. Sellarès i Chiva (dir. tes.)
• Lectura: En la Universitat de Girona ( España ) en 2010
• Idioma: inglés
• Tribunal Calificador de la Tesis: Pere Brunet Crosa (presid.) , Gustavo Patow (secret.) , Manuel Abellanas Oar (voc.) , François Anton Castro (voc.) , Antoni Susín Sánchez (voc.)
• Texto completo no disponible (Saber más ...)
• Resumen

  • In this thesis we design, implement and discuss algorithms that run in the graphics hardware for solving visibility and good-visibility problems. In particular, we compute a discretization of the multi-visibility and good-visibility maps from a set of view objects (points or segments) and a set of obstacles. This computation is carried out for two-dimensional and three-dimensional spaces and even over terrains, which in computational geometry are defined as a 2.5D space.

    First, we thoroughly review the graphics hardware capabilities and how the graphics processing units (known as GPUs) work. We also describe the key concepts and the most important computational geometry tools needed by the computation of multi-visibility and good-visibility maps. Afterwards, we study in a detailed manner the visibility problem and we propose new methods to compute visibility and multi-visibility maps from a set of view objects and a set of obstacles in 2D, 2.5D and 3D using the GPU. Moreover, we present some variations of the visibility to be able to deal with more realistic situations. For instance, we add restrictions in the angle or range to the visibility of viewpoints or we deal with objects emitting other kinds of signals which can cross a certain number of obstacles.

    Once the multi-visibility computation is explained in detail, we use it together with the depth contours concept to present good-visibility in the two-dimensional case. We propose algorithms running in the GPU to obtain a discretization of the 2D good-visibility map from a set of view objects and a set of obstacles. Related to the view objects, we present two alternatives: viewpoints and view segments. In the case of the obstacles we also expose two variants: a set of segment obstacles or an image where the color of a pixel indicates if it contains an obstacle or not. Then we show how the variations in the visibility change the good-visibility map accordingly. The good-visibility map over a terrain is explained as a variation of the 2D version, since we can first compute it in the plane by using a projection and then re-project again the solution to the faces of the terrain.

    We finally propose a method that using the graphics hardware capabilities computes the depth contours in a three-dimensional space in a fast and eficient manner. Afterwards, a set of triangle obstacles is added to the previously mentionned set of (view) points in order to compute a discretization of the good-visibility map in the three-dimensional space.