CAD Geometry Issues in Meshing

Leader: Mr. David White (drwhite@sandia.gov)

The first discussion topic of the group was: Should the mesher be inside or outside of a CAD package?

• In general everyone agreed that it was preferable to be inside the CAD package where the geometry was created. Experience has shown there are fewer problems when translation is not needed and native interpretation is done.
• Many agreed with this but also agreed that it isn't always going to happen citing the following reasons:
  • Many companies balk at having to buy both a license for the meshing package and another license for the CAD package. (Someone mentioned they are willing to spend $400K to train the analyst but not spend the $12K to $40K on the software they need.) In general many felt this would not always sell for economical reasons.
  • Many companies don't get geometries from a single CAD system citing different vendors and customers preferences.
  • Legacy models based on meshes as a CAD definition must be handled.
  • Running on parallel machines? Do you need 2000 licenses of Pro/E?
  • Adaptivity (see below).
• Still others brought up points that even when in the native CAD systems "dirty geometry" remains a problem. People mentioned techniques involving "best practices" to ensure these get fixed by the designers.
• The major issues remaining in this area are how to interface efficiently with CAD systems and get localized model updates and how to drive model changes from the analysis.

A second discussion topic of the group was where should the problems be fixed? In the mesher or the CAD system? This brought up other interesting debates.

• Many agreed that even if the mesher resides in or on top of a CAD system, the meshing package must have a way to modify the CAD model. Many systems now have "virtual" modifiers that allow the topology of the model to be changed independent of the CAD system and only in the meshing system.
• In the past many had hoped perhaps the same CAD model could be used for numerous different applications, for example, CAE, CAM, Visualization, Drawings, etc... In general people have found it easier to recreate models than it is to defeature them. People cited problems like basing new features off fillets or holes that may be insignificant to one of the many downstream applications; thus making removing the insignificant features difficult.
• We also discussed how and when to remove features. Some suggested removal of the features is difficult to predict and must be decided by the analyst. Others pointed out that this doesn't scale very well with 10s or 100s of small features. Others pointed out that the direction needed is for the analysis to dictate which features are important and which are not. Others responded to this point that just getting a mesh at a reasonable resolution on highly detailed parts is the reason we want to defeature at all. In tet meshing this is much easier than hex meshing.

This discussion moved the group into a discussion of the future vision, for instance, how CAD would be designed by the analysis. Some pointed to a few success stories of how parameterized models and adaptivity can work to build totally new solutions. The group agreed this was difficult to for general situations and that the problem mainly involves the two-way connection between CAD and analysis. How can models be parameterized correctly so that the new designs can be created generally from the analysis cycles?

Other tangential discussions involved the political problems involved with companies trusting these new design processes that are driven by modeling. Some said they were entirely politically inhibited while others felt there were still economical reasons for the hold up.  

Surface Meshing

Leader: Prof. Jonathan Shewchuk (jrc@cs.berkeley.edu)

The Surface Meshing BoF spent most of the time discussing notable advances over the last several years in research related to surface meshes. There were plenty of examples to discuss, as the field has been quite active. Most of the discussion fell into three broad categories: quality mesh generation and improvement on surfaces; surface geometry processing (e.g. simplification, parametrization); and surface reconstruction. Names in parentheses below indicate researchers who have made recent advances in the topic.

Quality mesh generation and improvement on surfaces

• Anisotropic surface meshing has received much recent attention.
• Dynamic meshing, especially for skin surfaces (Edelsbrunner).

Surface geometry processing

• The field of geometry processing is growing fast, and has produced a profusion of new ideas. A sampling appears below. The first application, remeshing, could equally well be included in the "quality mesh generation and improvement" category above.
• Remeshing: Algorithms remesh a previously meshed surface, typically by recovering a continuous model from the original mesh, then remeshing it. Applications include texture mapping and coding and compression for transmission. Techniques include
  • Moving least squares (Rassineux)
  • Gregory patches
  • Reparametrization, resampling, and remeshing
  • Geometry images (Hoppe) reparametrize with a structured mesh for fast texture mapping; no connectivity is explicitly stored
• Cutting/chartification methods to simplify topology. Criteria are
  • Low distortion (Hoppe)
  • Small cut size (Erickson & Har-Peled)
• Reparametrization methods.
  • Circle-packing parametrization (Noel & Leon)
  • Embedding by numerical optimization of a global distortion measure (Sheffer)
  • Least squares conformal isoparametric parametrizations (Levy)
  • Conformal intrinsic parametrization (Desbrun)
• Feature detection on meshes (Rassineux).
• Estimating surface properties (e.g. curvature) from a mesh (Morvan).

Surface reconstruction

• Many new algorithms have emerged lately. There has been an emphasis on creating guaranteed watertight surfaces.
  • Powercrust (Amenta/Choi/Kolluri)
  • Tight Cocone (Dey/Botswani)
  • Delaunay decomposition by normalized cuts (Kolluri/Shewchuk)
  • Natural Neighbor (Boissonat/Cazals)
• Helpful work has been done in characterizing the complexity of the Delaunay tetrahedralization of surface samples (Erickson).
• Challenges still remain in improving the handling of sharp features, manifolds with boundaries, and noise.

We concluded with a brief discussion of problems for which attendees would like to see better solutions.

• Smoothing mixed (triangular/quadrilateral) surface meshes with very high aspect ratios. Examples: microprocessors, car bodies.
• Meshing with nonrobust (i.e. all) solid modelers.
• Boundaries of manifolds in surface reconstruction.
• Noise in surface reconstruction.
• Error/quality evaluation for two different meshes of the same thing.
• Finding correspondences between two different meshes.

Volume Meshing

Leader: Dr. Scott Mitchell (samitch@sandia.gov)

State of the Art Review

We began with reviewing the "current technology" and percieved needs from the 10th IMR BOF volume meshing summary. Not much had changed since last year.

The overall feeling was that there wasn't a lot of current activity centered around advancing the core algorithms of volume meshing. BYU had a notable effort. But overall, most groups that were working on volume meshing were trying to advance ancilliary aspects, such as refinement and coarsening / adaptivity, or usability.

Changes Since Last Year

Tet

Finished problem? No from the user's standpoint (e.g. usability), but "yes" from the developer's standpoint (e.g. no fundamental interesting problems left).

Interesting surface meshing issues remain. Building a curved surface triangulation is not "finished." Also, issues remain in having a volume mesh respect a prescribed triangle boundary mesh, and getting good tet quality near that boundary.

Anisotropy. This is one bright spot that is receiving attention and where the state of the art is advancing.

Sizing control is not finished.

Hex

Overall, progress is "evolutionary" not "revolutionary".

Sweeping. Like last year, it exists but is inadequate. Not much progress since past year.

Octree: one "sculpting" paper at the 11 IMR.

Template conversions. The BOF participants thought it was still an active area: e.g. the "DTHEX" effort at BYU. But, there was less momentum around this topic than last year.

Challenges

Getting students

The academics reported it was difficult to attract students to meshing. Most engineering students view meshing as a means to an end (analysis), and would rather work on the ends (analysis), and don't value meshing intrinsicly. We speculated that the tension between "means and ends" might be a little better in CS, but the response from the CS participants in the BOF group was that the problems are rarely defined in a ways that are accessible to CS, and when they are defined that way the problems are unattractive because they are so very difficult.

Meshing has quite a bit of competition for capable students from other fields.

Meshing does not have a department home. As a consequence, students percieve that there is a risk in pursuing meshing: e.g. what will the job market be? Academics rarely succeed as meshing specialists, and usually emphasize some other aspect of their research when pursuing positions or tenure. To attract students, the challenge for professors is to identify some key problem where meshing is the roadblock.

Is volume meshing passe?

Attendance was low at the volume meshing group, only 12 people, comparted to about 50 for the geometry session. 8 were academics. Only 2 had a CS background, the rest were from engineering.

Geometry problems are not going away: e.g. the crack propogation issues described in Tony Ingraffea's keynote address.

All the easy problems in volume meshing have been solved, only difficult ones remain. This might change if revolutionary new paradigms are invented, but the group saw little chance of that.

Funding sources

Another disturbing trend is that "meshing" is absent from all of the funding calls and funding agency charters that the BOF attendees were aware of. For example, the NSF funding call at the 11IMR addressed software infrastructure rather than meshing per se. The situation is similar for the DOE Office of Scientific Research, and the Air Force research labs.

Desires

The BOF group would like to see more activity and investement in the following areas: (Session chair note: in the list of desired investements, I think it is significant that "unstructured hex mesh generation algorithms" was not mentioned this year.)

More parallel meshing, especially coupled with analysis.

Adaptivity for hexes, either motivated by parallel adaptivity based on analysis error estimators, or a priori for element quality.

Meshless methods

"Meshless" has replaced "automation" as the thing CFD analysts complain about. That is, CFD analysts are clamoring for advances in meshless methods, not automation of meshing methods.

The BOF group sees a need for someone to perform a high quality, rigorous, fair comparison between meshless methods and mesh-based methods. Perhaps the IMR could issue a special challenge akin to the poster contest. Another idea is to have an invited speaker from the meshless community come and explain the salient problems that the meshing community could address. The BOF group felt like they really didn't understand meshless methods.

Status of meshless method activity: Labs: not much Commercial: not much Academic: taking all the talented people, leaving none for meshing methods. (none of the BOF academic attendees represented meshless methods)

This state of affairs seems very significant! (Alarming?) Given that todays student's are tomorrow's lab and commercial staff, this could be a strong indicator that the technology focus will radically and suddenly shift away from mesh-based methods and towards meshless methods.

Perhaps the IMR could have a special session for "discretization" (mesh generation) for meshless methods. This might be essential in order for the IMR to remain relevant in the long term.  

Mesh Quality

Leader: Mr. Hugh Thornburg (Hugh.Thornburg@wpafb.af.mil)

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

Progress 10th - 11th IMR

• Development of grid quality metrics that incorporate both geometric and problem physical characteristics (error estimation)
• Community 'buy-in' on the need for and desirable characteristics of grid quality metrics
• Several orders of magnitude improvement in the performance of 2nd order node placement methods
• Beginnings of a theoretical basis for solution existence and uniqueness
• Solution adaptation
  • Error estimation
  • Mesh modification for tri/tet meshes
• Production capability for polyhedral mesh smoothing
• Enhanced user control of mesh distribution
• Smoothing of material interface (defined by facets) in order to improve quality
• Mesquite software framework
• Progress and continuing work on local vs. patched vs. global techniques for quality improvement

Open Problems

• Comparison of mesh improvement techniques
• Definition of mesh quality
  • Deviation from specified size
  • Deviation from desired shape specification
  • Orientation
  • Discretation error
    • FV
    • FE
    • FD
• Mesh quality for higher-order elements

Classes of problems that current technology cannot address

• Hex mesh of 'under hood'
• Time varying geometry
• Automatic generation of meshes for viscous simulation of complex aerospace systems

Solutions

• Set of test problems for 'common' evaluation
• Collection of quality improvement modules for framework to compare methods
• IMR sessions on solution adaptive meshing
  • Encourage submission of papers
  • Educate the community on current capabilities and research efforts

Software Issues in Meshing

Leader: Dr. Jamshid Samareh (j.a.samareh@larc.nasa.gov)

As the field of meshing matures, the need to make meshing software easy to implement grows. This BOF may discuss topics related to the software infrastructure that supports meshing research:

• Open standards for APIs and file formats
• Modularity
• Interoperability
• Parallel meshing

Notes

Only 10 people attended the session (3 commercial software developers, 5 academia, 2 government), far fewer than other sessions. Everyone agreed that the current APIs are either too bulky (e.g., STEP) or are difficult to implement. There are a couple of new developments:

• CAD Services (http://cgi.omg.org/cgi-bin/doc?dtc/02-01-03)
• STEP AP 237 for fluid dynamic data sets (http://www.cgns.org/ISO.html) - this is an outgrowth of CGNS

Issues

• We should use OpenGL API (www.opengl.org) experience as a successful model
• API development must include input from API developers and API users
• API development must be incremental
• We need a clearer definition of low and high level APIs
• STEP AP237 (fluid dynamics) should include binary file format for storing large meshes
• AFRL is funding the development of a standard API for meshing

Research Issues

• Develop/modify mesh generation algorithms to take advantage of commercial database (free algorithm development from data structure)
• Develop API for file format based on commercial database for meshing
• STL-based surface representation may resolve most of geometry API related issues

Parallel Meshing

• Parallel meshing is essential for meshes requiring large memory
• Splitting domains can facilitate parallel mesh generation
• Out-of-Core meshing may overcome memory issues

Open Standards for API (CAD)

• OMG CAD Services, A CORBA Interface for Geometry Information Sharing, development team: Ford, General Electric, Catia, Unigraphics (SDRC), ITI TranscenData, NASA, Boeing, Theorem Solutions, OpenCASCADE
• OMG, http://cgi.omg.org/cgi-bin/doc?dtc/02-01-03 (java, corba, c++, python)
• CADScript, http://www.transcendata.com/cadscript/ (python)
• CAPRI: Computational Analysis PRogramming Interface, http://raphael.mit.edu/capri/docs.html, (FORTRAN, C, C++)
• Common Geometry Module (CGM), A Generic, Extensible Geometry Interface, Tautges, Timothy J., Proceedings, 9th International Meshing Roundtable, Sandia National Laboratories, pp.337-348, October 2000
• MEGA, vendor neutral CAD interface from RPI
• API for STEP is Standard Data Access Interface, SDAI (e.g., IBM Prism and Intergraph implementations).

Open Standards for File Format (CAD)

Summary article on IGES and STEP by Don LaCourse (editor-in-chief of Handbook of Solid Modeling) October 2001, CADALYST Magazine, http://www.cadalyst.com/features/1001vendors/stepiges.htm

• IGES
  • Stable and mature.
  • B-rep solids (IGES V5.1).
  • Can read/write B-rep (186), (SolidWorks cannot write B-rep).
  • B-rep usage is around 15%, hampered by the onset of STEP.
  • STEP will never completely replace IGES simply because of the volume of IGES data out there.
• STEP
  • STEP is primarily used to transfer 3D solid models.
  • All participants (except SDRC) now ship STEP with their base products.
  • STEP has fewer options than IGES (less opportunity for flavoring).
  • Following factors limit the use STEP:
    • STEP is simply too large.
    • Variations in solid model representations and tolerances
    • Poor STEP documentation
    • Excessive duplication in the standard

Open Standards for API & File Format (Mesh)

• API
  • TSTT Interface Definition: mesh components compliant with query interface as CCA components stable and mature (Argonne National Laboratory). http://www.tstt-scidac.org/research/mesh.html
  • Gridgen, Glyph Tcl-based scripting language (http://www.pointwise.com/)
• File Formats
  • NASTRAN for FEM
  • CGNS: CFD General Notation System (www.cgns.org)
  • STEP AP209, finite element analysis
  • STEP AP237, fluid dynamics