An Effective Condition for Sampling Surfaces with Guarantees
2. Definitions and preliminary observations
3.3. Pseudo-disks
Definition 3.8Topological disks are pseudo-disks if they pairwise intersect along topological disks (that may be empty or reduced to a point) and if their boundaries pairwise intersect in at most two points.
Observe that the boundaries of two pseudo-disks either do not intersect, or intersect in one point tangentially, or intersect in two points transversally. topo-logical circles. Let us assume that ballsBandB0intersect, the other case being trivial. Notice that none of them can be contained in the other one, since they are Delaunay balls. Thus, their bounding 103
J-D Boissonnat and S. Oudot / An Effective Condition for Sampling Surfaces with Guarantees
P c z
y x
G
Γ
∆ Ll
Lr
Figure 1:Definition of G
P c Cone
z y x
G’
G
Figure 2:Definition of G0
spheres∂Band∂B0also intersect. LetΓbe the circle∂B∩∂B0,ρ its radius (ρ<min{r,r0}) andPits supporting plane. We define
∆=B∩Pand notice thatΓ=∂∆. SinceSis a closed surface, we haveC⊂∂BandC0⊂∂B0, which implies that
C∩C0⊆S∩Γ (4)
LetB+=B(c,2r). Sincekc−c0k ≤r+r0≤εdM(c) +εdM(c0), whereε≤ε0, by lemma 3.4 there exists a vector−→v orthogonal to
−→
cc0such that
∀x∈S∩B+,(−→n(x),−→v)≤π
4 (5)
Let us choose inR3a reference frame of originc, ofy-axis directed along−→
c0c, and ofz-axis directed along−→v. We callLlandLrthe two lines ofP, parallel to thez-axis, that are tangent toΓ. The region of Pbounded byLlandLris calledG(see figure 1). In the following, ξdenotesS∩B+∩G.
Lemma 3.10ξis a connectedx-monotone arc.
Proof According to (5), we have∀x∈S∩B+, (−→n(x),−→v)≤π4. Thus, by lemma 9.4, B+∩Sisxy-monotone, which implies that ξisx-monotone. Moreover, according to lemma 9.5,B+∩Slies outside the cone of apexc∈S, of vertical axis and of half-angleπ4.
The equation of the cone in our frame isz2=x2+y2. It intersects Palong two hyperbolic arcs of equationsz=±√
x2+d2, where d≤ris the distance fromctoP. Consider the subregionG0 ofG that is bounded vertically by the two hyperbolic arcs (see figure 2).
SinceS∩B+lies outside the cone,ξis included inG0.
The points of G0 that are farthest from c are the points (±ρ,−d,±p
ρ2+d2). Their distance tocis q2(ρ2+d2)<2r
In other words, G0 ⊂int(B+). It follows that ξ is included in int(B+)and cannot intersect∂B+. Its endpoints must then lie on the vertical linesLr andLl. But there can be only one endpoint per vertical line, sinceξisx-monotone. Hence,ξhas at most two endpoints and is thus connected.
Lemma 3.11|S∩Γ| ≤2.
Proof Let us assume for a contradiction that|S∩Γ|>2. First, we show that there exists a point where the curvature ofξis high and hence the distance to the medial axisMis small. Then we work out a contradiction with the fact thatEis a looseε-sample, withε≤ε0. Claim 1There exists a pointqat which the curvature ofξis at least
1ρ.
Proof We made the assumption that|S∩Γ|>2. SinceΓ⊂Gand Γ⊂B+,ξalso intersectsΓmore than twice. And sinceξis con-nected by lemma 3.10, there is a subarcabofξthat lies outside∆ and whose endpointsaandblie onΓ. This subarc may be reduced to a point (a=b), sinceξmay be tangent toΓ. But in this case, in the vicinity ofa,ξis locally included in∆and tangent toΓata.
Thus, its curvature atais at least 1ρ, which proves the claim with q=a. So now we assume that arcabofξis not reduced to a point.
Sinceξisx-monotone by lemma 3.10,aandblie on the same half ofΓ, upper half or lower half (say upper half). Thus, the smaller arc ofΓthat joinsaandbis alsox-monotone. Then, by lemma 9.3, there is a pointqof arcabofξat which the curvature ofξis at least
1ρ, which proves the claim.
Claim 2dM(q)≤ρ√ 2.
Proof Let−→nξ(q)be the normal to planar curveξat pointq. By inequation (5),−→n(q)is not orthogonal toP, thus−→nξ(q)is oriented along the projection of−→n(q)ontoP. Hence, by lemma 9.2, we have (−→n(q),−→nξ(q))≤(−→n(q),−→v)which is at mostπ4by inequation (5).
According to theorem 9.1, we then have atq II(ξ0,ξ0)≥cosπ
4kξ00k
ξ0is the unit tangent vector ofξatqandkξ00kis the curvature ofξ atq, which is more than 1ρaccording to claim 1. So, atqwe have
II(ξ0,ξ0)≥ 1 ρ√
2 (6)
Recall thatIIis a symmetric bilinear form, thus it can be diago-nalized in an orthonormal frame, and its eigenvalues are the min-imum and maxmin-imum curvatures ofSatq. Let us call these val-uesκmin(q)andκmax(q)respectively. Sinceξ0is a unit vector, we haveII(ξ0,ξ0)≤max{|κmin(q)|,|κmax(q)|}. It follows, according to (6), that max{|κmin(q)|,|κmax(q)|} ≥ρ√12, or, equivalently, that the minimal radius of curvature ofSatqis at mostρ√
2. The result follows.
104
J-D Boissonnat and S. Oudot / An Effective Condition for Sampling Surfaces with Guarantees The end of the proof of the lemma is immediate. We have
dM(c) ≤ dM(q) +kc−qk
Proof Let us assume thatSintersects∆in two points exactly, say aandb. Then, the subarc ofξthat joins pointsaandblies outside
∆. It follows, by the same reasoning as in the proof of claim 1, that there exists some pointqofξat which the curvature ofξis at least 1ρ. It follows by claim 2 thatdM(q)≤ρ√
2, which leads to a contradiction, as in the end of the proof of lemma 3.11.
It follows from the above lemmas thatDandD0 intersect along a topological disk. The result is clear if D⊆D0 or if D0 ⊆D. ends the proof of proposition 3.9.
4. Global properties of looseε-samples
In this section,Eis a looseε-sample ofS, withε≤ε0. We prove that Del|S(E)is a manifold without boundary (theorem 4.5), ambi-ent isotopic toS(corollary 4.7), at Hausdorff distanceO(ε2)from S(theorem 4.8). From the latter we deduce thatEis anε(1+16ε )-sample ofS(corollary 4.13). We also prove that the surface Delau-nay balls coverS(theorem 4.15).
4.1. Manifold
We first prove that every edge of Del|S(E)is incident to exactly two facets of Del|S(E). We then prove that every vertex of Del|S(E)has only oneumbrella. An umbrella of a vertexvis a subset of facets of Del|S(E)incident tovwhose adjacency graph is a cycle.
Lemma 4.1The dual of a facet of Del|S(E)intersectsSonly once, and transversally.
Proof Let f be a facet of Del|S(E), and f∗its dual Voronoi edge.
We denote byathe vertex offthat has the largest inner angle. We have ˆa≥π3, and sinceε≤ε0<17, lemma 3.1 says that
where−→nf denotes the unitary vector orthogonal to f that makes the smaller angle with−→n(a). LetBabe the ballB(a,1−εε dM(a)).
For any surface Delaunay ballB(c,r)that circumscribesf, we have kc−ak=r ≤εdM(c)
≤ε(dM(a) +kc−ak)
Hence,kc−ak ≤1−εε dM(a). In other words, every center of sur-face Delaunay ball offlies inBa. In addition, we have
∀x∈Ba∩S,kx−ak ≤1−εε dM(a) is a terrain over the planeΠfthat supportsf. Sincef∗is orthogonal toΠf, it cannot intersectBa∩Smore than once, nor tangentially.
And since every center of surface Delaunay ball of flies inBa, f∗ cannot intersectSmore than once, nor tangentially.
For a restricted Delaunay facetf, we denote byBf= (cf,rf)the corresponding surface Delaunay ball. The surface Delaunay patch of f,S∩Bf, is denoted byDf. We defineCf=∂Df.
Lemma 4.2Let f and f0be restricted Delaunay facets that share an edge. They make a dihedral angle greater thanπ2.
Proof This result is a consequence of theorem 1 of [24]. The latter states that the dihedral angle is at leastπ−2 2ε
1−4ε+arcsinε1−ε√3 , which is greater than π2sinceε≤ε0<ε4.
From lemmas 4.1 and 4.2 we deduce the following result.
Proposition 4.3Every edge of Del|S(E)is incident to exactly two facets of Del|S(E).
Proof Letebe an edge of Del|S(E). We denote bye∗the Voronoi face dual toe. SinceShas no boundary,S∩aff(e∗)is a union of simple closed curves, none of which intersects the boundary∂e∗of e∗tangentially, by lemma 4.1. Thus, by the Jordan curve theorem, each curve ofS∩aff(e∗)intersects∂e∗at an even number of points.
It follows thatSintersects∂e∗at an even number of points. More-over, by lemma 4.1, each edge of∂e∗can be intersected at most once byS. Thus,Sintersects an even number of edges of∂e∗, and eis incident to an even number of restricted Delaunay facets.
In addition, two restricted Delaunay facets incident toemake a di-hedral angle greater than π2, by lemma 4.2. It follows thatemay be incident to at most three restricted Delaunay facets. In conclu-sion, the number of restricted Delaunay facets incident toeis even, strictly positive (sincee∈Del|S(E)) and at most three, hence it is equal to two.
It follows from the above proposition that the restricted Delau-nay facets incident to a vertex of Del|S(E)form a set of umbrellas.
Proposition 4.4Every vertex of Del|S(E)has exactly one umbrella.
Proof Letabe a vertex of Del|S(E). Let F(a)be the set of all facets of Del|S(E)that are incident toa. Letfabe the facet ofF(a) that has the surface Delaunay ball of largest radius. We callrfathis radius. ThenB(a,2rfa)contains the surface Delaunay balls of all facets ofF(a). Moreover, by lemma 3.7,S∩B(a,2rfa)is a topolog-ical disk and a terrain over some planeΠ. We projectS∩B(a,2rfa) ontoΠ. This projection preserves topological properties such as 105
J-D Boissonnat and S. Oudot / An Effective Condition for Sampling Surfaces with Guarantees pseudo-disks. For simplicity of notations, we shall identify objects
with their projection ontoΠ. LetF1(a)be an umbrella ofa. We call U1(a)the union of the facets ofF1(a), andR1(a)the union of the surface Delaunay patches associated with the facets ofF1(a).
Claim a∈int(R1(a)).
Proof Ifa∈int(U1(a)), then it is clear thata∈int(R1(a)), since surface Delaunay patches are pseudo-disks, by proposition 3.9.
Now, let us assume thatalies on the boundary ofU1(a). Let[av]
be an edge of the boundary that is incident toa. By proposition 4.3, [av]is incident to two facets of Del|S(E), say(a,v,x)and(a,v,x0).
These facets belong toF1(a)since they are incident toa, and they both lie on the same side of[av]which is a boundary edge ofU1(a).
Thus, since surface Delaunay patches are pseudo-disks by proposi-tion 3.9, eitherxis included in the interior of the surface Delaunay patch of(a,v,x0)orx0is included in the interior of the surface De-launay patch of(a,v,x), which violates the Delaunay property.
We now assume for a contradiction that there exists a restricted Delaunay facet f= (a,b,d)∈/F1(a)that is incident toa. Vertices banddlie outside int(R1(a)), whereasalies in int(R1(a)), by the above claim. It follows thatCf intersects the boundary ofR1(a), at some pointzthat lies on the boundary of the surface Delaunay patch of some facet f0= (a,b0,d0)ofF1(a). By proposition 3.9,Cf and Cf0 intersect at pointsaandzonly. By the same proposition, open arcs(a,b0)and(a,d0)ofCf0are included in int(R1(a)). Sincea∈ int(R1(a)),zlies on arc(b0,d0)ofCf0. Ifz6=b0andz6=d0, thenb0 andd0lie on different sides ofCf, hence one of them lies in int(Df), which violates the Delaunay property. Otherwise (sayz=b0),d0 must lie outsideDf. In this case, consider the facet f00= (a,b0,d00) ofF1(a)that is incident to f0through edge[a,b0]. By proposition 3.9,Cfintersects arc(b0,d00)ofCf00at pointb0only, thusd0andd00 lie on different sides ofCf. Hence, eitherd0ord00lies in int(Df), which violates the Delaunay property.
The next theorem follows from propositions 4.3 and 4.4.
Theorem 4.5 LetSbe a smooth closed surface andE a loose ε-sample ofS. Ifε≤ε0≈0.091, then Del|S(E)is a 2-manifold with-out boundary.
Since Del|S(E)is a closed 2-manifold embedded inR3, we can orient the normals of its facets consistently. For instance, they can be chosen so as to point to the unbounded component of R3\Del|S(E).