Reconstrução a partir de pontos não organizados é um problema relevante e comum a vários tipos de aplicações, como tratamento de imagens médicas e computação gráfica. Este tipo de abordagem é relativamente recente e busca gerar malhas não estruturadas a partir de conjuntos de pontos geralmente fornecidos por scanners tridimensionais, sondas sísmicas, radares e amostragens de superfícies implícitas. O principal desafio a ser superado neste tipo de reconstrução é a falta de informação, tanto geométrica quanto topológica, a respeito do objeto a ser reconstruído. Essa falta de informação tem impossibilitado a elaboração de algoritmos robustos e eficientes. Diversas técnicas para a resolução deste: problema são descritas na literatura, tais como técnicas baseadas em zeros de funções, em "esculpimento", em modelos deformáveis e em métodos incrementais. Cada uma delas possui vantagens e desvantagens. No entanto, a maioria utiliza operações geométricas caras e pouco estáveis. Este projeto de doutorado propõe uma nova abordagem para o problema de reconstrução a partir de pontos não organizados. A abordagem é baseada em "esculpimento", e sua principal característica é diminuir a quantidade de operações geométricas, substituindo-as por operações topológicas, mais robustas e mais eficientes. Para isso, a teoria de Morse em complexos simpliciais é utilizada como ferramenta de decisão da inclusão ou não de simplexos na malha do objeto reconstruído. Além disso, apresentam-se garantias teóricas de que, sob uma taxa de amostragem adequada, a reconstrução é homeomorfa e próxima do objeto original. Adicionalmente, esse projeto vem atender as necessidades do grupo de mecânica de fluídos computacional do ICMC-USP, fornecendo um gerador de malhas não estruturadas a partir de pontos não organizados, o qual deverá ser empregado onde técnicas mais convencionais, tais como técnicas de triangulação de politopos e de reconstrução por seções planares, não produzem resultados satisfatórios.

Performing extensive geometrical computaiions is a major source of problems in reconstruction from sample points. Such operations are computationally intensive, and introduce numerical instabilities that may be difficult to handle. We introduce an innovative approach for generating a piecewise linear approximations from sample points that reduces geometrical calculations drastically by converting geometrical information into topological attributes. Geometrical tests are employed only at an initial step, to compute a Delaunay triangulation of the points. Discrete Morse theory is used to derive a topological framework towards reconstruction. The result is a robust reconstruction algorithm that handles multiple components and has reduced computational costs. In this work we introduce an innovative approach for generating 3D piecewise linear approximations from sample points that is strongly based on topological information, thus reducing the computational cost and numerical instabilities typically associated with geometric computations. Discrete Morse theory provides the basis of a topological framework for reconstruction that results in a robust reconstruction algorithm capable of handling multiple components and with low computational cost. We describe the proposed approach and introduce the reconstruction algorithm, called Tor - Topological Object Reconstructor. Reconstruction results are presented and the performance of Tor is compared with that of other reconstruction approaches for some standard point sets. Theoretical guarantees of reconstruction are also provided.