[en] AN ALGORITHM FOR CURVE RECONSTRUCTION FROM SPARSE POINTS - CRISTIANE AZEVEDO FERREIRA (2004)
[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.