Smooth-Surface Reconstruction in Near Linear Time
Stefan Funke, Edgar Ramos
A surface reconstruction algorithm takes as input a set of
sample points from an unknown closed and smooth surface in
3-d space, and produces a piece-wise linear approximation of
the surface that contains the sample points. This problem
has received considerable attention in computer graphics and
more recently in computational geometry. In the latter area,
four different algorithms (by Amenta and Bern `98; Amenta,
Choi, Dey and Leekha `00; Amenta, Choi and Kolluri `00;
Boissonnat and Cazals `00) have been proposed. These algorithms
have a correctness guarantee: if the sample is sufficiently
dense then the output is a good approximation to the original
surface. They have unfortunately a worst-case running time that
is quadratic in the size of the input. This is so because they
are based on the construction of 3-d Voronoi diagrams or Delaunay
tetrahedrizations, which can have quadratic size. Even worse,
according to recent work (Erickson `01), there are surfaces for
which this is the case even when the sample set is ``locally
uniform'' on the surface.
In this paper, we describe a new algorithm
that also has a correctness guarantee but whose worst-case running
time is almost linear. In fact, $O(n\log n)$ where $n$ is the input
size. As in some of the previous algorithms, the
piece-wise linear approximation produced by the new algorithm is a
subset of the 3-d Delaunay tetrahedrization; however, this is
obtained by computing only the relevant parts of the 3-d Delaunay
structure. The algorithm first estimates for each sample point the
surface normal and a parameter that is then used to ``decimate''
the set of samples. The resulting subset of sample points is
locally uniform and so a reconstruction based on it can be computed
using a simple and fast algorithm. In a last step, the decimated
points are incorporated into the reconstruction.
PDF