Zugl.: Bielefeld, Univ., Diss., 2007

Zugl.: Bielefeld, Univ., Diss., 2007.

Diss.--Kunstgeschichte--Saarbrücken, 1981. / Bibliogr. p. 254-269.

Memoria para optar al título de Ingeniero Civil en Computación / La triangulación de Delaunay es una entidad geométrica con muchas aplicaciones en computación gráfica e ingeniería. Por lo general, su construcción es un problema difícil que a menudo viene acompañado con restricciones geométricas y de calidad. Para facilitar la experimentación de algoritmos relativos al problema de Delaunay, se presenta una herramienta con mejoras en simplicidad, desempeño y robustez frente a otras opciones existentes. En primer lugar, se ofrece una implementación sólida del algoritmo de Delaunay incremental con intercambio de aristas, el cual es un método conocido que aborda el problema agregando cada punto de la triangulación secuencialmente. Esta implementación maneja las estructuras de datos de forma sencilla (triángulos con punteros a sus vecinos), por lo que es fácil de extender. Además, asegura que las triangulaciones siempre quedan bien definidas, anulando cualquier operación que invalide la triangulación de acuerdo con un criterio de robustez sobre los triángulos. En segundo lugar, se implementa un algoritmo que adapta las triangulaciones para satisfacer restricciones en las aristas, el cual funciona por medio de una idea sencilla que reusa conceptos del algoritmo de Delaunay incremental. En cada iteración se localizan los triángulos que intersectan la arista que se quiere respetar y se intercambian las diagonales secuencialmente hasta que sea respetada. Finalmente, el algoritmo Lepp-Centroide desarrollado por la profesora Rivara y coautores permite obtener una triangulación de buena calidad (ángulo mínimo acotado) por medio de la inserción de nuevos puntos. La implementación de esta memoria se comporta como ha sido establecido en estudios teóricos y prácticos previos, lo que significa que se consigue mejorar la calidad de las triangulaciones insertando pocos puntos y con restricciones geométricas menos fuertes.

La méthode des éléments finis, largement utilisée en analyse numérique, requiert que le domaine considéré soit préalablement maillé, c'est-à-dire partitionné en un ensemble de polytopes généralement, mais pas nécessairement, simpliciaux. Parmi les méthodes permettant la génération de tels maillages, la triangulation de Delaunay présente le double intérêt d'avoir un support théorique fondant la robustesse des algorithmes, ainsi que de produire des éléments de qualité, conditionnant fortement la précision des calculs ultérieurs. Elle présente cependant l'inconvénient de ne pas être à même de prendre en compte des considérations topologiques, lui interdisant de facto d'être utilisée en l'état pour produire des maillages. Un certain nombre de méthodes ont été proposées pour tenter de résoudre ce problème, mais aucune ne constitue une solution générale. Par ailleurs, les maillages qu'elles restituent ne possèdent plus la propriété de Delaunay. Ce travail étudie les conditions dans lesquelles une contrainte, en dimensions 2 et 3, apparaîtra dans toute triangulation de Delaunay du nuage de points auquel elle est associée. En particulier, des théorèmes de Delaunay-admissibilité a priori sont établis. A l'aide de ces résultats, des algorithmes de redéfinition de contraintes sont proposés, de telle sorte que les nouvelles discrétisations, recouvrements des anciennes, soient construites par toute triangulation de Delaunay. Ainsi, les contraintes étant satisfaites automatiquement, aucune opération de forçage a posteriori n'est requise, et les maillages produits sont de Delaunay. En raison du coût prohibitif de la convergence en dimension 3, deux algorithmes efficaces sont proposés, sans qu'aucune conjecture sur leur convergence ne soit formulée. A titre d'application de la méthode en dimension 3, l'interfaçage avec un mailleur de Delaunay contraint existant est étudié. En particulier, la pertinence de la méthode est illustrée grâce au déblocage d'une configuration que ce mailleur ne parvient pas à résoudre. D'autres applications possibles, ainsi que les développements en cours sont également évoqués.

Ingeniero Civil en Computación / Existen aplicaciones en donde una triangulación de buena calidad es esencial, entendiéndose por calidad que el ángulo mínimo de cada triángulo esté acotado inferiormente. El método de elementos finitos corresponde a una de las aplicaciones más importantes. Los algoritmos de refinamiento de triangulaciones eliminan aquellos triángulos que poseen algún ángulo interior menor a un umbral deseado, mediante la inserción de nuevos puntos en la triangulación original. Un subconjunto de estos algoritmos, que reciben el nombre de algoritmos de refinamiento Delaunay, toman como punto de partida una triangulación de Delaunay restringida de los datos de entrada, y mediante inserciones Delaunay de los nuevos vértices mantienen la condición de Delaunay tras cada inserción. Estos algoritmos son los más utilizados para obtener triangulaciones de calidad. En esta memoria se desarrolló un nuevo software de comparación de algoritmos de refinamiento llamado Compare2DMesh, el cual permite: hacer comparaciones experimentales rigurosas de los diferentes algoritmos de refinamiento Delaunay, manejar cualquier tamaño de mallas y geometrías complejas, visualizar cada inserción de un nuevo vértice mientras la triangulación está siendo refinada, refinar sin visualización del progreso, y configurar y ejecutar variaciones de los algoritmos. Este software usó como base un prototipo llamado MeshSuite. Para validar el desempeño de Compare2DMesh se realizaron experimentos de comparación entre los algoritmos implementados, y también se comparó con otros software de refinamiento. Se concluyó que Compare2DMesh supera considerablemente el rendimiento del prototipo del que fue originado, y que procesa mallas grandes en tiempos razonables, lo que permite que Compare2DMesh pueda ser utilizado para los fines de probar, comparar y afinar algoritmos.

An autonomous robot able to navigate inside an unknown environment and reconstruct full 3D scene models using monocular video has been a long term goal in the field of Machine Vision. A key component of such a system is the reconstruction of surface models from estimated scene structure. Sparse 3D measurements of real scenes are readily estimated from N-view image sequences using structure-from-motion techniques. In this thesis we present a geometric theory for reconstruction of surface models from sparse 3D data captured from N camera views. Based on this theory we introduce a general N-view algorithm for reconstruction of 3D models of arbitrary scenes from sparse data. Using a hypothesise and verify strategy this algorithm reconstructs a surface model which interpolates the sparse data and is guaranteed to be consistent with the feature visibility in the N-views. To achieve efficient reconstruction independent of the number of views a simplified incremental algorithm is developed which integrates the feature visibility independently for each view. This approach is shown to converge to an approximation of the real scene structure and have a computational cost which is linear in the number of views. Surface hypothesis are generated based on a new incremental planar constrained Delaunay triangulation algorithm. We present a statistical geometric framework to explicitly consider noise inherent in estimates of 3D scene structure from any real vision system. This approach ensures that the reconstruction is reliable in the presence of noise and missing data. Results are presented for reconstruction of both real and synthetic scenes together with an evaluation of the reconstruction performance in the presence of noise.

No description available.

No description available.

The main goal of this work is to present a discrete analogous of the laplacian operator, that is, a linear operator on the set of piecewise linear functions over a triangular mesh that has similar properties to the continuous laplacian over a surface. Particularly, we will show that if the mesh satisfies a Delaunay criterion, the laplacian obeys a discrete version of the maximum principle, which importance in the discrete setting is similar to the importance of the maximum principle in the theory of harmonic functions. We also present three applications of the discrete laplacian: the first one has as objective to get parametrizations of meshes for texture mapping; the second one consists of mesh smoothing by a diffusion process; the third and last application aims to identify forms and symmetries of objects by means of the contour curves associated to the eigenfunctions of the laplacian operator. / Fundação de Amparo a Pesquisa do Estado de Alagoas / O objetivo desta disserta¸c ao ´e apresentar um an´alogo discreto do operador laplaciano, ou seja, um operador linear definido no conjunto das fun¸c oes lineares por partes em uma malha de tri angulos que possua o m´aximo de propriedades an´alogas ao operador laplaciano cont´ınuo sobre uma superf´ıcie. Em particular, mostraremos que se a malha satisfaz ao crit´erio de Delaunay, o laplaciano obedece a uma vers ao discreta do princ´ıpio do m´aximo, que possui import ancia semelhante ao princ´ıpio do m´aximo na teoria das fun¸c oes harm onicas. Apresentamos ainda tr es aplica¸c oes do laplaciano discretizado: a primeira tem como objetivo obter parametriza¸c oes de malhas para efeito de mapeamento de textura; a segunda consiste na suaviza¸c ao de malhas por meio do processo de difus ao; a terceira e ´ultima aplica¸c ao visa identificar formas e simetrias de objetos por meio das curvas de contorno associadas `as autofun¸c oes do laplaciano.