#### Transcript Curve Preservation

Delaunay Meshing for Piecewise Smooth Complexes Tamal K. Dey The Ohio State U. Joint work: Siu-Wing Cheng, Joshua Levine, Edgar A. Ramos Piecewise Smooth Complexes Sharp Edges Non-manifold Department of Computer Science and Engineering 2/22 Piecewise Smooth Complexes • D is a piecewise smooth complex (PSC) if • Each k-dimensional element is a manifold and compact subset of a smooth (C2) k-manifold, 0≤k≤2. • The k-th stratum, Dk : set of k-dim elements of D. • D0 – vertices, D1 – 1-faces, D2 – 2-faces. • D≤k = D0 … Dk. • D satisfies usual reqs for being a complex. • Interiors of elements are disjoint and for σ D, bd σ D. • For any σ, D, either σ = or σ D . Department of Computer Science and Engineering 3/22 Delaunay refinement : History • Chew89, Ruppert92, Shewchuk98 (Linear domains with no small angle) • Cohen-Steiner-Verdiere-Yvinec02, Cheng-Dey-RamosRay04 (polyhedral domains with small angle) • Chew93 (surface without guarantees) • Cheng-Dey-Edelsbrunner-Sullivan01 (skin surfaces) • Boissonnat-Oudot03 and Cheng-Dey-Ramos-Ray04 (smooth surface) • Boissonnat-Oudot06 (Lipschitz surfaces) • Oudot-Rineau-Yvinec06 (Volumes) Department of Computer Science and Engineering 4/22 Basics of Delaunay Refinement • Chew 89, Ruppert 92, Shewchuk 98 • Maintain a Delaunay triangulation of the current set of vertices. • If some property is not satisfied by the current triangulation, insert a new point which is locally farthest. • Burden is on showing that the algorithm terminates (shown by packing argument). Department of Computer Science and Engineering 5/22 Challenges for PSC • Topology • Polyhedral case (input conformity,topology trivial). • Curved elements (topology is an issue). • Topological Ball Property (TBP) was used for smooth manifolds [BO03,CDRR04]. • We need extended TBP for nonmanifolds. • Nonsmoothness • Lipschitz surfaces [BO06], Remeshing [DLR05]. • Small angles • Delaunay refinement is hard [CP03, CDRR05, PW04]. Department of Computer Science and Engineering 6/22 Topological Ball Property • For a weighted point set S, let Vor S and Del S denote the weighted Voronoi and Delaunay diagrams. • S has the TBP for σDi if σ intersects any k-face in Vor S either in emptyset or in a closed topological (i+k-3)-ball. Department of Computer Science and Engineering 7/22 CW-Complexes • A CW-complex R is a collection of closed (topological) balls whose interiors are pairwise disjoint and whose boundaries are the union of other closed balls in R. • Our algorithm builds a CW-complex, Vor S||D|, to satisfy an extended TBP[ES97]. Department of Computer Science and Engineering 8/22 Extended TBP • S |D| has the extended TBP (eTBP) for D if there is a CWcomplex R with |R| = |D| s.t. • (C1) The restricted Voronoi face F |D| is the underlying space of a CW-complex R’ R. • (C2) The closed balls in R’ are incident to a unique closed ball bF R. • (C3) If bF is a j-ball then bF bd F is a (j-1)-sphere. • (C4) Each k-ball in R’, except bF, intersects bd F in a (k-1)-ball. Department of Computer Science and Engineering 9/22 Extended TBP • For a 1- or 2-face σ, let Del S|σ denote the Delaunay subcomplex restricted to σ. • Del S||Di| = σDi Del S|σ. • Del S||D| = σD Del S|σ. • Theorem. If S has the eTBP for D then the underlying space of Del S||D| is homeomorphic to |D| [ES97]. Department of Computer Science and Engineering 10/22 Feature Size • For analysis, we require a feature size which is 1Lipschitz and non-zero. • For any x |D|, let f(x) = min{m(x), g(x)}. • For any σ D, f() is 1-Lipschitz over int σ. • For δ (0,1] and x |D|, • if x D0, lfsδ(x) = δf(x). • if x int |Di|, for i ≥ 1, lfsδ(x) = max{δf(x), maxybd|Di| {lfsδ(y)-||x-y||}}. Department of Computer Science and Engineering 11/22 Protecting D1 1. Any 2 adjacent balls on a 1-face must overlap significantly without containing each others centers 2. No 3 balls have a common intersection 3. For a point p σ D1, if we enlarge any protecting ball Bp by a factor c ≤ 8, forming B’: 1. B’ intersects σ in a single curve, and intersects all D2 adjacent to σ in a topological disk. 2. For any q in B’ σ, the tangent variation between p and q is bounded. 3. For any q in B’ ( D2 adjacent to σ), the normal variation between p and q is bounded. Department of Computer Science and Engineering 12/22 Admissible Point Sets • Protecting balls are turned into weighted points • We call a point set S admissible if • S contains all weighted points placed on D1. • Other points in S are unweighted and they lie outside of the protecting balls (the weighted points). • We maintain an admissible point set at each step of the algorithm. Department of Computer Science and Engineering 13/22 D1 conformation • Lemma. Let S is an admissible point set. For a 1-face σ, if p and q are adjacent weighted vertices spanning segment σpq on σ then Vpq is the only Voronoi facet which intersects σpq and it does so exactly once. Department of Computer Science and Engineering 14/22 Meshing PSCs • Meshing algorithm uses four tests to detect eTBP violations. • Upon violation, we insert points outside of protected balls of weighted vertices. Department of Computer Science and Engineering 15/22 Test 1: Multi-Intersection(q,σ) • For a point q S on a 2face σ, find a triangle t Del S|σ incident to q s.t. Vt intersects σ multiple times. • If no t exists, return null, otherwise return the furthest (weighted) intersection point from q. q Department of Computer Science and Engineering 16/22 Test 2: Normal-Deviation(q,σ,Θ) • For a point q S on a 2-face σ, check nσ(p), nσ(q) < Θ for all points p Vq|σ. • 2ω ≤ Θ ≤ /6. • If so return null. • Otherwise return a point p where nσ(p), nσ(q) = Θ . Department of Computer Science and Engineering 17/22 Test 3: Infringement(q,σ) • We say q is infringed w.r.t. σ if • σ is a 2-face containing q s.t. pq Del S|σ for some p σ. • σ is a 2-face and there is a 1-face in bd σ containing q and a nonadjacent vertex p s.t. pq Del S|σ. • For q S σ, return null if q is not infringed, otherwise let pq be the infringing edge. • If the boundary edges of Vpq intersect int σ, return any intersection point. • Else, Vpq σ is a collection of closed curves, return a critical point of Vpq σ in a direction parallel to Vpq. Department of Computer Science and Engineering 18/22 Test 4: No-Disk(q,σ) • If the star of q in Del S|σ is a topological disk, return null. • Otherwise, find the triangle t Del S|σ incident to q which has the furthest (weighted) intersection point in Vt|σ from q and return the intersection point. Department of Computer Science and Engineering 19/22 Meshing Algorithm 1. Protect elements in D≤1 with weighted points. Insert a point in each element of D2 outside of protected regions. Let S be this point set. 2. For any σ D2 and point q S σ: • If Infringed(q,σ), Multi-Intersection(q,σ), Normal-Deviation(q,σ,Θ), or No-Disk(q,σ) (checked in that order) return a point x, insert x into S. 3. Repeat 2. until no points are inserted. 4. Return Del S|D. Department of Computer Science and Engineering 20/22 Admissibility is Invariant Lemma. The algorithm never attempts to insert a point in any protecting ball • Since no 3 weighted points intersect, • all surface points (intersections of dual Voronoi edges and D) lie outside of every protecting ball Department of Computer Science and Engineering 21/22 Initialization • The algorithm must initialize with a few points from each patch in D2 • Otherwise, components can be missed. Department of Computer Science and Engineering 22/22 Termination • Each point x inserted is Ω(lfsδ(x)) away from all other points. • Standard packing argument follows. Department of Computer Science and Engineering 23/22 Topology Preservation • To satisfy C1-C4 of eTBP, we show each Voronoi k-face F = Vp1 … Vp(4-k) has: • (P1) If F σ ≠ , for σ Dj, the intersection is a (k+j-3)-ball • (P2) There is a unique lowest dimensional σF s.t. p1, …, p(4-k)σF. • (P3) F intersects σF and only incident elements of σF. • Theorem. If S satisfies P1-P3 then S satisfies C1-C4 of eTBP. Department of Computer Science and Engineering 24/22 Feature Preservation • h:|D| |Del S|D| can be constructed which respects each Di [ES97]. • Thus hi:|Di| |Del S|Di| also a homeomorphism with vertex restrictions, ensuring that the nonsmooth features are preserved. Department of Computer Science and Engineering 25/22 Delaunay Refinement made practical for PSCs S.-W. Cheng, Tamal K. Dey, Joshua Levine Definitions • For a patch σ Di, • When sampled with S • Del S|σ is the Delaunay subcomplex restricted to σ • Skli S|σ is the i-dimensional subcomplex of Del S|σ, • Skli S|σ = closure { t | t Del S|σ is an i-simplex} • Skli S|Di = σ Di Skli S|σ Department of Computer Science and Engineering 27/22 Disk Condition • For a point p on a 2-face σ, • • • UmbD(p) is the set of triangles in Skl2 S|D2 incident to p. Umbσ(p) is the set of triangles in Skl2 S|σ incident to p. Disk_Condition(p) requires: i. UmbD(p) = σ, p σ Umbσ(p) ii. For each σ containing p, Umbσ(p) is a 2-disk where p is in the interior iff p int σ Department of Computer Science and Engineering 28/22 Meshing Algorithm DelPSC(D, r) 1. Protect elements of D≤1. 2. Mesh2Complex – Repeatedly insert surface points for triangles in Skl2 S|σ for some σ if either 1. Disk_Condition(p) violated for p σ, or 2. A triangle has orthoradius > r. 3. Mesh3Complex – Repeatedly insert orthocenters of tetrahedra in Skl3 S|σ for some σ if 1. A tetrahedra has orthoradius > r and its orthocenter does not encroach any surface triangle in Skl2 S|D2. 4. Return i Skli S|Di. Department of Computer Science and Engineering 29/22 Termination Properties 1. Curve Preservation • For each σ D1, Skl1 S|σ σ. Two vertices are joined by an edge in Skl1 S|σ iff they were adjacent in σ. 2. Manifold • • For 0 ≤ i ≤ 2, and σ Di, Skli S|σ is a manifold with vertices only in σ. Further, bd Skli S|σ = Skli-1 S|bd σ. For i=3, the above holds when Skli S|σ is nonempty after Mesh2Complex. 3. Strata Preservation • • There exists some r > 0 so that the output of DelPSC(D, r) is homeomorphic to D. This homeomorphism respects stratification. Department of Computer Science and Engineering 30/22 Voronoi Cells Intersect “Discly” • Given a vertex p on a 2-face σ, if • Triangles incident to p in Skl2 S|σ are small enough. • Then, • Vp|σ is a topological disk, • Any edge of Vp|σ intersects σ at most once, and • Any facet of Vp|σ which intersects σ does so in an open curve. Department of Computer Science and Engineering 31/22 TBP holds globally • if • All triangles incident in Skl2 S|σ are smaller than a bound for all 2-faces, • Then • TBP holds globally • This leads to the proof of ETBP and more…topic of a new unpublished paper. Department of Computer Science and Engineering 32/22 Adjusting MaxRad Example Department of Computer Science and Engineering 33/22 Adjusting MaxRad Example Department of Computer Science and Engineering 34/22 Examples Department of Computer Science and Engineering 35/22 Examples Department of Computer Science and Engineering 36/22 Examples Department of Computer Science and Engineering 37/22 Examples Department of Computer Science and Engineering 38/22 Examples Department of Computer Science and Engineering 39/22 Examples Department of Computer Science and Engineering 40/22 Examples Department of Computer Science and Engineering 41/22 Examples Department of Computer Science and Engineering 42/22 Examples Department of Computer Science and Engineering 43/22 Examples Department of Computer Science and Engineering 44/22 Sharp Example Department of Computer Science and Engineering 45/22 Conclusions • Delaunay meshing for PSC with guarantees. • Feature preservation is an extra `feature’. • Making computations easier, faster? • Analyzing size complexity? Department of Computer Science and Engineering 46/22