THESIS
2012
viii, 100 p. : ill. ; 30 cm
Abstract
This thesis studies the problems of reconstructing surfaces and maintaining a deforming
surface mesh. We first present a practical algorithm for surface reconstruction from a
point cloud, which runs in O(n log n) time, where n is the number of sample points.
This is optimal in the pointer machine model. The only existing O(n log n)-time algorithm
due to Funke and Ramos is far from practical as it involves several sophisticated
data structures, including the well-separated pair decomposition, approximate directional
nearest neighbor searching, and approximate range searching. Our algorithm is based on
a variant of the standard octree, and is much simpler.
We investigate the complexity of edge
flips in a surface mesh. Given a surface mesh
whose vertices are dense with respect t...[
Read more ]
This thesis studies the problems of reconstructing surfaces and maintaining a deforming
surface mesh. We first present a practical algorithm for surface reconstruction from a
point cloud, which runs in O(n log n) time, where n is the number of sample points.
This is optimal in the pointer machine model. The only existing O(n log n)-time algorithm
due to Funke and Ramos is far from practical as it involves several sophisticated
data structures, including the well-separated pair decomposition, approximate directional
nearest neighbor searching, and approximate range searching. Our algorithm is based on
a variant of the standard octree, and is much simpler.
We investigate the complexity of edge
flips in a surface mesh. Given a surface mesh
whose vertices are dense with respect to the local feature size and whose triangles have
angles at least a constant, we prove that one can
flip edges in linear time such that all
triangles have almost empty diametric balls. As a corollary, a planar triangulation with
a constant angle lower bound can be converted to the Delaunay triangulation in linear
time. It is known that a general planar triangulation needs
Ω(n
^{2}) edge
flips to become
Delaunay.
Using the edge
flip results, we design an efficient algorithm to update a deforming
surface mesh, which is specified only by a dense sample of n points that move with the
surface. Although edge
flips alone cannot improve the angles in the mesh substantially
after they worsen, they can be used in conjunction with vertex insertions and deletions
to restore the mesh quality. Under a reasonable motion model, we can enforce bounded
aspect ratios and a small approximation error throughout the entire deformation. The
update takes O(n) time at each time step.
The reconstruction and maintenance algorithms have been implemented and they give
good performance in our experiments.
Post a Comment