Optimización de algoritmos geométricos mediante el uso de recubrimientos simpliciales

Resumen

El modelado de sólidos es el conjunto de herramientas y técnicas destinadas a la representación y manipulación de objetos virtuales, Es una herramienta básica en el diseño y fabricación asistidos por ordenador, además de ser muy útil en la creación de objetos virtuales destinados a simulación, realidad virtual, videojuegos, etc. Todos los objetos que se definen en estos ámbitos tienen su base en actividades de modelado, ya sean manuales o procedurales. Dentro del modelado de sólidos existe una gran cantidad de métodos de representación de objetos y de algoritmos para procesarlos. La conversión entre esquemas de representación de objetos es uno de los problemas básicos, así como la adaptación de los algoritmos que se aplican sobre los mismos. De este conjunto de herramientas, los algoritmos geométricos tienen una gran importancia, ya que sirven como base para otros más complejos y de mayor nivel. Los algoritmos geométricos utilizados en modelado de sólidos cubren un amplio espectro de aplicación. Entre los más básicos destacan los métodos de inclusión e intersección de entidades geométricas, trazado de curvas, muestreo de superficies, etc. Hay otros problemas de mayor complejidad cuya resolución implica la utilización de las técnicas básicas. Uno de estos problemas es la evaluación de operaciones booleanas entre sólidos, que constituyen una herramienta básica en la construcción de objetos. En este trabajo se presentan diversos algoritmos basados en la teoría de recubrimientos simpliciales, que permite representar objetos gráficos basándose en la descomposición de los mismos en símplices. Esta forma de representación ofrece un nuevo enfoque para la resolución de múltiples problemas. Aunque en trabajos anteriores se habían presentado soluciones a dichos problemas, realmente no se habían desarrollado implementaciones eficientes ni versiones optimizadas. En esta tesis se proponen soluciones avanzadas e implementaciones op