Delaunay mesh decimation

For some applications it may be desirable to have a progression of self-Delaunay meshes, at multiple levels of details (LODs), which approximate an initial dense self-Delaunay mesh.

In practice any resource-constrained application can benefit from LOD representations to avoid redundancy and allow for more effective use of the triangle budget. In this section

we describe a mesh decimation algorithm for LOD modelling with self-Delaunay meshes.

Our geometry-preserving refinement, Algorithm 1, may produce an excess of small triangles, but the resulting self-Delaunay mesh serves well as input for the decimation algorithm we describe here. The output of this algorithm has a much more pleasing triangle distribution, but of course it is not geometry preserving.

q v w

u

p edge collapse

Figure 6.7: An edge collapse. The edges affected (blue and red) need to remain locally Delaunay.

The Delaunay mesh decimation algorithm has been adapted from a similar scheme for nonobtuse meshes [LZ06] and is based on edge collapse prioritized by a quadric error as introduced by Garland and Heckbert [GH97]. For each edge collapse, the resulting vertex needs to lie in afeasible region to ensure that all the affected edges remain locally Delaunay.

The optimal position of the vertex is chosen to minimize the standard quadric error [GH97], subject to constraints, and the resulting error sets the priority. By choosing theallowable regionto be a linearized and convexified subset of the feasible region, i.e., being conservative, the decimation algorithm is formulated as a constrained least-square problem and is solved using the OOQP solver of Gertz and Wright [GW03]. Thus the error quadric associated with each edge collapse is minimized subject to linear constraints in the form of planes bounding half spaces.

Since quadric-based edge collapsing schemes using priority queues are well-known [GH97, LZ06], we will concentrate on describing the feasible region and its linearization. In Fig-ure 6.7, we show an edge collapse [u, v] → w after which we need to ensure that all the incident edges atw(shown in red), e.g., [w, p] and [w, q], and all thesubtending edges tow (shown in blue), e.g., [p, q], remain locally Delaunay.

Allowable region associated with a subtending edge: Let [p, q] be a subtending edge, and let w^′ be the other subtended vertex. Then any w with ∠pwq ≤ π−∠pw^′q is feasible. Consider the circumcircle of [p, w^′, q]. If we rotate the arc subtended by edge [p, q]

about [p, q], as shown in Figure 6.8(a), we obtain a surface of revolution which we call a chordal spheroid. Anywoutside of the spheroid is feasible. To linearize the feasible region,

r q

w

p

(a)

r q

p

L

(b)

Figure 6.8: Feasible and allowable regions for subtending edges. (a) If e = [p, q] is a subtending edge, the feasible region is the complement of the chordal spheroid obtained by rotating the subtended arc of the circumcircle of [p, w^′, q], wherew^′ is the other subtending vertex ofe. (b) The allowable region is obtained by linearizing the feasible region by means of a tangent plane atr, as described in the text.

we replace it by a half space defined by a plane L tangent to the sphere or the chordal spheroid defined above (Figure 6.8(b)). The point of tangency, r, is chosen so that L is parallel to [p, q] and perpendicular to aff([p, w^′, q]).

Allowable region associated with an incident edge: To ensure that an incident edge [w, p] remains locally Delaunay, we need∠pow+∠pqw≤π, whereoandq are the one-ring vertices ofw adjacent to p; see Figure 6.9(a).

An example of the actual surface bounding the feasible region in 3D is shown in Fig-ure 6.9(b). To construct the linearized allowable region, we focus our attention on the circumcircle of [o, p, q]. Ifw were confined to lie in the plane supporting [o, p, q], then when wlies within the wedge defined by∠opq, [p, w] would be nlD ifwis outside the circumcircle of [o, p, q]. Therefore at a minimum our constraint planes must bound the allowable region away from this portion of the wedge.

We will call aff([o, p, q]) the horizontal plane. Our constraint planes will all be perpen-dicular to this plane, i.e., vertical. The constraint planes define half-spaces, the intersection of which is the allowable region. We focus our attention on the planes themselves: The allowable half-space will always be the one that contains the pointp.

o p

q

w ^r

q L

L

p o

(a) (b) (c)

Figure 6.9: Feasible and allowable regions for incident edges. (a) For [w, p] to be locally Delaunay, we need∠pow+∠pqw≤π. (b) An example plot of the actual surface bounding the feasible region with respect to o, p, and q. The two cusps on the surface correspond too and q, and the supporting plane of [o, p, q] is parallel to the top face of the box. (c) PlanesL₁ andL₂ enclose a conservative, linearized allowable region for our optimization in the simplest case. The definition ofL1 and L2 is given in the text.

Let p^∗ be the point antipodal to p in the circumcircle of [o, p, q]. An allowable region may be simply described by the two vertical planes that contain the segments [o, p^∗], and [q, p^∗] respectively. Since these planes are orthogonal to [p, o] and [p, q] respectively, both

∠powand∠pqware acute in this region, and therefore it is necessarily contained within the feasible region. However, our experiments revealed these constraints to be too restrictive.

On some models we would obtain clusters of vertices where no decimation had occurred.

Instead, we choose two initial planes which maximize the area of the allowable region within the circumcircle. We selectr to be the midpoint on the arc subtending ∠opq. This selection maximizes the area of [o, q, r]. We now consider the two vertical planes L₁, and L₂, containing [r, o] and [r, q] respectively, as shown in Figure 6.9(c).

As described in Section D.2,L₁, andL₂ are not always sufficient to bound the allowable region within the feasible region. In order to construct correct allowable regions we distin-guish between the opposite-side case, where o and q lie on opposite sides of the diameter through p, and the same-side case, where oand q both lie on the same side of [p, p^∗]. If o orq happens to coincide withp^∗, we treat it as an opposite-side case.

p

Figure 6.10: Allowable regions for incident edges. The shaded region is the allowable region forwin the plane of [o, p, q]. The constraint planes are defined by vertical (i.e. perpendicular to aff([o, p, q])) planes containing the red lines. The three cases are described in the text.

The circumcylinder is the vertical right cylinder defined by the circumcircle of [o, p, q].

If [o, p, q] defines an opposite-side case, then within the circumcylinder, planes L₁ and L₂ contain the allowable region within the feasible region. However, these two planes may not entirely lie within the feasible region outside of the circumcylinder. Sometimes a third plane must be added.

Theclose vertex is whichever of oand q is closest top^∗, the other is the far vertex. We label them c and f respectively. If |[c, p^∗]| < |[p^∗, r]|, then we add a third vertical plane, L_t, which contains c and a, wherea is the midpoint of cr, the arc between^⌢ c and r. Thus constructed, Lt is sufficient to contain the allowable region within the feasible region. As discussed in Appendix D, L_t may be viewed as a tangent plane atc to the portion of the boundary of the feasible region that lies outside of the circumcylinder. (The boundary of the feasible region has a cusp atc.) The opposite-side cases with two and with three planes are depicted schematically in aff([o, p, q]) in Figures 6.10(a), and (b), respectively.

In the same-side case, L₁ and L₂ are not sufficient even within the circumcylinder.

Instead, we defineL_c to be the vertical plane that contains r and p^∗, and L_f to be the one that contains f and r. Thus L_f corresponds to either L1 or L2 in the opposite-side case, butL_c is necessarily more restrictive, isolating the close vertex from the allowable region,

setr to midpoint ofqo^⌢

setc, f to whichever of oand q is closer,farther to,fromp^∗ if o andq are on opposite sides of [p, p^∗]then

set L1 to vertical constraint plane througho andr set L₂ to vertical constraint plane throughq andr if |[c, p^∗]|<|[p^∗, r]|then

setato midpoint of rc^⌢

setL_t to vertical constraint plane through cand a end if

else

set L_c to vertical constraint plane throughp^∗ and r set L_f to vertical constraint plane throughf andr set z top^∗+

set Lt to vertical constraint plane throughc and z end if

Algorithm 3: Incident edge constraints

rather than going through it. We also always need a planeL_t, tangent to the boundary of the feasible region atp^∗. In this case L_tis the vertical plane through p^∗ such that it makes an angleτ with [f, p^∗]. The angleτ is defined by Equation (D.10):

tanτ = ksinγ (1 +kcosγ),

whereγ =∠opq, and k= ^|[f,p_|[c,p^∗∗]|^]|. The same-side case is depicted in Figure 6.10(c).

The construction of the constraint planes for incident edges is summarized in Algorithm 3. The derivation and demonstration of the correctness of these constraints is detailed in Appendix D.

Remark 6.7 In the original implementation of the decimation algorithm [DZM07a], only planes L1 and L2 were used for all cases. The output was a self-Delaunay mesh on all models tested, indicating that the extra constraints imposed byL_c andL_tare not generally needed in practice. The output of the corrected algorithm is qualitatively similar to that of the original, but in some cases the Hausdorff error is slightly larger in the output of the corrected version.

Allowable region for an edge collapse: Referring to Figure 6.7, for an edge collapse [u, v]→w, the allowable region for wis the intersection of all the allowable regions defined for the incident and subtending edges for w. If this set is empty, then [u, v] will not be collapsed.