Representações computacionais de formas podem ser criadas em ferramentas CAD ou geradas a partir de um objeto físico já existente. Esta última abordagem oferece como vantagens rapidez e fidelidade ao objeto original, que são os aspectos fundamentais em muitas aplicações, como Simulações Numéricas de Equações Diferenciais Parciais e Imagens Médicas. A reconstrução (ou geração de malhas superficiais) a partir de pontos amostrados de uma superfície de um objeto é um problema clássico de representação de formas. Nesta dissertação apresentamos um vasto levantamento bibliográfico deste tipo de reconstrução, classificando e descrevendo os principais trabalhos presentes na literatura. A partir do levantamento bibliográfico, selecionamos um conjunto de algoritmos sobre os quais foram realizadas comparações teóricas e empíricas cujos resultados são apresentados. Para finalizar, apresentamos aplicações de nossas implementações em Simulação Numérica de Equações Diferenciais Parciais e processamento de Imagens / Computational representations of shapes can be developed using CAD applications or created from data acquired from a real physical object. This latter is advantageous with respect to time and fidelity to the original object which are essential to several applications, such as Numerical Simulation of Partial Differential Equations and Medical Imaging. A classical shape representation problem is that of reconstruction (or superficial mesh generation) from points sampled over the surface of an object. In this Master\'s thesis we describe a broad survey of these reconstruction methods. We focus in the classification and characterization of the main algorithms proposed in the literature. From this survey, we selected some algorithms and conducted some theoretical and practical comparisons. We conclude this work describing applications of the algorithms implemented in Numerical Simulations of Differential Partial Equations and Image Processing

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.

Representações computacionais de formas podem ser criadas em ferramentas CAD ou geradas a partir de um objeto físico já existente. Esta última abordagem oferece como vantagens rapidez e fidelidade ao objeto original, que são os aspectos fundamentais em muitas aplicações, como Simulações Numéricas de Equações Diferenciais Parciais e Imagens Médicas. A reconstrução (ou geração de malhas superficiais) a partir de pontos amostrados de uma superfície de um objeto é um problema clássico de representação de formas. Nesta dissertação apresentamos um vasto levantamento bibliográfico deste tipo de reconstrução, classificando e descrevendo os principais trabalhos presentes na literatura. A partir do levantamento bibliográfico, selecionamos um conjunto de algoritmos sobre os quais foram realizadas comparações teóricas e empíricas cujos resultados são apresentados. Para finalizar, apresentamos aplicações de nossas implementações em Simulação Numérica de Equações Diferenciais Parciais e processamento de Imagens / Computational representations of shapes can be developed using CAD applications or created from data acquired from a real physical object. This latter is advantageous with respect to time and fidelity to the original object which are essential to several applications, such as Numerical Simulation of Partial Differential Equations and Medical Imaging. A classical shape representation problem is that of reconstruction (or superficial mesh generation) from points sampled over the surface of an object. In this Master\'s thesis we describe a broad survey of these reconstruction methods. We focus in the classification and characterization of the main algorithms proposed in the literature. From this survey, we selected some algorithms and conducted some theoretical and practical comparisons. We conclude this work describing applications of the algorithms implemented in Numerical Simulations of Differential Partial Equations and Image Processing

A triangulação de Delaunay de um conjunto de pontos é uma importante entidade geométrica cujas aplicações abrangem diversas áreas da ciência. Triangulações regulares, que podem ser vistas como uma generalização da triangulação de Delaunay, onde pesos são associados aos vértices, também têm sido aplicadas em diversos problemas como reconstrução a partir de nuvens de pontos [5], geração de malha [12], modelagem molecular [7] e muitos outros. Apesar de ser muito utilizada, a fundamentação teórica referente à triangulação regular ainda não está tão desenvolvida quanto para triangulação de Delaunay. Por exemplo, pouco se sabe a respeito da dinâmica de uma triangulação regular [22] quando os pesos associados aos vértices mudam. Este trabalho tem como objetivo principal desenvolver um arcabouço teórico e computacional que permita representar uma triangulação qualquer como uma triangulação regular. Para isso, um estudo da dinâmica das operações de flip frente à variação de pesos nos vértices deve ser realizado. Este estudo tem como base o mapeamento da triangulação em um politopo que define os possíveis pesos para os vértices. Tal politopo pode ser obtido por meio de um sistema de inequações que gera um problema de programação linear cuja solução fornece os pesos adequados. A transformação de uma triangulação qualquer em triangulação regular permite o desenvolvimento de novas técnicas de morphing entre malhas e algoritmos para modelar níveis de detalhe, sendo este mais um objetivo deste trabalho / Delaunay triangulation of a set of points is an important geometrical entity whose applications encompass a range of scientfic fields. Regular triangulations, which can be seen as a generalization of Delaunay triangulation where weights are assigned to vertices, have also been widely employed in several problems, as for example mesh reconstruction from point clouds [5], mesh generation [12] and molecular modelling [7]. In spite of their applicability, the theoretical background of regular triangulations is not so developed as the theory of Delaunay triangulation. For example, the dynamic of regular triangulation is not completely known when the vertices weights change [22]. This work aims at developing a computational and theoretical framework that allow to represent a given triangulation as a regular triangulation. In this context, an investigation into the dynamic of edge ip operations regarding changes in the vertices weight must be accomplished. This investigation is based on mapping the triangulation in a polytope that defines the space of vertices weights. Such polytope can be built from an inequation system that can be associate to a linear program problem whose solution supplies the appropriated weights. By representing a triangulation as a regular triangulation one can conceive a new mesh morphing scheme and level of detail algorithm, being this another goal of this work

Técnicas para gerar malhas triangulares ou tetraedrais a partir de imagens, ou assumem como entrada uma imagem pré-processada, ou geram uma malha sem distinguir as diferentes estruturas contidas na imagem. O pré-processamento e a ausência de estruturas bem definidas podem apresentar dificuldades na utilização das malhas geradas em algumas aplicações, tais como simulações numéricas. Neste trabalho, apresentamos uma nova técnica que elimina a necessidade do pré-processamento embutindo a segmentação dentro do processo de geração de malha. Além disto, a técnica proposta considera critérios de qualidade nas malhas geradas, mostrando-se apropriada para aplicações de simulação numérica assim como modelagem de imagens com malhas / Techniques devoted to generate triangular or tetrahedral meshes from images either take as starting point a pre-processed image or generate a mesh without distinguishing different structures contained in the image. The pre-process and the absence of well defined structures may impose difficulties in using the resulting mesh in some applications as, for example, numerical simulations. In this work, we present a new technique that aims at eliminating the need for pre-processing by building the segmentation into the mesh generation process. Furthermore, the proposed technique consider quality criteria in the generated meshes, being appropriated for applications in numerical simulation as well as in image modeling

Técnicas para gerar malhas triangulares ou tetraedrais a partir de imagens, ou assumem como entrada uma imagem pré-processada, ou geram uma malha sem distinguir as diferentes estruturas contidas na imagem. O pré-processamento e a ausência de estruturas bem definidas podem apresentar dificuldades na utilização das malhas geradas em algumas aplicações, tais como simulações numéricas. Neste trabalho, apresentamos uma nova técnica que elimina a necessidade do pré-processamento embutindo a segmentação dentro do processo de geração de malha. Além disto, a técnica proposta considera critérios de qualidade nas malhas geradas, mostrando-se apropriada para aplicações de simulação numérica assim como modelagem de imagens com malhas / Techniques devoted to generate triangular or tetrahedral meshes from images either take as starting point a pre-processed image or generate a mesh without distinguishing different structures contained in the image. The pre-process and the absence of well defined structures may impose difficulties in using the resulting mesh in some applications as, for example, numerical simulations. In this work, we present a new technique that aims at eliminating the need for pre-processing by building the segmentation into the mesh generation process. Furthermore, the proposed technique consider quality criteria in the generated meshes, being appropriated for applications in numerical simulation as well as in image modeling

A triangulação de Delaunay de um conjunto de pontos é uma importante entidade geométrica cujas aplicações abrangem diversas áreas da ciência. Triangulações regulares, que podem ser vistas como uma generalização da triangulação de Delaunay, onde pesos são associados aos vértices, também têm sido aplicadas em diversos problemas como reconstrução a partir de nuvens de pontos [5], geração de malha [12], modelagem molecular [7] e muitos outros. Apesar de ser muito utilizada, a fundamentação teórica referente à triangulação regular ainda não está tão desenvolvida quanto para triangulação de Delaunay. Por exemplo, pouco se sabe a respeito da dinâmica de uma triangulação regular [22] quando os pesos associados aos vértices mudam. Este trabalho tem como objetivo principal desenvolver um arcabouço teórico e computacional que permita representar uma triangulação qualquer como uma triangulação regular. Para isso, um estudo da dinâmica das operações de flip frente à variação de pesos nos vértices deve ser realizado. Este estudo tem como base o mapeamento da triangulação em um politopo que define os possíveis pesos para os vértices. Tal politopo pode ser obtido por meio de um sistema de inequações que gera um problema de programação linear cuja solução fornece os pesos adequados. A transformação de uma triangulação qualquer em triangulação regular permite o desenvolvimento de novas técnicas de morphing entre malhas e algoritmos para modelar níveis de detalhe, sendo este mais um objetivo deste trabalho / Delaunay triangulation of a set of points is an important geometrical entity whose applications encompass a range of scientfic fields. Regular triangulations, which can be seen as a generalization of Delaunay triangulation where weights are assigned to vertices, have also been widely employed in several problems, as for example mesh reconstruction from point clouds [5], mesh generation [12] and molecular modelling [7]. In spite of their applicability, the theoretical background of regular triangulations is not so developed as the theory of Delaunay triangulation. For example, the dynamic of regular triangulation is not completely known when the vertices weights change [22]. This work aims at developing a computational and theoretical framework that allow to represent a given triangulation as a regular triangulation. In this context, an investigation into the dynamic of edge ip operations regarding changes in the vertices weight must be accomplished. This investigation is based on mapping the triangulation in a polytope that defines the space of vertices weights. Such polytope can be built from an inequation system that can be associate to a linear program problem whose solution supplies the appropriated weights. By representing a triangulation as a regular triangulation one can conceive a new mesh morphing scheme and level of detail algorithm, being this another goal of this work

Dado um processo de Poisson d-dimensional, construímos funções harmônicas na triangulação de Delaunay associada, com comportamento assintótico linear, como limite de um processo de harness sem ruído. Tais funções permitem que construamos uma nova imersão da triangulação de Delaunay, que denominaremos de deformação harmônica. / Given a d-dimensional Poisson point process, we construct harmonic functions on the associated Delaunay triangulation, with linear assymptotic behaviour, as the limit of a noiseless harness process. These mappings allow us to find a new embedding for the Delaunay triangulation. We call it harmonic deformation of the graph.

Dado um processo de Poisson d-dimensional, construímos funções harmônicas na triangulação de Delaunay associada, com comportamento assintótico linear, como limite de um processo de harness sem ruído. Tais funções permitem que construamos uma nova imersão da triangulação de Delaunay, que denominaremos de deformação harmônica. / Given a d-dimensional Poisson point process, we construct harmonic functions on the associated Delaunay triangulation, with linear assymptotic behaviour, as the limit of a noiseless harness process. These mappings allow us to find a new embedding for the Delaunay triangulation. We call it harmonic deformation of the graph.