A simple, light-weight C++ library for unstructured mesh generation in 2-D using Delaunay refinement algorithms
C++ C

README.md

umeshu

A simple, light-weight C++ library for unstructured mesh generation in 2-D using Delaunay refinement algorithms.

Overview

Umeshu is a small, light-weight C++ library for unstructured triangular mesh generation in two dimensions using Delaunay refinement approach. The library implements the algorithm described in the paper J. R. Shewchuk, Delaunay refinement algorithms for triangular mesh generation, Computational Geometry 22(1-3) (2002), 21-74. The mesh is stored in a half-edge data structure and the implementation relies on generic programming using templates and on containers and tools provided by STL and Boost.

Although other (faster, more sophisticated, complex, general) mesh libraries and mesh generators exist (e.g., OpenMesh, CGAL, Triangle), the principal advantage of Umeshu is its relative simplicity, the implementation is quite straightforward. It can be used as a learning tool for half-edge data structure, for Delaunay refinement techniques and as a basis upon which new mesh generation algorithms can be tested.

Features

  • Small and compact implementation of half-edge data structure
  • Implementation of Ruppert's algorithm for unstructured mesh generation
  • Handles small angles in input polygon by concentric shell splitting
  • Mesh output to:
    • EPS (Encapsulated Postscript)
    • OBJ
    • OFF
    • PLY
    • STL (ASCII)
  • Shewchuk's adaptive floating-point predicates
  • CMake build system
  • Mesh relaxation algorithm described in W. H. Frey, D. A. Field, Mesh relaxation: A new technique for improving triangulations, International Journal for Numerical Methods in Engineering 31(6) (1991), 1121-1133

TO DO

  • More mesh refinement criteria
  • Mesh smoothing
  • Edge collapsing in mesh relaxation
  • Test suite
  • Evaluation of mesh statistics
  • Command-line application for mesh generation
  • Provide means for inputting description of boundary conditions for use in FEM
  • Extend to domains with holes and with curved boundaries

Dependencies

  • Boost
  • Eigen3

Example

Initial triangulation of the input polygon:
Initial triangulation of the input polygon

Constrained Delaunay triangulation:
Constrained Delaunay triangulation

Refined mesh:
Refined mesh

Mesh prepared for smoothing after application of a relaxation algorithm:
Mesh prepared for smoothing after application of a relaxation algorithm