A Whitepaper on Mesh Processing Toolkits by ProtoTech Solutions

What is Mesh Processing?

In general, a mesh is a collection of vertices and its connecting edges to form the specified shape. Mesh processing is a general terminology used in different practical areas. Some topics under mesh processing are:

1. Noise removal
2. Mesh healing
3. Mesh decimation
4. Shape detection
5. Mesh deformation

• For e.g. scanned output of professional 3D scanner may contain unwanted elements (noise) which needs to be removed before scan is processed. Using mesh processing algorithms, this unwanted noise can be removed.
• Sometimes the scanner leaves some holes in the object or doesn’t connect the triangles properly. In these scenarios, mesh can be healed using different healing algorithms that are supported by libraries available in the market. 
• Due to high resolution scanning devices, the vertex count of scanned mesh is huge. High resolution scan is required in micro areas like medical but may not be required in the BIM industry. This huge scan leads to unnecessary processing overhead and performance hit for viewing applications. Using decimation techniques, shared vertices/redundant vertices can be removed to lower vertex count and maintain the scan shape. 
• Mesh processing can be used to detect shapes from scan. For e.g.if scan is of building, it might be essential to detect walls, door, windows etc. Using high end technologies like artificial intelligence and machine learning, shape detection from a dump scan seems possible.
• Also in the gaming industry or simulation area, shape deformation is required. Using mesh processing, efficient shape deformation can also be done.
• Example explained above is in terms of scan mesh. But similar operations can be performed on any mesh coming out of CAD tool or any other source.

What are various options available for Mesh Processing?

Following are some of the options that are available in the market for mesh processing. The brief information about the toolkit is not endorsed by the vendors and we recommend that you visit the respective vendors for the latest and exact information. 

1) Mesh Processing Library

 Publisher: Microsoft 

 License: MIT License

 References:

• https://rawgit.com/Microsoft/Mesh-processing-library/master/README.html
• https://github.com/Microsoft/Mesh-processing-library

Highlights: 

•  Surface reconstruction (from unorganized, unoriented points)
• Mesh optimization
• Subdivision surface fitting
• Mesh simplification
• Progressive meshes (level-of-detail representation)
• Geomorphs (smooth transitions across LOD meshes)
• View-dependent mesh refinement
• Smooth terrain LOD
• Progressive simplicial complexes                        

Platforms: The source code follows modern C++11 style and is designed for cross-platform usage.

2) CGAL (Computational Geometry Algorithms Library)

Publisher: CGAL

License: https://doc.cgal.org/latest/Manual/license.html

References: https://www.cgal.org

Highlights: 

• Mesh Downsize using edge collapse: https://doc.cgal.org/latest/Surface_mesh_simplification/index.html
• Mesh Downsize using approximation: https://doc.cgal.org/latest/Surface_mesh_approximation/index.html
• Polygon mesh processing (hole filling/refinement/remesh etc.) algorithms: https://doc.cgal.org/latest/Polygon_mesh_processing/index.html
• Skeleton extraction:  https://doc.cgal.org/latest/Surface_mesh_skeletonization/index.html
• List of available CGAL algorithms: https://doc.cgal.org/latest/Manual/packages.html

Platforms: Linux, Windows

3) CGAL 5.1 – Polygon Mesh Processing

Publisher: CGAL

Description: This package implements a collection of methods and classes for polygon mesh processing, ranging from basic operations on simplices to complex geometry processing algorithms. The implementation of this package mainly follows algorithms and references given in Botsch et al.’s book on polygon mesh processing

License: https://doc.cgal.org/latest/Manual/license.html

References: https://doc.cgal.org/latest/Polygon_mesh_processing/index.html#PMPIntroduction

Platforms: Linux, Windows

Highlights: 

• Meshing : meshing algorithms, including triangulation of non-triangulated meshes, refinement, optimization by fairing, isotropic remeshing of triangulated surface meshes and smoothing algorithms.

• Co-refinement and Boolean Operations : methods to corefine triangle meshes and to compute boolean operations out of corefined closed triangle meshes.

• Hole Filling : available hole filling algorithms, which can possibly be combined with refinement and fairing.

• Predicates : predicates that can be evaluated on the processed polygon. mesh, which includes point location and self intersection tests.

• Orientation : checking or fixing the orientation of a polygon soup.

• Combinatorial Repairing : repair of polygon meshes and polygon soups.

• Computing Normals : normal computation at vertices and on faces of a polygon mesh.

• Slicer : functor able to compute the intersections of a polygon mesh with arbitrary planes (slicer).

• Connected Components : methods to deal with connected components of a polygon mesh (extraction, marks, removal, …).

Platforms: Linux, Windows

4) Polygonica 

Publisher: Polygonica 

References: https://www.polygonica.com/

Highlights: 

• Mesh Healing – Fast and automatic repair of solid models and STL files

• Boolean Operations – Fast & accurate performance on Boolean algorithms

• Mesh Analysis – Complex algorithms for analysing polygon mesh

• Mesh Offsetting – Unique Boolean engine creating a solid offset

• Remeshing – Improved mesh quality and simplification by reducing triangle count

Platforms: Windows, Linux and Mac

5) MeshGems-CADSurf

Publisher: MeshGems

Description: The MeshGems-CADSurf component creates a surface mesh from a CAD definition, that can be defined either by composite parametric surfaces (analytical CAD) or discretized or faceted surfaces (STL-like geometries) while conforming to a prescribed size/shape/element description.

References: http://www.meshgems.com/surface-meshing-meshgems-cadsurf.html

Highlights: 

• Single Workflow for surface meshing from discrete or analytical CAD geometries

• CAD pre-processing performed: designed to enhance mesh generation on complex or dirty geometries

• No tolerance tuning required

• Can clean up very efficiently and fully automatically a lot of CAD artifacts

• Can enforce the CAD definition to allow periodic mesh generation or mesh matching

• Default option: can be deactivated

• Produces high quality very smooth and regular meshes

• Generates Triangle or Quadrangle dominant meshes

• Gradation control

• Anisotropic or isotropic curvature driven geometric meshes

• Precise size control on a global or local basis

• Works with manifold and non-manifold geometries

• Preserves the CAD associativity with the underlying CAD model

• 1D entities can be enforced

Platforms: Windows, Linux

6) MeshGems-SurfOpt

Publisher: MeshGems

Description: The MeshGems-SurfOpt component creates an isotropic or anisotropic surface mesh governed by both the geometric surface properties and an optional metric map from an arbitrary valid given surface triangulation

References: http://www.meshgems.com/mesh-processing-meshgems-surfopt.html

Highlights: 

• Fully automatic adaptive surface remeshing tool

• Mesh control options: gradation / « constant size » / anisotropic / curvature or user map driven

• Proximity detection of surfaces and surface structures

• Connex component selection

• Remeshing options:

• Coarsening, optimisation or « Flat » enrichment

• Finite element corrections and quadratic enrichment post-processing

• Mesh adaptation mode: sizes are considered nodal and not linear

• Sand papering of input surfaces

• Vertex coordinate preservation

• Geometry driving parameter

• Lightweight geometry driven remeshing (usually not suitable for computation)

• Ridge auto-detection based on angle: can be restricted to reference edges

• Required vertices, edges, or triangles may be specified

• Size control:

• Target for number of vertices can be set

• Adjustable maximum memory

• Several diagnostics and outputs available

Platforms: Windows, Linux

7) MeshGems-Adapt

Publisher: MeshGems

Description: MeshGems-Adapt is a fully automatic surface and volume adaptive mesh generator. MeshGems-Adapt creates an adapted surface (triangles) and/or the volume (tetrahedral) mesh from a background mesh which defines the size over the domain.

References: http://www.meshgems.com/mesh-adaptation-meshgems-adapt.html

Highlights: 

• MeshGems-Adapt Highlights

• Very reliable: creates correct meshes on the most complex industrial geometries without failure

• Isotropic or anisotropic mode available

• Background mesh for the size map can be any kind of mesh

Platforms: Windows, Linux

8) Open Mesh

Publisher: 

Description: OpenMesh is a generic and efficient data structure for representing and manipulating polygonal meshes. OpenMesh is a C++ library. Python bindings are also provided. On top of OpenMesh OpenFlipper is developed with a flexible geometry modeling and processing framework.

License: BSD 3 Clause: https://www.graphics.rwth-aachen.de/software/openmesh/license/

References: https://www.graphics.rwth-aachen.de/software/openmesh/

Highlights: 

• Representation of arbitrary polygonal (the general case) and pure triangle meshes (providing more efficient, specialized algorithms)

• Explicit representation of vertices, half edges, edges and faces.

• Fast neighborhood access, especially the one-ring neighborhood (see below).

• Highly customizable:

• Choose your coordinate type (dimension and scalar type)

• Attach user-defined elements/functions to the mesh elements.

• Attach and check for attributes.

• Attach data at runtime using dynamic properties.

• Mesh decimation

• Mesh smoothing

Platforms:

• Linux ( gcc and clang )

• Windows

• Microsoft Visual Studio 2015,2017

• MinGW

• MacOS X

9) Openflipper

Publisher: 

Description: OpenFlipper is an OpenSource multi-platform application and programming framework designed for processing, modeling and rendering of geometric data. Currently supported platforms are Windows, MacOS X and Linux. Using OpenMesh a variety of file formats are supported ( off, obj, ply, … ). Additionally OpenFlipper provides a highly flexible interface for creating and testing own geometry processing algorithms. A powerful scripting language can be used to access all parts of OpenFlipper and modify geometry or the user interface at runtime.

License: 3-Clause BSD

References: https://www.graphics.rwth-aachen.de/software/openflipper/

Highlights: 

• As described in the description

Platforms:

• Linux ( gcc, clang)
• Windows( Microsoft Visual Studio 2015,2017 )
• MacOS X (XCode )

10) Polygon Cruncher

Publisher: Mootools

Description: Polygon Cruncher is the 3D optimization software that takes place inside your 3D pipeline. Whether your activities are related to architecture, video games, CAD, 3D printing, or history (3D scan), Polygon Cruncher provides solutions for simplifying your 3D meshes. Can be used as SDK as well

License:  

• Per project licensing, globale license to a whole company.
• Source code licensing.
• Royalty based or global fee licensing.
• https://www.mootools.com/en/software/polygon-cruncher-sdk/licensing

References: 

• https://www.mootools.com/en/software/polygon-cruncher#sdk
• https://www.mootools.com/en/software/polygon-cruncher-sdk

Highlights:

• Polygon Cruncher optimization algorithm

• Reading and writing capabilities on most 3D file formats including (Fbx, Cinema 4D, 3ds, lxo, collada, wavefront, vrml, sketchup…)

• Scene hierarchy

• UVs, vertex colors, normals information

• Materials information

• A set of powerful 3D features such mesh cleaning, confused point welding, mesh collapsing based on materials or anything else…

• Very compact in term of memory needs, it also allows memory allocation callbacks

• LOD generation for JT files through Siemens JT SDK

Platforms: 

• for Windows with Visual Studio (2010 to 2017) in 64 bits.
• for MacOS with XCode.
• for Linux (Centos / gcc 4)

11) Clipper

Publisher: Angus Johnson.

Description: 

An open source freeware library for clipping and offsetting lines and polygons. The Clipper library performs line & polygon clipping – intersection, union, difference & exclusive-or, and line & polygon offsetting. The library is based on Vatti’s clipping algorithm.

License:  

• Freeware for both open source and commercial applications (Boost Software License)

References: http://www.angusj.com/delphi/clipper/documentation/Docs/Overview/_Body.htm

Highlights:

• it accepts all types of polygons including self-intersecting ones

• it supports multiple polygon filling rules (EvenOdd, NonZero, Positive, Negative)

• it’s very fast relative to other libraries

• it’s numerically robust

• it also performs line and polygon offsetting

• it’s free to use in both freeware and commercial applications

Platforms: 

• The download package contains the library’s full source code (written in Delphi, C++ and C#), numerous demos, a help file and links to third party Python, Perl, Ruby and Haskell modules

12) Okino’s  Polygon reduction

Publisher: Okino

Description: 

• The Okino polygon reduction system is a mechanism that can greatly reduce the number of polygons in one or more 3D objects of a scene without greatly sacrificing object quality. It is a vital polygon optimization tool of the Okino PolyTrans and NuGraf software packages, which is included for free as part of the base level Okino software packages
• If you are a Maya or 3ds Max user and wish to utilize the polygon reduction system, first export out an Okino .bdf file using the special PolyTrans-for-Maya or PolyTrans-for-3dsMax plug-in systems, load that file into the stand-alone PolyTrans or NuGraf programs, perform the reduction, re-save the Okino .bdf file and re-load it into Maya or 3ds Max. There will be no geometry data loss in the process
• If a 3D model has a sufficient number of polygons in it then typical reductions are 80% to 95% while retaining good visual fidelity. The Okino polygon reduction algorithm implementation is based on the quadric error metrics (QEM) technique. This technique tries to retain the quality and appearance of the original model while reducing the overall number of polygons

References: 

• https://www.okino.com/conv/polygon_reduction/geoman2/polygon_reduction.htm

13) PyMesh

Publisher: Qingnan Zhou

Description: 

• Read/write 2D and 3D mesh in .obj, .off, .ply, .stl, .mesh (MEDIT), .msh (Gmsh) and .node/.face/.ele (Tetgen) formats.

• Support load and save per-vertex/face/voxel scalar and vector fields.

• Local mesh processing such edge collapse/split, duplicated vertex/face removal etc.

• Mesh boolean support from CGAL, Cork, Carve, Clipper (2D only) and libigl.

• Mesh generation support from CGAL, Triangle, TetGen and Quartet.

• Wire network and inflation of wire networks.

• Finite element matrix assembly. (supports Laplacian, stiffness, mass, etc.)

References: 

• https://pymesh.readthedocs.io/en/latest/index.html

How can ProtoTech help?

If you are looking for services and experts in mesh capabilities, feel free to contact us. We have decades of staff years of experience in developing software around meshes. We are experienced in integrating toolkits available in the market and also developing our own algorithms. We can help you get the right solution, suitable to your scale, time, and budget.

Mesh optimization toolkits,Mesh repair toolkits,Mesh optimization methods,Simplify Mesh for BIM