[ft-devel] [PATCH 1/2] Improve FT_Outline_Embolden for the unintended arfifacts problem (#45597).

[Byeongsik Jeon]

FreeType-Bugs: https://savannah.nongnu.org/bugs/?45596
---
 src/base/ftoutln.c | 172 +++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 172 insertions(+)

diff --git a/src/base/ftoutln.c b/src/base/ftoutln.c
index 85a469737..97d6f2c08 100644
--- a/src/base/ftoutln.c
+++ b/src/base/ftoutln.c
@@ -892,6 +892,7 @@
    /* documentation is in ftoutln.h */
 +#if 0
   FT_EXPORT_DEF( FT_Error )
   FT_Outline_EmboldenXY( FT_Outline*  outline,
                          FT_Pos       xstrength,
@@ -1023,7 +1024,178 @@
      return FT_Err_Ok;
   }
+#endif
+
+
+  /*
+    --->----------------->------------>-----------> shift
+                A            /|\                  /
+                          di  |                  /
+                              |                 /
+                              |                /
+   ->------------>-----------> ----   do      /
+                     in      /     -----     /
+                            /           --->/
+                           /               /
+                      out /               /
+                         /               /
+                        /             B /
+                       /               /
+                      /               /
+                    |/_             |/_
+
+  assume one strength:
+    ( strength.x, strength.y ) = ( strength, strength )
+
+  normalized vector i, o :
+    i =  in /  |in| = ( i.x, i.y ) , i.x ^2 + i.y ^2 = 1
+    o = out / |out| = ( o.x, o.y ) , o.x ^2 + o.y ^2 = 1
+
+  vector di, do :
+    -90 degree rotate(truetype outline) from in, out vector.
+    and scale to strength.  |di| = |do| = strength.
+
+    di = ( -i.y * strength, i.x * strength )
+    do = ( -o.y * strength, o.x * strength )
+
+  line equation of A, B:
+    i.y * ( x - di.x ) = i.x * ( y - di.y )
+    o.y * ( x - do.x ) = o.x * ( y - do.y )
+
+  intersection of A, B == shift.
+
+  two coalition equation solution:
+    det = i.y * o.x - i.x * o.y , det != 0
+    shift.x = strength * ( i.x - o.x ) / det
+    shift.y = strength * ( i.y - o.y ) / det
+
+  two strength case:
+    introduced equation with a reasonable radical attempt.
+
+    det = i.y * o.x - i.x * o.y  , det != 0
+    shift.x = strength.x * ( i.x - o.x ) / det
+    shift.y = strength.y * ( i.y - o.y ) / det
+
+    This simple expression produces good results.
+    There is a more rigorous expression, but it is more complicated.
+
+  For postscript outline: ( -shift.x, -shift.y )
+
+  det == 0 case:
+     i.x == i.y == 0, or
+     o.x == o.y == 0, or
+     abs( gradient i ) == abs( gradient o )
+
+   */
+
+  FT_EXPORT_DEF( FT_Error )
+  FT_Outline_EmboldenXY( FT_Outline* outline,
+                         FT_Pos      xstrength,
+                         FT_Pos      ystrength )
+  {
+    FT_Vector*      points;
+    FT_Orientation  orientation;
+    FT_Vector       strength, shift, in, out, anchor;
+    FT_Int          c, n_first, n_last, n_head, n_prev, n_tail, n_anchor;
+    FT_Fixed        det;
+
+    if ( !outline ) return FT_THROW( Invalid_Outline );
+
+    strength.x = xstrength / 2;
+    strength.y = ystrength / 2;
+    if ( strength.x == 0 && strength.y == 0 ) return FT_Err_Ok;
+
+    orientation = FT_Outline_Get_Orientation( outline );
+    if ( orientation == FT_ORIENTATION_NONE )
+    {
+      if ( outline->n_contours ) return FT_THROW( Invalid_Argument );
+      else return FT_Err_Ok;
+    }
+
+    points = outline->points;
 +    for ( c = n_first = 0; c < outline->n_contours; c++, n_first = n_last + 1 
)
+    {
+      n_prev = n_last = outline->contours[c];
+      n_anchor = n_tail = -1;
+      in.x = in.y = anchor.x = anchor.y = 0;
+
+      /* Find the first corner type segment */
+      for ( n_head = n_first; n_head <= n_last; n_head++)
+      {
+        out.x = points[n_head].x - points[n_prev].x;
+        out.y = points[n_head].y - points[n_prev].y;
+        FT_Vector_NormLen( &out ); /* normalize */
+
+        det = FT_MulFix( in.y, out.x ) - FT_MulFix( in.x, out.y );
+        if ( det != 0 )
+        {
+          anchor = in = out;
+          n_anchor = n_tail = n_head;
+          break;
+        }
+
+        in = out;
+        n_prev = n_head;
+      }
+      if ( n_anchor == -1 ) continue;
+
+      do
+      {
+        n_prev = n_head;
+        n_head = ( n_head < n_last )? n_head + 1 : n_first;
+        if ( n_head != n_anchor )
+        {
+          out.x = points[n_head].x - points[n_prev].x;
+          out.y = points[n_head].y - points[n_prev].y;
+          FT_Vector_NormLen( &out ); /* normalize */
+        }
+        else
+          out = anchor;
+
+        /* The shift vector is only calculated from the corner type segment.
+           Other points -- zero length segment, forward straight segment,
+           wrong forward and backward mixed straight segment -- use this
+           shift vector as it is. Note the "in.x * out.y - in.y * out.x".
+
+           wrong forward and backward mixed straight segment:
+             one of the causes of unintended artifact generation.
+         */
+        det = FT_MulFix( in.y, out.x ) - FT_MulFix( in.x, out.y );
+        if ( det == 0 ) continue;
+
+        shift.x = FT_MulDiv( strength.x, in.x - out.x, det );
+        shift.y = FT_MulDiv( strength.y, in.y - out.y, det );
+
+        /* The large shift value creates a cross point, which appears
+           as one of the artifacts. The shift value limitation inhibits
+           the occurrence of artifacts. */
+        shift.x = FT_MAX( FT_MIN( shift.x, strength.x ), -strength.x );
+        shift.y = FT_MAX( FT_MIN( shift.y, strength.y ), -strength.y );
+
+        if ( orientation != FT_ORIENTATION_TRUETYPE )
+        {
+          shift.x = -shift.x;
+          shift.y = -shift.y;
+        }
+
+        while ( n_tail != n_head )
+        {
+          /* left and bottom side are unchanged.
+             grid aligned when using integer pixel {x,y}strength. */
+          points[n_tail].x += strength.x + shift.x;
+          points[n_tail].y += strength.y + shift.y;
+
+          n_tail = ( n_tail < n_last )? n_tail + 1 : n_first;
+        }
+
+        in = out;
+
+      } while ( n_head != n_anchor );
+    }
+
+    return FT_Err_Ok;
+  }
    /* documentation is in ftoutln.h */
 -- 2.19.0