Memoria para optar al título de Ingeniero Civil en Computación / El objetivo del presente trabajo de título consiste en el diseño y desarrollo de una aplicación web para la visualización y evaluación de la calidad de mallas de polígonos. Las mallas de polígonos se refieren a un conjunto de polígonos, aristas y vertices que definen alguna forma u objeto. Actualmente existen variados visualizadores de mallas de polígonos, pero la existencia de esta aplicación se justifica en que ninguno de los visualizadores existentes provee capacidades de evaluación según las propiedades geométricas de las mallas (y si las tiene, no es de manera explícita). Con esta característica, la aplicación busca ser de utilidad para investigadores que trabajen con mallas de polígonos, ayudándolos a encontrar defectos o problemas en estas de manera rápida y sencilla. Durante el desarrollo de la aplicación se usan conceptos de interacción humano computador para lograr una aplicación que sea agradable estéticamente, y que sea fácil de aprender utilizar. El enfoque principal del trabajo es el de aprender y aplicar conceptos de Computación Gráfica. Esto incluye entre otras la manipulación de las mallas utilizando matrices, modelos de iluminación y hacer uso de la GPU. En esta línea, se procura también que el código de la aplicación sea lo suficientemente legible para que sirva también como una herramienta educativa, en que los estudiantes o personas interesadas en Computación Gráfica puedan ver en el código y documentación, los conceptos matemáticos y de programación que hay detrás de esta. Como resultado final se obtiene una herramienta que permite visualizar mallas geométricas, las cuales pueden ser inspeccionadas con acciones como mover, rotar y escalar. Para evaluarlas permite seleccionar elementos de las mallas según propiedades geométricas, y permite generar gráficos respecto a estas mismas propiedades. La aplicación posee una interfaz usable, que es útil tanto para investigadores como para estudiantes. También tiene un buen rendimiento, que hace que la aplicación pueda soportar sin problemas mallas de hasta 1.500.000 de polígonos; y actualmente está a la par con otros visualizadores web existentes. Todo lo anterior, sumado a que la aplicación es gratis y de código abierto, permite que cualquier persona pueda utilizarla sin restricción, ya sea para evaluar mallas o para aprender Computación Gráfica. También, cualquier usuario con conocimientos de programación tiene la libertad de adaptarla para sus necesidades específicas. En el futuro cercano, se planea mejorar el rendimiento de la aplicación, y aumentar el número de formas de visualizar y evaluar las mallas geométricas. / Fondecyt N° 1181506

Ingeniero Civil en Computación / La resolución de diversos problemas en ciencia e ingeniería, requiere el apoyo de soluciones y herramientas computacionales que permitan representar, visualizar y modelar sus objetos de estudio, como superficies, terrenos o células. Una forma de representar estos objetos es mediante el uso de mallas geométricas, sobre las cuales se realizan operaciones y simulaciones para modelar los problemas inherentes a cada disciplina. Uno de los principales problemas asociados a trabajar con mallas geométricas, es el tiempo que demoran en ser procesadas. Con el auge de las tarjetas y procesadores gráficos (GPU), se han investigado nuevas técnicas que permitan usar el poder de computo de estas unidades, para desarrollar e implementar estos algoritmos. Actualmente se cuenta con una librería (llamada Cleap), la cual permite realizar la operación de triangulación de Delaunay en Paralelo usando GPU s de marca Nvidia. A ella, se desea integrar otros algoritmos que trabajen con mallas geométricas, como algoritmos de suavizado y simplificación, además de comparar su rendimiento y calidad con otras implementaciones ya existentes. En este trabajo, se investigó sobre algoritmos de suavizado, triangulación y simplificación de mallas geométricas, y luego se implementaron versiones de los dos primeros, los cuales fueron integrados en Cleap, y se comparó el rendimiento y calidad de sus soluciones. Con respecto al algoritmo de simplificación, solo se llegó hasta la fase de investigación teórica, pero se obtuvo la información y conocimientos necesarios para implementar e integrar una versión de este algoritmo. Los resultados muestran que el uso de la GPU permite reducir considerablemente los tiempos de ejecución, cuando se trabaja con mallas de gran tamaño, en comparación a sus contrapartes secuenciales, y que la calidad de sus resultados es similar o incluso mejor a la de las implementaciones conocidas actualmente. Estos resultados también muestran que no siempre lo que se espera teóricamente, ocurre en la práctica, debido a problemas y fallos que ocurren al realizar cálculos con error asociado, y detalles particulares asociados a una arquitectura o plataforma determinada.

Doctor en Ciencias, Mención Computación / Las técnicas de generación y refinamiento de mallas no estructuradas son usadas para la descomposición de objetos geométricos. Estas técnicas son muy utilizadas en áreas como modelamiento geométrico, computación gráfica, computación científica y aplicaciones de ingeniería, entre otras, lo que les da un interés interdisciplinario. Trabajando con triangulaciones (mallas compuestas por triángulos), el reto es generar una descomposición precisa del objeto geométrico o dominio, y al mismo tiempo satisfacer las restricciones adicionales impuestas por la aplicación, como restricciones en la forma de los elementos, el número de elementos, o la transición entre elementos de diferentes tamaños. Los algoritmos que ofrecen garantías teóricas sobre estos temas son preferidos. Los algoritmos de arista más larga fueron diseñados para el refinamiento iterativo de triangulaciones en aplicaciones de método de elementos finitos adaptativo. Estos algoritmos están basados en la estrategia de propagación por la arista más larga. Comparados a otros algoritmos de refinamiento, los algoritmos de arista más larga rápidamente producen una descomposición del dominio (o de regiones de interés) a través de operaciones locales simples. Las triangulaciones obtenidas presentan buena densidad y la calidad de los triángulos refinados está acotada. El propósito de esta tesis es proporcionar nuevas garantías teóricas para los algoritmos de arista más larga basados en bisección y los algoritmos de arista más larga basados en refinamiento Delaunay, para la generación y el refinamiento de mallas de buena calidad en 2 dimensiones. Nuestro estudio del algoritmo basado en bisección muestra que el algoritmo inserta un número constante de puntos por triángulo refinado, con costo asintóticamente óptimo. También mostramos que durante el proceso de refinamiento el algoritmo mejora la calidad promedio de los triángulos. Obtenemos nuevas cotas para el tamaño de la triangulación refinada y probamos que éste es a lo sumo un factor constante mayor que el tamaño de la triangulación inicial. Esta es la primera prueba completa sobre la complejidad del algoritmo. Seguidamente estudiamos el algoritmo basado en refinamiento Delaunay y su estrategia de inserción de puntos. Demostramos que los puntos insertados por el algoritmo no pueden estar arbitrariamente cerca de puntos existentes, lo que nos permite acotar la longitud de nuevas aristas. Analizamos el mejoramiento de la calidad de triángulos para diversas cotas en el ángulo mínimo, y definimos las propiedades geométricas de los triángulos obtenidos después del refinamiento. Utilizamos las técnicas existentes para el análisis de algoritmos de refinamiento Delaunay para demostrar que el algoritmo produce triangulaciones de tamaño óptimo, con buena densidad de puntos, y con ángulos internos entre 25.66 y 128.68 grados. También estudiamos las propiedades de la propagación en estos algoritmos de arista más larga. Mostramos que el número de triángulos afectados por refinamiento propagado converge rápidamente a aproximadamente dos. Esto demuestra que el refinamiento propagado representa un factor constante en el costo de refinamiento.

En el actual mercado globalizado las grandes compañías de desarrollo de software están entregando a sus clientes distinta variedad de productos y con cada vez menos distancia de tiempo entre un producto y otro. Esto se debe a gran parte en la reutilización de sus productos para la generación de los nuevos. Esto responde a una creciente demanda por la variedad en los productos o su customización. Para llevar esto a cabo, las empresas de tecnología desarrollan lo que se conoce como “familia de productos” que se generan a partir de un paradigma de desarrollo conocido como SPL o línea de productos de software. Sus ventajas son la de tener un bajo Time to Market, además de disminuir los costos de producción y mejorar la mantenibilidad de los productos, entre muchas otras. Se pretende aplicar este paradigma en base a dos aplicaciones que actualmente comparten gran parte de su implementación. Estas aplicaciones son “Face animator” y “Tree grow simulator”, las cuales básicamente son aplicaciones que permiten visualizar mallas geométricas y manipularlas según distintos parámetros y algoritmos. “Face animator” es una aplicación pensada en la manipulación de mallas geométricas que modelan rostros humanos, permitiendo el movimiento de distintas partes del rostro. Por otro lado la aplicación “Tree grow simulator” está pensada para la manipulación de mallas geométricas que modelan troncos de árboles, permitiendo crear una animación para ver su crecimiento mediante la distribución de una hormona. Para lograr generar una familia de productos en base a estas dos aplicaciones, se tuvo que estudiar el código fuente de ambos y hacer correcciones en el código fuente de una de estas, para poder hacer una aplicación genérica. Para esto se identificaron los puntos en común (commonalities) y las distintas opciones para una funcionalidad (puntos de variabilidad). Para esto se utilizó una herramienta web llamada “S.P.L.O.T.”, que permite generar un modelo de características o “features” y aplicar reglas lógicas entre las distintas opciones para mantener la consistencia de los productos. Esta herramienta también cuenta con un catalogo o configurador de productos, donde se permite elegir las opciones (variantes) de los puntos de variabilidad, así generando una configuración para una aplicación especifica. El paso siguiente fue la creación de una nueva aplicación, que permite seleccionar las variantes para los puntos variables pre definidos. Luego esta herramienta compila el código fuente y genera un archivo de configuración y un ejecutable, que es la nueva aplicación configurada con las opciones seleccionadas. Dentro de las dificultades encontradas, el actual diseño no permite la separación de componentes de manera de que estos sean independientes, importante al momento de compilar, por lo que se propone como un futuro desarrollo la restructuración en las clases de la interfaz grafica y donde se implementan los distintos puntos de variabilidad. También se puede agregar funcionalidades como lectura de un archivo XML directamente desde la herramienta “S.P.L.O.T.” cargando así automáticamente la selección de opciones. También se hace necesario agregar funcionalidades que existen en la aplicación “Tree grow simulator” y no se encuentran implementados en el código fuente de “Face Animator”.

Ingeniero Civil en Computación / El objetivo del presente trabajo de titulación es desarrollar y diseñar una aplicación multiplataforma para visualizar y analizar mallas geométricas mixtas en tres dimensiones. El visualizador debió ser implementado priorizando la eficiencia para poder manejar mallas muy grandes, y además poseer un diseño de calidad que permitiera extenderlo fácilmente. Una malla geométrica es un conjunto de celdas adyacentes que buscan modelar un objeto complejo de forma discreta; dependiendo del tipo de malla, las celdas serán polígonos y/o poliedros. Los elementos que forman las mallas pueden ser evaluados bajo distintos criterios para medir su calidad. Algunos modelos tienen millones de elementos, por lo que realizar cualquier tipo de cálculo sobre la malla, incluyendo renderizarla, es muy costoso. Para manejar mallas grandes de forma eficiente, varios algoritmos fueron acelerados utilizando la unidad de procesamiento gráfico de la tarjeta de video (GPU). Las GPU de última generación permiten realizar un gran número de tareas en paralelo, ya que tienen cientos de núcleos de procesamiento. Para poder aprovechar el potencial de la tarjeta de video se utiliza la API gráfica multiplataforma OpenGL. La interfaz de la API provee un gran número de funciones para controlar la tarjeta de video, y además especifica el lenguaje de programación GLSL, el cual nos permite programar el pipeline de renderizado, todo esto sin preocuparse del tipo de tarjeta de video ni del sistema operativo. Para abordar el problema, primero se analizaron los requerimientos específicos de la aplicación y se confeccionó un diseño para satisfacerlos. Se propuso un esquema modular, utilizando programación orientada a objetos y patrones de diseño, con lo cual se consiguió una aplicación extensible y capaz de realizar las tareas requeridas. Después, se implementaron las clases especificadas en el diseño y se generó una interfaz gráfica amigable para el usuario utilizando Qt. Esta interfaz permite al usuario acceder a todas las funcionalidades de la aplicación. Además, se utilizaron múltiples programas de Shaders para producir distintos efectos de iluminación y para acelerar algoritmos que no están relacionados con la visualización. Como resultado se obtuvo una poderosa herramienta gratuita y multiplataforma para analizar mallas. Con un diseño de calidad se consiguió que la aplicación fuese fácilmente extensible en estrategias de evaluación, modos de visualización, tipos de formatos que lee y exporta, y modos de seleccionar elementos. Además, el visualizador es capaz de procesar mallas que contienen por sobre un millón de elementos en tiempos reducidos, por lo que sigue siendo una aplicación altamente interactiva bajo estas condiciones.

No description available.

Ingeniera Civil en Computación / Las líneas de productos de software constituyen un paradigma de desarrollo, en el cual se busca construir, a partir de un conjunto de elementos clave, sistemas que comparten características comunes, o similitudes, y a la vez mantienen características propias, o variabilidades. Un ejemplo de sistema que puede verse beneficiado con este paradigma es el software generador de mallas geométricas. Las mallas geométricas son poderosas herramientas que permiten representar un objeto como un conjunto de polígonos contiguos. El presente trabajo de título tuvo por objetivo la construcción de una interfaz gráfica que permita al usuario la configuración y creación automática de productos correspondientes a generadores de mallas con distintas funcionalidades, utilizando la ingeniería de líneas de productos de software. El desarrollo consistió en extender la aplicación desarrollada en un trabajo de título anterior, que permitía configurar un producto, pero dado el acoplamiento del software base utilizado, todos los productos contenían el mismo código fuente. El software base utilizado se compone de dos generadores de mallas ya existentes: Simulador de crecimiento de árboles, sistema que modela el crecimiento de un árbol mediante mallas geométricas, y Generador genérico de mallas, que implementa una secuencia de pasos básica y común para todos los generadores de mallas y provee un apoyo conceptual. Ambos productos permiten cargar, almacenar y manipular las mallas. Durante el desarrollo de esta memoria, primero se realizó una revisión de las funcionalidades de ambos productos, para después identificar sus similitudes y variabilidades. Luego, estas características fueron agrupadas en tres grupos: Tipo de Aplicación, Manejo de Archivos y Algoritmos de procesamiento de mallas. Cada uno de estos grupos correspondió a una sección de la interfaz desarrollada. La interfaz de usuario fue construida de manera que permita la configuración de los productos en tiempo de compilación y de ejecución, mediante la generación de dos archivos de configuración. Esto implicó un análisis sobre el código fuente del software base, en el cual se detectó un alto acoplamiento entre varias de sus clases; por lo tanto, fue necesario realizar una intervención sobre el código de estas clases, para poder desacoplarlas y así compilarlas por separado, excluyendo las clases innecesarias. Como resultado, la interfaz desarrollada permite configurar y crear automáticamente productos generadores de mallas geométricas, de manera que incluyan sólo las funcionalidades escogidas por el usuario. Para trabajos futuros, se propone una re-ingeniería mayor del software base Simulador de crecimiento de árboles, que lo adapte para su utilización en el contexto de una linea de productos de software; además, es posible la adición de nuevos algoritmos y funcionalidades a la línea de productos ya construida.

Ingeniero Civil en Computación / La ortodoncia invisible consta de alineadores o placas que son fabricadas en base a un es- caneo tridimensional de la dentadura del paciente. Cada placa es diseñada en un software especializado, y es fabricada posteriormente con impresión 3D. El alumno fue intervenido con un tratamiento de ortodoncia invisible, durante el cual se detectaron múltiples falencias. Debido a esto, se ideó un sistema para realizar tratamientos de esta índole solucionando las deficiencias observadas. Esta misión se enmarca en el naci- miento de la empresa TecDent, cuyo único propósito es entregar estos tratamiento de manera económica y cómoda. La presente memoria consistió en el diseño del primer paso para poder realizar un tra- tamiento una vez que la dentadura del paciente ya ha sido digitalizada. Este primer paso es identificar de manera automática y correcta cada una de las estructuras anatómicas pre- sentes en el escaneo tridimensional, es decir, cada uno de los dientes y encía. Este paso es fundamental, ya que para poder modificar la posición de los dientes cualquier programa o sistema requiere saber su posición inicial. Después de cuatro implementaciones de algoritmos fallidos, aquella que resultó exitosa fue una adaptación obtenida desde la literatura. En esta, se detectan puntos claves dentro de los dientes de manera automática y se utilizan campos armónicos para detectar la forma final y posición de cada diente. El trabajo fue probado con un total de veintidós modelos. Seis de estos obtenidos de medios públicos y los dieciséis restantes siendo tomados por una asistente dental en yeso, de pacientes que activamente buscaban un tratamiento de ortodoncia, para ser digitalizados posteriormente por un escáner tridimensional. Como resultado el programa desarrollado logró segmentar correctamente las estructuras anatómicas en los modelos tridimensionales, debido a que en base a esta segmentación se fabricaron y ejecutaron tratamientos de ortodoncia de manera exitosa. El proceso de seg- mentación requiere aún en algunos casos de mínima intervención humana, siendo un sistema semi-automático.

Los modelos tridimensionales son útiles para representar objetos reales en el mundo digital. Su uso se encuentra en muchas aplicaciones tales como medicina, ingeniería, seguridad y otros. Recientemente, la introducción de dispositivos de captura baratos ha incrementado el interés por este tipo de información, generando una gran cantidad de modelos disponibles en diferentes lugares. Por lo tanto, es imperativo proveer algorithmos efectivos y eficientes para procesar y analizar datos 3D. La evaluación de similitud de modelos 3D es una tarea importante que puede ser útil para procesos de alto nivel tales como recuperación por contenido y reconocimiento. Estos procesos requieren atención ya que los repositorios 3D están en constante crecimiento y es cada vez más necesario realizar búsquedas basadas en contenido. Más aún, la comparación de modelos 3D es una tarea desafiante debido a la dificultad de representar adecuadamente un modelo 3D para una subsecuente comparación. En esta tesis, abordamos el problema de matching y recuperación por contenido en modelos 3D. Nosotros proponemos nuevas representaciones para modelos 3D basándonos en la habilidad de detectar características locales robustas sobre mallas. De esta forma, este trabajo se enfoca primero en la detección efectiva y eficiente de puntos de interés en mallas 3D. Luego, nosotros proveemos representaciones efectivas para lidiar con problemas como recuperación genérica, recuperación de formas no rígidas y correspondencias entre mallas. Para la recuperación basada en contenido, nosotros desarrollamos representaciones basadas en grupos de puntos de interés. Estas representaciones permiten aprovechar el poder de representación de las características locales mientras reducimos la cantidad de información necesaria. Para computar correspondencias, desarrollamos una representación jerárquica la cual conlleva una descomposición recursiva de un modelo 3D en regiones y puntos de interés. Esta representación es útil para decrementar el error de localización de las correspondencias en formas no rígidas mientras se reduce considerablemente el tiempo de procesamiento. Nuestros experimentos muestran que nuestros métodos para detectar estructuras locales en mallas son robustos a diferentes transformaciones. Además, nosotros presentamos una detallada evaluación de nuestras representaciones para recuperación genérica por contenido, recuperación de formas no rígidas y correspondencias en mallas. Desde nuestros resultados, es posible concluir que el uso de características locales puede mejorar el proceso de evaluar la similitud entre modelos 3D. Y más aún, nuestras representaciones pueden ayudar a mejorar simultáneamente la efectividad y la eficiencia de la recuperación de modelos 3D basada en contenido y de la búsqueda de correspondencias.

Ingeniero Civil en Computación / El método de elementos finitos, que permite resolver numéricamente problemas modelados por ecuaciones diferenciales parciales para el análisis de complejos problemas físicos sobre geometrías complejas, es una de las más importantes aplicaciones del ámbito científico. En estos problemas las geometrías son modeladas utilizando mallas geométricas, cuya calidad determina la precisión de los cálculos y de los resultados obtenidos por el método. En una malla geométrica definida por una triangulación, se entiende por calidad que el ángulo mínimo de cada triángulo esté acotado inferiormente por un valor acorde a la necesidad del problema. Dado un conjunto de puntos para construir una triangulación, las triangulaciones de tipo «Delaunay» se caracterizan por maximizar el ángulo mínimo interior de sus triángulos, y en consecuencia producen la triangulación de mejor calidad basada en tales puntos. Sin embargo, en caso de requerirse una mejor calidad, ésta puede mejorarse insertando nuevos puntos estratégicamente. En este contexto, los algoritmos tipo «Delaunay» de refinamiento de mallas juegan un rol de importancia ya que proveen métodos de mejoramiento de la calidad de una triangulación por medio de la inserción de puntos adicionales. Cada inserción se realiza mediante un proceso que mantiene la propiedad de «Delaunay» de la malla, e incrementan su calidad. Los distintos de algoritmos refinamiento tipo «Delaunay» presentan diferencias en cuanto a su desempeño y a la malla resultante. Ciertos algoritmos incorporan una etapa de «preprocesamiento», en la cual se prepara la malla para prevenir complicaciones durante el desempeño del resto del algoritmo. Adicionalmente, algunos se benefician de procesar los triángulos siguiendo un orden en particular. Omitir el preprocesamiento u ordenamiento en estos casos, altera el resultado obtenido. Es posible estudiar el comportamiento de los algoritmos al establecer comparaciones entre sus condiciones de procesamiento respecto a los resultados obtenidos. Existen programas computacionales que permiten la aplicación de un algoritmo de refinamiento sobre una malla y que como resultado presentan la malla mejorada y estadísticas respecto al desempeño del algoritmo durante la ejecución. Estas aplicaciones requieren ser ejecutadas una vez por cada refinamiento. Para el caso en que el número de algoritmos y/o mallas es considerable, lo anterior impone una dificultad. En particular cuando se busca establecer comparaciones relativas al comportamiento de los algoritmos, esta situación obliga al investigador a realizar un trabajo posterior de manejo de datos y visualización para los resultados obtenidos. Así, el tiempo de trabajo y esfuerzos adicionales, en casos de grandes volúmenes de pruebas y datos, pueden llegar a ser imprácticos fácilmente. En esta memoria se pretende elaborar una herramienta inteligente para comparar algoritmos de refinamiento tipo «Delaunay», realizar «tuning» de algunos algoritmos, proponer nuevos, etcétera, considerando diversas condiciones de procesamiento. Adicionalmente, se espera que la herramienta permita definir esquemas de ejecuciones de procesamiento, a través de los cuales sea posible analizar y obtener grandes cantidades de resultados de manera simple y práctica. Finalmente, la aplicación deberá generar «Reportes de Visualización de Resultados» en archivos «html», que incluyen cada detalle de la configuración y de los resultados, además de visualizaciones de gráficos para las tablas comparativas producidas. En las siguientes páginas se aborda en detalle el proceso de diseño e implementación de esta herramienta, cuyo desarrollo se ejecuta a partir de la elaboración de una biblioteca basada en la aplicación «Compare2DMesh», que fue producida en trabajos anteriores, la cual permite la ejecución individual y obtención de resultados de un refinamiento tipo «Delaunay» sobre una malla. Esta nueva biblioteca, llamada «C2M», supera a la aplicación original en múltiples aspectos. Además, se construye una nueva aplicación «BatchRefinement» que utiliza «C2M», y que provee una interfaz gráfica a través de la cual se proveen funcionalidades que satisfacen todos los requerimientos relacionado al trabajo con volúmenes de experimentos y generación de reportes con los análisis de los resultados. Estos reportes son creados en unos pocos segundos, de manera automática y flexible, y presentan información que habría tomado horas procesar sin esta herramienta. Las pruebas realizadas confirman la versatilidad de la aplicación, e indican una mejoría respecto a «Compare2DMesh» en muchos aspectos. A lo largo de este documento, se discuten temas relevantes y consideraciones relacionadas con la implementación actual y, en determinados casos, con los trabajos anteriores.