[pt] A reconstrução de curvas e superfícies a partir de pontos esparsos é um problema que tem recebido bastante atenção ultimamente. A não-estruturação dos pontos (ou seja, desconhecimento das relações de vizinhança e proximidade) e a presença de ruído são dois fatores que tornam este problema complexo. Para resolver este problema, várias técnicas podem ser utilizadas, como triangulação de Delaunay, reconstrução de iso-superfícies através de Marching Cubes e algoritmos baseados em avanço de fronteira. O algoritmo proposto consiste de quatro etapas principais: a primeira etapa é a clusterização dos pontos de amostragem de acordo com sua localização espacial. A clusterização fornece uma estrutura espacial para os pontos, e consiste em dividir o espaço em células retangulares de mesma dimensão, classificando as células em cheias (caso possuam pontos de amostragem em seu interior) ou vazias (caso não possuam pontos de amostragem em seu interior). A estrutura de dados gerada nesta etapa permite também obter o conjunto dos pontos de amostragem de cada uma das células. A segunda etapa é o processamento dos pontos através de projeções MLS. A etapa de pré- processameno visa reduzir ruído dos pontos de amostragem, bem como adequar a densidade de pontos ao nível de detalhe esperado, adicionando ou removendo pontos do conjunto inicial. A terceira etapa parte do conjunto das células que possuem pontos de amostragem em seu interior (células cheias) e faz a esqueletonização deste conjunto de células, obtendo, assim, uma aproximação digital para a curva a ser reconstruída. Este esqueleto é encontrado através do afinamento topológico das células que possuem pontos. A implementação do algoritmo de afinamento é feita de modo que o número de pontos em cada célula seja levado em consideração, removendo primeiro sempre as células com menor número de pontos. Na quarta etapa, a reconstrução da curva é finalmente realizada. Para tal, parte-se do esqueleto obtido na terceira etapa e constrói-se uma curva linear por partes, onde cada vértice é obtido a partir da projeção MLS do ponto médio de cada célula do esqueleto. / [en] Curve and surface reconstruction from sparse data has been recognized as an important problem in computer graphics. Non structured data points (i.e., a set of points with no knowledge of connectivity and proximity) together with the existence of noise make this problem quite difficult. In order to solve it, several techniques have been proposed, such as, some of them are based on Delaunay triangulation, other are based on implicit surface reconstruction or on the advancing front techniques. Our algorithm consists basically in four steps. In the first step, a clustering procedure is performed in order to group the sample points according to their spatial location. This procedure obtains an spatial structure for the points by subdividing uniformly the plane in rectangular cells, and classifying them into two categories: empty (when the cell contains no point inside) or not empty (otherwise). At this stage, a data structure is built in such way that it is possible to query the set of sample points that belong to a given rectangular cell. The second step processes the point through the Moving Least Squares method. Its objective is not only to reduce the noise on the data, but also to adapt the number of point to the desired level, by adding or removing points from the initial set. The third step builds the skeleton of the set of cells that have sample point on its interior. Such skeleton is in fact a digital approximation for the curve that will be reconstructed. It is obtained by the use of a topological thinning algorithm, and its implementation is done in such a way that the number of points in each cell is considered, for example, the cells with less number of points are not considered for the thinning. In the last step, the curve is finally reconstructed To do so, the skeleton obtained in the third step is used to construct a piecewise-linear approximation for the curve, where each vertex is obtained from the MLS projection on the middle point of the skeleton rectangular cell.

This paper is concerned with approximating noisy samples by non-uniform rational B-spline curves with special emphasis on free knots. We show how to set up the problem such that nonlinear optimization methods can be applied efficiently. This involves the introduction of penalizing terms in order to avoid undesired knot positions. We report on our implementation of the nonlinear optimization and we show a way to implement the program in parallel. Parallel performance results are described. Our experiments show that our program has a linear speedup and an efficiency value close to unity. Runtime results on a parallel computer are displayed.