[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.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:4430 |
| Date | 23 January 2004 |
| Creators | CRISTIANE AZEVEDO FERREIRA |
| Contributors | HELIO CORTES VIEIRA LOPES |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.002 seconds