Geometry Issues in Meshing

Leader: Dr. Steven Owen (sjowen@sandia.gov)

Geometry Import - Current Process

• From CAD format (SolidWorks, Parasolid, ACIS, Pro/E, STL, CATIA, etc.) thru...
• Translator into
• Native Geometry Engine which interfaces to
• Mesh Generation

Geometry Import - Desired Process

• CAD Abstraction Layer: Generic API to embedded commercial geometry engine
• For example: CGM, CAPRI, VIG, in-house versions
• should not base meshing on one specific geometry package

Native vs. 3rd Party Geometry Kernels

• Native
  • Advantages
    • speed (3rd party can be slow)
    • more control (3rd party may not have what you need i.e. parametrization)
  • Disadvantages
    • Translation may fail or produce unexpected/poor results
    • Maintenance of many translators of different formats
• 3rd Party
  • Advantages
    • They do most of the work for you, provide services for Booleans, translations, geometry query, modification, etc.
  • Disadvantages
    • Maintenance of many interfaces
    • Different requirements/paradigms for each kernel

Geometry Kernel

• Many different choices of "Routes"
  • i.e. STEP to 3rd Party, XML to Native, 3rd party to Native, etc...
• Conclusion:
  • No Route is 100% reliable

Geometry Representation: Facets vs NURBs

• Facets
  • evolving geometry
  • bio models
  • starting point for reparametrization
  • point projection can be faster
  • flexible - can modify, composite or split surfaces easily
• NURBs
  • Some apps "must" have exact surface (e.g. aerodynamics)

Facet Geometry Representation

• Parameterization of facet surfaces
  • multiple loops open problem (fill in holes)
  • periodic or closed sets of facets?
• Feature Extraction
  • Feature angle not enough
  • "Beautification" or reverse engineering
• High order approximation
  • necessary for H and P adaptivity
  • linear could cause errors in FEA solution

Geometry Representation - Hybrid Approach

• Designers need both facets and NURBs for maximum flexibility

Thin Solids

• Hex Shells
• Automatic methods needed for defining where to put shells (hex shells)
• Medial Objects
  • good mathematic foundation
  • algorithms are not 100%
  • automatic trim and extend algorithms needed
• Why not build geometry from surfaces rather than 3D solid model?
• Industrial customers are asking for this capability

Fix Geometry Problems vs. Fault Tolerant Meshing

• Fix Geometry
  • Expectations from CAD operator are low - "He's not going to fix it"
  • Tools - CADfix - modifies geometry
  • Danger in automatically changing geometry
    • How do you know features to suppress/fix and if it wasn't what the analyst really wanted?
    • Provide interface to detect potential problems and the user picks what to fix
• Fault Tolerance
  • Detect common problems while meshing
  • Mesh over gaps, small features
  • Assumes what is error or bad geometry
  • Virtual Geometry - does not change geometry

Mesh/Geom Forum

• Mailing list/Web page to discuss current issues
  • more specific than current mesh mailing list - mesh@yahoogroups.com
  • meshgeom@yahoogroups.com
• Other subdisciplines in meshing?

Surface Meshing

Leader: Dr. Pascal Frey (Pascal.Frey@inria.fr)

A few remarks:

• surfaces are very important for various reasons
  • define boundary of 3D domains
  • used to represent an object (domain)
  • only "interaction" with the object (assign boundary cond. in FE, ...)
• topic of current interest
  • Number of papers in literature is increasing...
  • but number of papers at IMR is decreasing.
• why? difficult topic - requires background (maths)
  • theorems versus algorithms (ex. point cloud reconstruction)
  • numerical analysis, mathematics, ... algorithms - mesh
  • (cf. Tim Baker: surface recovery for tet. meshing)
• Surface Meshing does not mean 2D!
• Surface definition: each has specific domains of interest.
  • parametric: CAD, ...
  • discrete: reconstruction, ...
  • implicit: morphing
• What is meant by the "weird" notion of a Delaunay surface: it is not defined!
• The "natural" element type for surface meshing appears to be a quad.

Advances in surface meshing

• metric definition (G₃)
  • based on the local curvatures
  • 2D parametric
  • discrete surfaces
  • surface evaluation before meshing!
• point cloud surface reconstruction
  • not fully done yet
  • theory versus algorithms
• coupling with CAD systems (models) as well as with computations
• quality issues
• anisotropic meshes (cf. metric)
• moving meshes (based on optimization) coupled with computation
• adaption
• Delaunay admissibility (for 3D)
• Simplification algorithms:
• Feature extraction (internal CAD)

Open Issues

• CAD cleaning (addressed by geometry BOF)
• feature extraction / defeaturing
• surface reconstruction from sampling
• "provably" Delaunay-admissibility
• re-parametrization
• dynamic meshes (lots of potential applictions incl. FE, graphics...)

Solutions

• investigate and focus on real problems (ie forget GUI, API,...)
• keep in mind the target: mesh, not a theorem
• test sets: see Drexel Univ. repository

Volume Meshing

Leader: Dr. Ted Blacker (ted@fluent.com)

Current Technology

• Hex Meshing
  • Sweeping (but inadequate)
  • Octree-Based (viable, but w/ concerns)
  • Template Conversions (new)

• Tet Meshing
  • Not a finished problem
  • Size Limitations
  • Surface Meshing Constraints
  • H-Morph Implications to Hex Meshing
  • No New Paradigms

Advances Needed

• Hex Meshing
  • Surface Adjusting
  • Intuitive Quality Measure
  • Auto Blocking
  • Medial Axis Research
  • Sheet Manipulation

• Tet Meshing
  • Surface Adjusting
  • Size Gradation Quality Guarantees
  • Anisotropy
  • Non-Obtuse Triangulations

• General
  • Adaptation
  • GUI Optional Meshing
    • Automated
    • Controllable
  • Geometry Tolerant Algorithms
  • Combined Methods

• New Ideas
  • Crystal Growth
  • Combined Approaches
    • WW + Plastering

How Do We Accomplish Progress

• More People leads to Better Solutions leads to More Work leads to More People ...
• Exploring Attitudes
• Overcome University Issues
  • MS time too short
  • Multiple disciplinary students
  • Show more real problems
  • Advertise w/flashy presentations
• Commercial Openness
  • Publish More
  • Honest Weak/Strength
• Library of Shared Problems
• Open Shared Code
  • Reduce Startup Costs
  • Increase Research Pool

Mesh Quality

Leader: Dr. Lori Freitag (freitag@mcs.anl.gov)

Current State-of-the-Art

• Guaranteed quality triangular mesh generation (some work for quads)
• Sliver exudation and Delaunay perturbation for quality improvement
• Algebraic mesh quality metrics
• Optimization-based smoothing algorithms
• Work in the structured grid community to optimize meshes wrt particular PDE
• Increasing amount of work in a posteriori metrics and quality improvement

Measuring Mesh Quality

• Solution efficiency, solution accuracy
  • Linear solvers
  • Discretization approximations
• Shape measures
  • Tetrahedra
    • Not all that are currently used are valid measures
    • Most tha are valid can be shown to be equivalent
    • Are there reasons be prefer one over another? (Computation time)
  • Hexahedra
    • Not as much work done here
    • Some valid shape measures exist
  • Adaptive determination of mesh quality as solution method proceeds is necessary.

Open Problems - Highest Priority

• Using information about PDE operators and discretization methods to "custom" smooth all mesh types
  • Anisotropic smoothing for ideal reference elements that are not isotropic
  • Tuning the mesh quality metrics
  • Developing predictive capabilities
• Assessment of methods/metrics to determine which work best
  • What is the relationship between quality metrics and solution quality for a given PDE
• Measuring mesh quality in the aggregate rather than on an element by element basis

More Open Problems

• Quality guarantees for mesh generation
  • Meaningful guarantees for tetrahedral and hexahedral meshes
  • General polyhedral meshes with small input angles
  • When does an all non-obtuse mesh exist?
• Smoothing meshes with curved surfaces and mixed elements
• Obtaining consistency among quality metrics; in particular addressing the fact that many similar (but not identical) metrics go under the same name, e.g. skew
• Mesh quality for higher-order elements
• Strategies for maintaining quality as the mesh dynamically changes
• Determining global convergence properties of local operations
• Mesh quality metrics that combine size and shape

Research Directions

• Revisit the benchmarks suggested by Compierre, et. al. at the 7IMR
  • Need a broad spectrum of meshes to exercise methods and metrics
    • Randomly generated local submeshes
    • Known difficult cases that are not randomly generated
• Need a comparative study of metrics and optimization techniques

Software Issues in Meshing

Leader: Dr. Nikos Chrisochoides (nikos@cs.wm.edu)

Issues

• Components
  • How? Generic Programming
  • What? Application Program Interface
• Application Program Interface
  • Geometry (Steven Own)
  • Mesh (to application)
  • Parallel Mesh (Partition, Commun., Load Balance)
  • Field (tensor/scalar data, diff. reps: nodal, elm)

Current Status

• Geometry: CGM, CAPRI, Cornell/MSU
• Mesh: RPI, NASA_Ames, Exodus, CGNS, PNL
• Parallel Mesh
  • Mesh Specific: Zoltan, PLUM, SMP
  • Mesh Centric: DMCS & MOL
  • Available at http://www.cs.wm.edu/~nikos/pes/
• Field: NASA_Ames, LNL

DMCS

DMCS Remote Service Request Functions
dmcs_async_rsrX	RSR with an X argument handler where X = {0,1,2,3,4}
dmcs_async_rsrN	RSR with a handler taking a variable size buffer
DMCS Remote Memory Manipulation Functions
dmcs_malloc	allocate memory on a remote processor
dmcs_free	free memory on a remote processor
dmcs_put	copy a data buffer to a remote processor
dmcs_put_op	copy a data buffer to a remote processor; the remote processor then returns with a dmcs_async_rsr1
dmcs_get	retreive a data buffer from a remote processor
dmcs_get_op	requests a dmcs_put_op be executed on a remote processor
DMCS Environmental Functions
dmcs_init & shutdown	initialize and shutdown DMCS
dmcs_my_proc	the relative process ID of the calling process
dmcs_num_procs	the number of running processes
dmcs_register_rsrX_handlers	registers rsrX type handlers where X = {0,1,2,3,4,N}