[freetype2] master 2ea511e: [smooth] Simplify cubic Bézier flattening.

[Alexei Podtelezhnikov]

branch: master
commit 2ea511eed81770f423544525adebf7f954b8be93
Author: Alexei Podtelezhnikov <address@hidden>
Commit: Alexei Podtelezhnikov <address@hidden>

    [smooth] Simplify cubic Bézier flattening.
    
    The previous implementation is correct but it is too complex.
    The revised algorithm is based on the fact that each split moves
    the control points closer to the trisection points on the chord.
    The corresponding distances are good surrogates for the curve
    deviation from the straight line.
    
    This cubic flattening algorithm is somewhat similar to the conic
    algorithm based the distance from the control point to the middle of
    the chord.  The cubic distances, however, decrease less predictably
    but are easy enough to calculate on each step.
    
    * src/smooth/ftgrays.c (gray_render_cubic): Replace the split
    condition.
---
 ChangeLog            | 18 ++++++++++++++++++
 src/smooth/ftgrays.c | 49 +++++++------------------------------------------
 2 files changed, 25 insertions(+), 42 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index dd9f48c..1efd28a 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,21 @@
+2019-04-29  Alexei Podtelezhnikov  <address@hidden>
+
+       [smooth] Simplify cubic Bézier flattening.
+
+       The previous implementation is correct but it is too complex.
+       The revised algorithm is based on the fact that each split moves
+       the control points closer to the trisection points on the chord.
+       The corresponding distances are good surrogates for the curve
+       deviation from the straight line.
+
+       This cubic flattening algorithm is somewhat similar to the conic
+       algorithm based the distance from the control point to the middle of
+       the chord.  The cubic distances, however, decrease less predictably
+       but are easy enough to calculate on each step.
+
+       * src/smooth/ftgrays.c (gray_render_cubic): Replace the split
+       condition.
+
 2019-04-26  Alexei Podtelezhnikov  <address@hidden>
 
        [smooth] Bithacks and cosmetics.
diff --git a/src/smooth/ftgrays.c b/src/smooth/ftgrays.c
index b421fc8..72ab546 100644
--- a/src/smooth/ftgrays.c
+++ b/src/smooth/ftgrays.c
@@ -1093,9 +1093,6 @@ typedef ptrdiff_t  FT_PtrDist;
   {
     FT_Vector   bez_stack[16 * 3 + 1];  /* enough to accommodate bisections */
     FT_Vector*  arc = bez_stack;
-    TPos        dx, dy, dx_, dy_;
-    TPos        dx1, dy1, dx2, dy2;
-    TPos        L, s, s_limit;
 
 
     arc[0].x = UPSCALE( to->x );
@@ -1124,45 +1121,13 @@ typedef ptrdiff_t  FT_PtrDist;
 
     for (;;)
     {
-      /* Decide whether to split or draw. See `Rapid Termination          */
-      /* Evaluation for Recursive Subdivision of Bezier Curves' by Thomas */
-      /* F. Hain, at                                                      */
-      /* 
http://www.cis.southalabama.edu/~hain/general/Publications/Bezier/Camera-ready%20CISST02%202.pdf
 */
-
-      /* dx and dy are x and y components of the P0-P3 chord vector. */
-      dx = dx_ = arc[3].x - arc[0].x;
-      dy = dy_ = arc[3].y - arc[0].y;
-
-      L = FT_HYPOT( dx_, dy_ );
-
-      /* Avoid possible arithmetic overflow below by splitting. */
-      if ( L > 32767 )
-        goto Split;
-
-      /* Max deviation may be as much as (s/L) * 3/4 (if Hain's v = 1). */
-      s_limit = L * (TPos)( ONE_PIXEL / 6 );
-
-      /* s is L * the perpendicular distance from P1 to the line P0-P3. */
-      dx1 = arc[1].x - arc[0].x;
-      dy1 = arc[1].y - arc[0].y;
-      s = FT_ABS( SUB_LONG( MUL_LONG( dy, dx1 ), MUL_LONG( dx, dy1 ) ) );
-
-      if ( s > s_limit )
-        goto Split;
-
-      /* s is L * the perpendicular distance from P2 to the line P0-P3. */
-      dx2 = arc[2].x - arc[0].x;
-      dy2 = arc[2].y - arc[0].y;
-      s = FT_ABS( SUB_LONG( MUL_LONG( dy, dx2 ), MUL_LONG( dx, dy2 ) ) );
-
-      if ( s > s_limit )
-        goto Split;
-
-      /* Split super curvy segments where the off points are so far
-         from the chord that the angles P0-P1-P3 or P0-P2-P3 become
-         acute as detected by appropriate dot products. */
-      if ( dx1 * ( dx1 - dx ) + dy1 * ( dy1 - dy ) > 0 ||
-           dx2 * ( dx2 - dx ) + dy2 * ( dy2 - dy ) > 0 )
+      /* with each split, control points quickly converge towards  */
+      /* chord trisection points and the vanishing distances below */
+      /* indicate when the segment is flat enough to draw          */
+      if ( FT_ABS( 2 * arc[0].x - 3 * arc[1].x + arc[3].x ) > ONE_PIXEL / 2 ||
+           FT_ABS( 2 * arc[0].y - 3 * arc[1].y + arc[3].y ) > ONE_PIXEL / 2 ||
+           FT_ABS( arc[0].x - 3 * arc[2].x + 2 * arc[3].x ) > ONE_PIXEL / 2 ||
+           FT_ABS( arc[0].y - 3 * arc[2].y + 2 * arc[3].y ) > ONE_PIXEL / 2 )
         goto Split;
 
       gray_render_line( RAS_VAR_ arc[0].x, arc[0].y );