an unorganized point set S, we create
a point set S
+
that adds the vertices of a cubical bounding box, then
compute the Delaunay triangulation T and Voronoi diagram Q of
S
+
. We form a graph G whose nodes are vertices of Q, and use
a spectral graph partitioning algorithm to cut this graph into two
pieces, the inside and outside subgraphs. Because every Voronoi
vertex in Q represents a tetrahedron in T , these labels are afxed to
the tetrahedra too. If the points in S are sampled densely enough
from a simple closed surface, then the surface is approximated rea-
sonably well by the faces of T that separate the inside tetrahedra
from the outside tetrahedra.
Our algorithm rst identies the set V of Voronoi vertices called
poles [?], which are likely to lie near the medial axis of the surface
being recovered. The algorithm then constructs a sparse pole graph
G
= (V, E). The set E of edges is dened as follows: for each
sample point s with poles u and v,
(u, v) is an edge in E, and for
each edge
(s, s ) of the Delaunay tetrahedralization T , the poles of
s and s are connected by edges in E.
The edge weights are based on observations of Amenta et al. [?].
If a sample s has a long, thin Voronoi cell, the likelihood is high
that its poles are on opposite sides of the surface. For each sample
s with poles u and v, we assign a negative weight to the edge
(u, v).
Let t
u
and t
v
be the tetrahedra in T whose duals are u and v. The
circumscribing spheres of t
u
and t
v
intersect at an angle . We
assign
(u, v) a weight of w
u,v
= e
4
+4 cos . Next, let
(u, v) be an
edge of E that is not assigned a negative weight. For all such edges
(u, v), we assign a weight of w
u,v
= e
4
4 cos . If is close to 180 ,
u and v are likely to lie on the same side of the surface, so we use a
large, positive edge weight.
We know a priori that tetrahedra with vertices on the bounding
box must be labeled outside. Hence, we x their labels prior to the
partitioning step by collapsing the poles dual to such tetrahedra into
a single supernode z, yielding a modied graph G .
From the modied pole graph G , we construct a pole matrix
L
= (D A). Here, A is the weighted adjacency matrix of graph G
and D is a diagonal matrix whose entries are the row sums D
ii
= j
=i
|A
i j
|.
We partition G by nding the eigenvector x associated with the
smallest eigenvalue of the generalized eigensystem Lx
= Dx.
Because L is a sparse matrix, we compute x using TRLAN, an im-
plementation of the Lanczos algorithm [?]. When this method is
applied to smooth, well-sampled surfaces, we nd that x is rela-
tively polarized: most of its entries are clearly negative or clearly
positive. Noisy models are more ambiguous; see Figure ??. Each
entry of x corresponds to one node of G . Suppose the entry corre-
sponding to the supernode z is positive; then the nodes of G whose
entries are positive are labeled outside, and the nodes whose entries
are negative are labeled inside.
0.5
1
1.5
2
2.5
3
x 10
6
4
3
2
1
0
1
2
3
4 x 10
6
Entry
Value
Eigenvector for dragon
Figure 1: Reconstruction of the Stanford dragon from noisy raw
data that includes outliers (upper right). At lower right are the
sorted entries of the eigenvector used to reconstruct the model.
1,770,421 input points, 3,031,078 triangles, 229 minutes.
Spectral partitioning labels each tetrahedron whose dual Voronoi
vertex is a pole. To label a tetrahedron t whose dual vertex v is not
a pole, we examine the poles of its four vertices. If t has a vertex u
that has a pole p that is labeled inside, and
 
vup < 90 , we label t
inside. Otherwise, we label t outside. We output every triangle at
which an inside tetrahedron meets an outside tetrahedron. This is
the reconstructed surface.
An alternative is to use power cells (all of which dualize to poles)
instead of Delaunay tetrahedra, like Amenta et al.s power crust al-
gorithm. Power cells offer better reconstruction of sharp corners,
but pay for it by generating many extra vertices in the surface.
The goal of our algorithm is to produce the same labeling as
the provably good power crust algorithm when the surface is well-
sampled and the samples are noiseless, but to behave more robustly
otherwise. Because the spectral partitioner has a global view of
the samples, it can ll large holes and correct for noise and under-
sampling in circumstances where the local labeling algorithm that
Amenta et al. use fails. Outliers are usually removed: if every tetra-
hedron adjoining an outlier is labeled outside (or every tetrahedron
is labeled inside), the outlier does not appear in the nal surface.
The spectral algorithm is not infallible. The global eigenvector
computation takes longer time than the labeling algorithm in power
crust. Given point sets that represent non manifold geometries with
internal cells, the spectral method can confuse the inside and the
outside of a model. However, given point sets sampled from man-
ifold surfaces, spectral surface reconstruction is remarkably robust
against noise, outliers, and undersampling. In particular, the spec-
tral algorithm performs well on the output of range scanners.
References
A
MENTA
, N., C
HOI
, S.,
AND
K
OLLURI
, R. 2001. The Power Crust, Unions of
Balls, and the Medial Axis Transform. Computational Geometry: Theory and
Applications 19, 23 (July), 127153.
P
OTHEN
, A., S
IMON
, H. D.,
AND
L
IOU
, K.-P. 1990. Partitioning Sparse Matrices
with Eigenvectors of Graphs. SIAM Journal on Matrix Analysis and Applications
11, 3 (July), 430452.