# Size Complexity of Volume Meshes vs. Surface Meshes - Don

## Transcript Of Size Complexity of Volume Meshes vs. Surface Meshes - Don

Size Complexity of Volume Meshes vs. Surface Meshes ∗

Benoˆıt Hudson Toyota Technological Institute, Chicago

[email protected]

Gary L. Miller Todd Phillips Don Sheehy Carnegie Mellon University

{glmiller,tp517,dsheehy}@cs.cmu.edu

July 3, 2008. (Under Submission)

Abstract

Typical volume meshes in three dimensions are designed to conform to an underlying two-dimensional surface mesh, with volume mesh element size growing larger away from the surface. The surface mesh may be uniformly spaced or highly graded, and may have ﬁne resolution due to extrinsic mesh size concerns. When we desire that such a volume mesh have good aspect ratio, we require that some spaceﬁlling scaﬀold vertices be inserted oﬀ the surface. We analyze the number of scaﬀold vertices in a setting that encompasses many existing volume meshing algorithms. We show that under simple preconditions, the number of scaﬀold vertices will be linear in the number of surface vertices.

1 Introduction

Given a surface mesh, many scientiﬁc computing and graphics applications will want to produce a volume mesh. Conversely, to build a surface mesh from another description of an input geometry, one might temporarily build a point location structure such as an oct-tree, which is a volume mesh. A natural question arises: can we relate the size of the surface mesh to the size of the volume mesh? A volume mesh will obviously have more vertices than the corresponding surface mesh, but in most settings, the spacing between vertices should grow quickly away from the surface. Since the density of the volume mesh is driven only by the surface, it is intuitive that the surface vertices should dominate in quantity. Our main result is to show that given a surface mesh in a well-proportioned domain, the total number of vertices in the volume is linear in the number of vertices on the surface. We will make this statement speciﬁc later as the Scaﬀold Theorem (Theorem 3.1).

This result has immediate and important ramiﬁcations concerning the asymptotic work and space of a large host of existing meshing and surface reconstruction algorithms. For example, in volume meshing, the user may specify a closed surface and ask for its interior to be meshed. Typical algorithms enclose the surface in a bounding box that contains the closed surface, incrementally add points until the surface is recovered and the volume mesh has good quality, then strip away the exterior volume vertices (see Figure 1). The surface and interior vertices are then returned to the user. This approach is widespread and is used for many two-, three-, and higher-dimensional meshing algorithms [BEG94, ABE98, CDE+00, ELM+00, She98, MV00, U¨ ng04, MPW02, HMP06, CDR07]. The work and space complexity of these algorithms is output-sensitive and depends on the number of exterior vertices, even though these vertices are transient. Our new analysis is the ﬁrst to control this exterior work. Since we show that the number of transient vertices is bounded by

∗This work was supported in part by the National Science Foundation under grants ACI 0086093, CCR-0085982 and CCR0122581.

1

Figure 1: Incremental mesh reﬁnement algorithms ﬁrst generate a mesh over a bounding box (left), then remove the scaﬀold vertices and elements (center). Some applications may be interested in only the surface mesh (right). The (one-dimensional) Lake Superior surface shown mesh has 530 surface vertices. The volume mesh shown has 1072 total volume vertices; 258 interior and 284 exterior. We oﬀer the ﬁrst theoretical analysis of the costs of this scaﬀolding.

the surface vertices, this for the ﬁrst time implies that these algorithms run output-sensitively with respect to the true user-desired output.

In the rest of this work we make our results precise. A good deal of care is taken to ensure the generality of these results, so that this analysis may be applied to many of the existing meshing algorithms with theoretical guarantees. Our proofs are in two parts. In the ﬁrst part, we prove that if a good-quality volume mesh respects a surface, the volume vertices outnumber the surface vertices by only a constant. Our deﬁnition of respecting a surface is much looser than that of most prior work: the Voronoi cells of the surface vertices must cover the surface, but there is no topological requirement. In addition, our deﬁnition of a surface is extremely loose; it need not be manifold, or even connected. Additionally, our surface need not be d − 1 dimensional: for instance, it could be a curve in 3D. Our only requirements are that the surface have a bounded number of connected components, and that each connected component of the surface have diameter within a constant factor of the diameter of the bounding domain.

In the second part, we show how this result relates to standard concepts from mesh reﬁnement and surface reconstruction. In particular, we show that our result proves that a volume mesh of an -net of a surface is only a constant factor larger than the surface. We also show that many prior quality mesh reﬁnement algorithms are susceptible to our analysis. This implies that they still run in the time (and memory usage) bounds they claim, even when the volume actually meshed is larger than what the user asked to mesh.

2 Preliminary Geometric Deﬁnitions

In this paper, we assume there exists a surface S embedded in Rd. It need not be connected. Let D be the minimum diameter of any connected component of S, where the diameter is the maximum Euclidean distance between two points in the component. We require that the diameter of all other components, and the diameter of S, be in Θ(D). Around S there is a compact and connected domain Ω with S ⊂ Ω ⊂ Rd. Typically, Ω will be a box or a hypercube. The diameter of Ω must be in Θ(D).

Let Γd denote the volume of the unit ball in Rd. For x ∈ Rd and r ∈ R, let B(x, r) be the open ball centered at x or radius r (whose volume is given by Γd rd.)

Suppose we have a set of points (vertices) M ⊂ Ω. A vertex-set M induces a local feature size function fM : Ω → R. At a point x ∈ Ω, the local feature size is the distance from x to the second-nearest vertex. We frequently use the fact that fM is 1-Lipschitz: that is, fM(x) ≤ fM(y) + |x − y| for all x and y in Rd (this is easily veriﬁed by the triangle inequality. At a vertex v ∈ M, the local feature size coincides with the distance

2

VM (v)

rM (v) v

RM (v)

x u

VM (u)

Figure 2: The Voronoi cells of two vertices u and v in a vertex-set M (not pictured). The radii of the inner-ball and outer-ball of v are labeled. The point x is 0.9-medial.

to the nearest neighbour, which we denote NNM(v). Given the vertex-set M, we denote by VM(v) the closed Voronoi cell of v: those points in Rd for which

no vertex in M is closer than is v. We identify two natural balls with v: the inner-ball bM(v) is the largest ball centered at v that is contained within VM(v), while the outer-ball BM(v) is the smallest ball centered at v that contains all of VM(v) ∩ Ω. We denote by rM(v) and RM(v) their respective radii (i.e. BM(v) = B(v, RM(v)).) See Figure 2.

2.1 Well-spaced, Well-paced, and Medial Points

If there is a constant τ for which every v in a vertex-set M, has the property RM(v) ≤ τrM(v), then we say that v is τ-well-spaced. Loosely, this implies that the VM(v) ∩ Ω is roundly shaped and that v is roughly centered. Figure 3(right) shows a set of well-spaced points; contrast this with the vertices of Figure 4(left).

The problem of scaﬀolding a surface mesh with a volume mesh is that of ﬁnding a minimal well-spaced superset (volume mesh) M of a vertex-set (surface mesh) N.

We will make use of a theorem from [MPS08]. First, we introduce some relevant deﬁnitions. The boundaries of the Voronoi cells of each vertex in M form the medial axis of M. Miller et al [MPS08] generalize this and say that a point x is θ-medial with respect to M if it lies near the medial axis, in the sense that NNM(x) ≥ θ fM(x). Notice that whenever we had a point x to a set M, it will decrease the feature-size fM in the vicinity of x. A key observation is that adding a θ-medial point will only decrease the feature-size by a constant amount.

Given an arbitrary vertex-set N, and an ordered set of vertices E ≡ v1, . . . , vk , we say that E is a θwell-paced extension of N if v1 is a θ-medial point of N, and each vi is a θ-medial point of N ∪ {v1 . . . vi−1}. Informally, the name arises from the fact that the local feature size shrinks only slowly after each insertion.

Well-paced extensions are not well-spaced in general, but they have useful similarities to surface meshes. We now state for completeness the Well-Pacing Theorem ([MPS08], Corollary 3).

Theorem 2.1 (Well-Pacing Theorem) There is a constant C2.1, such that if N is a well-paced extension of a well-spaced set, then there exists a well-spaced superset M ⊃ N, with |M| ≤ C2.1|N|.

(For Review Purposes: [MPS08] will appear in August. Appendix section C contains relevant proof details. )

3

3 Scaﬀold Theorem

3.1 Overview

Our main result is the Scaﬀold Theorem 3.1, showing that given a volume mesh M with underlying surface mesh N, |M| is bounded above by a constant times the size of |N|. (Informally, |M| |N|.) Section 3.2 deﬁnes the formal setting in where Theorem applies.

The easiest proof would be to show that N can be written as a well-paced extension of a well-spaced set, then we could simply apply the Well-Pacing Theorem 2.1 to directly bound |M|. This is diﬃcult, so instead we deﬁne the concept of a spacing-equivalent surface mesh N , and show that one exists (Theorem 3.6). We can then construct a scaﬀolding volume mesh M for N . The proof then proceeds as three straightforward lemmas (3.3, 3.4, and 3.5). First, Lemma 3.3 shows that M M . This follows because the surface meshes N and N are roughly equivalent, so then their associated scaﬀolding volume meshes are also roughly equivalent. Next, Lemma 3.4 applies Theorem 2.1 to show that M N . Lastly, Lemma 3.5 shows that N N and follows simply by the spacing-equivalence of N . Putting these together yields M M N N. We now proceed with a formal proof.

3.2 Deﬁnitions: Scaﬀold Mesh and Seeded Surface Mesh

Suppose we are given a domain Ω as in Section 2. Further suppose we are given a “surface” S ⊂ Ω. We

require only that S is a closed subset. Suppose we have a ﬁnite vertex-set M ⊂ Ω. Deﬁne the surface vertices

as N = M ∩ S. To capture the notion that the sizing of this point set is solely due to the surface, we wish to

relate the Voronoi cells of M to the feature-size due to N. Formally, the input must satisfy the following two

conditions:

∃ α+ ∈ (0, ∞), ∀ m ∈ M, RM(m) ≤ α+ fN(m)

(1)

∃ α− ∈ (0, 1), ∀ m ∈ M, rM(m) ≥ α− fN(m)

(2)

Note this implicitly implies that M is a well-spaced set of vertices, with R(m)/r(m) ≤ α+/α−. When M and N satisfy conditions (1) and (2), we will say that M is an α-scaﬀolding volume mesh of the set N in Ω. We further require that the surface vertices N cover S in the following sense:

S ⊂ VM(n)

(3)

n∈N

Lastly, we require that the volume being ﬁlled is well-proportioned to the underlying surface. We accomplish this by requiring the existence of a seed N0 ⊂ N, The seed N0 must contain two vertices in each connected component of S and must be a well-spaced set of points. Formally:

For each connected component T ⊂ S, ∃p, q ∈ N0 ∩ T , s.t. p q

(4)

N0 is ρ-well-spaced, i.e.∃ρ ∈ (1, ∞)∀n ∈ N0, RN0(n) ≤ ρrN0(n)

(5)

If a set N with scaﬀolding volume mesh M meets conditions (3)-(5), then we say that N is a seeded surface mesh of S in Ω. Figures 3 and 4 illustrate these deﬁnitions.

3.3 Deﬁnitions: Spacing-Equivalent Sets

Suppose N ⊂ S is a vertex-set. Consider a vertex-set N ⊂ S that satisﬁes the following two conditions:

∃ β+ ∈ (0, ∞), ∀ s ∈ S, fN (s) ≤ β+ fN(s)

(6)

∃ β− ∈ (0, β+), ∀ s ∈ S, fN (s) ≥ β− fN(s)

(7)

4

Figure 3: The deﬁnitions of Section 3.2 illustrated abstractly. Left, a surface S is composed of both black shapes, with the domain Ω shaded. Center, vertices form a volume mesh M of Ω. The subset of surface vertices N are shown in black, with the volume vertices in white. Note how the density of the volume vertices is driven only by the density of surfaces vertices. Right, a possible seed N0, containing at least two points from each component of the surface S. Notice the four points are well-spaced and have quality Voronoi cells (shown in dashed lines).

We then say that such an N is β-spacing-equivalent to N on S. Theorem 3.6 will show that a seeded surface mesh N (with seed N0) always has a β-spacing-equivalent set N , with the additional property that N is also a (1/3)-well-paced extension of the seed N0. For any vertex-set N , it is possible to construct (using oﬀ the shelf algorithms [Rup95]) a well-spaced superset of vertices M that is a γ-scaﬀolding volume mesh, for some γ determined by the algorithm selected. This mesh M need not be aware of the surface at

all, since we will not require that N be a seeded surface mesh.

3.4 Scaﬀold Theorem Proof

Theorem 3.1 (Scaﬀold Theorem) Suppose M is an α-scaﬀolding volume mesh of N, and that N is a seeded surface mesh. Then there exists a constant C3.1 depending only on α+ and α− such that:

|M| ≤ C3.1|N|

The main theorem will follow immediately from the existence of a spacing-equivalent surface mesh (Theorem 3.6) and then composing Lemmas 3.3, 3.4, and 3.5. The proof begins with a small technical lemma with the goal of extending spacing-equivalence to the entire domain Ω, since it is only guaranteed on S.

Lemma 3.2 Suppose N is a surface mesh as in Section 3.2 and N is a β-spacing-equivalent vertex-set,

then:

∀ x ∈ Ω, fN (x) ≤ (1 + 2β+) fN(x)

Proof: Let x ∈ Ω. Let s ∈ S be a point on S with minimum Euclidean distance to x (s exists by the closure of S.) Because N ⊂ S, we have fN(x) ≥ |x − s|. Combining this fact with the Lipschitz conditions and condition (6), we ﬁnd:

fN (x) ≤ fN (s) + |x − s| ≤ β+ fN(s) + |x − s| ≤ β+( fN(x) + |x − s|) + |x − s| ≤ (1 + 2β+) fN(x) (8)

Using the previous lemma, we can now show that an induced scaﬀold M of a spacing-equivalent set N is at least as large (up to a constant) as the scaﬀold M of the original set N. (A bound in the other direction is also true with diﬀering constants, but we will not need it.)

5

Figure 4: Examples of violations of the conditions in Section 3.2. Left, when the surface S has disproportionately small components, it will be too costly to ﬁll the volume in a way that resolves these small surface features. Note that no seed can exist in this example. An attempted seed is shown, but as the surface components grow relatively small, there is no way to ﬁt two points on each component in a way that is well-spaced. Center, this volume mesh is not a scaﬀold mesh, because the sizing is not driven by the surface. The sink in the lower-center could contain arbitrarily many volume vertices. Note how this violates equation (2). Right, If the surface vertices do not cover S as in equation 3, then there could be a small surface feature requiring many volume vertices to resolve without having to add any more surface vertices. Note that a seed still exists in this example.

Lemma 3.3 Suppose M is an α-scaﬀolding volume mesh of N as in Section 3.2, and suppose M scaﬀolding volume mesh for a β-spacing-equivalent surface mesh N , then:

|M| ≤ C3.3|M |

where

2(1 + 2β+)γ+ d

C3.3 =

α−γ−

is a γ-

Proof: The proof is a packing argument showing that if we partition the vertices M into the Voronoi cells VM , no cell receives more than a constant-sized portion of M. There are disjoint empty balls around the vertices of M with radii that are lower bounded by fN which lower bounds fN (by Lemma 3.2). But fN also upper bounds the size of the Voronoi cells of M because it is a γ-scaﬀolding volume mesh of N . A detailed proof is given in the appendix.

Lemma 3.4 Suppose M is a γ-scaﬀolding volume mesh of a N , and that N is a well-paced extension of a well-spaced seed, then:

|M | ≤ C3.4|N |

Proof: This is a direct application of the Well-Pacing Theorem 2.1. The constant C3.4 will be inversely proportional to γ−.

Lemma 3.5 Suppose N mesh M, then we have:

is β-spacing-equivalent to a seeded surface mesh N with α-scaﬀolding volume

|N | ≤ C3.5|N|

where

4α+ d C3.5 = α−β−

Proof: Lemma 3.5 follows from a packing argument and the proof is similar Lemma 3.3. See Appendix for details.

6

3.5 Existence of Spacing-Equivalent Sets

Theorem 3.6 (Spacing-Equivalent Existence) Suppose N is a seeded surface mesh of S in Ω (with seed N0) as speciﬁed by Section 3.2. Then there exists a β-spacing-equivalent N that is a (1/3)-well-paced extension of N0, for any β+ ∈ (0, 1] and β− ∈ (0, β+/17).

Proof: Let N, N0, S, β+, and β− be given satisfying the hypothesis of the theorem.

according to the following algorithm:

Begin with the seed N0 and a counter i, initially i = 0. While ∃x ∈ S such that fNi(x) > β+ fN(x), let p ∈ Ni such that x ∈ VN (p):

Proof is by construction

1. If x bNi(p). Set Ni+1 = {x} ∪ Ni. 2. If x ∈ bNi(p). Let y ∈ ∂bNi(p) ∩ S. (Note y exists by 4.) Set Ni+1 = {y} ∪ Ni. 3. Increment i.

The ﬁniteness of N guarantees this will terminate at some index I. Take N = NI. First, we claim that any points added to Ni is (1/3)-medial wrt Ni. Consider a point x on any iteration i of the loop. Let q ∈ Ni be the nearest neighbor of p. If x is inserted in Step 1.:

fNi(x) ≤ |x − p| + fNi(p) = |x − p| + 2rNi(p) ≤ 3|x − p| = 3NNNi(x)

so x is (1/3)-medial. If y is inserted in Step 2., we have: fNi(y) ≤ |y − p| + fNi(p) = 3|y − p| = 3NNNi(y)

so y is (1/3)-medial. Thus N is a well-paced extension of the well-spaced N0. It remains to show that N is β-spacing-equivalent to N, namely that conditions (6) and (7) hold. Clearly, the upper bound condition (6) holds by construction. Either there are no more violations of (6)

or N = S, but the latter would clearly violate ﬁniteness of N. The proof of condition (7) is more subtle but follows similar arguments from previous work [Rup95]. We will use the following lemma to show condition (7).

Lemma 3.7 Suppose x ∈ N is inserted at iteration i (i.e. x ∈ Ni+1 − Ni), then: β+

NNNi(x) > fN(x) 7

Note that this Lemma would imply the immediate corollary:

Corollary 3.8

β+ ∀x ∈ N , fN (x) > fN(x)

8

Proof of corollary: Let x ∈ N (iteration i) be given and take y ∈ N (iteration j) s.t. |x − y| = NNN (x). If i > j , then we simply apply the lemma directly:

β+

β+

NNN (x) = NNNi(x) > fN(x) > fN(x)

7

8

If i < j, then we use Lipschitz of fN and apply the lemma to y:

7

7

8

8

fN(x) ≤ fN(y) + |x − y| < β+ NNNj(y) + |x − y| ≤ β+ |x − y| + |x − y| < β+ |x − y| = β+ NNN (x)

7

We return to proving Lemma 3.7. Proof is by induction. Note that the corollary always holds inductively

whenever the lemma does. For x ∈ N0, the lemma clearly holds since N0 ⊂ N. Let x be a point added in

Case (1) at iteration i. The lemma follows immediately since x was selected as a point where fN was large

and x was (1/3)-medial: .

1

β+

β+

NNNi(x) ≥ fNi(x) > fN(x) > fN(x)

3

3

7

Let y be a point added in Case (2) at iteration i relative to some x ∈ S and p ∈ Ni. Let q be the nearest

neighbor of p in Ni. We will use the Lipschitz condition on fN and fNi, as well as applying the corollary as

an inductive hypothesis:

1

fN(y) ≤ fN(x) + |x − y| < β+ fNi(x) + |x − y|

(9)

1

1

1

1

≤ β+ fNi(y) + β+ |x − y| + |x − y| = β+ fNi(y) + (1 + β+ )|x − y|

(10)

1

1

≤ β+ |y − q| + (1 + β+ )2rNi(p)

(11)

1

1

5

7

≤ β+ 3rNi(p) + (1 + β+ )2rNi(p) = (2 + β+ )NNNi(y) ≤ β+ NNNi(y) (12)

Having proved the lemma and corollary, we recall that condition (7) must hold for any x ∈ S. Let x ∈ S

be given and take v ∈ N such that x ∈ VN (v). then. We ﬁrst notice that fN (x) ≥ rN (p). We use Lipschitz

property of fN and apply the corollary at v:

8

16

16

17

1

fN(x) ≤ fN(v) + |x − v| < β+ fN (v) + |x − v| = β+ rN (v) + |x − v| ≤ β+ fN (x) + fN (x) ≤ β+ fN (x) < β− fN (x)

4 Algorithms

Our result assumes that the surface S, the volume mesh M, the surface mesh N, and the seed N0 were all given. Ideally, we should not need to know so much, and instead we would have an algorithm to ﬁll in the unknowns. There are many mesh reﬁnement algorithms in the literature that need only know either S or N. Provided the seed exists—it need not be known—said mesh reﬁnement algorithms will produce an output that matches the requirements of the Scaﬀold Theorem 3.1: |M| ∈ Θ(|N|). The surprising conclusion is that in terms of runtime and output size, when the ambient dimension is bounded, it is asymptotically free to mesh a volume rather than meshing only a surface—again, provided the surface has a seed.

4.1 Meshing a surface sample

The simplest application is to take as input a set of points N that all lie on a manifold surface (for example, the famous Stanford Bunny model), and construct from it the volume mesh M. This is a useful endeavor if we are to animate the model. To generate the volume mesh, we use a Voronoi (or Delaunay) reﬁnement algorithm. The volume mesher ﬁrst wraps the points of N into an appropriate bounding box, of diameter only a constant factor larger than the diameter of N. It initializes M with N, then ﬁnds a vertex v with RM(v) ≥ τrM(v), and identiﬁes some point p that is in the Voronoi cell of v, but far from it: |vp| ≤ |up| for all u ∈ M, but |vp| ≥ τrM(v). The algorithm then adds p to M, and continues this process until M is τ-wellspaced. A large number of algorithms implement this process (e.g. [Rup95, She98, HPU05, HMP06]).

Our theorem requires that the surface is covered by the Voronoi cells of just the surface vertices—that is, no point of S lies in the Voronoi cell of a vertex in M\N. Under certain assumptions on N, we can prove

8

this holds. We require that there be some such that for all x, there is a vertex v ∈ N such that |vx| ≤ ; but for all u ∈ N, all other vertices v ∈ N lie at distance |uv| ≥ /2. In other words, N is an -net of S.

Lemma 4.1 Consider a point x ∈ S whose nearest neighbour in N is v. If the volume mesh M is computed with τ > 4, then x remains in the Voronoi cell VM(v).

Proof: For any vertex u created during reﬁnement, there is some u that created u: when u was inserted, its nearest neighbour was u , and |uu | ≥ τrM(u ). In other words, created vertices have nearest neighbour larger than the distance between the closest pair of points in N. The closest pair must be at least /2 from each other, by assumption, so any u ∈ M\N has rM(u) ≥ τ /4. Return now to consider x. For a contradiction, we assume that the nearest neighbour of x in M is a created vertex u. Then |ux| < |vx|. Given that |vx| ≤ , we know that |uv| ≤ 2 . Clearly, rM(u) can be no larger than half the distance to any vertex: rM(u) ≤ |uv|/2 ≤ . Remembering the previous bound, we conclude that ≥ τ /4, or equivalently, τ ≤ 4, a contradiction.

As a corollary, this means that every point x ∈ S is in the Voronoi cell of some vertex in N, and therefore Theorem 3.1 holds. Then |M| ∈ O(|N|), assuming N is an -net of S, and that τ > 4. But N is input, so n = |N|: the volume mesh contains a number of vertices only linear in the size of the input! We can relax the requirement on τ by remembering that a τ-well-spaced mesh and a τ -well-spaced mesh have size within a constant factor of each other, where the constant is a function of τ, τ . This lets us conclude:

Corollary 4.2 A τ-well-spaced mesh of an -net has size O(n) for any τ and .

4.2 Meshing a surface

In mesh reﬁnement for engineering and scientiﬁc applications, the input is typically speciﬁed as a piecewise linear complex or a piecewise smooth complex, made up of a collection of vertices, segments or curves, and polygons or smooth surfaces (and so on, in higher dimension). As in the prior subsection, we assume the algorithm ﬁrst places a box around the input complex, then iteratively inserts vertices. In the face of linear or smooth features, this requires greater care than before although the details are nearly irrelevant to our results here. The mesher continues adding vertices until two conditions are met: that the vertices are wellspaced, and that the Delaunay triangulation “respects” the input complex. In the case of piecewise linear complexes, we say a triangulation respects it if each linear facet appears as the union of a set of Delaunay simplices [Rup95, She98]. In other words, the Voronoi diagram of surface vertices covers the input. For smooth complexes [CDR07, RY07], respecting a surface requires even more than the covering condition.

The analysis of algorithms that mesh complexes typically rely on a global function called the local feature size, denoted lfs, which represents how much reﬁnement will be necessary locally. For our purposes, we require that the local feature size be deﬁned on S, and extended to the entire domain via the minimum 1-Lipschitz function: at x ∈ Ω\S, lfs(x) ≡ miny∈S lfs(y) + |xy|. This is within a factor of three of Ruppert’s more traditional local feature size function deﬁne on linear complexes, but extends more easily to smooth complexes. Most mesh reﬁnement algorithms arising from the computational geometry community guarantee that vertices are not too closely packed: at every v ∈ M, rM(v) ≥ γ− lfs(v). For our purposes here, we also need the algorithm to guarantee that every vertex v must have RM(v) ≤ γ+ lfs(v), and every point x must have some neighbour v with |vx| ≤ γ+ lfs(x). Parallel mesh reﬁnement algorithms happen to require this for fast parallel runtime [STU¨ 07, HMP07]. These conditions are extremely reminiscent of conditions (1) and (2), assuming fN and lfs are related.

Lemma 4.3 For all x ∈ Ω, fN(x) ∈ [δ− lfs(x), δ+ lfs(x)].

Proof: For the lower bound on fN, consider a point x in the domain. It lies in the Voronoi cell of some vertex v ∈ M. Since local feature size is 1-Lipschitz, lfs(x) ≤ lfs(v) + |vx|. By the assumption on the algorithm,

9

rM(v) ≥ γ− lfs(v). We also know that the second-nearest vertex to x is at least as far as max(rM(v), |vx|).

Thus we know lfs(x) ≤ (1 + 1/γ−) fM(x). Finally, removing vertices can only increase f : fM(x) ≤ fN(x),

which

proves

that

fN ( x)

≥

γ− 1+γ−

lfs(x).

Then

δ−

=

1+γ−γ− .

For the upper bound, ﬁrst consider a vertex u ∈ N. Because the Voronoi cells of N cover S, we know

that u has a neighbour u on N with |uu | ≤ 2RM(u). The algorithm guarantees RM(u) ≤ γ+ lfs(u). Thus

fN(u) ≤ 2γ+ lfs(u). Next, consider a a point y ∈ S whose nearest neighbour is u. We know that fN(y) ≤

fN(u) + |uy| ≤ 2γ+ lfs(u) + |uy|. At u, the Lipschitz condition bounds lfs(u) ≤ lfs(y) + |uy|. Finally, u is the

nearest vertex to y, but there must be some vertex within distance γ+ lfs(y), which means |uy| ≤ γ+ lfs(y).

Thus fN(y) ≤ 2γ+ lfs(y) + 2|uy| ≤ 4γ+ lfs(y). We can now consider an arbitrary point x. Let y be the point

of S for which lfs(x) = lfs(y) + |xy|. By the Lipschitz condition on fN, we know fN(x) ≤ fN(y) + |xy|. We

just proved that fN(y) ≤ 4γ+ lfs(y). By deﬁnition, lfs(y) ≤ lfs(x), so we know fN(y) ≤ 4γ+ lfs(x). Equally,

|xy| ≤ lfs(x). Therefore, fN(x) ≤ (1 + 4γ+) lfs(x). Then δ+ = (1 + 4γ+).

Corollary 4.4 When presented with an input piecewise smooth or piecewise linear complex for which there exists a seed, a quality mesh reﬁnement algorithms that outputs a mesh of optimal size creates a volume mesh M and a surface mesh N, with |M| ∈ O(|N|).

5 Conclusions

Accounting for scaﬀolding costs is a pressing question in the timing and output-size analysis of many mesh generation algorithms that are used in practice. The Scaﬀold Theorem shows that these costs are not dominant, as has so often been assumed without proof in prior work. This analysis is made applicable to many algorithms by abstracting the meshing problem to that of simply generating a minimal well-spaced superset of a vertex-set. This ignores many of the topological and geometric intricacies that make meshing algorithms diﬃcult to analyze, while still preserving enough distribution information about the vertices to make meaningful statements on mesh-size.

Reﬂecting on the analysis, the surface vertices are paramount and the underlying surface itself plays only a small role in controlling the size of the volume mesh, It is then theoretically of interest to simply consider the size of a minimal well-spaced superset M of a vertex-set N ⊂ Ω. It is well-established that:

|M| ∈ Θ 1 Ω fNd

A worst case upper bound on this integral is O(|N| log ∆), where ∆ is the spread of the domain; the ratio of the diameter of Ω to the closest pair in N. In general, this bears no combinatorial relationship to |N|. The Scaﬀold Theorem provides suﬃcient conditions (that are highly relevant in practice) for a setting wherein |M| is linear in |N|. But these conditions are nowhere near necessary. It is an interesting question whether there exist simple necessary and suﬃcient conditions that will combinatorially bound |M| when N is given arbitrarily.

References

[ABE98] Nina Amenta, Marshall Bern, and David Eppstein. The crust and the β-skeleton: Combinatorial curve reconstruction. Graphical models and image processing: GMIP, 60(2), 1998.

[BEG94] Marshall Bern, David Eppstein, and John R. Gilbert. Provably Good Mesh Generation. Journal of Computer and System Sciences, 48(3):384–409, June 1994.

10

Benoˆıt Hudson Toyota Technological Institute, Chicago

[email protected]

Gary L. Miller Todd Phillips Don Sheehy Carnegie Mellon University

{glmiller,tp517,dsheehy}@cs.cmu.edu

July 3, 2008. (Under Submission)

Abstract

Typical volume meshes in three dimensions are designed to conform to an underlying two-dimensional surface mesh, with volume mesh element size growing larger away from the surface. The surface mesh may be uniformly spaced or highly graded, and may have ﬁne resolution due to extrinsic mesh size concerns. When we desire that such a volume mesh have good aspect ratio, we require that some spaceﬁlling scaﬀold vertices be inserted oﬀ the surface. We analyze the number of scaﬀold vertices in a setting that encompasses many existing volume meshing algorithms. We show that under simple preconditions, the number of scaﬀold vertices will be linear in the number of surface vertices.

1 Introduction

Given a surface mesh, many scientiﬁc computing and graphics applications will want to produce a volume mesh. Conversely, to build a surface mesh from another description of an input geometry, one might temporarily build a point location structure such as an oct-tree, which is a volume mesh. A natural question arises: can we relate the size of the surface mesh to the size of the volume mesh? A volume mesh will obviously have more vertices than the corresponding surface mesh, but in most settings, the spacing between vertices should grow quickly away from the surface. Since the density of the volume mesh is driven only by the surface, it is intuitive that the surface vertices should dominate in quantity. Our main result is to show that given a surface mesh in a well-proportioned domain, the total number of vertices in the volume is linear in the number of vertices on the surface. We will make this statement speciﬁc later as the Scaﬀold Theorem (Theorem 3.1).

This result has immediate and important ramiﬁcations concerning the asymptotic work and space of a large host of existing meshing and surface reconstruction algorithms. For example, in volume meshing, the user may specify a closed surface and ask for its interior to be meshed. Typical algorithms enclose the surface in a bounding box that contains the closed surface, incrementally add points until the surface is recovered and the volume mesh has good quality, then strip away the exterior volume vertices (see Figure 1). The surface and interior vertices are then returned to the user. This approach is widespread and is used for many two-, three-, and higher-dimensional meshing algorithms [BEG94, ABE98, CDE+00, ELM+00, She98, MV00, U¨ ng04, MPW02, HMP06, CDR07]. The work and space complexity of these algorithms is output-sensitive and depends on the number of exterior vertices, even though these vertices are transient. Our new analysis is the ﬁrst to control this exterior work. Since we show that the number of transient vertices is bounded by

∗This work was supported in part by the National Science Foundation under grants ACI 0086093, CCR-0085982 and CCR0122581.

1

Figure 1: Incremental mesh reﬁnement algorithms ﬁrst generate a mesh over a bounding box (left), then remove the scaﬀold vertices and elements (center). Some applications may be interested in only the surface mesh (right). The (one-dimensional) Lake Superior surface shown mesh has 530 surface vertices. The volume mesh shown has 1072 total volume vertices; 258 interior and 284 exterior. We oﬀer the ﬁrst theoretical analysis of the costs of this scaﬀolding.

the surface vertices, this for the ﬁrst time implies that these algorithms run output-sensitively with respect to the true user-desired output.

In the rest of this work we make our results precise. A good deal of care is taken to ensure the generality of these results, so that this analysis may be applied to many of the existing meshing algorithms with theoretical guarantees. Our proofs are in two parts. In the ﬁrst part, we prove that if a good-quality volume mesh respects a surface, the volume vertices outnumber the surface vertices by only a constant. Our deﬁnition of respecting a surface is much looser than that of most prior work: the Voronoi cells of the surface vertices must cover the surface, but there is no topological requirement. In addition, our deﬁnition of a surface is extremely loose; it need not be manifold, or even connected. Additionally, our surface need not be d − 1 dimensional: for instance, it could be a curve in 3D. Our only requirements are that the surface have a bounded number of connected components, and that each connected component of the surface have diameter within a constant factor of the diameter of the bounding domain.

In the second part, we show how this result relates to standard concepts from mesh reﬁnement and surface reconstruction. In particular, we show that our result proves that a volume mesh of an -net of a surface is only a constant factor larger than the surface. We also show that many prior quality mesh reﬁnement algorithms are susceptible to our analysis. This implies that they still run in the time (and memory usage) bounds they claim, even when the volume actually meshed is larger than what the user asked to mesh.

2 Preliminary Geometric Deﬁnitions

In this paper, we assume there exists a surface S embedded in Rd. It need not be connected. Let D be the minimum diameter of any connected component of S, where the diameter is the maximum Euclidean distance between two points in the component. We require that the diameter of all other components, and the diameter of S, be in Θ(D). Around S there is a compact and connected domain Ω with S ⊂ Ω ⊂ Rd. Typically, Ω will be a box or a hypercube. The diameter of Ω must be in Θ(D).

Let Γd denote the volume of the unit ball in Rd. For x ∈ Rd and r ∈ R, let B(x, r) be the open ball centered at x or radius r (whose volume is given by Γd rd.)

Suppose we have a set of points (vertices) M ⊂ Ω. A vertex-set M induces a local feature size function fM : Ω → R. At a point x ∈ Ω, the local feature size is the distance from x to the second-nearest vertex. We frequently use the fact that fM is 1-Lipschitz: that is, fM(x) ≤ fM(y) + |x − y| for all x and y in Rd (this is easily veriﬁed by the triangle inequality. At a vertex v ∈ M, the local feature size coincides with the distance

2

VM (v)

rM (v) v

RM (v)

x u

VM (u)

Figure 2: The Voronoi cells of two vertices u and v in a vertex-set M (not pictured). The radii of the inner-ball and outer-ball of v are labeled. The point x is 0.9-medial.

to the nearest neighbour, which we denote NNM(v). Given the vertex-set M, we denote by VM(v) the closed Voronoi cell of v: those points in Rd for which

no vertex in M is closer than is v. We identify two natural balls with v: the inner-ball bM(v) is the largest ball centered at v that is contained within VM(v), while the outer-ball BM(v) is the smallest ball centered at v that contains all of VM(v) ∩ Ω. We denote by rM(v) and RM(v) their respective radii (i.e. BM(v) = B(v, RM(v)).) See Figure 2.

2.1 Well-spaced, Well-paced, and Medial Points

If there is a constant τ for which every v in a vertex-set M, has the property RM(v) ≤ τrM(v), then we say that v is τ-well-spaced. Loosely, this implies that the VM(v) ∩ Ω is roundly shaped and that v is roughly centered. Figure 3(right) shows a set of well-spaced points; contrast this with the vertices of Figure 4(left).

The problem of scaﬀolding a surface mesh with a volume mesh is that of ﬁnding a minimal well-spaced superset (volume mesh) M of a vertex-set (surface mesh) N.

We will make use of a theorem from [MPS08]. First, we introduce some relevant deﬁnitions. The boundaries of the Voronoi cells of each vertex in M form the medial axis of M. Miller et al [MPS08] generalize this and say that a point x is θ-medial with respect to M if it lies near the medial axis, in the sense that NNM(x) ≥ θ fM(x). Notice that whenever we had a point x to a set M, it will decrease the feature-size fM in the vicinity of x. A key observation is that adding a θ-medial point will only decrease the feature-size by a constant amount.

Given an arbitrary vertex-set N, and an ordered set of vertices E ≡ v1, . . . , vk , we say that E is a θwell-paced extension of N if v1 is a θ-medial point of N, and each vi is a θ-medial point of N ∪ {v1 . . . vi−1}. Informally, the name arises from the fact that the local feature size shrinks only slowly after each insertion.

Well-paced extensions are not well-spaced in general, but they have useful similarities to surface meshes. We now state for completeness the Well-Pacing Theorem ([MPS08], Corollary 3).

Theorem 2.1 (Well-Pacing Theorem) There is a constant C2.1, such that if N is a well-paced extension of a well-spaced set, then there exists a well-spaced superset M ⊃ N, with |M| ≤ C2.1|N|.

(For Review Purposes: [MPS08] will appear in August. Appendix section C contains relevant proof details. )

3

3 Scaﬀold Theorem

3.1 Overview

Our main result is the Scaﬀold Theorem 3.1, showing that given a volume mesh M with underlying surface mesh N, |M| is bounded above by a constant times the size of |N|. (Informally, |M| |N|.) Section 3.2 deﬁnes the formal setting in where Theorem applies.

The easiest proof would be to show that N can be written as a well-paced extension of a well-spaced set, then we could simply apply the Well-Pacing Theorem 2.1 to directly bound |M|. This is diﬃcult, so instead we deﬁne the concept of a spacing-equivalent surface mesh N , and show that one exists (Theorem 3.6). We can then construct a scaﬀolding volume mesh M for N . The proof then proceeds as three straightforward lemmas (3.3, 3.4, and 3.5). First, Lemma 3.3 shows that M M . This follows because the surface meshes N and N are roughly equivalent, so then their associated scaﬀolding volume meshes are also roughly equivalent. Next, Lemma 3.4 applies Theorem 2.1 to show that M N . Lastly, Lemma 3.5 shows that N N and follows simply by the spacing-equivalence of N . Putting these together yields M M N N. We now proceed with a formal proof.

3.2 Deﬁnitions: Scaﬀold Mesh and Seeded Surface Mesh

Suppose we are given a domain Ω as in Section 2. Further suppose we are given a “surface” S ⊂ Ω. We

require only that S is a closed subset. Suppose we have a ﬁnite vertex-set M ⊂ Ω. Deﬁne the surface vertices

as N = M ∩ S. To capture the notion that the sizing of this point set is solely due to the surface, we wish to

relate the Voronoi cells of M to the feature-size due to N. Formally, the input must satisfy the following two

conditions:

∃ α+ ∈ (0, ∞), ∀ m ∈ M, RM(m) ≤ α+ fN(m)

(1)

∃ α− ∈ (0, 1), ∀ m ∈ M, rM(m) ≥ α− fN(m)

(2)

Note this implicitly implies that M is a well-spaced set of vertices, with R(m)/r(m) ≤ α+/α−. When M and N satisfy conditions (1) and (2), we will say that M is an α-scaﬀolding volume mesh of the set N in Ω. We further require that the surface vertices N cover S in the following sense:

S ⊂ VM(n)

(3)

n∈N

Lastly, we require that the volume being ﬁlled is well-proportioned to the underlying surface. We accomplish this by requiring the existence of a seed N0 ⊂ N, The seed N0 must contain two vertices in each connected component of S and must be a well-spaced set of points. Formally:

For each connected component T ⊂ S, ∃p, q ∈ N0 ∩ T , s.t. p q

(4)

N0 is ρ-well-spaced, i.e.∃ρ ∈ (1, ∞)∀n ∈ N0, RN0(n) ≤ ρrN0(n)

(5)

If a set N with scaﬀolding volume mesh M meets conditions (3)-(5), then we say that N is a seeded surface mesh of S in Ω. Figures 3 and 4 illustrate these deﬁnitions.

3.3 Deﬁnitions: Spacing-Equivalent Sets

Suppose N ⊂ S is a vertex-set. Consider a vertex-set N ⊂ S that satisﬁes the following two conditions:

∃ β+ ∈ (0, ∞), ∀ s ∈ S, fN (s) ≤ β+ fN(s)

(6)

∃ β− ∈ (0, β+), ∀ s ∈ S, fN (s) ≥ β− fN(s)

(7)

4

Figure 3: The deﬁnitions of Section 3.2 illustrated abstractly. Left, a surface S is composed of both black shapes, with the domain Ω shaded. Center, vertices form a volume mesh M of Ω. The subset of surface vertices N are shown in black, with the volume vertices in white. Note how the density of the volume vertices is driven only by the density of surfaces vertices. Right, a possible seed N0, containing at least two points from each component of the surface S. Notice the four points are well-spaced and have quality Voronoi cells (shown in dashed lines).

We then say that such an N is β-spacing-equivalent to N on S. Theorem 3.6 will show that a seeded surface mesh N (with seed N0) always has a β-spacing-equivalent set N , with the additional property that N is also a (1/3)-well-paced extension of the seed N0. For any vertex-set N , it is possible to construct (using oﬀ the shelf algorithms [Rup95]) a well-spaced superset of vertices M that is a γ-scaﬀolding volume mesh, for some γ determined by the algorithm selected. This mesh M need not be aware of the surface at

all, since we will not require that N be a seeded surface mesh.

3.4 Scaﬀold Theorem Proof

Theorem 3.1 (Scaﬀold Theorem) Suppose M is an α-scaﬀolding volume mesh of N, and that N is a seeded surface mesh. Then there exists a constant C3.1 depending only on α+ and α− such that:

|M| ≤ C3.1|N|

The main theorem will follow immediately from the existence of a spacing-equivalent surface mesh (Theorem 3.6) and then composing Lemmas 3.3, 3.4, and 3.5. The proof begins with a small technical lemma with the goal of extending spacing-equivalence to the entire domain Ω, since it is only guaranteed on S.

Lemma 3.2 Suppose N is a surface mesh as in Section 3.2 and N is a β-spacing-equivalent vertex-set,

then:

∀ x ∈ Ω, fN (x) ≤ (1 + 2β+) fN(x)

Proof: Let x ∈ Ω. Let s ∈ S be a point on S with minimum Euclidean distance to x (s exists by the closure of S.) Because N ⊂ S, we have fN(x) ≥ |x − s|. Combining this fact with the Lipschitz conditions and condition (6), we ﬁnd:

fN (x) ≤ fN (s) + |x − s| ≤ β+ fN(s) + |x − s| ≤ β+( fN(x) + |x − s|) + |x − s| ≤ (1 + 2β+) fN(x) (8)

Using the previous lemma, we can now show that an induced scaﬀold M of a spacing-equivalent set N is at least as large (up to a constant) as the scaﬀold M of the original set N. (A bound in the other direction is also true with diﬀering constants, but we will not need it.)

5

Figure 4: Examples of violations of the conditions in Section 3.2. Left, when the surface S has disproportionately small components, it will be too costly to ﬁll the volume in a way that resolves these small surface features. Note that no seed can exist in this example. An attempted seed is shown, but as the surface components grow relatively small, there is no way to ﬁt two points on each component in a way that is well-spaced. Center, this volume mesh is not a scaﬀold mesh, because the sizing is not driven by the surface. The sink in the lower-center could contain arbitrarily many volume vertices. Note how this violates equation (2). Right, If the surface vertices do not cover S as in equation 3, then there could be a small surface feature requiring many volume vertices to resolve without having to add any more surface vertices. Note that a seed still exists in this example.

Lemma 3.3 Suppose M is an α-scaﬀolding volume mesh of N as in Section 3.2, and suppose M scaﬀolding volume mesh for a β-spacing-equivalent surface mesh N , then:

|M| ≤ C3.3|M |

where

2(1 + 2β+)γ+ d

C3.3 =

α−γ−

is a γ-

Proof: The proof is a packing argument showing that if we partition the vertices M into the Voronoi cells VM , no cell receives more than a constant-sized portion of M. There are disjoint empty balls around the vertices of M with radii that are lower bounded by fN which lower bounds fN (by Lemma 3.2). But fN also upper bounds the size of the Voronoi cells of M because it is a γ-scaﬀolding volume mesh of N . A detailed proof is given in the appendix.

Lemma 3.4 Suppose M is a γ-scaﬀolding volume mesh of a N , and that N is a well-paced extension of a well-spaced seed, then:

|M | ≤ C3.4|N |

Proof: This is a direct application of the Well-Pacing Theorem 2.1. The constant C3.4 will be inversely proportional to γ−.

Lemma 3.5 Suppose N mesh M, then we have:

is β-spacing-equivalent to a seeded surface mesh N with α-scaﬀolding volume

|N | ≤ C3.5|N|

where

4α+ d C3.5 = α−β−

Proof: Lemma 3.5 follows from a packing argument and the proof is similar Lemma 3.3. See Appendix for details.

6

3.5 Existence of Spacing-Equivalent Sets

Theorem 3.6 (Spacing-Equivalent Existence) Suppose N is a seeded surface mesh of S in Ω (with seed N0) as speciﬁed by Section 3.2. Then there exists a β-spacing-equivalent N that is a (1/3)-well-paced extension of N0, for any β+ ∈ (0, 1] and β− ∈ (0, β+/17).

Proof: Let N, N0, S, β+, and β− be given satisfying the hypothesis of the theorem.

according to the following algorithm:

Begin with the seed N0 and a counter i, initially i = 0. While ∃x ∈ S such that fNi(x) > β+ fN(x), let p ∈ Ni such that x ∈ VN (p):

Proof is by construction

1. If x bNi(p). Set Ni+1 = {x} ∪ Ni. 2. If x ∈ bNi(p). Let y ∈ ∂bNi(p) ∩ S. (Note y exists by 4.) Set Ni+1 = {y} ∪ Ni. 3. Increment i.

The ﬁniteness of N guarantees this will terminate at some index I. Take N = NI. First, we claim that any points added to Ni is (1/3)-medial wrt Ni. Consider a point x on any iteration i of the loop. Let q ∈ Ni be the nearest neighbor of p. If x is inserted in Step 1.:

fNi(x) ≤ |x − p| + fNi(p) = |x − p| + 2rNi(p) ≤ 3|x − p| = 3NNNi(x)

so x is (1/3)-medial. If y is inserted in Step 2., we have: fNi(y) ≤ |y − p| + fNi(p) = 3|y − p| = 3NNNi(y)

so y is (1/3)-medial. Thus N is a well-paced extension of the well-spaced N0. It remains to show that N is β-spacing-equivalent to N, namely that conditions (6) and (7) hold. Clearly, the upper bound condition (6) holds by construction. Either there are no more violations of (6)

or N = S, but the latter would clearly violate ﬁniteness of N. The proof of condition (7) is more subtle but follows similar arguments from previous work [Rup95]. We will use the following lemma to show condition (7).

Lemma 3.7 Suppose x ∈ N is inserted at iteration i (i.e. x ∈ Ni+1 − Ni), then: β+

NNNi(x) > fN(x) 7

Note that this Lemma would imply the immediate corollary:

Corollary 3.8

β+ ∀x ∈ N , fN (x) > fN(x)

8

Proof of corollary: Let x ∈ N (iteration i) be given and take y ∈ N (iteration j) s.t. |x − y| = NNN (x). If i > j , then we simply apply the lemma directly:

β+

β+

NNN (x) = NNNi(x) > fN(x) > fN(x)

7

8

If i < j, then we use Lipschitz of fN and apply the lemma to y:

7

7

8

8

fN(x) ≤ fN(y) + |x − y| < β+ NNNj(y) + |x − y| ≤ β+ |x − y| + |x − y| < β+ |x − y| = β+ NNN (x)

7

We return to proving Lemma 3.7. Proof is by induction. Note that the corollary always holds inductively

whenever the lemma does. For x ∈ N0, the lemma clearly holds since N0 ⊂ N. Let x be a point added in

Case (1) at iteration i. The lemma follows immediately since x was selected as a point where fN was large

and x was (1/3)-medial: .

1

β+

β+

NNNi(x) ≥ fNi(x) > fN(x) > fN(x)

3

3

7

Let y be a point added in Case (2) at iteration i relative to some x ∈ S and p ∈ Ni. Let q be the nearest

neighbor of p in Ni. We will use the Lipschitz condition on fN and fNi, as well as applying the corollary as

an inductive hypothesis:

1

fN(y) ≤ fN(x) + |x − y| < β+ fNi(x) + |x − y|

(9)

1

1

1

1

≤ β+ fNi(y) + β+ |x − y| + |x − y| = β+ fNi(y) + (1 + β+ )|x − y|

(10)

1

1

≤ β+ |y − q| + (1 + β+ )2rNi(p)

(11)

1

1

5

7

≤ β+ 3rNi(p) + (1 + β+ )2rNi(p) = (2 + β+ )NNNi(y) ≤ β+ NNNi(y) (12)

Having proved the lemma and corollary, we recall that condition (7) must hold for any x ∈ S. Let x ∈ S

be given and take v ∈ N such that x ∈ VN (v). then. We ﬁrst notice that fN (x) ≥ rN (p). We use Lipschitz

property of fN and apply the corollary at v:

8

16

16

17

1

fN(x) ≤ fN(v) + |x − v| < β+ fN (v) + |x − v| = β+ rN (v) + |x − v| ≤ β+ fN (x) + fN (x) ≤ β+ fN (x) < β− fN (x)

4 Algorithms

Our result assumes that the surface S, the volume mesh M, the surface mesh N, and the seed N0 were all given. Ideally, we should not need to know so much, and instead we would have an algorithm to ﬁll in the unknowns. There are many mesh reﬁnement algorithms in the literature that need only know either S or N. Provided the seed exists—it need not be known—said mesh reﬁnement algorithms will produce an output that matches the requirements of the Scaﬀold Theorem 3.1: |M| ∈ Θ(|N|). The surprising conclusion is that in terms of runtime and output size, when the ambient dimension is bounded, it is asymptotically free to mesh a volume rather than meshing only a surface—again, provided the surface has a seed.

4.1 Meshing a surface sample

The simplest application is to take as input a set of points N that all lie on a manifold surface (for example, the famous Stanford Bunny model), and construct from it the volume mesh M. This is a useful endeavor if we are to animate the model. To generate the volume mesh, we use a Voronoi (or Delaunay) reﬁnement algorithm. The volume mesher ﬁrst wraps the points of N into an appropriate bounding box, of diameter only a constant factor larger than the diameter of N. It initializes M with N, then ﬁnds a vertex v with RM(v) ≥ τrM(v), and identiﬁes some point p that is in the Voronoi cell of v, but far from it: |vp| ≤ |up| for all u ∈ M, but |vp| ≥ τrM(v). The algorithm then adds p to M, and continues this process until M is τ-wellspaced. A large number of algorithms implement this process (e.g. [Rup95, She98, HPU05, HMP06]).

Our theorem requires that the surface is covered by the Voronoi cells of just the surface vertices—that is, no point of S lies in the Voronoi cell of a vertex in M\N. Under certain assumptions on N, we can prove

8

this holds. We require that there be some such that for all x, there is a vertex v ∈ N such that |vx| ≤ ; but for all u ∈ N, all other vertices v ∈ N lie at distance |uv| ≥ /2. In other words, N is an -net of S.

Lemma 4.1 Consider a point x ∈ S whose nearest neighbour in N is v. If the volume mesh M is computed with τ > 4, then x remains in the Voronoi cell VM(v).

Proof: For any vertex u created during reﬁnement, there is some u that created u: when u was inserted, its nearest neighbour was u , and |uu | ≥ τrM(u ). In other words, created vertices have nearest neighbour larger than the distance between the closest pair of points in N. The closest pair must be at least /2 from each other, by assumption, so any u ∈ M\N has rM(u) ≥ τ /4. Return now to consider x. For a contradiction, we assume that the nearest neighbour of x in M is a created vertex u. Then |ux| < |vx|. Given that |vx| ≤ , we know that |uv| ≤ 2 . Clearly, rM(u) can be no larger than half the distance to any vertex: rM(u) ≤ |uv|/2 ≤ . Remembering the previous bound, we conclude that ≥ τ /4, or equivalently, τ ≤ 4, a contradiction.

As a corollary, this means that every point x ∈ S is in the Voronoi cell of some vertex in N, and therefore Theorem 3.1 holds. Then |M| ∈ O(|N|), assuming N is an -net of S, and that τ > 4. But N is input, so n = |N|: the volume mesh contains a number of vertices only linear in the size of the input! We can relax the requirement on τ by remembering that a τ-well-spaced mesh and a τ -well-spaced mesh have size within a constant factor of each other, where the constant is a function of τ, τ . This lets us conclude:

Corollary 4.2 A τ-well-spaced mesh of an -net has size O(n) for any τ and .

4.2 Meshing a surface

In mesh reﬁnement for engineering and scientiﬁc applications, the input is typically speciﬁed as a piecewise linear complex or a piecewise smooth complex, made up of a collection of vertices, segments or curves, and polygons or smooth surfaces (and so on, in higher dimension). As in the prior subsection, we assume the algorithm ﬁrst places a box around the input complex, then iteratively inserts vertices. In the face of linear or smooth features, this requires greater care than before although the details are nearly irrelevant to our results here. The mesher continues adding vertices until two conditions are met: that the vertices are wellspaced, and that the Delaunay triangulation “respects” the input complex. In the case of piecewise linear complexes, we say a triangulation respects it if each linear facet appears as the union of a set of Delaunay simplices [Rup95, She98]. In other words, the Voronoi diagram of surface vertices covers the input. For smooth complexes [CDR07, RY07], respecting a surface requires even more than the covering condition.

The analysis of algorithms that mesh complexes typically rely on a global function called the local feature size, denoted lfs, which represents how much reﬁnement will be necessary locally. For our purposes, we require that the local feature size be deﬁned on S, and extended to the entire domain via the minimum 1-Lipschitz function: at x ∈ Ω\S, lfs(x) ≡ miny∈S lfs(y) + |xy|. This is within a factor of three of Ruppert’s more traditional local feature size function deﬁne on linear complexes, but extends more easily to smooth complexes. Most mesh reﬁnement algorithms arising from the computational geometry community guarantee that vertices are not too closely packed: at every v ∈ M, rM(v) ≥ γ− lfs(v). For our purposes here, we also need the algorithm to guarantee that every vertex v must have RM(v) ≤ γ+ lfs(v), and every point x must have some neighbour v with |vx| ≤ γ+ lfs(x). Parallel mesh reﬁnement algorithms happen to require this for fast parallel runtime [STU¨ 07, HMP07]. These conditions are extremely reminiscent of conditions (1) and (2), assuming fN and lfs are related.

Lemma 4.3 For all x ∈ Ω, fN(x) ∈ [δ− lfs(x), δ+ lfs(x)].

Proof: For the lower bound on fN, consider a point x in the domain. It lies in the Voronoi cell of some vertex v ∈ M. Since local feature size is 1-Lipschitz, lfs(x) ≤ lfs(v) + |vx|. By the assumption on the algorithm,

9

rM(v) ≥ γ− lfs(v). We also know that the second-nearest vertex to x is at least as far as max(rM(v), |vx|).

Thus we know lfs(x) ≤ (1 + 1/γ−) fM(x). Finally, removing vertices can only increase f : fM(x) ≤ fN(x),

which

proves

that

fN ( x)

≥

γ− 1+γ−

lfs(x).

Then

δ−

=

1+γ−γ− .

For the upper bound, ﬁrst consider a vertex u ∈ N. Because the Voronoi cells of N cover S, we know

that u has a neighbour u on N with |uu | ≤ 2RM(u). The algorithm guarantees RM(u) ≤ γ+ lfs(u). Thus

fN(u) ≤ 2γ+ lfs(u). Next, consider a a point y ∈ S whose nearest neighbour is u. We know that fN(y) ≤

fN(u) + |uy| ≤ 2γ+ lfs(u) + |uy|. At u, the Lipschitz condition bounds lfs(u) ≤ lfs(y) + |uy|. Finally, u is the

nearest vertex to y, but there must be some vertex within distance γ+ lfs(y), which means |uy| ≤ γ+ lfs(y).

Thus fN(y) ≤ 2γ+ lfs(y) + 2|uy| ≤ 4γ+ lfs(y). We can now consider an arbitrary point x. Let y be the point

of S for which lfs(x) = lfs(y) + |xy|. By the Lipschitz condition on fN, we know fN(x) ≤ fN(y) + |xy|. We

just proved that fN(y) ≤ 4γ+ lfs(y). By deﬁnition, lfs(y) ≤ lfs(x), so we know fN(y) ≤ 4γ+ lfs(x). Equally,

|xy| ≤ lfs(x). Therefore, fN(x) ≤ (1 + 4γ+) lfs(x). Then δ+ = (1 + 4γ+).

Corollary 4.4 When presented with an input piecewise smooth or piecewise linear complex for which there exists a seed, a quality mesh reﬁnement algorithms that outputs a mesh of optimal size creates a volume mesh M and a surface mesh N, with |M| ∈ O(|N|).

5 Conclusions

Accounting for scaﬀolding costs is a pressing question in the timing and output-size analysis of many mesh generation algorithms that are used in practice. The Scaﬀold Theorem shows that these costs are not dominant, as has so often been assumed without proof in prior work. This analysis is made applicable to many algorithms by abstracting the meshing problem to that of simply generating a minimal well-spaced superset of a vertex-set. This ignores many of the topological and geometric intricacies that make meshing algorithms diﬃcult to analyze, while still preserving enough distribution information about the vertices to make meaningful statements on mesh-size.

Reﬂecting on the analysis, the surface vertices are paramount and the underlying surface itself plays only a small role in controlling the size of the volume mesh, It is then theoretically of interest to simply consider the size of a minimal well-spaced superset M of a vertex-set N ⊂ Ω. It is well-established that:

|M| ∈ Θ 1 Ω fNd

A worst case upper bound on this integral is O(|N| log ∆), where ∆ is the spread of the domain; the ratio of the diameter of Ω to the closest pair in N. In general, this bears no combinatorial relationship to |N|. The Scaﬀold Theorem provides suﬃcient conditions (that are highly relevant in practice) for a setting wherein |M| is linear in |N|. But these conditions are nowhere near necessary. It is an interesting question whether there exist simple necessary and suﬃcient conditions that will combinatorially bound |M| when N is given arbitrarily.

References

[ABE98] Nina Amenta, Marshall Bern, and David Eppstein. The crust and the β-skeleton: Combinatorial curve reconstruction. Graphical models and image processing: GMIP, 60(2), 1998.

[BEG94] Marshall Bern, David Eppstein, and John R. Gilbert. Provably Good Mesh Generation. Journal of Computer and System Sciences, 48(3):384–409, June 1994.

10