Visibilidad de Superficies 3D Mediante Barrido de Segmentos

Abstract

Este documento y el codigo C++ adjunto son presentados como requisito del Trabajo Fin de Master para la titulacion de Master en Matematica Computacional, de los estudios oficiales de la Universidad Politecnica de Madrid. Introduce un algoritmo de visibilidad de superficies tridimensionales, mediante la aplicacion por cada linea de imagen de aun otro algoritmo que determina en dos dimensiones la envolvente superior de un conjunto de segmentos mediante un barrido de izquierda a derecha. Se sugiere el barrido Bentley-Ottmann , cuya cota superior asintotica es, con una entrada de n segmentos con k intersecciones, O((n)k )∗log (n)) [1]. Otros algoritmos pueden ser utilizados para determinar la envolvente superior, con su correspondiente conjunto de ventajas e inconvenientes. Utilizando Bentley-Ottmann, para una visualizacion consistente en l lineas de precision de imagen, con n poligonos activos y k intersecciones de poligonos (donde n y k son valores medios por lineas) el algoritmo presentado consigue resolver el problema de la visibilidad de superficies con una cota superior asintotica de O(l∗)n(k )∗log(n)) .