# 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 ﬁnite point set in ¡£¢ , the surface reconstruction problem asks for a surface

that passes through many but not necessarily all points. We describe an unambiguous deﬁnition 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 ﬁelds, acyclic relations, collapsing, deleting.

1 Introduction

The original version of this paper was written in 1995. To preserve that version, we have limited modiﬁcations 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 ﬁve years use letters rather than numbers in the citation.

Problem and solution. The input to the surface reconstruction problem is a ﬁnite set of points scattered in three-dimensional Euclidean space. The general task is to ﬁnd 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 speciﬁc about what exactly we mean by this and what properties we expect from the mesh.

The ﬁrst 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 ﬁelds and cell decompositions. For generic data sets, this description is unambiguous and completely determines the surface. The second part of our solution is an efﬁcient algorithm that constructs the deﬁned surface. The algorithm is based on Delaunay complexes and extracts a subcomplex through repeated collapsing. All ideas and results generalize to any arbitrary ﬁxed number of dimensions. For reasons of speciﬁcity, 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 deﬁned 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 deﬁning 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 ﬁnitely 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 reﬁned [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 ﬁt 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 ﬁnite 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 deﬁnes the basic surface construction as a sequence of collapses. Section 8 discusses generalizations of the basic construction with and without interactive surface modiﬁcation. 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 ﬂow ﬁeld in which every point is attracted by the Voronoi vertex that is nearest in a weighted sense. The Voronoi vertex at inﬁnity 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 ﬁnite 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 ﬁrst 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 ﬁnite collection of points is denoted as

EGFIHQP D & 2' . A -simplex, , is the convex hull of afﬁnely independent points. T¡ h¢e

& ¦¨§)©&¤ dimension of is

. At most four points can be afﬁnely 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 ﬁnite 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

deﬁned 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 ﬁnite. 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 deﬁnition 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 satisﬁes 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 ﬁnite 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 ﬁve points lie on a common sphere. The algorithmic justiﬁcation 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 speciﬁcally, the Delaunay complex of , deﬁned 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 deﬁnitions, all results extend from

the¡ u¢ nwei¡ ghted to the more general weighted case, in which

is a ﬁnite 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

deﬁned 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

. Speciﬁcally,

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 ﬁve 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 afﬁne hulls are orthogonal ﬂats 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 afﬁne 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 ﬁelds and ﬂow curves. We are interested in smooth functions ¡ ¡ ¢ ¥ ¡

that satisfy a few genericity assumptions. Smoothness means that is continuous and inﬁnitely 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 ﬁnite point set in ¡£¢ , the surface reconstruction problem asks for a surface

that passes through many but not necessarily all points. We describe an unambiguous deﬁnition 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 ﬁelds, acyclic relations, collapsing, deleting.

1 Introduction

The original version of this paper was written in 1995. To preserve that version, we have limited modiﬁcations 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 ﬁve years use letters rather than numbers in the citation.

Problem and solution. The input to the surface reconstruction problem is a ﬁnite set of points scattered in three-dimensional Euclidean space. The general task is to ﬁnd 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 speciﬁc about what exactly we mean by this and what properties we expect from the mesh.

The ﬁrst 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 ﬁelds and cell decompositions. For generic data sets, this description is unambiguous and completely determines the surface. The second part of our solution is an efﬁcient algorithm that constructs the deﬁned surface. The algorithm is based on Delaunay complexes and extracts a subcomplex through repeated collapsing. All ideas and results generalize to any arbitrary ﬁxed number of dimensions. For reasons of speciﬁcity, 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 deﬁned 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 deﬁning 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 ﬁnitely 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 reﬁned [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 ﬁt 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 ﬁnite 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 deﬁnes the basic surface construction as a sequence of collapses. Section 8 discusses generalizations of the basic construction with and without interactive surface modiﬁcation. 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 ﬂow ﬁeld in which every point is attracted by the Voronoi vertex that is nearest in a weighted sense. The Voronoi vertex at inﬁnity 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 ﬁnite 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 ﬁrst 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 ﬁnite collection of points is denoted as

EGFIHQP D & 2' . A -simplex, , is the convex hull of afﬁnely independent points. T¡ h¢e

& ¦¨§)©&¤ dimension of is

. At most four points can be afﬁnely 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 ﬁnite 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

deﬁned 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 ﬁnite. 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 deﬁnition 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 satisﬁes 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 ﬁnite 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 ﬁve points lie on a common sphere. The algorithmic justiﬁcation 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 speciﬁcally, the Delaunay complex of , deﬁned 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 deﬁnitions, all results extend from

the¡ u¢ nwei¡ ghted to the more general weighted case, in which

is a ﬁnite 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

deﬁned 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

. Speciﬁcally,

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 ﬁve 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 afﬁne hulls are orthogonal ﬂats 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 afﬁne 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 ﬁelds and ﬂow curves. We are interested in smooth functions ¡ ¡ ¢ ¥ ¡

that satisfy a few genericity assumptions. Smoothness means that is continuous and inﬁnitely 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