Global optimization of mesh quality D. Eppstein, Meshing Roundtable 20011Global Optimization of Mesh QualityDavid EppsteinUniv. of California, IrvineDept. of Information and Computer ScienceGlobal optimization of mesh quality D. Eppstein, Meshing Roundtable 20012IntroductionMesh quality issues, meshing stepsConnectivity optimizationDelaunay triangulation, edge insertionGlobal point placementQuadtrees, incremental Delaunay refinementIndividual point placementQuasiconvex programming, sliver exudationOutline:Global optimization of mesh quality D. Eppstein, Meshing Roundtable 20013I. What is Meshing?Given an input domain(manifold with boundary or possibly non-manifold geometry)Partition it into simple cells(triangles, quadrilaterals, tetrahedra, cuboids)Essential preprocessing step for finite element method(numerical solution of differential equations e.g. airflow)Other applications e.g. computer graphicsGlobal optimization of mesh quality D. Eppstein, Meshing Roundtable 20014Triangle mesh of Lake Superior [Ruppert]Global optimization of mesh quality D. Eppstein, Meshing Roundtable 20015Quadrilateral mesh of an irregular polygon(all quadrilaterals kite-shaped)Global optimization of mesh quality D. Eppstein, Meshing Roundtable 20016Triangle mesh on three-dimensional surface [Chew]Global optimization of mesh quality D. Eppstein, Meshing Roundtable 20017Tetrahedral mesh of a cubeGlobal optimization of mesh quality D. Eppstein, Meshing Roundtable 20018Portion of hexahedral mesh of elbow pipe[Tautges and Mitchell]Global optimization of mesh quality D. Eppstein, Meshing Roundtable 20019Mesh Quality IssuesElement type?2d: triangles vs quadrilaterals3d: tetrahedra vs hexahedraThis talk: primarily triangles and tetrahedraQuality guarantees for quad/hex meshes much less developedElement shape?Avoid sharp angles, flat angles, distorted elementsAffects accuracy of numerical simulationElement size?Need small elements near small features or abrupt changes in solutionlarge elements ok in uninteresting parts of domainNumber of elements?More elements = slower solution timeElements on domain boundaries?May be required to match existing domain boundary meshfor quality reasons or to mesh multi-domain inputGlobal optimization of mesh quality D. Eppstein, Meshing Roundtable 200110Theory vs. PracticePractical emphasis: get system to workTechniques often ad-hocEvaluation of result quality may be visual,or by examining numerical quality of “typical” meshesWorks well in many casesUnusual inputs may lead to bad mesh, slow construction, or crashingTypical paper outlet: Meshing Roundtable(should be familiar to this audience)Global optimization of mesh quality D. Eppstein, Meshing Roundtable 200111Theoretical emphasis: prove system worksProve guarantee that method gives high-quality meshwith small polynomial for worst-case running timeLeads to robust algorithms that work every timeGuarantees may be weaker than typical practiceBigger problem: lack of implementationTypical paper outlet: Symposium on Computational Geometry(but also sometimes in Roundtable)This tutorial mainly concentrates on theoretical approachGlobal optimization of mesh quality D. Eppstein, Meshing Roundtable 200112Goal: Synthesize best practices from theory and practiceImplement fast, guaranteed-quality algorithmsmaintaining speed, robustness, mesh quality guaranteesApply practical mesh improvements to lift quality above worst-case guaranteeswithout violating quality, robustness guaranteesEvaluate meshes and meshing algorithmsby both provable and observed meshing qualityNeed continued research on appropriate quality measuresas well as meshing algorithm developmentAlso insufficiently studied:What is a “typical” meshing input, and how can we use its structureto improve results compared to worst-case inputs?Maintain communications between SCG and Roundtable communitiesGlobal optimization of mesh quality D. Eppstein, Meshing Roundtable 200113Not fully settled, varies by meshing applicationAvoid sharp angles? Allow sharp angles but avoid obtuse angles?Use non-directional quality measures?Align mesh elements with domain boundaries?Concentrate quality near boundary, allow worse elements in interior?A priori measures (depending only on domain geometry)vs. measures depending on finite element solutionWhat is the “right” quality measure?Global optimization of mesh quality D. Eppstein, Meshing Roundtable 200114Use general-purpose algorithms that canbe adapted to different quality measuresProve that certain algorithms (primarily, Delaunay triangulation)simultaneously optimize many quality measuresRelate different measures to each otherallowing quality guarantees for one measure to apply to anotherWhat to do when you don’tknow the right quality measure?Global optimization of mesh quality D. Eppstein, Meshing Roundtable 200115Typical mesh generation stages:Generate initial point placementWell spaced, other quality considerationsDetermine mesh connectivityUsually, Delaunay triangulationMay be intermixed with point placement stageIterate mesh improvement stagesLaplacian or optimization-based smoothingFlips and other connectivity changesOrder for this talk:Mesh connectivityInitial placementMesh smoothingEasier to understand justification for placementafter seeing connectivityConnectivity improvement similar to initial connectivityGlobal optimization of mesh quality D. Eppstein, Meshing Roundtable 200116IntroductionMesh quality issues, meshing stepsConnectivity optimizationDelaunay triangulation, edge insertionGlobal point placementQuadtrees, incremental Delaunay refinementIndividual point placementQuasiconvex programming, sliver exudationOutline:Global optimization of mesh quality D. Eppstein, Meshing Roundtable 200117Delaunay Triangulation:Given planar point setConnect two points by edgeif some circle existswith them on boundary,empty interiorCollection of all such edgesfor points in general position(no four cocircular)forms triangle meshcovering convex hullGlobal optimization of mesh quality D. Eppstein, Meshing Roundtable 200118Delaunay Triangulation:Given planar point setConnect two points by edgeif some circle existswith them on boundary,empty interiorCollection of all such edgesfor points in general position(no four cocircular)forms triangle meshcovering convex hullGlobal optimization of mesh quality D. Eppstein, Meshing Roundtable 200119Delaunay Triangulation:Given planar point setConnect two points by edgeif some circle existswith them on