Surface Reconstruction by Wrapping Finite Sets in Space
Transcript Of Surface Reconstruction by Wrapping Finite Sets in Space
Surface Reconstruction by Wrapping Finite Sets in Space
Herbert Edelsbrunner
Abstract
Given a finite point set in ¡£¢ , the surface reconstruction problem asks for a surface
that passes through many but not necessarily all points. We describe an unambiguous definition of such a surface in geometric and topological terms, and sketch a fast algorithm for constructing it. Our solution overcomes past limitations to special point distributions and heuristic design decisions. Keywords. Computational geometry, computer graphics, geometric modeling; Delaunay complexes, Morse functions, vector fields, acyclic relations, collapsing, deleting.
1 Introduction
The original version of this paper was written in 1995. To preserve that version, we have limited modifications to minor stylistic changes and to the addition of a paragraph that accounts for the new and related work during the years from 1996 to 2001. All citations of work during these five years use letters rather than numbers in the citation.
Problem and solution. The input to the surface reconstruction problem is a finite set of points scattered in three-dimensional Euclidean space. The general task is to find a surface passing through the points. There are of course many possible such surfaces, and we would want one that in some sense is most reasonable and best represents the way the input points are distributed. We allow for the case that some points lie off the surface inside the bounded volume. We propose a solution that provides structural information in terms of a mesh or complex connecting the
¤
Then: Department of Computer Science, University of Illinois at Urbana-Champaign, and Raindrop Geomagic, Champaign-Urbana, Illinois, USA. Now: Department of Computer Science, Duke University, Durham, and Raindrop Geomagic, Research Triangle Park, North Carolina, USA.
1
points. Section 2 will be more specific about what exactly we mean by this and what properties we expect from the mesh.
The first part of our solution consists of a description of the surface in geometric and topological terms. There are minimum distance functions and ideas from Morse theory turning these functions into vector fields and cell decompositions. For generic data sets, this description is unambiguous and completely determines the surface. The second part of our solution is an efficient algorithm that constructs the defined surface. The algorithm is based on Delaunay complexes and extracts a subcomplex through repeated collapsing. All ideas and results generalize to any arbitrary fixed number of dimensions. For reasons of specificity, the discussion in this paper is exclusively three-dimensional.
Work prior to 1995. The surface reconstruction problem has a long history. Most of the previous work assumes some kind of additional structure given along with the data points. A common assumption is that the points lie on curves defined by slicing a surface with a collection of parallel planes [9, 13]. The surface reconstruction is reduced to a sequence of steps, each connecting two curves in contiguous planes.
Another common assumption is differentiability¡¡[11]. The surface is constructed
from patches defining diffeomorphisms between and local neighborhoods on the surface. Fairly dense point distributions are required to allow the reconstruction of tangents and normals.
We are interested in the general surface reconstruction problem that¡ a¢ dmits no
assumption other than that the input consists of finitely many points in . At the time of writing this paper in 1995, we found only three pieces of work studying the general problem. In two cases, the surface or shape is obtained from the threedimensional Delaunay complex of the input points. This is also the approach followed in this paper. Boissonnat [1] compromises the global nature of the approach by using local rules for removing simplices from the Delaunay complex. The resulting surfaces are somewhat unpredictable and not amenable to rational analysis. Edelsbrunner and Mu¨cke [6] use distance relationships to identify certain subcomplexes of the Delaunay complex as alpha shapes of the given data set. For uneven densities, these shapes tend to either exhibit a lack of detail in dense regions or gaps and holes in sparse regions. Rather than subcomplexes of the Delaunay complex, Veltkamp [15] uses two-parameter neighborhood graphs to form surfaces from points in space. Depending on the choice of the parameters the graphs may exhibit self-intersections or poor shape representation.
Development after 1995. The algorithm described in this paper has been implemented in 1996 at Raindrop Geomagic, which successfully commercialized it as geomagic Wrap. It is also described in U. S. Patent No. 6,3777,865, which has issued on April 23, 2002.
The surface reconstruction problem has enjoyed increasing popularity over the last few years, both in computer graphics and in computational geometry. A number of essentially two-dimensional algorithms that rely primarily on density and
2
smoothness assumptions of the data have been developed [C, E, F, J]. In parallel,
the use of three-dimensional Delaunay complexes has been refined [A, B, D, I]. The
focus of that work is the detailed study of Delaunay complexes for data sets that sat-
isfy density and smoothness assumptions, and to exploit their special structure for
surface reconstruction. Possibly surprisingly, neither development has come close
to reproducing the ideas presented in this paper.
From a completely different angle, Robin Forman’s development of a discrete
Morse theory for simplicial complexes [H] is related to work in this paper. Accord-
ing to Forman, a discrete Morse function is a map from the collection of simplices
¡ to the real numbers such that for every simplex the following two conditions hold:
¢¤£¥¡ ¦¨§©¥¢¦¨§©¡ ¢"!$# ¡%! (1) there is at most one face &'#¥¡ ¦(§)©&01¦¨§©¥¡321 &4!5£ ¡%! (2) there is at most one coface
with with
and
, and
and
.
The theory developed in this paper uses relations that correspond to functions violating these conditions and thus does not seem to fit into Forman’s framework. It would be interesting to elucidate the connection between the two approaches to a discrete Morse theory. Another recent development that resonates with the work in this paper is the introduction of persistent Betti numbers [G]. It relates to the discussion of granularity in Section 9, in which it is suggested to construct coarse-grained decompositions of the Delaunay complex by merging discrete stable manifolds, possibly by suppressing some of the less persistent critical points. Maybe the time has come to integrate all these ideas and to develop a hierarchical approach to surface reconstruction based on a more extensive use of algebraic structures developed in topology.
Outline. Section 2 displays sample results obtained with software implemented
at R¡ a¢ indrop Geomagic. Section 3 reviews Delaunay complexes for finite point sets
in . Section 4 reviews notions from Morse theory and constructs a family of Morse functions from local distance information. Section 5 derives an ordering principle for the Delaunay simplices from the Morse functions. Section 6 studies mechanisms to cluster simplices based on the ordering. Section 7 defines the basic surface construction as a sequence of collapses. Section 8 discusses generalizations of the basic construction with and without interactive surface modification. Section 9 mentions possible extensions of the presented results and related open questions.
2 Examples and Properties
We use notation and terminology from combinatorial topology [10] to describe the surfaces and the algorithm that constructs them. In a nut-shell, that algorithm starts with the Delaunay complex of the input set and constructs an acyclic partial order over its simplices. This order is motivated by a continuous flow field in which every point is attracted by the Voronoi vertex that is nearest in a weighted sense. The Voronoi vertex at infinity corresponds to a dummy simplex in the relation, and the
3
reconstructed surface is obtained by sculpting away all predecessors of that dummy simplex. We begin by giving a few examples constructed by software implementing the algorithm.
Sample surfaces. In the simplest an¡£d¢ possibly most common case, the surface
constructed from a finite point set in is connected like a sphere, as in Figure 1. With our approach, it is possible to modify the construction and to introduce tunnels, as illustrated in Figure 2. There are also cases, in which the surface cannot be naturally closed and remains connected like a disk, as in Figure 3. Finally, if the points are lined up, it is possible that the surface reconstructed by our algorithm degenerates to a curve, as in Figure 4.
Figure 1: An engine block surface homeomorphic to a sphere.
In technical terms, the constructed surface is a simplicial complex of dimension 2 with the topology of a possibly pinched sphere. If forced by the distribution of the data points, the complex can be one- or zero-dimensional. We first introduce the relevant terminology and then describe the reconstructed surface in more detail.
Spaces and maps. All topological sp¡¢ac¡ es in this paper are subsets of Euclidean
space of some dimension , denoted b¡ y¡
induced by the Euclidean metric in .
. Without exception, we use the topology
The Euclidean distance between points £
and ¤ is denoted by ¥¦£ §¤¨¥ , and the norm of £ is the distance from the origin,
which is ¥©£¥ ¥©£ §¥ . Other than for Euclidean -dimensional space, we need
short notation for the -dimensional sphere and the -dimensional ball,
¡ £ ¡ ¡ "!$# ¥¦£¥ &%(' ) ¡ £ ¡ ¡ # ¥¦£¥ £ &%(0
4
Figure 2: The engine block surface in Figure 1 after pushing open a tunnel.
We refer to
a circle, the
¡ as the
0-sphere
-sphere and to ) ¡
is a pair of points,
as the and the
!-ball. For example, the 1-sphere is -sphere is the empty set. The
2-sphere is what we ordinarily call a sphere. The 2-ball is a closed disk, the 1-ball
is a closed interval, and the 0-ball is a point.
Topological spaces are compared via continuous functions referred to as maps.
¢¡¤£¦¥¨§ A homeomorphism,
, is a continuous bijection with continuous inverse.
£ § The inverse of a homeomorphism is again a homeomorphism. and are homeo-
£©§ morphic or topologically equivalent, denoted
, if there is a homeomorphism
¡£¥§ between them. An embedding is an injective map
whose restriction to
£ ! the image, , is a homeomorphism.
¢¡£ ¥!§ "#¡ A homotopy between two maps '
£$&% (')¥0§ " ! 1 ! " ! 2 ! ¢£ £ '
with £ '
£ and £"'
is a continuous function
£ for all £ . and
§ £435§ ¡£¥ § are homotopy equivalent, denoted by
, if there are maps
and
6 ¡)§7¥8£ [email protected] £ and homotopies between
and the identity for and between
9A6 § and the identity for . Two spaces have the same homotopy type if they
are homotopy equivalent. A space is contractible if it is homotopy equivalent to a
£B©¢§ £B3C§ point. Homotopy equivalence
that
implies
.
is
weaker
than
topological
equivalence,
in
the
sense
Simplicial complexes. We use combinatorial structures to represent topological
spaces in the computer. We begin by introducing the geometric elements that make
D up these structures. The convex hull of a finite collection of points is denoted as
EGFIHQP D & 2' . A -simplex, , is the convex hull of affinely independent points. T¡ h¢e
& ¦¨§)©&¤ dimension of is
. At most four points can be affinely independent in
and we have four types of simplices: vertices or 0-simplices, edges or 1-simplices,
5
Figure 3: Points on a saddle surface triangulated to form a patch homeomorphic to a disk.
Figure 4: Points on the moment curve connected to form a curve homeomorphic to an interval.
¡ EGFIHQP triangles or 2-simplices, and tetrahedra or 3-simplices. A simplex
¡ is a
& EGFIHQP D & ¡ D face of another simplex
, and is a coface of , if £¢ . We denote
¡ £ & & ¦ & this relationship by
§ H & & ¦ & faces, and the interior is
¦¥ .
The boundary of , ¤ , is the union of all proper §¤ . For example, the boundary of an edge
consists of its two endpoints and the interior is the open edge, without endpoints.
The boundary of a vertex is empty and the interior is the vertex itself.
& A simplicial complex, ¨ , is a finite collection of simplices such that §¨ and
¡ £ & ¡ & & & & implies §¨ , and ' © ¨ implies that © is either empty or a face
of both. The dimension of ¨ is the maximum dimension of any of its simplices.
¦(§)© A principal simplex has no proper coface in ¨ . For example, if ¨ then
& ¦¨§©¥& e ve¢ ry¨
tetrahedron in . The vertex
¨ is a set of ¨
priisnc ip"a! ¥l
simplex.
¨
A#s¨ ub# complex
is
a
%
simplicial complex
. ¨ is connected if
& for every non-trivial partition "! ¥ ¨ %$ !' & $ th# ere# is a simplex #¨ that has
& vertices in $ ! and in $ . The underlying space is ¨ £(0)¦132 . The interiors of
6
& simplices
a unique
partition the
¨ with £
H§ & u nd¦er¥ lyi.ng
space.
In
other
words,
for
every
£
#¨
# there is
¡ ¡ tpShlpaeextcc¨ioanlistsautihnbessse¡ etts, oaafnndcdotfhsauecbelicsno,ktmhoepfclaeloxsseimus.rpeloeTxfhaesustba¨sretois¡f tah¢ seims¨ eptisloetfxhseimsimnpalailclseeissmtispnultibhccieaolcmlcoposlmeedx-
¡ star that are disjoint from :
¡ & ¡£& ¢ ¥
¨ # % '
¡ ¡ £¥& £¥¤ ¡
¨ #
¡ %('
¡ & ¡ & ¡ ¦¨§
£¥¤©¢ ¥ # %(0
In other words, the link consists not belong to the (open) star of
¡ of all simplices in the closed star
any face of . Links can be used
of to
¡ that do
introduce
& combinatorial notions of interior
space that contains the complex,
and boundary. They a¡re¢
which in this paper is
defined relative to
. The interior of ¨
the is
the set of simplices, , whose links are homeomorphic to spheres of appropriate
dimension, and the boundary consists of all other simplices:
H © ¦¥ ¨ & ¨ # # ¦¨§ & # ) % ' H ¦ ¨ ¨ ¦¥ ¨ 0
In ¡ ¢ , the boundary of a simplicial complex consists of all simplices of dimension
2 or less that are not completely surrounded by tetrahedra.
Surface properties. Let ¢ ¡£¢ be finite. The solution to the surface reconstruc-
tion problem proposed in
¡ ¥ is what we call a pinched
this paper
" -sphere,
itshaatsiism, p# !lici#ailsctohme pimleaxg, e!
. of
Iats¡ mu¢ anpde# rlying
spa¡ c¢e
and every neighborhood of # contains an embedding of in . Another way
¡ ¥ ! ! to
e xpress¡
t¢hewliathtte¥'r#
condition
££
is that
¥)($
for every real
for every £
$& %
.
there is an embedding
As we will see in Section
6 — which contains the formal definition of ! — not every topological type of
a pinched 2-sphere can be realized by ! . Here we just list a few not necessarily
independent properties of ! :
(P1) ! ¥ ! ¢ .
(P2) !¡
(P3)
¢
is
c# o! nn#ecctoends.ists
of
0
2
'#
open components exactly one of which is
unbounded.
Lcoemt 1 plebme tehnet oufnb1 o,uthnadteids,c#o2 mp# one¡£n¢ t,6an1 d. lOetu24r al35go! rithbme aimcopmlicpitlleyxctroinasntgruuclatstisnugcthhea
complex 2 that satisfies the following again not necessarily independent properties:
(P4) ! ¥ 2 7 .
7
(P5) I# f 0 # then 2 7! .
(P6) 2 is contractible.
¦ (P7) !
2.
(P8) 2 may have principal simplices of dimension less than 3.
We also consider variants of the basic construction yielding complexes ! late property (P2) and complexes 2 that violate (P4) and (P6).
that vio-
3 Delaunay Complexes
The complexes ! and 2 of Section 2 are both constructed as subcomplexes of the
Delaunay complex of the data set. This section introduces Delaunay complexes and
mentions properties relevant to the discussions in this paper.
Voronoi cells and Delaunay simplices. Let be a finite set in ¡ ¢ . The Voronoi
cell of ¡ is
£ $£¢
£ ¡ ¢ # ¥¦£ ¡ ¥ ¥¦£ ¥¤ ¥ for all ¤ % 0
Let $§¦ $ ¢ # ¡ % for every £¢ . Any two Voronoi cells h¡ a¢ ve disjoint in-
teriors and the collection of all Voronoi cells, $©¨ , covers the entire . Throughout
this paper, we assume the generic case, in which no four points lie on a common
plane and no five points lie on a common sphere. The algorithmic justification of
this assumption is a simulated perturbation, as described in [5]. In the generic case,
two Voronoi cells are either disjoint or they meet along a common two-dimensional
face. Three cells either have no points in common or they meet along a common
line segment or half-line. Four cells either have no points in common or they meet
in a common point. Five or more cells have no points in common.
The intersection pattern among the Voronoi cells can be recorded using a simpli-
cial complex. More specifically, the Delaunay complex of , defined as
E(F HQP ¤
# $ ¦ %('
E(FIHQP is such a reco¡ r¢ d. The non-degeneracy assu# m pt¤ ion# implies that
¤
is a simplicial
c o"m! ¥ p lex¤ in
. Its underlying space is
. Whether or not a simplex belongs to
¤
, and its vertex set is can be decided by a
¡£¢
local geometric test. Call a sphere in empty if all points of lie on or outside
the sphere.
FACT 1. &
E(FIHQP¡
¤
iff there is an empty sphere that passes through all
points of .
& E ¦ ¥ &4! If is a tetrahedron then ! and there is a unique sph ere¤
& through the four points. We call the orthosphere of or .
passing contains exactly
a ll
¤
tetrahedra are the
whose orthospheres are empty. faces of these tetrahedra.
The
triangles,
edges,
and
vertices
in
8
Weighted points. In some circumstances, it is useful to assign real weights to the
points in . With the proper generalization of definitions, all results extend from
the¡ u¢ nwei¡ ghted to the more general weighted case, in which
is a finite subset ¡
$ of $ :
it
can
e.ithIterisbceotnhveenwieenigthttoedbepoaimntbi¡ gu ou¡ ¡£s ¢abou¡t
the or
meaning of a its projection
poi¡£nt¢
to
.
in In
either case,
¡ ! ¢ a point £
th¡ e¢
weight is from the
denoted by ¢ weighted point
¡
. The weighted square distance of
is §¢ £
¥¦£ ¡ ¥
¢ . Voronoi
cells and Delaunay simplices can be
EGFIHQP dista¥ n ce¤ for Euclidean distance. We
defined as#
still have
b efo¤ re,#
substituting weighted square . It is possible that ¡
a
"!
vertex
of
is
n¤ ot
equal iff its
to but rather Voronoi cell
a is
proper subset empty.
of
. Specifically,
is not
To extend the local criterion
£ ¤ tion of orthosphere. A sphere
expressed by with center
F act¡
1¢ ,
we need to and radius
generalize the nois orthogonal to
¥£ ¦ 2§¤ a weighted point ¡ if ¥ ¡ ¥
¨£ 2©¤ ¤ ¤ ¥ ¡ ¥ exceeds ¢
. Here,
¢
¡
, and it is further than orthogonal if and it is convenient to choose from the
set of non-negative multiples of the real and the imaginary units, 1 and . We
call a sphere empty if it is orthogonal to or further than orthogonal from all weighted
EGFIHQP points in .
FACT 2. &
¡ ¤
weighted points in .
iff there is an empty sphere orthogonal to all
Again we assume non-degeneracy. In the weighted case, this means that every four
& E(F H P weighted points have a unique sphere orthogonal to all of them, a¡nd no five points
have such a sphere. The orthosphere of a orthogonal to the four weighted points in
t.etra h¤ edrcoonntains
exa¤ ctly
is the sphere all tetrahedra
with empty orthosphere. The triangles, edges, and vertices in are the faces of
these tetrahedra.
2 Relative position. Call the non-empty intersection of
Voronoi cells an -
0£ £ ' cell, for & E(FIHQP an -cell iff
a¡nd
is
a
-simp. leAxnininter s¤ ec.tioWneoafrVe oinrotenroeistceedllisn
the
$ ¦ is
position
& of and relative to each other in space. Their affine hulls are orthogonal flats of
2 complementary dimension,
, that intersect at a point ¤ . In the assumed
§ H & 0& igseenietrhiecrccaosne,ta¤ inisedeiitnher ¥conotarin¤ ed in.tWheeindtiesrtiinogr uoifsh oforuitrlmieustouuatlslyideexc.luSsiimveilcaarlsye,s¤:
§ H '§ H & (R1) ¦¥ ¦¥ ,
§ H '§ H &0 § H & (R2) ¦¥ ¦¥ and ¥ ,
§ H '§ H &0 '§ H & (R3) ¦¥ ¦¥ and ¦¥ ,
§ H &¤ '§ H &¤ (R4) ¦¥
¦¥ .
Figure 5 illustrates all cases for all values of . For
, only Cases (R1) and
(R3) and for ¡ ! of points £
¡
¢
only Cases (R1) and (R2) are possible. The for which the sphere with center £ and radius §¢
-cell is the set
£ , with ¡ ,
9
y z z=y
y
y
z=y
z=y
z
z
z
z
z=y
y
z=y
y
z=y z=y
¢¡¤£ Figure 5: From left to right: Cases (R1), (R2), (R3), and (R4), and from top to bottom:
,
¥§¦©¨ 1, 2, and 3. In each case, the center of the smallest empty sphere orthogonal to all
is
and the intersection of the two affine hulls is .
is empty and orthogonal to all points in . The smallest such sphere is centered at
£ ¨ & the point closest to the point ¤ . This implies that for
,
the Cases (R2) and (R4) cannot occur unless the points are weighted. For 7" , all
four cases are possible even in the unweighted case.
4 Morse Functions The complex 2 of Section 2 is a subcomplex of ¤ constructed by collapsing
Delaunay simplices from the outside in. To decide which simplices to collapse and which not, we construct an acyclic relation among the Delaunay simplices, which is motivated by a particular family of Morse functions. This section constructs these functions after reviewing relevant concepts from Morse theory. The reader interested in a more complete account of that theory is referred to Milnor [14] or Wallace [16].
Vector fields and flow curves. We are interested in smooth functions ¡ ¡ ¢ ¥ ¡
that satisfy a few genericity assumptions. Smoothness means that is continuous and infinitely often differentiable, but we will see later that this can be weakened to twice differentiable or even only once differentiable and almost everywhere twice
10
Herbert Edelsbrunner
Abstract
Given a finite point set in ¡£¢ , the surface reconstruction problem asks for a surface
that passes through many but not necessarily all points. We describe an unambiguous definition of such a surface in geometric and topological terms, and sketch a fast algorithm for constructing it. Our solution overcomes past limitations to special point distributions and heuristic design decisions. Keywords. Computational geometry, computer graphics, geometric modeling; Delaunay complexes, Morse functions, vector fields, acyclic relations, collapsing, deleting.
1 Introduction
The original version of this paper was written in 1995. To preserve that version, we have limited modifications to minor stylistic changes and to the addition of a paragraph that accounts for the new and related work during the years from 1996 to 2001. All citations of work during these five years use letters rather than numbers in the citation.
Problem and solution. The input to the surface reconstruction problem is a finite set of points scattered in three-dimensional Euclidean space. The general task is to find a surface passing through the points. There are of course many possible such surfaces, and we would want one that in some sense is most reasonable and best represents the way the input points are distributed. We allow for the case that some points lie off the surface inside the bounded volume. We propose a solution that provides structural information in terms of a mesh or complex connecting the
¤
Then: Department of Computer Science, University of Illinois at Urbana-Champaign, and Raindrop Geomagic, Champaign-Urbana, Illinois, USA. Now: Department of Computer Science, Duke University, Durham, and Raindrop Geomagic, Research Triangle Park, North Carolina, USA.
1
points. Section 2 will be more specific about what exactly we mean by this and what properties we expect from the mesh.
The first part of our solution consists of a description of the surface in geometric and topological terms. There are minimum distance functions and ideas from Morse theory turning these functions into vector fields and cell decompositions. For generic data sets, this description is unambiguous and completely determines the surface. The second part of our solution is an efficient algorithm that constructs the defined surface. The algorithm is based on Delaunay complexes and extracts a subcomplex through repeated collapsing. All ideas and results generalize to any arbitrary fixed number of dimensions. For reasons of specificity, the discussion in this paper is exclusively three-dimensional.
Work prior to 1995. The surface reconstruction problem has a long history. Most of the previous work assumes some kind of additional structure given along with the data points. A common assumption is that the points lie on curves defined by slicing a surface with a collection of parallel planes [9, 13]. The surface reconstruction is reduced to a sequence of steps, each connecting two curves in contiguous planes.
Another common assumption is differentiability¡¡[11]. The surface is constructed
from patches defining diffeomorphisms between and local neighborhoods on the surface. Fairly dense point distributions are required to allow the reconstruction of tangents and normals.
We are interested in the general surface reconstruction problem that¡ a¢ dmits no
assumption other than that the input consists of finitely many points in . At the time of writing this paper in 1995, we found only three pieces of work studying the general problem. In two cases, the surface or shape is obtained from the threedimensional Delaunay complex of the input points. This is also the approach followed in this paper. Boissonnat [1] compromises the global nature of the approach by using local rules for removing simplices from the Delaunay complex. The resulting surfaces are somewhat unpredictable and not amenable to rational analysis. Edelsbrunner and Mu¨cke [6] use distance relationships to identify certain subcomplexes of the Delaunay complex as alpha shapes of the given data set. For uneven densities, these shapes tend to either exhibit a lack of detail in dense regions or gaps and holes in sparse regions. Rather than subcomplexes of the Delaunay complex, Veltkamp [15] uses two-parameter neighborhood graphs to form surfaces from points in space. Depending on the choice of the parameters the graphs may exhibit self-intersections or poor shape representation.
Development after 1995. The algorithm described in this paper has been implemented in 1996 at Raindrop Geomagic, which successfully commercialized it as geomagic Wrap. It is also described in U. S. Patent No. 6,3777,865, which has issued on April 23, 2002.
The surface reconstruction problem has enjoyed increasing popularity over the last few years, both in computer graphics and in computational geometry. A number of essentially two-dimensional algorithms that rely primarily on density and
2
smoothness assumptions of the data have been developed [C, E, F, J]. In parallel,
the use of three-dimensional Delaunay complexes has been refined [A, B, D, I]. The
focus of that work is the detailed study of Delaunay complexes for data sets that sat-
isfy density and smoothness assumptions, and to exploit their special structure for
surface reconstruction. Possibly surprisingly, neither development has come close
to reproducing the ideas presented in this paper.
From a completely different angle, Robin Forman’s development of a discrete
Morse theory for simplicial complexes [H] is related to work in this paper. Accord-
ing to Forman, a discrete Morse function is a map from the collection of simplices
¡ to the real numbers such that for every simplex the following two conditions hold:
¢¤£¥¡ ¦¨§©¥¢¦¨§©¡ ¢"!$# ¡%! (1) there is at most one face &'#¥¡ ¦(§)©&01¦¨§©¥¡321 &4!5£ ¡%! (2) there is at most one coface
with with
and
, and
and
.
The theory developed in this paper uses relations that correspond to functions violating these conditions and thus does not seem to fit into Forman’s framework. It would be interesting to elucidate the connection between the two approaches to a discrete Morse theory. Another recent development that resonates with the work in this paper is the introduction of persistent Betti numbers [G]. It relates to the discussion of granularity in Section 9, in which it is suggested to construct coarse-grained decompositions of the Delaunay complex by merging discrete stable manifolds, possibly by suppressing some of the less persistent critical points. Maybe the time has come to integrate all these ideas and to develop a hierarchical approach to surface reconstruction based on a more extensive use of algebraic structures developed in topology.
Outline. Section 2 displays sample results obtained with software implemented
at R¡ a¢ indrop Geomagic. Section 3 reviews Delaunay complexes for finite point sets
in . Section 4 reviews notions from Morse theory and constructs a family of Morse functions from local distance information. Section 5 derives an ordering principle for the Delaunay simplices from the Morse functions. Section 6 studies mechanisms to cluster simplices based on the ordering. Section 7 defines the basic surface construction as a sequence of collapses. Section 8 discusses generalizations of the basic construction with and without interactive surface modification. Section 9 mentions possible extensions of the presented results and related open questions.
2 Examples and Properties
We use notation and terminology from combinatorial topology [10] to describe the surfaces and the algorithm that constructs them. In a nut-shell, that algorithm starts with the Delaunay complex of the input set and constructs an acyclic partial order over its simplices. This order is motivated by a continuous flow field in which every point is attracted by the Voronoi vertex that is nearest in a weighted sense. The Voronoi vertex at infinity corresponds to a dummy simplex in the relation, and the
3
reconstructed surface is obtained by sculpting away all predecessors of that dummy simplex. We begin by giving a few examples constructed by software implementing the algorithm.
Sample surfaces. In the simplest an¡£d¢ possibly most common case, the surface
constructed from a finite point set in is connected like a sphere, as in Figure 1. With our approach, it is possible to modify the construction and to introduce tunnels, as illustrated in Figure 2. There are also cases, in which the surface cannot be naturally closed and remains connected like a disk, as in Figure 3. Finally, if the points are lined up, it is possible that the surface reconstructed by our algorithm degenerates to a curve, as in Figure 4.
Figure 1: An engine block surface homeomorphic to a sphere.
In technical terms, the constructed surface is a simplicial complex of dimension 2 with the topology of a possibly pinched sphere. If forced by the distribution of the data points, the complex can be one- or zero-dimensional. We first introduce the relevant terminology and then describe the reconstructed surface in more detail.
Spaces and maps. All topological sp¡¢ac¡ es in this paper are subsets of Euclidean
space of some dimension , denoted b¡ y¡
induced by the Euclidean metric in .
. Without exception, we use the topology
The Euclidean distance between points £
and ¤ is denoted by ¥¦£ §¤¨¥ , and the norm of £ is the distance from the origin,
which is ¥©£¥ ¥©£ §¥ . Other than for Euclidean -dimensional space, we need
short notation for the -dimensional sphere and the -dimensional ball,
¡ £ ¡ ¡ "!$# ¥¦£¥ &%(' ) ¡ £ ¡ ¡ # ¥¦£¥ £ &%(0
4
Figure 2: The engine block surface in Figure 1 after pushing open a tunnel.
We refer to
a circle, the
¡ as the
0-sphere
-sphere and to ) ¡
is a pair of points,
as the and the
!-ball. For example, the 1-sphere is -sphere is the empty set. The
2-sphere is what we ordinarily call a sphere. The 2-ball is a closed disk, the 1-ball
is a closed interval, and the 0-ball is a point.
Topological spaces are compared via continuous functions referred to as maps.
¢¡¤£¦¥¨§ A homeomorphism,
, is a continuous bijection with continuous inverse.
£ § The inverse of a homeomorphism is again a homeomorphism. and are homeo-
£©§ morphic or topologically equivalent, denoted
, if there is a homeomorphism
¡£¥§ between them. An embedding is an injective map
whose restriction to
£ ! the image, , is a homeomorphism.
¢¡£ ¥!§ "#¡ A homotopy between two maps '
£$&% (')¥0§ " ! 1 ! " ! 2 ! ¢£ £ '
with £ '
£ and £"'
is a continuous function
£ for all £ . and
§ £435§ ¡£¥ § are homotopy equivalent, denoted by
, if there are maps
and
6 ¡)§7¥8£ [email protected] £ and homotopies between
and the identity for and between
9A6 § and the identity for . Two spaces have the same homotopy type if they
are homotopy equivalent. A space is contractible if it is homotopy equivalent to a
£B©¢§ £B3C§ point. Homotopy equivalence
that
implies
.
is
weaker
than
topological
equivalence,
in
the
sense
Simplicial complexes. We use combinatorial structures to represent topological
spaces in the computer. We begin by introducing the geometric elements that make
D up these structures. The convex hull of a finite collection of points is denoted as
EGFIHQP D & 2' . A -simplex, , is the convex hull of affinely independent points. T¡ h¢e
& ¦¨§)©&¤ dimension of is
. At most four points can be affinely independent in
and we have four types of simplices: vertices or 0-simplices, edges or 1-simplices,
5
Figure 3: Points on a saddle surface triangulated to form a patch homeomorphic to a disk.
Figure 4: Points on the moment curve connected to form a curve homeomorphic to an interval.
¡ EGFIHQP triangles or 2-simplices, and tetrahedra or 3-simplices. A simplex
¡ is a
& EGFIHQP D & ¡ D face of another simplex
, and is a coface of , if £¢ . We denote
¡ £ & & ¦ & this relationship by
§ H & & ¦ & faces, and the interior is
¦¥ .
The boundary of , ¤ , is the union of all proper §¤ . For example, the boundary of an edge
consists of its two endpoints and the interior is the open edge, without endpoints.
The boundary of a vertex is empty and the interior is the vertex itself.
& A simplicial complex, ¨ , is a finite collection of simplices such that §¨ and
¡ £ & ¡ & & & & implies §¨ , and ' © ¨ implies that © is either empty or a face
of both. The dimension of ¨ is the maximum dimension of any of its simplices.
¦(§)© A principal simplex has no proper coface in ¨ . For example, if ¨ then
& ¦¨§©¥& e ve¢ ry¨
tetrahedron in . The vertex
¨ is a set of ¨
priisnc ip"a! ¥l
simplex.
¨
A#s¨ ub# complex
is
a
%
simplicial complex
. ¨ is connected if
& for every non-trivial partition "! ¥ ¨ %$ !' & $ th# ere# is a simplex #¨ that has
& vertices in $ ! and in $ . The underlying space is ¨ £(0)¦132 . The interiors of
6
& simplices
a unique
partition the
¨ with £
H§ & u nd¦er¥ lyi.ng
space.
In
other
words,
for
every
£
#¨
# there is
¡ ¡ tpShlpaeextcc¨ioanlistsautihnbessse¡ etts, oaafnndcdotfhsauecbelicsno,ktmhoepfclaeloxsseimus.rpeloeTxfhaesustba¨sretois¡f tah¢ seims¨ eptisloetfxhseimsimnpalailclseeissmtispnultibhccieaolcmlcoposlmeedx-
¡ star that are disjoint from :
¡ & ¡£& ¢ ¥
¨ # % '
¡ ¡ £¥& £¥¤ ¡
¨ #
¡ %('
¡ & ¡ & ¡ ¦¨§
£¥¤©¢ ¥ # %(0
In other words, the link consists not belong to the (open) star of
¡ of all simplices in the closed star
any face of . Links can be used
of to
¡ that do
introduce
& combinatorial notions of interior
space that contains the complex,
and boundary. They a¡re¢
which in this paper is
defined relative to
. The interior of ¨
the is
the set of simplices, , whose links are homeomorphic to spheres of appropriate
dimension, and the boundary consists of all other simplices:
H © ¦¥ ¨ & ¨ # # ¦¨§ & # ) % ' H ¦ ¨ ¨ ¦¥ ¨ 0
In ¡ ¢ , the boundary of a simplicial complex consists of all simplices of dimension
2 or less that are not completely surrounded by tetrahedra.
Surface properties. Let ¢ ¡£¢ be finite. The solution to the surface reconstruc-
tion problem proposed in
¡ ¥ is what we call a pinched
this paper
" -sphere,
itshaatsiism, p# !lici#ailsctohme pimleaxg, e!
. of
Iats¡ mu¢ anpde# rlying
spa¡ c¢e
and every neighborhood of # contains an embedding of in . Another way
¡ ¥ ! ! to
e xpress¡
t¢hewliathtte¥'r#
condition
££
is that
¥)($
for every real
for every £
$& %
.
there is an embedding
As we will see in Section
6 — which contains the formal definition of ! — not every topological type of
a pinched 2-sphere can be realized by ! . Here we just list a few not necessarily
independent properties of ! :
(P1) ! ¥ ! ¢ .
(P2) !¡
(P3)
¢
is
c# o! nn#ecctoends.ists
of
0
2
'#
open components exactly one of which is
unbounded.
Lcoemt 1 plebme tehnet oufnb1 o,uthnadteids,c#o2 mp# one¡£n¢ t,6an1 d. lOetu24r al35go! rithbme aimcopmlicpitlleyxctroinasntgruuclatstisnugcthhea
complex 2 that satisfies the following again not necessarily independent properties:
(P4) ! ¥ 2 7 .
7
(P5) I# f 0 # then 2 7! .
(P6) 2 is contractible.
¦ (P7) !
2.
(P8) 2 may have principal simplices of dimension less than 3.
We also consider variants of the basic construction yielding complexes ! late property (P2) and complexes 2 that violate (P4) and (P6).
that vio-
3 Delaunay Complexes
The complexes ! and 2 of Section 2 are both constructed as subcomplexes of the
Delaunay complex of the data set. This section introduces Delaunay complexes and
mentions properties relevant to the discussions in this paper.
Voronoi cells and Delaunay simplices. Let be a finite set in ¡ ¢ . The Voronoi
cell of ¡ is
£ $£¢
£ ¡ ¢ # ¥¦£ ¡ ¥ ¥¦£ ¥¤ ¥ for all ¤ % 0
Let $§¦ $ ¢ # ¡ % for every £¢ . Any two Voronoi cells h¡ a¢ ve disjoint in-
teriors and the collection of all Voronoi cells, $©¨ , covers the entire . Throughout
this paper, we assume the generic case, in which no four points lie on a common
plane and no five points lie on a common sphere. The algorithmic justification of
this assumption is a simulated perturbation, as described in [5]. In the generic case,
two Voronoi cells are either disjoint or they meet along a common two-dimensional
face. Three cells either have no points in common or they meet along a common
line segment or half-line. Four cells either have no points in common or they meet
in a common point. Five or more cells have no points in common.
The intersection pattern among the Voronoi cells can be recorded using a simpli-
cial complex. More specifically, the Delaunay complex of , defined as
E(F HQP ¤
# $ ¦ %('
E(FIHQP is such a reco¡ r¢ d. The non-degeneracy assu# m pt¤ ion# implies that
¤
is a simplicial
c o"m! ¥ p lex¤ in
. Its underlying space is
. Whether or not a simplex belongs to
¤
, and its vertex set is can be decided by a
¡£¢
local geometric test. Call a sphere in empty if all points of lie on or outside
the sphere.
FACT 1. &
E(FIHQP¡
¤
iff there is an empty sphere that passes through all
points of .
& E ¦ ¥ &4! If is a tetrahedron then ! and there is a unique sph ere¤
& through the four points. We call the orthosphere of or .
passing contains exactly
a ll
¤
tetrahedra are the
whose orthospheres are empty. faces of these tetrahedra.
The
triangles,
edges,
and
vertices
in
8
Weighted points. In some circumstances, it is useful to assign real weights to the
points in . With the proper generalization of definitions, all results extend from
the¡ u¢ nwei¡ ghted to the more general weighted case, in which
is a finite subset ¡
$ of $ :
it
can
e.ithIterisbceotnhveenwieenigthttoedbepoaimntbi¡ gu ou¡ ¡£s ¢abou¡t
the or
meaning of a its projection
poi¡£nt¢
to
.
in In
either case,
¡ ! ¢ a point £
th¡ e¢
weight is from the
denoted by ¢ weighted point
¡
. The weighted square distance of
is §¢ £
¥¦£ ¡ ¥
¢ . Voronoi
cells and Delaunay simplices can be
EGFIHQP dista¥ n ce¤ for Euclidean distance. We
defined as#
still have
b efo¤ re,#
substituting weighted square . It is possible that ¡
a
"!
vertex
of
is
n¤ ot
equal iff its
to but rather Voronoi cell
a is
proper subset empty.
of
. Specifically,
is not
To extend the local criterion
£ ¤ tion of orthosphere. A sphere
expressed by with center
F act¡
1¢ ,
we need to and radius
generalize the nois orthogonal to
¥£ ¦ 2§¤ a weighted point ¡ if ¥ ¡ ¥
¨£ 2©¤ ¤ ¤ ¥ ¡ ¥ exceeds ¢
. Here,
¢
¡
, and it is further than orthogonal if and it is convenient to choose from the
set of non-negative multiples of the real and the imaginary units, 1 and . We
call a sphere empty if it is orthogonal to or further than orthogonal from all weighted
EGFIHQP points in .
FACT 2. &
¡ ¤
weighted points in .
iff there is an empty sphere orthogonal to all
Again we assume non-degeneracy. In the weighted case, this means that every four
& E(F H P weighted points have a unique sphere orthogonal to all of them, a¡nd no five points
have such a sphere. The orthosphere of a orthogonal to the four weighted points in
t.etra h¤ edrcoonntains
exa¤ ctly
is the sphere all tetrahedra
with empty orthosphere. The triangles, edges, and vertices in are the faces of
these tetrahedra.
2 Relative position. Call the non-empty intersection of
Voronoi cells an -
0£ £ ' cell, for & E(FIHQP an -cell iff
a¡nd
is
a
-simp. leAxnininter s¤ ec.tioWneoafrVe oinrotenroeistceedllisn
the
$ ¦ is
position
& of and relative to each other in space. Their affine hulls are orthogonal flats of
2 complementary dimension,
, that intersect at a point ¤ . In the assumed
§ H & 0& igseenietrhiecrccaosne,ta¤ inisedeiitnher ¥conotarin¤ ed in.tWheeindtiesrtiinogr uoifsh oforuitrlmieustouuatlslyideexc.luSsiimveilcaarlsye,s¤:
§ H '§ H & (R1) ¦¥ ¦¥ ,
§ H '§ H &0 § H & (R2) ¦¥ ¦¥ and ¥ ,
§ H '§ H &0 '§ H & (R3) ¦¥ ¦¥ and ¦¥ ,
§ H &¤ '§ H &¤ (R4) ¦¥
¦¥ .
Figure 5 illustrates all cases for all values of . For
, only Cases (R1) and
(R3) and for ¡ ! of points £
¡
¢
only Cases (R1) and (R2) are possible. The for which the sphere with center £ and radius §¢
-cell is the set
£ , with ¡ ,
9
y z z=y
y
y
z=y
z=y
z
z
z
z
z=y
y
z=y
y
z=y z=y
¢¡¤£ Figure 5: From left to right: Cases (R1), (R2), (R3), and (R4), and from top to bottom:
,
¥§¦©¨ 1, 2, and 3. In each case, the center of the smallest empty sphere orthogonal to all
is
and the intersection of the two affine hulls is .
is empty and orthogonal to all points in . The smallest such sphere is centered at
£ ¨ & the point closest to the point ¤ . This implies that for
,
the Cases (R2) and (R4) cannot occur unless the points are weighted. For 7" , all
four cases are possible even in the unweighted case.
4 Morse Functions The complex 2 of Section 2 is a subcomplex of ¤ constructed by collapsing
Delaunay simplices from the outside in. To decide which simplices to collapse and which not, we construct an acyclic relation among the Delaunay simplices, which is motivated by a particular family of Morse functions. This section constructs these functions after reviewing relevant concepts from Morse theory. The reader interested in a more complete account of that theory is referred to Milnor [14] or Wallace [16].
Vector fields and flow curves. We are interested in smooth functions ¡ ¡ ¢ ¥ ¡
that satisfy a few genericity assumptions. Smoothness means that is continuous and infinitely often differentiable, but we will see later that this can be weakened to twice differentiable or even only once differentiable and almost everywhere twice
10