[freetype2] adjust 1c0ab1680 5/7: [autofit] Add tilde-unflattening algorithm.

[Werner Lemberg]

branch: adjust
commit 1c0ab1680c6ac92f748023a2bce20bbf52a37de2
Author: Craig White <gerzytet@gmail.com>
Commit: Werner Lemberg <wl@gnu.org>

    [autofit] Add tilde-unflattening algorithm.
    
    * src/autofit/aflatin.c (af_find_highest_contour,
    af_remove_segments_containing_point,
    af_latin_remove_tilde_points_from_edges, af_latin_stretch_tildes): New
    functions.
    (af_latin_hints_apply): Call tilde-unflatting code if necessary.
---
 src/autofit/aflatin.c | 240 ++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 240 insertions(+)

diff --git a/src/autofit/aflatin.c b/src/autofit/aflatin.c
index 91d369f40..464d7aabe 100644
--- a/src/autofit/aflatin.c
+++ b/src/autofit/aflatin.c
@@ -2777,6 +2777,236 @@
   }
 
 
+  static FT_Int
+  af_find_highest_contour( AF_GlyphHints  hints )
+  {
+    FT_Int  highest_contour = -1;
+
+    FT_Pos  highest_min_y = 0;
+    FT_Pos  current_min_y = 0;
+
+    FT_Int  contour;
+
+
+    for ( contour = 0; contour < hints->num_contours; contour++ )
+    {
+      AF_Point  point       = hints->contours[contour];
+      AF_Point  first_point = point;
+
+
+      if ( !point )
+        continue;
+
+      current_min_y = point->y;
+
+      do
+      {
+        if ( point->y < current_min_y )
+          current_min_y = point->y;
+        point = point->next;
+
+      } while ( point != first_point );
+
+      if ( highest_contour == -1 || current_min_y > highest_min_y )
+      {
+        highest_min_y   = current_min_y;
+        highest_contour = contour;
+      }
+    }
+
+    return highest_contour;
+  }
+
+
+  static void
+  af_remove_segments_containing_point( AF_GlyphHints  hints,
+                                       AF_Point       point )
+  {
+    AF_AxisHints  axis     = &hints->axis[AF_DIMENSION_VERT];
+    AF_Segment    segments = axis->segments;
+
+    FT_UInt  i;
+
+
+    for ( i = 0; i < axis->num_segments; i++ )
+    {
+      AF_Segment  seg = &segments[i];
+      AF_Point    p   = seg->first;
+
+      FT_Bool  remove = 0;
+
+
+      while ( 1 )
+      {
+        if ( p == point )
+        {
+          remove = 1;
+          break;
+        }
+
+        if ( p == seg->last )
+          break;
+
+        p = p->next;
+      }
+
+      if ( remove )
+      {
+        /* First, check the first and last segment of the edge. */
+        AF_Edge  edge = seg->edge;
+
+
+        if ( edge->first == seg && edge->last == seg )
+        {
+          /* The edge only consists of the segment to be removed. */
+          /* Remove the edge.                                     */
+          *edge = axis->edges[--axis->num_edges];
+        }
+        else
+        {
+          if ( edge->first == seg )
+            edge->first = seg->edge_next;
+
+          if ( edge->last == seg )
+          {
+            edge->last = edge->first;
+
+            while ( edge->last->edge_next != seg )
+              edge->last = edge->last->edge_next;
+          }
+        }
+
+        /* Now, delete the segment. */
+        *seg = axis->segments[--axis->num_segments];
+
+        i--; /* We have to check the new segment at this position. */
+      }
+    }
+  }
+
+
+  /* Remove all segments containing points on the tilde contour. */
+  static void
+  af_latin_remove_tilde_points_from_edges( AF_GlyphHints  hints )
+  {
+    FT_Int    highest_contour = af_find_highest_contour( hints );
+    AF_Point  first_point     = hints->contours[highest_contour];
+
+    AF_Point  p = first_point;
+
+
+    do
+    {
+      p = p->next;
+      af_remove_segments_containing_point( hints, p );
+
+    } while ( p != first_point );
+  }
+
+
+  /*
+    The tilde-unflattening algorithm sometimes goes too far and makes an
+    unusually high tilde, where decreasing the ppem will increase the height
+    instead of a steady decrease in height as less pixels are used.
+
+    For example, the 'n tilde' glyph from 'Times New Roman', with forced
+    autofitting on, exhibits this behaviour in the font size range 16.5 to
+    18 ppem.
+  */
+  static void
+  af_latin_stretch_tildes( AF_GlyphHints  hints )
+  {
+    FT_Int    highest_contour = af_find_highest_contour( hints );
+    AF_Point  p               = hints->contours[highest_contour];
+
+    AF_Point  first_point = p;
+
+    FT_Pos    min_y, max_y;
+    FT_Short  min_fy, max_fy;
+
+    FT_Pos  min_measurement;
+
+    FT_Pos  height;
+    FT_Pos  target_height;
+
+
+    min_y  = max_y  = p->y;
+    min_fy = max_fy = p->fy;
+
+    do
+    {
+      p = p->next;
+
+      if ( p->y < min_y )
+        min_y = p->y;
+      if ( p->y > max_y )
+        max_y = p->y;
+
+      if ( p->fy < min_fy )
+        min_fy = p->fy;
+      if ( p->fy > max_fy )
+        max_fy = p->fy;
+
+    } while ( p != first_point );
+
+    min_measurement = 32000;
+    do
+    {
+      p = p->next;
+
+      if ( !( p->flags & AF_FLAG_CONTROL )          &&
+           p->prev->y == p->y && p->next->y == p->y &&
+           p->y != min_y && p->y != max_y           &&
+           p->prev->flags & AF_FLAG_CONTROL         &&
+           p->next->flags & AF_FLAG_CONTROL         )
+      {
+        /* This point could be a candidate.  Find the next and previous */
+        /* on-curve points, and make sure they are both either above or */
+        /* below the point, then make the measurement.                  */
+        AF_Point  prevOn = p->prev;
+        AF_Point  nextOn = p->next;
+
+        FT_Pos  measurement;
+
+
+        while ( prevOn->flags & AF_FLAG_CONTROL )
+          prevOn = prevOn->prev;
+        while ( nextOn->flags & AF_FLAG_CONTROL )
+          nextOn = nextOn->next;
+
+        if ( nextOn->y > p->y && prevOn->y > p->y )
+          measurement = p->y - min_y;
+        else if ( nextOn->y < p->y && prevOn->y < p->y )
+          measurement = max_y - p->y;
+        else
+          continue;
+
+        if ( measurement < min_measurement )
+          min_measurement = measurement;
+      }
+    } while ( p != first_point );
+
+    height        = max_y - min_y;
+    target_height = min_measurement + 64;
+
+    if ( height >= target_height )
+      return;
+
+    p = first_point;
+    do
+    {
+      p     = p->next;
+      p->y  = ( ( p->y - min_y ) * target_height / height ) + min_y;
+      p->fy = ( ( p->fy - min_fy ) * target_height / height ) + min_fy;
+      p->oy = p->y;
+
+      if ( !( p->flags & AF_FLAG_CONTROL ) )
+        p->flags |= AF_FLAG_TOUCH_Y;
+
+    } while ( p != first_point );
+  }
+
+
   /* Return 1 if the given contour overlaps horizontally with the bounding */
   /* box of all other contours combined.  This is a helper for function    */
   /* `af_glyph_hints_apply_vertical_separation_adjustments`.               */
@@ -3895,11 +4125,21 @@
 
     if ( AF_HINTS_DO_VERTICAL( hints ) )
     {
+      FT_Bool  is_tilde = af_lookup_tilde_correction_type(
+                            metrics->root.reverse_charmap, glyph_index );
+
+
+      if ( is_tilde )
+        af_latin_stretch_tildes( hints );
+
       axis  = &metrics->axis[AF_DIMENSION_VERT];
       error = af_latin_hints_detect_features( hints,
                                               axis->width_count,
                                               axis->widths,
                                               AF_DIMENSION_VERT );
+      if ( is_tilde )
+        af_latin_remove_tilde_points_from_edges( hints );
+
       if ( error )
         goto Exit;