Efficient Mesh Generation for Piecewise LinearComplexesTodd PhillipsCMU-CS-09-156August 2009School of Computer ScienceCarnegie Mellon UniversityPittsburgh, PA 15213Thesis Committee:Gary L. Miller, ChairAnupam GuptaDaniel D.K. SleatorNoel J. WalkingtonTamal K. Dey, The Ohio State UniversitySubmitted in partial fulfillment of the requirementsfor the degree of Doctor of Philosophy.Copyrightc 2009 Todd PhillipsThis work was supported in part by the National Science Foundation under grant CCF-0635257Keywords: Computational Geometry, Scientific Computing, Mesh G enerationAbstractThe mesh generation problem is to output a set of tetrahedra that discretizean input geometry. The input is given as a piecewise linear complex (PLC), a setof points, lines, and polygons to which the output tetrahedra must conform. Ad-ditionally, a mesh generation algorithm must make guarantees on the quality andnumber of output tetrahedra. Downstream applications in scientific computingand visualization necessitate these guarantees on the mesh.Recent advances have led to provably correct algorithms for a number of inputclasses. Particular difficulties arise when the input contains creases, regions whereinput segments or polygons meet at acute angles. When the input is withoutcreases, the mesh generation problem is better understood. Algorithms for suchinputs exist with near-optimal runtimes of O(n log ∆+m), where n and m are thesize of the input and output, and ∆ is the ratio of largest-to-smallest distancesin the input geometry. The principle result of this thesis is to extend this resultto the general case of piecewise linear complexes with creases.Correct algorithms to handle inputs with creases involve explicitly construct-ing a system of specially designed collars around the creases. These collars mustbe specifically sized according to the input geometry. I give a new procedure tocompute the needed collar sizes in near-optimal O(n log ∆ + c), where c is thedescription complexity of the collar system. Additionally, I give a procedure forimplicitly constructing a collar system on the fly, so that a complete meshingalgorithm for a PLC can be run in one pass with total work in O(n log ∆ + m)and space usage in O(m).Central to the analysis is the “Scaffold-Sizing Theorem”, a structural resultgoverning the number of vertices created during mesh generation. The theoremis general enough to have an added benefit of retroactively improving the analysisof almost all existing meshing algorithms.4Contents1 Introduction 91.1 The Meshing Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.2 Conforming Me shes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.3 Quality Mesh Elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.3.1 Quality Tetrahedra . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.3.2 Delaunay and Voronoi . . . . . . . . . . . . . . . . . . . . . . . . . . 141.3.3 Computational Needs . . . . . . . . . . . . . . . . . . . . . . . . . . . 161.4 Mesh Sizing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171.5 Efficient Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201.5.1 Delaunay Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . 201.5.2 Point Location Costs . . . . . . . . . . . . . . . . . . . . . . . . . . . 211.5.3 Related . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212 Preliminaries 232.1 Standard Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242.1.1 Sizing Functions and Voronoi Diagrams . . . . . . . . . . . . . . . . . 242.1.2 Proximal Packing Lemma . . . . . . . . . . . . . . . . . . . . . . . . 252.2 Structural Properties of Quality Voronoi Diagrams . . . . . . . . . . . . . . 272.2.1 Gap Ball Sizing Lemma . . . . . . . . . . . . . . . . . . . . . . . . . 272.2.2 Degree Bound Theorem . . . . . . . . . . . . . . . . . . . . . . . . . 292.2.3 Grading Lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312.2.4 Proximity in Well-Spaced Meshes . . . . . . . . . . . . . . . . . . . . 322.3 Scaffolding P reliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332.4 Surface Reconstruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3552.4.1 Collar Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362.4.2 Restricted Delaunay and Voronoi . . . . . . . . . . . . . . . . . . . . 373 Algorithm SVRC 413.1 Algorithm Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413.1.1 Sparse Refinement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423.1.2 Enhancements for handling Creases . . . . . . . . . . . . . . . . . . . 433.1.3 Correctness of SVRC . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463.2 Structures in SVRC . …