Deforming Surface Meshes

Abstract

We study the problem of maintaining a deforming surface mesh, specified only by a dense sample of n points that move with the surface. We propose a motion model under which the class of $(\varepsilon,\alpha )$-meshes can be efficiently maintained by a combination of edge flips and insertion and deletion of vertices. We can enforce bounded aspect ratios and a small approximation error throughout the deformation.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

1.1 Background

The simulation of deforming surfaces appears in various settings such as the interface between fluids [14, 18, 21, 28], boundary element methods [5, 15], moving cloth [4, 29], and surgery simulation [10, 19]. In this paper, we consider the simulation of a surface that deforms without changing its topology. The surface is specified only by a set of sample points dense with respect to the local feature size (LFS) and the goal is to approximate the surface by a mesh with vertices chosen from the sample points and triangles of bounded aspect ratio, the latter being a desirable feature for numerical simulation. The deformation may make the angles in the mesh smaller between two successive time steps. Our problem is to restore the mesh quality at the next time step before resuming the deformation. The left two images in Fig. 1 shows snapshots of a twisting cylinder output by our algorithm.

Fig. 1

The left two images show a twisting cylinder. On the right, the dashed skeleton is the medial axis. The local feature sizes are small at x and y because the curvature is high at x and y is near a subcurve that is far way from y along the curve

Some notation is needed to state our results. The Euclidean distance between two points x and y is denoted by d(x, y). For all $Y \subseteq \mathbb{R}^{3}$, $d(x,Y ) =\inf _{y\in Y }d(x,y)$. For every pair of vectors $\mathbf{u}$ and $\mathbf{v}$, $\angle (\mathbf{u},\mathbf{v})$ denotes the angle between them which lies in the range [0, π]. Given three points a, b and c, we use $\angle abc$ to denote $\angle (a - b,c - b)$. Let h and h′ be two linear objects such as vectors, segments, lines, polygons, and planes. We use $\angle _{a}(h,h')$ to denote the nonobtuse angle between the affine subspaces spanned by h and h′. B(x, r) denotes the ball with center x and radius r. Given a ball B, we use ∂ B to denote its boundary. Given a triangle τ, c _τ denotes its circumcenter, γ _τ denotes its circumradius, B _τ denotes the diametric ball $B(c_{\tau },\gamma _{\tau })$ of τ, and n _τ denotes a unit vector orthogonal to aff(τ).

A triangulated polygonal surface T is a set of vertices, edges and triangles such that the intersection of every pair of elements in T is either empty or an element in T, and for every vertex of T, its incident triangles form a topological disk. The union of the vertices, edge and triangles form the underlying space | T | of T. The star of a vertex p ∈ T, denoted star(p), is the set of edges and triangles in T that are incident to p.

Let $\varSigma \subset \mathbb{R}^{3}$ be a closed connected C ²-smooth surface throughout this paper. For every point x ∈ Σ, a medial ball B at x is a maximal ball tangent to Σ at x such that the interior of B does not intersect Σ. The medial axis $\mathcal{M}$ of Σ is the set of centers of medial balls at points in Σ. The local feature size of a point x ∈ Σ is $f(x) = d(x,\mathcal{M})$. The local feature size function f is 1-Lipschitz, i.e., f(x) ≤ f(y) + d(x, y) [11].

A finite point set P ⊂ Σ is an $\varepsilon$ -sample of Σ for some $\varepsilon \in (0,1)$ if $d(x,P) \leq \varepsilon f(x)$ for every point x ∈ Σ. The local feature size is mall at a point x if the curvature is high at x or if x is near a point in Σ whose geodesic distance from x is much larger. The image on the right in Fig. 1 illustrates these two cases in 2D. In such cases, a higher sampling density is needed around x for the reconstruction to be faithful. The local feature size must be nonzero for an $\varepsilon$-sample to be well defined. Thus, Σ is required to be C ²-smooth (no sharp feature or junction). Boundary is also not allowed, although it seems not difficult to handle boundaries in practice as shown in our experiments. Suppose that one has the primitive to compute intersections between Σ and lines, and the primitive to check for every axes-aligned cube C, whether every pair of surface normals in $\varSigma \cap C$ deviate by a small angle. Then, one can recursively refine an octree partition until the intersections between the leaf cell edges and Σ define a dense sample of Σ [25].

The nearest point map $\varphi$ maps a point $x \in \mathbb{R}^{3}\setminus \mathcal{M}$ to the point $\varphi (x) \in \varSigma$ closest to x. We use n _x to denote the outward unit surface normal at a point x ∈ Σ.

A mesh of Σ is a triangulated polygonal surface T such that the vertices of T are points in Σ and | T | is homeomorphic to Σ.

1.2 Motion Model

Consider the simulation of a deforming surface that progresses in unit time steps. The surface is specified by n moving sample points on it. At time t, Σ _t denotes the surface, f _t denotes the LFS function of Σ _t , P _t denotes the set of moving sample points, and Δ _t (x) denotes the speed of a point x ∈ Σ _t . For any vertex v of a mesh T of Σ _t , n _T (v) denotes the distance from v to the nearest vertex in T and R _T (v) denotes the largest circumradius of the triangles incident to v.

Suppose that P _t is an $\varepsilon$-sample of Σ _t at all times and, at any time step t, the velocities of the n sample points are returned by the numerical procedure that drives the simulation. Not all points in P _t can be used as mesh vertices in order that no triangle angle is too small. Theoretically, since an $\varepsilon$-sample can be arbitrarily dense locally, it is impossible to prove that some constant fraction of P _t must appear as mesh vertices. However, it is unlikely that P _t is arbitrarily dense anywhere in practice, and we have observed in our experiments that more that 50 % of the sample points appear as mesh vertices. We assume that the deformation is smooth as defined below.

Definition 1

We say that deformation is smooth if the following conditions are satisfied at every time step t:

• (i) For every point x ∈ Σ _t , Δ _t (x) is at most $0.005\varepsilon _{0}\sin \alpha _{0}$ times the LFS of x at t, and $\varDelta _{t+1}(x) = O(\varDelta _{t}(x))$.

• (ii) For every pair of sample points p and q, if d(p, q) ≤ Δ _t (p), then Δ _t (p) = O(Δ _t (q)).

• (iii) At time t, the displaced mesh vertices from the previous time step form an $\varepsilon _{1}$-sample, where $\varepsilon _{1} \leq \kappa \varepsilon$ for some constant κ.

We are interested in the deformation of a particular class of surfaces meshes defined as follows [7, 8].

Definition 2

For every $\varepsilon \in (0,1)$ and every constant α ∈ (0, π∕3], an $(\varepsilon,\alpha )$-mesh of Σ is a triangulation T that satisfies the following conditions.

• The vertices of T form an $\varepsilon$-sample of Σ.

• The angles of every triangle in T are at least α.

• There exists a triangle τ in T and a vertex p of τ such that $\angle_a (\mathbf{n}_{p},\mathbf{n}_{\tau})\leq \arcsin\left(\frac{0.8}{1+2\csc(\alpha/2)}\right)$.

• $\varphi$ restricted to | T | is a homeomorphism between | T | and Σ.

1.3 Main Result

We prove that there exist constants $\varepsilon _{0} \in (0,1)$ and $\alpha _{0} \in (0,\pi /6)$ such that an $(\varepsilon _{0},\alpha _{0})$-mesh can be constructed before the simulation begins and, at each subsequent time step, an $(\varepsilon _{0},\alpha _{0})$-mesh can be restored via edge flips and insertions and deletions of vertices. Theoretically, α ₀ can be made close to π∕6, but the sampling density would need to be extremely high. Our experiments suggest that α ₀ can be made greater than 10^∘ in practice. The asymptotic running time can be made O(n) [7, 17]. In our experiments (Sect. 6), 90 % of angles are in the range $[30^{\circ },120^{\circ }]$, only less than 0. 02 % of angles are less than 15^∘, and no angle is smaller than 11^∘.

Our theoretical framework does not allow for topological changes, boundaries, or sharp features. We cater for boundaries in our experiments by keeping all input sample points on the boundaries as mesh vertices and the edges connecting such adjacent sample points as mesh edges.

Level set methods [12, 23, 27] and point-based methods [1, 22, 24] are popular methods to model deforming objects with topological changes, but an explicit mesh is not maintained. Our focus is on fast maintenance of a mesh with theoretical guarantees on its quality instead of producing the deformation. We avoid reconstruction from scratch in order to improve efficiency. Thus, our result is most similar to the prior work on tracking a deforming mesh without any topological change [14, 16, 28], but these prior work do not offer any guarantee. Several techniques have been developed to track and modify a mesh in order to produce topological changes [6, 26, 30]. It may be possible to combine them with our algorithm to allow topological changes and preserve sharp features.

2 High Level Strategy

Our strategy is to maintain an $(\varepsilon _{0},\alpha _{0})$-mesh M _t with vertices from P _t that satisfies the following conditions C1–C3. Let ℓ and λ be two constants such that ℓ is sufficiently large and λ is less than 1. The setting of ℓ and λ will be explained later. By C2, α ₀ can be set to be arcsin(λ∕2).

C1::

For every vertex v of M _t , $\mathit{n}_{M_{t}}(v) \geq 20(\sin \alpha _{0})^{-1}\varDelta _{t}(v)$.

C2::

For every vertex v and triangle τ in M _t , if $v \in B(c_{\tau },\ell\gamma _{\tau })$, then $\mathit{n}_{M_{t}}(v) \geq \lambda \gamma _{\tau }$.

C3::

Some points in P _t may not appear as vertices in M _t . Such a point p is stored in some list points(v), where v is a vertex of M _t and $d(p,v) \leq 2\mathit{R}_{M_{t}}(v)$.

Property C1 ensures that a mesh edge turns an angle less than α ₀∕10 from time t to t + 1. Property C2 ensures that the triangle circumradii vary smoothly. By C3, every sample point that is not a vertex is stored at some vertex nearby. Let K _t+1 denote the deformed M _t at time t + 1, which has the same connectivity as M _t . Based on C1–C3 and the smoothness of the deformation, we can show that the deformed mesh K _t+1 is an $(\varepsilon _{1},\alpha _{1})$-mesh for some $\alpha _{1} \in [\frac{4} {5}\alpha _{0},\alpha _{0}]$ that satisfies the following conditions $\hat{\mathrm{C}}1$–$\hat{\mathrm{C}}3$, which are degraded versions of C1–C3. The proof is given in Sect. 3.

$\hat{\mathrm{C}}$ 1::

For any vertex v of K _t+1, $\mathit{n}_{K_{t+1}}(v) \geq 18(\sin \alpha _{0})^{-1}\varDelta _{t}(v)$.

$\hat{\mathrm{C}}$ 2::

For every vertex v and triangle τ in K _t+1, if $v \in B(c_{\tau }, \frac{1} {2}\ell\gamma _{\tau })$, then $\mathit{n}_{K_{t+1}}(v) \geq \frac{1} {2}\lambda \gamma _{\tau }$.

$\hat{\mathrm{C}}$ 3::

For every vertex v in K _t+1 and every point p ∈ points(v), $d(p,v) = O(\mathit{R}_{K_{t+1}}(v))$. The big-Oh constant depends on that the constant in assumption (ii) of our smooth deformation model.

Our problem is to compute an $(\varepsilon _{0},\alpha _{0})$-mesh M _t+1 from K _t+1 that satisfies C1–C3 so that the simulation can continue to the next time step and so on.

The initial $(\varepsilon _{0},\alpha _{0})$-mesh can be obtained by pruning the sample to an $\varepsilon _{0}$-sample that is sparse with respect to their initial velocities and the local feature sizes, followed by running a surface reconstruction algorithm (e.g. [3, 9]) on the pruned sample. The output mesh is an $(\varepsilon _{0},\alpha _{0})$-mesh satisfying C1–C3.

Lemma 1

One can compute an $(\varepsilon _{0},\alpha _{0})$ -mesh from an $\varepsilon$ -sample that satisfies C1 , C2 and C3 .

Proof

We first compute a surface mesh M′ from the $\varepsilon$-sample using a surface reconstruction algorithm. Then for every vertex v, we define its decimation radius $\delta _{v} =\max \left \{4\lambda \gamma _{\tau } -\frac{\lambda }{\ell}d(v,c_{\tau }): \mbox{triangle $\tau \in M'$}\right \}$. Initially, all vertices are unmarked. Take an unprocessed vertex v that is unmarked. Mark all vertices in $B(v,\max \{\delta _{v},20(\sin \alpha _{0})^{-1}\varDelta _{0}(v)\})\setminus \{v\}$. Repeat it until all vertices are processed. Run reconstruction again on the unmarked vertices to compute our initial mesh M. We enforce condition C3 by storing each non-vertex sample point in the point list of its nearest vertex in M. We can show that $M$ is an $(\varepsilon _{0},\alpha _{0})$-mesh that satisfies C1–C3 by using the same arguments as in the proofs of Lemmas 17 and 18. □ 

At time t + 1, we call Update(K _t+1) to compute M _t+1. Update iterates two phases, Refine and Decimate. In the first iteration, Refine inserts some sample points as vertices to make the vertex set an $O(\lambda \varepsilon _{1})$-sample of Σ _t+1. Refinement alone cannot restore the angle lower bound α ₀, because the vertices may become very crowded in some region, where the inter-vertex distance is much less than $\varepsilon$ times the local features sizes, and we run out of sample points to refine its neighborhood. In the second phase, Decimate deletes some vertices to increase the inter-vertex distances while keeping a good sampling density. At the end of the first iteration, the vertex set forms an $O(\lambda \varepsilon _{1})$-sample. Another iteration of the two phases makes the vertex set an $O(\lambda ^{2}\varepsilon _{1})$-sample. So we obtain M _t+1 in $O(\log (1/\varepsilon _{0})) = O(1)$ iterations.

3 Mesh Deterioration

Inductively, the mesh at time t satisfies conditions C1–C3. We want to show that after the deformation, the mesh at time t + 1 satisfies $\hat{\mathrm{C}}1$–$\hat{\mathrm{C}}3$, a set of similar conditions with some degraded constants. The next lemma can be proved by a straightforward trigonometric argument.

Lemma 2

Let τ′ = x′y′x′ be a triangle at time t with minimum angle larger than α ₀ , and it deforms to τ = xyz at time t + 1. Assume that the displacement of each vertex is at most $\kappa ^{-1}\sin \alpha _{0}$ times the length of any of its incident edges, where κ is a constant greater than 14. Then $(1 - 6/\kappa )\gamma _{\tau '} \leq \gamma _{\tau }\leq (1 + 14/\kappa )\gamma _{\tau '}$ .

Lemma 3

Let M _t be the mesh at time t satisfying C1–C3 . Let K _t+1 be the deformed mesh at time t + 1. Assume ℓ ≥ 54. Then K _t+1 satisfies $\hat{\mathrm{C}}1$ – $\hat{\mathrm{C}}3$ .

Proof

Consider $\hat{\mathrm{C}}1$. Let u be the nearest vertex of v in K _t+1. Suppose u and v are at u′ and v′, respectively, at time t. By C1, both Δ _t (v′) and Δ _t (u′) are less than d(u′, v′)∕20. Therefore, $\mathit{n}_{K_{t+1}}(v) = d(u,v) \geq d(u',v') -\varDelta _{t}(v') -\varDelta _{t}(u') \geq 0.9d(u',v') \geq 0.9\mathit{n}_{M_{t}}(v')$. which is at least $18(\sin \alpha _{0})^{-1}\varDelta _{t}(v)$ by C1.

$\hat{\mathrm{C}}$ 2 requires that for every triangle τ and every vertex v in $B(c_{\tau }, \frac{1} {2}\ell\gamma _{\tau })$, $\mathit{n}_{K_{t+1}}(v)$ is at least $\frac{1} {2}\lambda \gamma _{\tau }$. Let u be the vertex of τ. Let u′, v′ and τ′ be the counterparts of u, v and τ in M _t . $d(v',u') \leq d(v,c_{\tau }) + d(u,c_{\tau }) +\varDelta _{t}(u') +\varDelta _{t}(v') \leq (\ell/2 + 1)\gamma _{\tau } + d(v',u')/10$. Rearranging the terms, we obtain $d(v',u') \leq \frac{10} {9} \left (\frac{1} {2}\,\ell + 1\right )\gamma _{\tau } <(\ell-1)\gamma _{\tau '}$ by Lemma 2 and the fact that ℓ ≥ 54. Since $d(v',c_{\tau '}) \leq d(v',u') +\gamma _{\tau '} \leq \ell\gamma _{\tau '}$, C2 implies that $\mathit{n}_{M_{t}}(v') \geq \lambda \gamma _{\tau '}$ and hence $\mathit{n}_{K_{t+1}}(v) \geq 0.9\mathit{n}_{M_{t}}(v') \geq 0.9\lambda \gamma _{\tau '}$. Lemma 2 further implies that $\mathit{n}_{K_{t+1}}(v) \geq 0.9\lambda \gamma _{\tau '} \geq \frac{0.9\lambda \gamma _{\tau }} {1+14/20}> \frac{1} {2}\,\lambda \gamma _{\tau }$, establishing $\hat{\mathrm{C}}2$.

Consider $\hat{\mathrm{C}}$ 3. Let v be a vertex in K _t+1, and p a sample point in points(v). Suppose they are at v′ and p′ at time t, respectively. By C1 and C3, $d(p,v) \leq d(p',v')+\varDelta _{t}(p')+\varDelta _{t}(v') \leq 2\mathit{R}_{M_{t}}(v')+\varDelta _{t}(p')+\mathit{n}_{M_{t}}(v')/20 \leq 2.1\mathit{R}_{M_{t}}(v')+\varDelta _{t}(p')$. If Δ _t (p′) ≤ d(p′, v′), $\varDelta _{t}(p') \leq d(p',v') \leq 2\mathit{R}_{M_{t}}(v')$. Otherwise, by our assumption on the smoothness of the deformation, $\varDelta _{t}(p') \leq c\varDelta _{t}(v')$ for some constant c. Therefore, $\varDelta _{t}(p') \leq c\varDelta _{t}(v') \leq c\mathit{n}_{M_{t}}(v')/20 \leq c\mathit{R}_{M_{t}}(v')/10$. In both cases, $d(p,v) <(5 + c/10)\mathit{R}_{M_{t}}(v') = O(R_{K_{t+1}}(v))$ by Lemma 2. □ 

4 Refinement

In the first iteration, the input to Refine is K _t+1. In remaining iterations, we feed it with the output of Decimate. Inductively, the input mesh X of Refine is an ($\varepsilon _{X},\alpha _{0})$-mesh satisfying $\hat{\mathrm{C}}$ 1–$\hat{\mathrm{C}}$ 3 for some $\varepsilon _{X} \leq \varepsilon _{1}$. Our goal is to improve the sampling condition from $\varepsilon _{X}$ to $O(\lambda \varepsilon _{X})$.

First, we update the point lists of every vertex, so that a non-vertex sample point is stored in the point list of its nearest vertex. As a result, for every non-vertex sample point p and the vertex u such that p ∈ points(u), d(p, u) ≤ 2R _X (u). Then, initialize an intermediate mesh T to be X and incrementally inserts points. We go through the points in P _t+1 that are not vertices and insert those that are far away from existing vertices. Let p be the current non-vertex point being processed. Let u be the vertex of X such that p is stored in points(u). Let w be the vertex of the current mesh T nearest to p, which must lie in B(u, 4R _X (u)) because d(u, w) ≤ d(u, p) + d(p, w) ≤ 2d(p, u) ≤ 4R _X (u). We find w by searching T within B(u, 4R _X (u)). If the distance between p and w is less than λ R _X (u) or $20(\sin \alpha _{0})^{-1}\varDelta _{t+1}(p)$, skip p; otherwise, insert p as explained below.

Suppose that p is a candidate point to be inserted. We apply a result to be introduced shortly, Theorem 1(iii), to the vertices whose incident triangles intersect B(u, 4R _X (u)). In the end, all the triangles intersecting B(u, 4R _X (u)) have almost empty diametric balls, and so do their neighboring triangles. The common edge ab between two triangles abc and abd is flippable if and only if the diametric ball of abc contains d in its interior and the diametric ball of abd contains c in its interior.

In particular, the triangle $v_{1}v_{2}v_{3}$ nearest to p has an almost empty diametric ball, because the distance between u and the nearest triangle $v_{1}v_{2}v_{3}$ is at most $d(u,p) + d(p,v_{1}v_{2}v_{3}) \leq 2d(u,p) \leq 4\mathit{R}_{X}(u)$. We insert p by calling Add(T, p, $v_{1}v_{2}v_{3}$). It works as follows. Compute the point $\tilde{p}$ in $v_{1}v_{2}v_{3}$ nearest to p. Split $v_{1}v_{2}v_{3}$ using $\tilde{p}$. That is, we replace $v_{1}v_{2}v_{3}$ by three triangles $\tilde{p}v_{1}v_{2}$, $\tilde{p}v_{2}v_{3}$ and $\tilde{p}v_{3}v_{1}$. Flip the edges $v_{1}v_{2}$, $v_{2}v_{3}$ and $v_{1}v_{3}$ if they are flippable. Finally, for each triangle incident to $\tilde{p}$, replace its vertex $\tilde{p}$ by p. This adds p as a vertex to T.

After all the insertions, we flip the flippable edges in T, and migrate all non-vertex sample points to the point lists of their nearest vertices in the current mesh.

4.1 Mesh Properties

To analyze Refine, we need some surface sampling results in the literature and some properties of $(\varepsilon,\alpha )$-meshes that we established in another paper [8]. Some preliminary analogous results can be found in [7].

Lemma 4 ([2, 11, 13])

Let p, q and r be any three points on Σ.

• (i) For every $\varepsilon \leq 1/3$ , if $d(p,q) \leq \varepsilon f(p)$ , then $\angle (\mathbf{n}_{p},pq) \geq \pi /2-\varepsilon$ and $\angle (\mathbf{n}_{p},\mathrm{\mathbf{n}}_{q}) \leq 2\varepsilon$ .

• (ii) For every $\varepsilon \leq 1/10$ , if $\gamma _{\mathit{pqr}} \leq \varepsilon f(p)$ , then $\angle (\mathbf{n}_{p},\mathbf{n}_{\mathit{pqr}}) \leq 10\varepsilon$ .

• (iii) For every $\varepsilon \leq 1/4$ and every point z on tangent plane at p, if $d(p,z) \leq \varepsilon f(p)$ , then $d(z,\varSigma ) \leq \varepsilon d(p,z)$ .

Lemma 5 ([8])

Let p, q and r be any three points on Σ. Let c be any positive constant. Suppose that $\gamma _{\mathit{pqr}} \leq c\varepsilon f(p)$ for some $\varepsilon <\min \{ 1,1/(72c)\}$ . Then, for every point x in the circumdisk of pqr, $d(x,\varphi (x)) \leq 10c\varepsilon \,d(p,x) \leq 20c^{2}\varepsilon ^{2}f(p)$ and $d(p,\varphi (x)) \leq (2c\varepsilon + 20c^{2}\varepsilon ^{2})f(p)$ .

Lemma 6 ([8])

Let $\mu = 2(\csc\alpha)^{4\pi/\alpha+1}$ . There exists an $\varepsilon _{0} \in (0,1)$ depending on α such that for every $\varepsilon \in (0,\varepsilon _{0}]$ , if If T is an $(\varepsilon,\alpha )$ -mesh of Σ, then

• (i) For each vertex p ∈ T and every triangle τ ∈ star (p), $\gamma _{\tau } \leq \mu \varepsilon f(p)$ and $\angle _{a}(\mathbf{n}_{p},\mathbf{n}_{\tau }) <6\mu \varepsilon$ .

• (ii) For every pair of triangles σ,τ ∈ T that share an edge, the dihedral angle at $\sigma \cap \tau$ is greater than $\pi -12\mu \varepsilon$ .

Lemma 7 ([8, 17])

For all c > 1, if T is an $(\varepsilon,\alpha )$ -mesh of Σ for a small enough $\varepsilon$ , then for every vertex p ∈ T, $\vert T\vert \cap B(p,c\mu \varepsilon f(p))$ is connected and it projects injectively onto any plane that makes an angle at least π∕3 with n _p .

Theorem 1 ([7, 8])

For every constant c ∈ (0,0.5) and every constant α ∈ [0,π∕3], there exists $\varepsilon _{0} \in (0,1)$ depending on c and α such that for every $\varepsilon \in (0,\varepsilon _{0}]$ , if T is an $(\varepsilon,\alpha )$ -mesh of a connected closed smooth surface, then the following properties are satisfied. The common edge ab between two triangles abc and abd is flippable if and only if the diametric ball of abc contains d in its interior and the diametric ball of abd contains c in its interior.

• (i) We can flip flippable edges in T until no edge is flippable in time linear in the number of vertices in T. An $(\varepsilon,\alpha )$ -mesh T′ is produced in the end and for every triangle τ ∈ T′, $B(c_{\tau },(1 -\varepsilon ^{c})\gamma _{\tau })$ does not contain any vertex.

• (ii) For every vertex p ∈ T and every triangle τ ∈ star (p), if $B(c_{\tau },(1 -\varepsilon ^{c})\gamma _{\tau })$ does not contain any vertex, then $\gamma _{\tau } \leq (\varepsilon +O(\varepsilon ^{1+c}))f(p)$ .

• (iii) Given any subset V of vertices of T, we can flip flippable edges in O(|V |) time to produce an $(\varepsilon,\alpha )$ -mesh T′ so that for every triangle τ ∈ T′ that is incident to a vertex in V or a neighbor of a vertex in V, $B(c_{\tau },(1 -\varepsilon ^{c})\gamma _{\tau })$ does not contain any vertex.

4.2 Analysis of Refinement

We apply the mesh properties to analyze the effects of refinement. The proofs of the next two technical lemmas are straightforward and omitted.

Lemma 8

Let T be an $(\varepsilon,\alpha )$ -mesh of Σ for a sufficiently small $\varepsilon$.

• (i) For every point x in the circumdisk of a triangle τ ∈ T, $d(x,\varphi (x)) \leq 10\mu \varepsilon \gamma _{\tau } \leq 10\mu ^{2}\varepsilon ^{2}f(\varphi (x))$ .

• (ii) For every point y ∈Σ, the distance between y and its nearest point z ∈|T| is at most $10\mu ^{2}\varepsilon ^{2}f(y)$ . For any triangle σ ∈ T that contains z, $d(y,z) <24\mu \varepsilon \gamma _{\sigma }$ .

Lemma 9

Let T ₁ and T ₂ be a $(\xi _{1},\theta _{1})$ -mesh and a (ξ ₂ ,θ ₂ )-mesh of Σ, respectively, possibly with different vertex sets. Let τ be a triangle in T ₁ . Let σ be the triangle in T ₂ nearest to $\varphi (c_{\tau })$.

• (i) $d(c_{\tau },\sigma ) \leq 10\mu \xi _{1}\gamma _{\tau } + 24\mu \xi _{2}\gamma _{\sigma }$ .

• (ii) Let β be any constant in the range (0,1]. Assume that ξ ₁ and ξ ₂ are sufficiently small. If B(c _τ ,βγ _τ ) does not contain any vertex of T ₂ , then $\gamma _{\sigma } \geq 0.9\beta \gamma _{\tau }$ .

Throughout the procedure, we need to maintain certain invariants so that the local edge-flip algorithm works (which requires a constant lower bound on angles).

Lemma 10

Let X be an $(\varepsilon _{X},\alpha _{0})$ -mesh satisfying $\hat{\mathrm{C}}1$ – $\hat{\mathrm{C}}3$ . During the execution of Refine(X),the following invariants on the intermediate mesh T are maintained.

• (i) For every vertex a in X and every vertex b in T, if $d(a,b) \leq (\ell/4 - 3)\mathit{R}_{X}(a)$ , then $\mathit{n}_{T}(b) \geq \frac{1} {4}\lambda ^{2}\mathit{R}_{ X}(a)$ .

• (ii) T is an $(\varepsilon _{X},\theta )$ -mesh for some constant θ > 0.

Proof

Consider invariant (i). Let T be the mesh just after we add a vertex p. Let u be the vertex of X nearest to p. It is also the vertex whose point list contains p at the beginning of the main loop.

We first show that invariant (i) holds for b = p. Let a be any vertex in X such that $d(a,p) \leq (\ell/4 - 3)\mathit{R}_{X}(a)$. If R _X (a) ≤ R _X (u), then since $\mathit{n}_{T}(p) \geq \lambda \mathit{R}_{X}(u)$ for us to decide to insert p, we have $\mathit{n}_{T}(p) \geq \lambda \mathit{R}_{X}(a)$ as desired. Assume that $\mathit{R}_{X}(a)> \mathit{R}_{X}(u)$. We have $d(a,u) \leq d(a,p) + d(p,u) \leq (\ell/4 - 3)\mathit{R}_{X}(a) + 2\mathit{R}_{X}(u) <(\ell/4 - 1)\mathit{R}_{X}(a)$. Let τ be the triangle incident to a in X with the largest circumradius, i.e., $\gamma _{\tau } = \mathit{R}_{X}(a)$. Then, $d(u,c_{\tau }) \leq d(a,u) + d(a,c_{\tau }) \leq (\ell/4)\gamma _{\tau }$. So $\hat{\mathrm{C}}2$ applies and implies that $\mathit{R}_{X}(u) \geq \frac{1} {2}\,\mathit{n}_{X}(u) \geq \frac{1} {4}\lambda \gamma _{\tau } = \frac{1} {4}\lambda \mathit{R}_{X}(a)$. Since $\mathit{n}_{X}(p) \geq \lambda \mathit{R}_{X}(u)$ for us to insert p, we conclude that $\mathit{n}_{X}(p) \geq \frac{1} {4}\lambda ^{2}\mathit{R}_{ X}(a)$. This proves invariant (i) for the new vertex $p$.

Now consider a vertex b of T other than p. If the nearest vertex to b is not changed by the insertion of p, then invariant (i) holds for b inductively. Assume that the nearest vertex of b becomes p. Let a be any vertex of X such that $d(a,b) \leq (\ell/4 - 3)\mathit{R}_{X}(a)$. If R _X (a) ≤ R _X (u), then $\mathit{n}_{T}(b) = d(p,b) \geq \mathit{n}_{T}(p) \geq \lambda \mathit{R}_{X}(u) \geq \lambda \mathit{R}_{X}(a)$. So invariant (i) holds for b in this case. Assume that R _X (a) > R _X (u). Since p is the nearest vertex of b, we have $d(p,b) \leq d(a,b) \leq (\ell/4 - 3)\mathit{R}_{X}(a)$. This implies that $d(a,u) \leq d(a,b) + d(p,b) + d(p,u) \leq (\ell/2 - 4)\mathit{R}_{X}(a)$. Then, we can invoke the same analysis as in the previous paragraph to show that $\mathit{R}_{X}(u) \geq \frac{1} {4}\lambda \mathit{R}_{X}(a)$.

It follows that $\mathit{n}_{X}(b) = d(p,b) \geq \mathit{n}_{X}(p) \geq \frac{1} {4}\lambda ^{2}\mathit{R}_{ X}(a)$. This proves invariant (i).

Consider invariant (ii). The mesh density cannot decrease because vertices are being inserted. We show that any new angle in X is at least some constant θ after inserting a point p. We omit the argument for establishing the bound on the triangle circumradii and the nearest point map being a homeomorphism as required by the definition of an $(\varepsilon _{X},\theta )$-mesh, which is similar to the proof of Theorem 1(i) [8].

Suppose that a point p is inserted into the triangle $v_{1}v_{2}v_{3}$. That is, $v_{1}v_{2}v_{3}$ is the closest triangle to p in the current mesh and we split $v_{1}v_{2}v_{3}$ into three smaller triangles by connecting the three vertices to the projection $\tilde{p}$ of p on $v_{1}v_{2}v_{3}$. Let $\mathit{qv}_{1}v_{2}$ be the triangle that shares $v_{1}v_{2}$ with $\tilde{p}v_{1}v_{2}$.

We first bound the angles in the triangle $\mathit{qv}_{1}v_{2}$ from below. Applying Theorem 1(iii) makes the diametric ball of $\mathit{qv}_{1}v_{2}$ almost empty. Thus, $B(c_{\mathit{qv}_{1}v_{2}},0.8\gamma _{\mathit{qv}_{1}v_{2}})$ does not contain any vertex of X. Then by Lemma 9, we can find a triangle σ in X such that $\gamma _{\sigma }> 0.7\gamma _{\mathit{qv}_{1}v_{2}}$, and $d(c_{\mathit{qv}_{1}v_{2}},\sigma ) <0.1\gamma _{\mathit{qv}_{1}v_{2}} + 0.1\gamma _{\sigma }$. Take the vertex a of σ nearest to $c_{\mathit{qv}_{1}v_{2}}$. The distance between a and any vertex of $\mathit{qv}_{1}v_{2}$ is at most

$$\displaystyle{ d(a,c_{\mathit{qv}_{1}v_{2}}) +\gamma _{\mathit{qv}_{1}v_{2}} <\gamma _{\sigma } + (0.1\gamma _{\mathit{qv}_{1}v_{2}} + 0.1\gamma _{\sigma }) +\gamma _{\mathit{qv}_{1}v_{2}} <3\gamma _{\sigma }. }$$

(1)

Thus, invariant (i) applies to a and any vertex of $\mathit{qv}_{1}v_{2}$. We conclude that $\mathit{qv}_{1}v_{2}$ has edge lengths at least $\frac{1} {4}\lambda ^{2}\mathit{R}_{ X}(a) \geq \frac{1} {4}\lambda ^{2}\gamma _{ \sigma }> \frac{1} {6}\lambda ^{2}\gamma _{ \mathit{qv}_{1}v_{2}}$. The angles in $\mathit{qv}_{1}v_{2}$ are then at least $\psi =\arcsin (\lambda ^{2}/12)$. Similarly, all angles in $v_{1}v_{2}v_{3}$ are at least ψ.

Since we decide to insert p, $\mathit{n}_{T}(p) \geq \lambda \mathit{R}_{X}(u)$. As argued in proving (i), this leads to $\mathit{n}_{T}(p) \geq \frac{1} {4}\lambda ^{2}\mathit{R}_{ X}(a)$, so $\mathit{n}_{T}(p)> \frac{1} {6}\lambda ^{2}\gamma _{ \mathit{qv}_{1}v_{2}}$. This implies that d(p, v ₁) and d(p, v ₂) are at least $\frac{1} {6}\lambda ^{2}\gamma _{ \mathit{qv}_{1}v_{2}}$. Since $\tilde{p}$ is the point on the current mesh nearest to p, Lemma 8(ii) implies that $d(p,\tilde{p}) \leq (40\kappa _{\mathrm{rad}}\varepsilon _{X})\gamma _{v_{1}v_{2}v_{3}} \leq \frac{40\kappa _{\mathrm{rad}}\varepsilon _{X}} {\sin \psi } \gamma _{\mathit{qv}_{1}v_{2}} \leq \frac{40\kappa _{\mathrm{rad}}\varepsilon _{1}} {\sin \psi } \,\gamma _{\mathit{qv}_{1}v_{2}}$. So for a small enough $\varepsilon _{1}$, $d(\tilde{p},v_{1})$ and $d(\tilde{p},v_{2})$ are at least $\frac{1} {7}\lambda ^{2}\gamma _{ \mathit{qv}_{1}v_{2}}$.

Suppose that $\gamma _{\mathit{qv}_{1}v_{2}} \geq \gamma _{\tilde{p}v_{1}v_{2}}\sin (\psi /2)$. So $\sin \angle \tilde{p}v_{1}v_{2} = \frac{d(\tilde{p},v_{2})} {2\gamma _{\tilde{p}v_{1}v_{2}}} \geq \frac{\frac{1} {7} \lambda ^{2}\gamma _{ \mathit{qv}_{1}v_{2}}} {2\gamma _{\mathit{qv}_{1}v_{2}}/\sin (\psi /2)} \geq \frac{\lambda ^{2}} {14}\sin (\psi /2)$. It follows that $\angle \tilde{p}v_{2}v_{1} \geq \arcsin {\bigl ( \frac{\lambda ^{2}} {14}\sin (\psi /2)\bigr )}$. Similarly, $\angle \tilde{p}v_{2}v_{1} \geq \arcsin {\bigl ( \frac{\lambda ^{2}} {14}\sin (\psi /2)\bigr )}$. Also, we have $\angle v_{1}\tilde{p}v_{2} \geq \angle v_{1}v_{3}v_{2} \geq \psi$.

Suppose that $\gamma _{\mathit{qv}_{1}v_{2}} \leq \gamma _{\tilde{p}v_{1}v_{2}}\sin (\psi /2)$. We claim that $v_{1}v_{2}$ is flippable. Since $\angle v_{1}\tilde{p}v_{2} \geq \angle v_{1}v_{3}v_{2} \geq \psi$ and $\sin \angle v_{1}\tilde{p}v_{2} = \frac{d(v_{1},v_{2})} {2\gamma _{\tilde{p}v_{1}v_{2}}} \leq \frac{2\gamma _{\mathit{qv}_{1}v_{2}}} {2\gamma _{\tilde{p}v_{1}v_{2}}} \leq \sin (\psi /2)$, the angle $\angle v_{1}\tilde{p}v_{2}$ must be obtuse and greater than $\pi -\psi /2$. Imagine that we rotate $v_{1}\tilde{p}v_{2}$ while fixing $v_{1}v_{2}$ to make the dihedral angle between $v_{1}\tilde{p}v_{2}$ and $v_{1}qv_{2}$ larger. Since $\angle v_{1}\tilde{p}v_{2}>\pi /2$, $\tilde{p}$ moves closer to the boundary of the diametric ball of $v_{1}qv_{2}$ as we rotate $v_{1}\tilde{p}v_{2}$. Let p′ be the point in the plane of $v_{1}v_{2}q$ such that $\angle v_{1}p'v_{2} = \angle v_{1}\tilde{p}v_{2}$ and it is on the different side of $v_{1}v_{2}$ from q. So $\tilde{p}$ is in the diametric ball of $v_{1}qv_{2}$, if p′ is in the diametric ball of $v_{1}qv_{2}$, which is true because $\angle v_{1}p'v_{2} + \angle v_{1}qv_{2} <\pi$. We show below that q also lies inside the diametric ball of $v_{1}v_{2}\tilde{p}$, and hence $v_{1}v_{2}$ is flippable. The plane of $v_{1}v_{2}q$ intersects $B_{v_{1}v_{2}\tilde{p}}$ in a disk D with radius $\gamma \geq (1 - O(\varepsilon ))\gamma _{v_{1}v_{2}\tilde{p}}$, as the dihedral angle between $v_{1}v_{2}q$ and $v_{1}v_{2}\tilde{p}$ is $\pi -O(\varepsilon )$. If q is outside $B_{v_{1}v_{2}\tilde{p}}$, then q is outside D, and $\psi \leq \angle v_{1}qv_{2} \leq \arcsin \left (\frac{d(v_{1},v_{2})} {2\gamma } \right )$. Since $d(v_{1},v_{2}) = 2\gamma _{v_{1}v_{2}\tilde{p}}\sin \angle v_{1}\tilde{p}v_{2} \leq 2\gamma _{v_{1}\tilde{p}v_{2}}\sin (\psi /2)$, we get $\sin \psi \leq (1 + O(\varepsilon ))\sin (\psi /2) \Leftrightarrow 2\cos (\psi /2) \leq 1 + O(\varepsilon )$, which is impossible for ψ < π∕3. So q lies inside the diametric ball of $v_{1}v_{2}\tilde{p}$.

Flipping $v_{1}v_{2}$ produces $v_{1}\tilde{p}q$ and $v_{2}\tilde{p}q$. First, $\angle \tilde{p}v_{1}q \geq v_{2}v_{1}q \geq \psi$, as the dihedral angle between $\mathit{qv}_{1}v_{2}$ and $\tilde{p}v_{1}v_{2}$ is obtuse. Next, if $\angle v_{1}\tilde{p}q$ is non-obtuse, since $v_{1}v_{2}$ is flippable, one can show that $\angle v_{1}\tilde{p}q \geq \angle v_{1}v_{2}q \geq \psi$ [8]. If $\angle v_{1}\tilde{p}q$ is obtuse, it is less than $\pi -\angle \tilde{p}v_{1}q \leq \pi -\psi$. This implies that $\sin \angle v_{1}\tilde{p}q \geq \sin \psi$. Finally, we can bound $\angle v_{1}q\tilde{p}$: $\sin \angle v_{1}q\tilde{p} = \frac{d(\tilde{p},v_{1})} {d(q,v_{1})} \cdot \sin \angle v_{1}\tilde{p}q \geq \frac{\frac{1} {7} \lambda ^{2}\gamma _{ \mathit{qv}_{1}v_{2}}} {2\gamma _{\mathit{qv}_{1}v_{2}}} \cdot \sin \psi = (\lambda ^{2}/14)\sin \psi$. A similar argument bounds the angles in $v_{2}q\tilde{p}$ from below.

So all new angles are at least min{ψ, ψ′, ψ″} before lifting the triangles incident to $\tilde{p}$ to p, where $\psi ' =\arcsin {\bigl ( \frac{\lambda ^{2}} {14}\sin (\psi /2)\bigr )}$, and $\psi '' =\arcsin {\bigl ( \frac{\lambda ^{2}} {14}\sin \psi \bigr )}$. Since p is very close to $\tilde{p}$, the lifting decreases the angles by only a constant factor. So an angle lower bound θ can be preserved by an appropriate setting of θ. □ 

The lemma below summarizes the properties of the final mesh obtained.

Lemma 11

Let X be an $(\varepsilon _{X},\alpha _{0})$ -mesh satisfying $\hat{\mathrm{C}}$ 1–$\hat{\mathrm{C}}$ 3. Refine(X) runs in time linear in the number of sample points, and produces a mesh Y such that:

• (i) For every triangle τ in Y, there is no vertex in B(c _τ ,0.8γ _τ ), and if a vertex v lies in $B{\bigl (c_{\tau },(\ell/6 - 4)\gamma _{\tau }\bigr )}$ , then $\mathit{n}_{Y }(v) \geq \frac{1} {6}\lambda ^{2}\gamma _{ \tau }$ .

• (ii) Y is an $(\varepsilon _{Y },\theta )$ -mesh, where θ ∈ (0,π∕3] and $\varepsilon _{Y } =\max \{ 0.3\varepsilon _{0},4\mu \lambda \varepsilon _{X}\}$ .

Proof

Consider the running time of Refine(X). We first show that updating the nearest vertex for each sample point takes O(1) time. For every non-vertex sample point p, it is initially stored in the list of some vertex u such that d(p, u) = O(R _X (u)), as X satisfies $\hat{\mathrm{C}}$ 3. Set ℓ large enough so that $2d(p,u) \leq (\ell/2)\mathit{R}_{X}(u)$. The distance between p and its nearest vertex w is at most d(p, u), so d(w, u) ≤ 2d(p, u). All triangles intersecting B(u, 2d(p, u)) are connected, and they project injectively in the tangent plane at u by Lemma 7. $\hat{\mathrm{C}}$ 2 ensures that all edges of those triangles have lengths at least Ω(R _X (u)). Since all angles in X are at least some constant, a standard packing argument shows that there are only O(1) triangles intersecting B(u, 2d(p, u)). Therefore, we can search for the nearest vertex of p by traversing the triangles intersecting B(u, 2d(p, u)) in O(1) time.

Inside the main loop, for each sample point p, we need to find its nearest vertex again. The point p is stored in the point list of the vertex u in X nearest to p. So d(p, u) ≤ 2R _X (u). Lemma 10(ii) ensures that all angles in an intermediate mesh are at least some constant. Lemma 10(i) implies that all edges intersecting B(u, 4R _X (u)) have lengths Ω(R _X (u)). Then the nearest vertex of p can be found in O(1) time by the same reasoning. Consider edge flips before the search for the nearest triangle of p. There are constant number of vertices whose incident triangles intersect B(u, 4R _X (u)). So by Theorem 1(iii), it takes O(1) time to flip edges so that their incident triangles have almost empty diametric balls. Finding the nearest triangle of p can also be done in O(1) time by traversing the triangles intersecting B(u, 4R _X (u)). The remaining operations in the main loop clearly take O(1) time.

The post-processing, including the edge flips and point migrations, can be done in linear time. Therefore, Refine runs in linear time.

Consider (i). Since edges are flipped in post-processing until none is flippable, Theorem 1(i) any triangle τ in Y, $B(c_{\tau },0.8\gamma _{\tau })$ does not contain any vertex. Let v be a vertex such that $d(v,c_{\tau }) \leq (\ell/6 - 4)\gamma _{\tau }$. By Lemma 9, we can find a triangle σ in X such that $d(c_{\tau },\sigma ) <0.1(\gamma _{\tau } +\gamma _{\sigma })$ and $\gamma _{\sigma } \geq 0.7\gamma _{\tau }$. Let a be a vertex of σ. So we have $d(a,v) \leq d(a,c_{\tau }) + d(v,c_{\tau }) \leq 2\gamma _{\sigma } + 0.1(\gamma _{\tau } +\gamma _{\sigma }) + (\ell/6 - 4)\gamma _{\tau } \leq (\ell/4 - 3)\gamma _{\sigma }$. Lemma 10(i) applies and implies that $\mathit{n}_{Y }(v) \geq \frac{1} {4}\lambda ^{2}\mathit{R}_{ X}(a) \geq \frac{1} {4}\lambda ^{2}\gamma _{ \sigma }> \frac{1} {6}\lambda ^{2}\gamma _{ \tau }$.

Consider (ii). The angle lower bound θ follows from Lemma 10(ii). It remains to show that the vertices of Y form an $\varepsilon _{Y }$-sample of Σ _t+1. Take any point x in Σ _t+1. Since P _t+1 remains an $\varepsilon$-sample of Σ _t+1 in our motion model, there exists p ∈ P _t+1 such that $d(p,x)\, \leq \,\varepsilon f_{t+1}(x)$. If p is a vertex of Y, we are done. Suppose that p is not a vertex of Y. Let u be the vertex of X where p ∈ points(u). Recall that, before the main loop, we move every sample point to the point list of its nearest vertex in X, so d(p, u) ≤ 2R _X (u). Let w′ be the nearest vertex to p in the intermediate mesh when we decided not to insert p. Let w be the vertex of Y nearest to p. The point p was not inserted because $d(p,w') \leq 20(\sin \alpha _{0})^{-1}\varDelta _{t+1}(p)$ or d(p, w′) ≤ λ R _X (u). Since nearest vertex distances can only decrease in the insertion phase, we have $d(p,w) \leq d(p,w') \leq 20(\sin \alpha _{0})^{-1}\varDelta _{t+1}(p)$ or d(p, w) ≤ d(p, w′) ≤ λ R _X (u).

In the case that $d(p,w) \leq 20(\sin \alpha _{0})^{-1}\varDelta _{t+1}(p)$, we have $d(p,w) \leq 0.1\varepsilon _{0}f_{t+1}(p)$ as $\varDelta _{t+1}(p) \leq (0.005\varepsilon _{0}\sin \alpha _{0})f_{t+1}(p)$ by the smoothness of the deformation. Then, $d(w,x) \leq d(p,w) + d(p,x) \leq 0.1\varepsilon _{0}f_{t+1}(p) +\varepsilon f_{t+1}(x)$. The Lipschitzness of LFS implies that $d(w,x) \leq 0.1\varepsilon _{0}(1+\varepsilon )f_{t+1}(x) +\varepsilon f_{t+1}(x) <0.3\varepsilon _{0}f_{t+1}(x)$ because we assume that $\varepsilon _{0} \geq 10\varepsilon$. Therefore, $d(w,x) \leq \varepsilon _{Y }f_{t+1}(x)$.

Thus, the requirement of an $\varepsilon _{Y }$-sample is fulfilled by the vertex w of Y.

Consider the case that d(p, w) ≤ λ R _X (u). Since X is an $(\varepsilon _{X},\alpha _{0})$-mesh, $d(p,u) \leq 2\mathit{R}_{X}(u) \leq 2\mu \varepsilon _{X}f_{t+1}(u)$. So $d(u,x) \leq d(p,u) + d(p,x) \leq 2\mu \varepsilon _{X}f_{t+1}(u) +\varepsilon f_{t+1}(x)$. The Lipschitzness of LFS implies that $f_{t+1}(u) \leq (1 + 2\varepsilon + 4\mu \varepsilon _{X})f_{t+1}(x) <2f_{t+1}(x)$. So $d(p,w) \leq \lambda \mathit{R}_{X}(u) \leq \mu \lambda \varepsilon _{X}f_{t+1}(u) = 2\mu \lambda \varepsilon _{X}f_{t+1}(x)$, and $d(w,x) \leq d(p,w) + d(p,x) \leq (2\mu \lambda \varepsilon _{X}+\varepsilon )f_{t+1}(x) \leq \max \{ 4\mu \lambda \varepsilon _{X},2\varepsilon \} \cdot f_{t+1}(x) <\varepsilon _{Y }f_{t+1}(x)$. □ 

5 Decimation

Some vertices must be deleted in order to increase the inter-vertex distances. This will restore conditions C1 and C2 and the angle lower bound $\alpha _{0} =\varOmega (\lambda )$. Let Y be the output of the refinement phase. Our idea is to define a decimation radius δ _v for each vertex v of Y sensitive to the triangle circumradii nearby, so that if we keep v, then the vertices at distance less than radius δ _v from v should be deleted. We want the decimation radius to satisfy the following properties.

P1::

For any two vertices v and u, $\delta _{v} -\delta _{u} \leq (\lambda /\ell)d(v,u)$.

P2::

There exists a constant κ _dec such that for each vertex v, $\delta _{v} \geq 4\lambda \mathit{R}_{Y }(v)$ and there exists a triangle τ in Y such that $d(v,c_{\tau }) \leq \kappa _{\mathrm{dec}}\gamma _{\tau }$ and $\delta _{v} \leq \frac{1} {15}\gamma _{\tau }$.

P1 ensures that the function is smooth, so after the decimation, the nearest vertex distances of close vertices are similar. P2 provides lower and upper bounds on the decimation radius.

Define the decimation radius $\delta _{v} =\max \{ 4\lambda \gamma _{\tau } - (\lambda /\ell)d(v,c_{\tau }): \mbox{triangle $\tau in Y$ }\}$. It is easy to verify that it satisfies P1 and P2 with κ _dec = 4ℓ for $4\lambda \leq \frac{1} {15}$. To evaluate the decimation radii for all vertices, we perform a breadth-first search from each triangle τ, update the decimation radii at the vertices visited, and stop at edges e where $4\lambda \gamma _{\tau } \leq (\lambda /\ell)d(e,c_{\tau })$.

Algorithm 1 Delete(mesh T, vertex w)

Vertex deletions cannot be performed in an arbitrary order because this may produce tiny angles in an intermediate mesh that makes it impossible to apply Theorem 1(iii) in subsequent vertex deletions. To avoid this problem, we decimate vertex neighborhoods gradually in rounds as explained below.

Define n _min to be the smallest distance between two vertices in Y. Define $\delta _{\max } =\max {\bigl \{\max \{\delta _{v},20(\sin \alpha _{0})^{-1}\varDelta _{t+1}(v)\}: \text{vertex v in Y.}\bigr \}}$. Place the vertices of Y into lists $S_{0},\ldots,S_{m}$ such that S _i contains v iff $2^{i}\mathit{n}_{\min } \leq \mathit{n}_{Y }(v) <2^{i+1}\mathit{n}_{\min }$, where $m =\max \{ 0,\lfloor \log _{2}(\delta _{\max }/\mathit{n}_{\min })\rfloor \}$. This can be done in O(m + n) time as follows without assuming constant-time integral logarithm operations. We find m by computing δ _max in O(n) time and computing the integral logarithm in O(m) time in a brute force manner. Then initialize m + 1 empty lists, and insert the vertex v _min with the smallest nearest vertex distance in S _m . Next, start a breadth-first search to traverse the mesh from v _max. Notice that for any two adjacent vertices, their nearest vertex distances differ by a constant factor. So for each vertex encountered during the traversal, knowing at which list any of its adjacent vertices is placed allows us to locate its list in O(1) time.

Then, we initialize a mesh T to be Y and decimate its vertices in m + 1 rounds. In round i, we decimate the neighborhood of each vertex v ∈ S _i as follows.

• 1. Remove v from S _i . If $2^{i}\mathit{n}_{\min } \leq \max \{\delta _{v},20(\sin \alpha _{0})^{-1}\varDelta _{t+1}(v)\}$, delete the vertices in $B(v,2^{i+1}\mathit{n}_{\min })$ other than v from T. Algorithm 1 explains how to delete a vertex from T. Deleted vertices are also removed from the lists $S_{0},\ldots,S_{m}$.

• 2. Compute the nearest vertex distance n _T (v) of v by finding its nearest vertex in the updated mesh T. The nearest vertex of v can be found by traversing the triangles intersecting B(v, d(u, v)) for any edge uv incident to v in T.

• 3. Compute the index j such that $2^{j}\mathit{n}_{\min } \leq \mathit{n}_{T}(v) <2^{j+1}\mathit{n}_{\min }$. We will show in Lemma 16 that $j = i + O(1)$, so j can be computed in O(1) time. If j > m, then n _T (v) ≥ δ _max, so we can drop v. If j ≤ m, we put v in S _j for future processing.

In other words, vertices within distances $2\mathit{n}_{\min },4\mathit{n}_{\min },8\mathit{n}_{\min },\ldots$ from v are deleted in rounds. After processing all vertices in S _m+1, we need to migrate the points in points(w) for each vertex w deleted.

In the end, the algorithm flips edges until none is flippable, and places every point that is not a vertex to the point list of its nearest vertex.

In the following, we show that the algorithm correctly decimates the neighborhood of each vertex (Lemma 12); and it does not over-decimate in the sense that each deleted vertex is at distance $O{\bigl (\max \{\delta _{v},20(\sin \alpha _{0})^{-1}\varDelta _{t+1}(v)\}\bigr )}$ from some vertex v in Z (Lemma 13).

Lemma 12

Let Z be the output mesh of Decimate(Y ). The distance between any vertex v to its nearest vertex in Z is at least $\max \{\delta _{v},20(\sin \alpha _{0})^{-1}\varDelta _{t+1}(v)\}$.

Proof

Throughout the decimation procedure, we maintain the invariant that each vertex v in S _i has nearest vertex distance $\mathit{n}_{Z}(v) \geq 2^{i}\mathit{n}_{\min }$, and we drop it only when $2^{i}\mathit{n}_{\min }>\max \{\delta _{v},20(\sin \alpha _{0})^{-1}\varDelta _{t+1}(v)\}$. So the lemma follows. □ 

Consider a chronological sequence of vertices $(w_{0},w_{1},\ldots,w_{g})$ that satisfies the following properties: (1) for k ∈ [0, g], w _k is a vertex in the initial mesh Y; (2) w _g is a vertex of an intermediate mesh T in Decimate(Y ); (3) for k ∈ [1, g], $w_{k-1} \in B(w_{k},2^{i_{k}+1}\mathit{n}_{\min })$ and w _k−1 was deleted when we processed w _k in some list $S_{i_{k}}$. We call the chronological sequence $(w_{0},w_{1},\ldots,w_{g})$ a deletion chain. It has the following property.

Lemma 13

Let $(w_{0},w_{1},\ldots,w_{g})$ be a deletion chain. Suppose that $w_{g} \in S_{j}$ when w _g−1 was deleted. If $2^{j}\mathit{n}_{\min } \leq \delta _{w_{g}}$ , then $d(w_{0},w_{g}) \leq 2^{j+2}\mathit{n}_{\min } \leq 4\delta _{w_{g}}$ ; otherwise, $d(w_{0},w_{g}) \leq 80(\sin \alpha _{0})^{-1}\varDelta _{t+1}(w_{g}) \leq 0.4\varepsilon _{0}f(w_{g})$ .

Proof

For k ∈ [0, g − 1], after deleting the vertices in $B(w_{k},2^{i_{k}+1}\mathit{n}_{\min })\setminus \{w_{ k}\}$ for some i _k , we cannot delete w _k when examining another vertex in the same list $S_{i_{k}}$. Thus, $w_{k+1} \in S_{i_{k+1}}$ for some $i_{k+1}> i_{k}$ when w _k was deleted. We have $d(w_{0},w_{g}) \leq \sum _{k=1}^{g}d(w_{k-1},w_{k}) \leq \sum _{i=0}^{j}2^{i+1}\mathit{n}_{\min } \leq 2^{j+2}\mathit{n}_{\min }$. Since $w_{g} \in S_{j}$ when w _g−1 was deleted, we have $2^{j}\mathit{n}_{\min } \leq \max \{\delta _{w_{g}},20(\sin \alpha _{0})^{-1}\varDelta _{t+1}(w_{g})\}$. If $2^{j}\mathit{n}_{\min } \leq \delta _{w_{g}}$, we obtain $d(w_{0},w_{g}) \leq 4\delta _{w_{g}}$. Suppose that $2^{j}\mathit{n}_{\min } \leq 20(\sin \alpha _{0})^{-1}\varDelta _{t+1}(w_{g})$. Since we assume that $\varDelta _{t+1}(w_{g}) \leq (0.005\varepsilon _{0}\sin \alpha _{0})f_{t+1}(w_{g})$, we get $d(w_{0},w_{g}) \leq 80(\sin \alpha _{0})^{-1}\varDelta _{t+1}(w_{g}) \leq 0.4\varepsilon _{0}f_{t+1}(w_{g})$. □ 

In Delete(T, w), the first step is to flip edges so that the triangles incident to w have almost empty diametric balls. The next technical result shows the property ensured by this step.

Lemma 14

Consider the intermediate mesh T during Decimate(Y ). Suppose that ℓ is sufficiently large and λ is sufficiently small. (Their settings depend on the hidden constant in assumption (i) in our motion model.) Suppose that all the angles are at least some constant before calling DELETE(T,w). Then after the execution of line 1 of DELETE(T,w), for any vertex v of T, $\mathit{n}_{T}(v) \geq \frac{1} {14}\lambda ^{2}\mathit{R}_{ T}(v)$ .

Proof

Let τ be the triangle incident to v such that $\gamma _{\tau } = \mathit{R}_{T}(v)$. Recall that Y stands for the output mesh of the insertion phase. Let σ be the triangle in Y closest to $\varphi _{\varSigma _{t+1}}(c_{\tau })$. By Lemma 9, we have $d(c_{\tau },\sigma ) <0.1(\gamma _{\tau } +\gamma _{\sigma })$. Let a be any vertex of σ. The distance d(a, c _τ ) is at most $2.1\gamma _{\sigma } + 0.1\gamma _{\tau }$.

Suppose that the vertices of σ lie outside $B(c_{\tau },0.5\gamma _{\tau })$. Then, $\gamma _{\sigma } \geq 0.45\gamma _{\tau }$ by Lemma 9. We have $d(a,v) \leq d(a,c_{\tau }) + d(v,c_{\tau }) \leq 2.1\gamma _{\sigma } + 0.1\gamma _{\tau } +\gamma _{\tau } <5\gamma _{\sigma }$. Then, for ℓ ≥ 54, Lemma 11(i) implies that $\mathit{n}_{T}(v) \geq \mathit{n}_{Y }(v) \geq \frac{1} {6}\lambda ^{2}\gamma _{ \sigma } \geq \frac{1} {14}\lambda ^{2}\gamma _{ \tau }$.

Suppose that some vertex a of σ lies in B(c _τ , 0. 5γ _τ ). There is a deletion chain $(a,\ldots,u,w)$, where w is a vertex in the current T. Since $B(c_{\tau },0.8\gamma _{\tau })$ contains no vertex of T, $d(w,c_{\tau }) \geq 0.8\gamma _{\tau }$. So we have $d(a,w) \geq d(w,c_{\tau }) - d(a,c_{\tau }) \geq 0.3\gamma _{\tau }$ Hence, $d(v,w) \leq d(v,c_{\tau }) + d(a,c_{\tau }) + d(a,w) <1.5\gamma _{\tau } + d(a,w) \leq 6d(a,w)$. Assume that u was deleted when we processed w in some list S _i .

Suppose that $2^{i}\mathit{n}_{\min } \leq \delta _{w}$. Lemma 13 implies that $\delta _{w} \geq \frac{1} {4}\,d(a,w).$ Combining it with the previous inequality and the smoothness of the decimation radii, we have $\delta _{v} \geq \delta _{w} - (\lambda /\ell)d(v,w) \geq \delta _{w} - (24\lambda /\ell)\delta _{w}>\delta _{w}/2$. If we dropped v before processing w (i.e., did not place v in any list for further processing), we must have $\mathit{n}_{T}(v) \geq \delta _{v}$, which is greater than $\frac{1} {2}\delta _{w}$. Then, Lemma 13 implies that $\mathit{n}_{T}(v)>\delta _{w}/2 \geq d(a,w)/8 \geq 0.3\gamma _{\tau }/8$, which is greater than $\lambda ^{2}\gamma _{\tau }/14$. If we did not drop v before processing w, we must have $\mathit{n}_{T}(v) \geq 2^{i}\mathit{n}_{\min }$. Then, Lemma 13 implies that $\mathit{n}_{T}(v) \geq 2^{i}\mathit{n}_{\min }\, \geq \, d(a,w)/4 \geq 0.3\gamma _{\tau }/4$, which is also greater than $\lambda ^{2}\gamma _{\tau }/14$.

If $2^{i}\mathit{n}_{\min }>\delta _{w}$, then $d(a,w) \leq 80(\sin \alpha _{0})^{-1}\varDelta _{t+1}(w)$ by Lemma 13. By assumption, $\varDelta _{t+1}(w) \leq c\varDelta _{t}(w)$ for some constant c. Condition $\hat{\mathrm{C}}$ 1 and the working of Refine ensure that $\mathit{R}_{Y }(w) \geq \mathit{n}_{Y }(w) \geq \frac{18\varDelta _{t}(w)} {\sin \alpha _{0}} \geq \frac{18\varDelta _{t+1}(w)} {c\sin \alpha _{0}} \geq \frac{9d(a,w)} {40c}$. Recall that d(a, w) ≥ 0. 3γ _τ . By property P2 of decimation radii, we have $\delta _{w} \geq 4\lambda \mathit{R}_{Y }(w)> \frac{9} {10c}\lambda d(a,w) \geq \frac{27} {100c}\lambda \gamma _{\tau }$. Set ℓ to be a constant greater than 20c∕3. Then $\delta _{v} \geq \delta _{w} -\frac{\lambda }{\ell}\cdot d(w,v) \geq \delta _{w} -\frac{\lambda }{\ell}\cdot 6d(a,w) \geq \delta _{w} -\frac{\lambda }{\ell}\cdot \frac{10c} {9\lambda } \cdot 6\delta _{w} \geq \delta _{w}/2 \geq \frac{27} {200c}\lambda \gamma _{\tau }$. Then, we can invoke the same analysis in the previous paragraph and show that $\mathit{n}_{T}(v) \geq \lambda ^{2}\gamma _{\tau }/14$ by setting λ small enough. □ 

By Lemma 14, all triangles have angles at least $\arcsin \left ( \frac{1} {28}\lambda ^{2}\right )$ after the execution of line 1 in Delete. This allows us to show that the deletion of a single vertex preserves an Ω(1) lower bound on angles. Then, inductively, any intermediate mesh during the decimation has constant lower bound on its smallest angle.

Lemma 15

At any time during Decimate, DELETE(T,w) produces angles that are at least some constant.

Proof

Consider the deletion of a vertex w from T. We first show that the distance between any two vertices adjacent to w is at least Ω(n _T (w)). Take any two vertices a and b incident to w. If ∠ a w b ≥ π∕2, then d(a, b) ≥ d(a, w) ≥ n _T (w). Suppose ∠ a w b < π∕2. Then $d(a,b) \geq d(a,w) \cdot \sin \angle awb\; \geq \;\mathit{n}_{T}(w) \cdot \sin \angle \mathit{awb}$. Since each angle at w is at least $\arcsin \left ( \frac{1} {28}\lambda ^{2}\right )$ and triangles incident to w are fairly flat, we have $\angle awb \geq \arcsin \left ( \frac{1} {28}\lambda ^{2}\right )$, and hence $d(a,b) \geq \frac{1} {28}\lambda ^{2}\mathit{n}_{ T}(w)$.

Let Q be the projection of the triangles incident to w to the plane of one of these triangles. By Lemma 7, Q is a simple polygon. The distance between any two vertices adjacent to w is shortened by a constant factor by the projection. So the distance between any two vertices of Q is $\varOmega (\lambda ^{2}\mathit{n}_{T}(w))$. In the following, we prove that any triangle τ in the constrained Delaunay triangulation of Q has circumradius at most $\frac{112} {\lambda ^{2}} \mathit{R}_{T}(w)$. Then, the ratio of the shortest edge length of τ to γ _τ is $\varOmega \left (\lambda ^{4} \cdot \frac{\mathit{n}_{T}(w)} {\mathit{R}_{T}(w)}\right ) =\varOmega (1)$, which implies that the smallest angle in τ is Ω(1).

Assume to the contrary that $\gamma _{\tau }> \frac{112} {\lambda ^{2}} \mathit{R}_{T}(w)$. Refer to Fig. 2. Since the distance between w and any vertex incident to w is at most 2R _T (w), each edge of τ is at most 4R _T (w). The large circumradius of τ implies that it has an obtuse angle. Moreover, c _τ lies outside Q because γ _τ is larger than the largest distance between two vertices of Q. Let a be the vertex of τ with an obtuse angle. Since Q contains τ, the line segment ac _τ must intersect at least one edge of Q. Let xy be the one closest to a. Let p denote the intersection point $\mathit{xy} \cap ac_{\tau }$. Both x and y avoid the interior of the circumcircle of τ by the constrained Delaunay condition. The line segment ap is inside Q by our choice of xy. The polygon Q is star-shaped with w in the kernel, so the line segment wp lies inside Q as well. Thus, w and a are on the same side of xy. If $\angle wxy> \angle \mathit{axy}$ and $\angle wyx> \mathit{ayx}$, the triangle wxy would contain a in its interior, which is impossible. So $\angle wxy \leq \angle \mathit{axy}$ or $\angle wyx \leq \mathit{ayx}$. Assume the former is true.

Fig. 2

τ is a constrained Delaunay triangle of the projected polygon Q

Recall that all angles in the triangles incident to w are at least $\arcsin \left ( \frac{1} {28}\lambda ^{2}\right )$. They can be affected by the projection only slightly. So $\angle axy \geq \angle wxy>\arcsin ( \frac{1} {56}\lambda ^{2})$. Since x and y are outside the circumcircle of τ and xy separates a and c _τ , we have $\gamma _{\tau } \leq \gamma _{\mathit{axy}} \leq \frac{d(a,y)} {2\sin \angle axy} \leq \frac{28d(a,y)} {\lambda ^{2}}$. Both a and y are at distance at most 2R _T (w) from w, so d(a, y) ≤ 4R _T (w). It follows that $\gamma _{\tau } \leq \frac{112} {\lambda ^{2}} \mathit{R}_{T}(w)$, a contradiction. □ 

Lemma 16

Let v be a vertex in list S _i . Lines 14–15 of Decimate place v in list S_j for some $j = i + O(1)$.

Proof

Let T be the current mesh. Consider the mesh T′ right before the last vertex u in $B(v,2^{i}\mathit{n}_{\min })\setminus \{v\}$ is deleted. Let w ≠ v be a vertex adjacent to u in T′. By Lemma 15, $d(w,u) \leq c\mathit{n}_{T'}(u) \leq cd(u,v)$ for some constant c. So $d(v,w) \leq d(v,u) + d(u,w) \leq (c + 1)d(v,u) \leq (c + 1)2^{i}\mathit{n}_{\min }$, and the nearest vertex distance of v after deleting u is at most $(c + 1)2^{i}\mathit{n}_{\min }$.

If u is deleted during the decimation of the neighborhood of v, then w remains a vertex in T. Therefore, $\mathit{n}_{T}(n) \leq d(v,w) \leq (c + 1)2^{i}\mathit{n}_{\min }$, and $j = i + O(\log c)$.

Suppose that u is deleted during the decimation of the neighborhood of another vertex. Consider the deletion chain $(w_{0},w_{1},\ldots,w_{g})$ that contains u, where w _g is a vertex in T. The neighborhood of w _g is decimated in round i or earlier, so we have $d(u,w_{g}) \leq \sum _{k=0}^{g-1}d(w_{k},w_{k+1}) <2d(w_{g-1},w_{g}) \leq 2^{i+1}\mathit{n}_{\min }$. So $\mathit{n}_{T}(v) \leq d(v,w_{g}) \leq d(v,u) + d(u,w_{g}) \leq 3 \cdot 2^{i}\mathit{n}_{\min }$, meaning that j ≤ i + 2. □ 

Next, we show that the vertices of the output mesh Z of Decimate is still a dense sample despite the vertex deletions.

Lemma 17

Let Y be the output of the refinement phase, and Z = REFINE(Y ). The vertices of Z form an $\varepsilon _{Z}$ -sample, where $\varepsilon _{Z} =\max \{\varepsilon _{0},15\mu \lambda \varepsilon _{X}\}$ .

Proof

Take any point x ∈ Σ _t+1. Let w be the nearest vertex in Y to x. So $d(w,x) \leq \varepsilon _{Y }f_{t+1}(x)$ by Lemma 11. If w is a vertex of Z, we are done. Suppose that w was deleted. Then by Lemma 13, there exists a vertex v in Z such that $d(v,w) \leq \max \{ 4\delta _{v},0.4\varepsilon _{0}f_{t+1}(v)\}$.

Suppose $d(v,w) \leq 0.4\varepsilon _{0}f_{t+1}(w)$. Then, $d(x,v) \leq d(x,w) + d(w,v) \leq \varepsilon _{Y }f_{t+1}(x) + 0.4\varepsilon _{0}f_{t+1}(v)$. The Lipschitzness of LFS implies that $d(x,v) \leq \frac{0.4\varepsilon _{0}+\varepsilon _{Y }} {1-0.4\varepsilon _{0}} \,f_{t+1}(x) \leq (0.7\varepsilon _{0} +\varepsilon _{Y }) \cdot f_{t+1}(x)$. Since $\varepsilon _{Y } \leq \max \{ 0.3\varepsilon _{0},4\mu \lambda \varepsilon _{X}\}$ by Lemma 11, it can be verified that $0.7\varepsilon _{0} +\varepsilon _{Y } \leq \max \{\varepsilon _{0},15\mu \lambda \varepsilon _{X}\}.$ So $d(x,v) \leq \varepsilon _{Z}f_{t+1}(x)$.

Consider the case that d(v, w) ≤ 4δ _v . By property P2 of decimation radii, we can find a triangle τ in Y such that $d(v,c_{\tau }) \leq \kappa _{\mathrm{dec}}\gamma _{\tau }$ and $\delta _{v} \leq \frac{1} {15}\gamma _{\tau }$. Let a be a vertex of τ. By Theorem 1(ii), $\gamma _{\tau } \leq 1.5\varepsilon _{Y }f_{t+1}(a)$. Therefore, we have $d(v,c_{\tau }) \leq 1.5\kappa _{\mathrm{dec}}\varepsilon _{Y }f_{t+1}(a)$ and $\delta _{v} \leq \frac{1} {15}\gamma _{\tau } \leq 0.1\varepsilon _{Y }f_{t+1}(a)$. The Lipschitzness of LFS implies that $\delta _{v} \leq 0.1\varepsilon _{Y }{\bigl (1 + 1.5(\kappa _{\mathrm{dec}} + 1)\varepsilon _{Y }\bigr )}f_{t+1}(v) \leq 0.2\varepsilon _{Y }f_{t+1}(v)$. Thus, $d(x,v) \leq 4\delta _{v}+\varepsilon _{Y }f_{t+1}(x) \leq 0.8\varepsilon _{Y }f_{t+1}(v)+\varepsilon _{Y }f_{t+1}(x) <3\varepsilon _{Y }f_{t+1}(x) \leq \varepsilon _{Z}f_{t+1}(x)$. □ 

We are ready to show that Decimate restores the angle lower bound to α ₀, while ensuring a good sampling density.

Lemma 18

Let X be an $(\varepsilon _{X},\alpha _{1})$ -mesh satisfying $\hat{\mathrm{C}}$ 1–$\hat{\mathrm{C}}$ 3 for some constants $\varepsilon _{X}$ and α ₁ . Let Y be the output mesh of Refine(X). Assume that the decimation radii for the vertices in Y are known. Then, Decimate(Y ) runs in linear time and produces an $(\varepsilon _{Z},\alpha _{0})$ -mesh Z that satisfies conditions C1–C3 , where $\varepsilon _{Z} =\max \{\varepsilon _{0},15\mu \lambda \varepsilon _{X}\}$ and $\alpha _{0} =\varOmega (\lambda )$ .

Proof

The angles in Y are at least some constant by Lemma 11, so deleting the first vertex can be done in O(1) time. Then by Lemma 15, all angles in the mesh after the deletion are still at least some constant. So Lemmas 14 and 15 are applicable inductively, and hence the deletion of each single vertex can be deleted in O(1) time. Thus, we only need to bound the total number of migrations of vertices in the m + 1 rounds of vertex deletions. Let τ be the triangle in Y with the largest circumradius. Let u be the vertex in Y with the largest Δ _t+1(u). So, $m \leq \log \left ( \frac{1} {\mathit{n}_{\min }}\max {\bigl \{ \frac{1} {15}\gamma _{\tau },\;20(\sin \alpha _{0})^{-1}\varDelta _{ t+1}(u)\bigr \}}\right ) =\log \frac{O(\gamma _{\tau }+\varDelta _{t}(u))} {\mathit{n}_{\min }} =\log \frac{O(\gamma _{\tau }+\mathit{R}_{Y }(u))} {\mathit{n}_{\min }} = O{\bigl (\log (\gamma _{\tau }/\mathit{n}_{\min })\bigr )}$. Since each angle in Y is at least some constant, the circumradii of two adjacent triangles differ by a constant factor, implying that the radio of the largest to the smallest circumradii is at most 2^O(n). Therefore, m = O(n). Consider the processing of v ∈ S _i in a round. In the case that i < j ≤ m + 1, we deleted some vertex p in a previous round where d(p, v) equals the old n _M (v). We charge to p the migration of v to S _j . We can show that p is charged only O(1) time as in bounding the degree of a planar minimum spanning tree by six. Therefore, the total number of migrations is O(n), implying that the total running time is O(n).

Condition C1 follows from Lemma 12.

Condition C2 requires that for any vertex v and any triangle τ in Z, if $v \in B(c_{\tau },\ell\gamma _{\tau })$, then $\mathit{n}_{M}(v)>\lambda \gamma _{\tau }$. Let σ be the triangle in Y closest to $\varphi _{\varSigma _{t+1}}(c_{\tau })$. Let a be any vertex of σ. By Lemma 9, $d(a,c_{\tau }) <2.1\gamma _{\sigma } + 0.1\gamma _{\tau }$. Suppose that the vertices of σ lie outside $B(c_{\tau },0.7\gamma _{\tau })$. Then, Lemma 9 implies that $\gamma _{\sigma }\,>\, 0.6\gamma _{\tau }$, and we have $d(a,v) \leq d(a,c_{\tau }) + d(v,c_{\tau }) \leq 2.1\gamma _{\sigma } + 0.1\gamma _{\tau } +\ell\gamma _{\tau } <2\ell\gamma _{\sigma }$. By the properties of decimation radii, $\delta _{a} \geq 4\lambda \gamma _{\sigma }$ and $\mathit{n}_{Z}(v) \geq \delta _{v} \geq \delta _{a} - (\lambda /\ell)d(a,v) \geq 2\lambda \gamma _{\sigma }>\lambda \gamma _{\tau }$. If some vertex a of σ lies inside $B(c_{\tau },0.7\gamma _{\tau })$, $d(a,v) \leq \ell\gamma _{\tau } + 0.7\gamma _{\tau } <2\ell\gamma _{\tau }$. We can invoke the same proof as that in Lemma 14: identify the deletion chain $(a,\ldots,w)$ where w is a vertex of Z, and relate δ _v and δ _w . We have $d(w,c_{\tau }) \geq 0.8\gamma _{\tau }$ and $0.1\gamma _{\tau } \leq d(a,w) \leq 4\delta _{w}$. Set λ to be a small enough number. We have $\delta _{v} \geq \delta _{w}-(\lambda /\ell)d(v,w) \geq \delta _{w}-(\lambda /\ell)(d(v,a)+d(a,w)) \geq (1-4\lambda /\ell)\delta _{w}-(\lambda /\ell)(2\ell\gamma _{\tau })> \frac{1} {80}\gamma _{\tau }>\lambda \gamma _{\tau }$.

Condition C3 is satisfied simply because we put every point p ∈ P _t+1 that is not a vertex of M in points(w) such that w is the nearest vertex of M to p.

Finally, by Lemma 17, the vertices of the output mesh Z form an $\varepsilon _{Z}$-sample of Σ _t+1, and by C2, α ₀ can be set to arcsin(λ∕2), so Z is an $(\varepsilon _{Z},\alpha _{0})$-mesh. □ 

Lemma 19

Let K _t+1 be the deformed mesh at time t + 1, which is an $(\varepsilon _{1},\alpha _{1})$ -mesh satisfying $\hat{\mathrm{C}}1 -\hat{\mathrm{ C}}3$ . We can iterate Refine and Decimate O(1)times to return an $(\varepsilon _{0},\alpha _{0})$-mesh M_t+1 that satisfies C1–C3 .

Proof

Our mesh update procedure iterates Refine and Decimate for $O(\log \frac{1} {\varepsilon _{0}} ) = O(1)$ times. The angle bound α ₀ and the conditions C1–C3 are enforced by Lemma 18. Consider the sampling condition. The vertex set of K _t+1 is an $\varepsilon _{1}$-sample, so after the first iteration, we obtain a mesh whose vertex set is an $\max \{\varepsilon _{0},O(\lambda \varepsilon _{1})\}$-sample by Lemma 18. Another iteration gives a $\max \{\varepsilon _{0},O(\lambda ^{2}\varepsilon _{1})\}$-sample. Therefore, after $O(\log \frac{1} {\varepsilon _{0}} )$ iterations, we can obtain an $(\varepsilon _{0},\alpha _{0})$-mesh. □ 

Finally, we obtain our deforming mesh maintenance result as stated in the theorem below. The O(n) running time bound is obtained by using an octree to speed up the computation of the decimation radii.

Theorem 2 ([7, 17])

Consider the simulation of a deforming surface, specified by n moving sample points, that progresses in unit time steps. Suppose that the sample points form an $\varepsilon$ -sample for a sufficiently small $\varepsilon$ throughout the simulation. There exist constants $\varepsilon _{0} \in (10\varepsilon,1)$ and α ₀ > 0 such that an $(\varepsilon _{0},\alpha _{0})$ -mesh can be built before the simulation begins and if the deformation is smooth, an $(\varepsilon _{0},\alpha _{0})$ -mesh can be restored in O(n) time at each subsequent time step.

6 Experiments

We built a prototype of the mesh maintenance algorithm and experimented with two test cases on a machine with Intel Xeon E5450 3GHz CPU and 16G memory. Two iterations of the insertion and deletion phases were run on the two test cases, and we found that the mesh size and quality are nearly identical at the end of the first and second iterations. Since the iterations aim to increase the mesh density, it is reasonable to stop if the mesh size stays nearly the same.

The first test case is a deformation of a sphere [12, 20]. The velocity field is defined as: $v_{x} = 2\sin ^{2}(\pi x)\sin (2\pi y)\sin (2\pi z)$, $v_{y} = -\sin (2\pi x)\sin ^{2}(\pi y)\sin (2\pi z)$, and $v_{z} = -\sin (2\pi x)\sin (2\pi y)\sin ^{2}(\pi z)$. Initially we have 10K random samples on a sphere centered at (0. 35, 0. 35, 0. 35) with radius 0. 15. After the simulation starts, the points move with the velocity determined by its current position. Figure 3 shows how the object deforms. The rightmost two images in Fig. 3 show the front and back views of the surface mesh at time 0.7. As the object deforms, the front side is stretched and the sample points move to the back side of object. From the screen shots, one can see that our algorithm is indeed adaptive to the sampling: the triangles in the front are much larger than those at back. The average number of mesh vertices is around 6K, 90 % of angles are in the range $[30^{\circ },120^{\circ }]$, less than 0. 02 % of them are less than 15^∘, and none is smaller than 11^∘. The average update time per time step is less than 0.36 s. Reduction in running time seems possible as we did not optimize the code. For comparison, we reconstructed the mesh from the sample points using Cocone [3]. Cocone took 3.7 s on average per time step.

Fig. 3

The leftmost screen shots are taken at time 0.2, 0.4 and 0. 7 respectively. The rightmost screen shot is the back of the object at time 0.7

We also ran our algorithm with different numbers of sample points and observed that the average update time increases linearly with the number of sample points.

Our second test case is the deformation of a piece cloth as it falls on a sphere [4]. 10K sample points are used. The cloth boundary is preserved by not allowing any boundary edge to be flipped. Figure 4 shows the results. The statistics is highly similar to the first test case.

Fig. 4

A piece of cloth falling on a ball