Delaunay extrinsic edge flips and triangle circumradius

If a mesh is smooth, then it has no unflippable nlD edges. However, the Delaunay extrinsic edge flipping algorithm may encounter unflippable edges even if the initial mesh is smooth.

Without additional constraints on the input mesh, there is no guarantee that the algorithm will maintain mesh smoothness, as demonstrated in Figure 7.2 . A desire to characterize the needed additional constraints is the motivation behind the work presented in this section.

As discussed in Section 2.4, smoothness will be ensured if we are able to provide a suffi-cient bound on the triangle circumradii. In this section we examine the relative circumradii of triangles in the flip-tet of an nlD edge. We rely heavily upon Lemma 4.14, which for convenience we restate here for the specific case of triangles:

Lemma 7.7 Suppose trianglest andt^′ share an edge eand thatt^′ is contained inBt. Ife subtends an acute angle int^′, thenr_t> r_t′.

(a) Smooth mesh (b) Showing vertices

(c) Voronoi diagram (d) Unflippable edge

Figure 7.2: From a smooth mesh we obtain an unflippable nlD edge. (a) The initial mesh is smooth (the boundary is irrelevant; we could cap this object with smooth self-Delaunay domes). (b) There is a solitary vertex in the interior of the cylinder. (c) The Voronoi diagram of the mesh vertices is not well formed (We are looking at the back; the solitary vertex is on the other side). (d) The Delaunay edge flipping algorithm eventually encounters an unflippable edge.

u

q v

p

e’

σ e

Flip-tet In what follows we will consider an nlD edgee= [p, q] with opposing

edge e^′ = [u, v] as shown in the figure. Let the pre-flip triangles be t1 = [u, p, q] and t2 = [p, v, q] and without loss of generality, assume r_t1 ≥r_t2. The post-flip triangles will be denotedt^′₁andt^′₂ and such that r_t′

1 ≥r_t′ 2.

In the case of a planar triangulation, a Delaunay edge flip will always yieldr_t′

1 < r_t1 andr_t′

2 < r_t2, however for Delaunay extrinsic edge flips in a non-planar mesh, the first inequality does not always hold. We do at least maintain the second inequality for all flips:

Lemma 7.8 In an Delaunay extrinsic edge flip (t₁, t₂)→(t^′₁, t^′₂) on a non-sharp mesh, the smaller of the circumradii of the post-flip triangles is smaller than the circumradius of each of the pre-flip triangles. I.e.,r_t′

2 < r_t2.

Proof By Lemma 4.11, and Lemma 4.10, t₂ has an acute angle subtended by e, and it does not yield a Gabriel certificate to e. We will show that Lemma 7.7 can be used to compare at least one ofr_t′

1,r_t′

2 with r_t2. To that end, we need to verify that eithert^′₁ ort^′₂ has an acute angle atu.

If ∠puq is acute, then it follows from Lemma 7.2 that both∠puv and ∠vuq are acute.

Indeed, the scalar product of−uv→ and −up→ is determined by the component of−uv→ that lies in the plane of [u, p, q], and will clearly be positive. Thus if ∠puq is acute the result follows from Lemma 7.7 by comparingt₂ and t^′₂ on their common edge.

If∠puq is not acute, Lemma B.8 implies that at least one of the angles∠puv and∠vuq must be acute. This follows because Lemma 7.3 ensures that u is a sharp vertex in the flip-tet and the Gauss map transforms the valence three vertex u into a spherical triangle whose angles are the supplements of the corresponding face angles atu. Therefore we can again apply Lemma 7.7 to comparer_t2 with at least one ofr_t′

1 andr_t′

2, and the result follows.

Although the smaller circumradius will always be reduced, the behaviour of the larger circumradius is not so easily tamed. In the following we classify the flip-tets according to their behaviour in this regard. Since Lemma 7.7 is the primary tool used to compare circumradii, the Gabriel properties of the flip-tet become a natural way to classify the different cases. This classification leads to three possible cases.

The first case, when the initial nlD edge has no Gabriel certificates, can be handled analogously to the planar case, as demonstrated in Cheng and Dey [CD07][Lemma 3.2]:

Lemma 7.9 Ifehas no Gabriel certificates, then the largest post-flip circumradius will be smaller than the largest pre-flip circumradius. I.e.,r_t′

1 < r_t1.

Proof Sincet^′₁shares an edge witht₁ and another witht₂, one of these edges must subtend an acute angle int^′₁. Since neither t₁, nor t₂ yields a Gabriel certificate toe, we can apply Lemma 7.7 to get the required comparison with at least one ofr_t1 and r_t2. The remaining two cases arise when ehas a single Gabriel certificate. If the opposing hinge has only a single Gabriel certificate, then the edge flip results in circumradius growth.

Lemma 7.10 If nlD edgeeis flipped to an opposing edgee^′ which has only a single Gabriel certificate, then the largest post-flip circumradius will exceed both of the pre-flip circumradii.

I.e.,r_t′ 1 > r_t1.

Proof Lemma 4.11 and Lemma 4.10 imply thatt^′₁has an acute angle subtended bye^′, and does not yield a Gabriel certificate toe^′. Also, sincet₁ andt^′₁share an edge that terminates in u, and t₁ has an obtuse angle at u (by Lemma 4.11), it follows that the common edge must subtend an acute angle int₁. Therefore the result follows from Lemma 7.7.

The only remaining case to consider is when an edge with a single Gabriel certificate gets flipped to one with two Gabriel certificates. In this case further information is needed to determine whether circumradius growth occurs.

Lemma 7.11 Suppose edgeehas a single Gabriel certificate and it is flipped to an edge e^′ that has two Gabriel certificates. If t^′₁ has an acute angle atu, then r_t′

1 < r_t1. Otherwise, r_t^′₁ < rt1 iff the acute angle int^′₁ atv is larger than the angle int1 that is subtended by the edge common tot₁ and t^′₁.

Proof Lemma 4.11 together with Lemma 4.10 implies that t2 does not yield a Gabriel certificate to e. Therefore, if t^′₁ has an acute angle at u then Lemma 7.7 ensures that r_t′

1 < r_t2.

If t^′₁ does not have an acute angle at u, then the final statement follows from the fact that for a triangle on a fixed edge subtending an acute angle, the circumradius grows as the

angle decreases. In Section 3.2.1, we observed that most of the functionals

which are optimized by the Delaunay edge flip algorithm in the plane, or on a fixed pwf surface, are not optimized by the Delaunay extrinsic edge flip algorithm. Lemma’s 7.10 and 7.11 confirm that the triangle circumradius is no exception to this trend.

If we could guarantee that triangle circumradius would not increase as a result of a Delaunay extrinsic edge flip, then mesh

smoothness would be ensured if the sampling density were constant (i.e. not adapted to the local feature size). However, even if a local uniformity constraint is imposed on the sample

distribution, nlD hinges satisfying the hypothesis of Lemma 7.10 may still occur. Indeed, the same flip-tet, depicted in Figure 4.4, that provided an obstruction to the existence of closed Gabriel meshes, may be furnished as an example. The observations of Section D.1 indicate that we may ensure that edge [p, q] is nlD, while the ratio of the circumradius to shortest edge inσ is arbitrarily close to unity.

If a smooth self-Delaunay mesh onP exists, then we expect that the circumradii of the triangles will be similar in size to that of nearby triangles in the rDt. However, the obser-vations of this section imply that a bound on the triangle circumradii cannot be obtained through the flip algorithm unless there is a definite bound on the number of flips that may occur on edges incident to a given vertex.