Mesh smoothing

[lemmih]

Many morphing algorithms rely on deconstructing polygons into triangles (aka triangulation). However, not all triangles are created equal and there's a lower angle limit where the algorithms break down. Floating point trigonometry is never exact and with long, skinny triangles, the noise drown out the signal.

Below are examples of the same algorithm trying to morph an 'S' into a 'C'. In the first GIF, polygon count is low, the triangles are reasonably sized, and the morphing works as intended. In the second GIF, there are a lot more triangles and they are much skinnier, leading to numerical problems and a jerky morph.

These numerical problems can be avoided by smoothing the mesh inside of the polygon.

Tasks necessary for mesh smoothing:

• Half-edge data structure.
• Half-edge convenience functions:
  • Splitting edges.
  • Moving nodes.
  • Flipping edges.
• Metrics:
  • Average angle.
  • Minimum angle.
  • Angle ratio.
  • Length ratio.
• Mesh smoothing:
  • Laplacian.
  • Angle-based.
  • Delaunay edge-flips.
  • Edge splitting.

[lemmih]

Raw mesh on the left, smoothed mesh on the right: