[Git][freetype/freetype][master] 3 commits: [raster] Instantly remove pr

Alexei Podtelezhnikov pushed to branch master at FreeType / FreeType

Commits:

046c4fc7

by Alexei Podtelezhnikov (Алексей Подтележников) at 2023-11-03T22:34:37-04:00

[raster] Instantly remove profiles from linked lists.

* src/raster/ftraster.c (DelOld): Remove loopy function.
(Draw_Sweep): Implement instant profile removal.

32081d81

by Alexei Podtelezhnikov (Алексей Подтележников) at 2023-11-03T23:10:41-04:00

[raster] Consolidate profile increment to the next line.

* src/raster/ftraster.c (s/Sort/Increment): Rename this function to
reflect its true purpose, delete exhausted profiles here...
(Draw_Sweep): ... instead of here.

9e86fb80

by Alexei Podtelezhnikov (Алексей Подтележников) at 2023-11-03T23:59:05-04:00

[raster] Improve profile accounting during sweeping.

* src/raster/ftraster.c (TProfile): Get rid of `countL`.
(Draw_Sweep): Use `start` for countdown to activation.
(Horizontal_Sweep_Drop, Vertical_Sweep_Drop): Rely on `height` and
`offset` to verify profile ends for the stub detection.

1 changed file:

src/raster/ftraster.c

Changes:

src/raster/ftraster.c

@@ -340,14 +340,13 @@
                               /* during drop-out control                  */
      Int         offset;      /* bottom or currently scanned array index  */
      Int         height;      /* profile's height in scanlines            */
 -    Int         start;       /* profile's starting scanline              */
 +    Int         start;       /* profile's starting scanline, also use    */
 +                             /* as activation counter                    */
      UShort      flags;       /* Bit 0-2: drop-out mode                   */
                               /* Bit 3: profile orientation (up/down)     */
                               /* Bit 4: is top profile?                   */
                               /* Bit 5: is bottom profile?                */
 -    Int         countL;      /* number of lines to step before this      */
 -                             /* profile becomes drawable                 */
      FT_F26Dot6  X;           /* current coordinate during sweep          */
      Long        x[1];        /* actually variable array of scanline      */
                               /* intersections with `height` elements     */
@@ -2019,59 +2018,32 @@
    /**************************************************************************
+    *
 -   * DelOld
 +   * Increment
+    *
 -   *   Removes an old profile from a linked list.
 +   *   Advances all profile in the list to the next scanline.  It also
 +   *   sorts the trace list in the unlikely case of profile crossing.
 +   *   In 95%, the list is already sorted.  We need an algorithm which
 +   *   is fast in this case.  Bubble sort is enough and simple.
     */
    static void
 -  DelOld( PProfileList    list,
 -          const PProfile  profile )
 -  {
 -    PProfile  *old, current;
+-
+-
 -    old     = list;
 -    current = *old;
+-
 -    while ( current )
 -    {
 -      if ( current == profile )
 -      {
 -        *old = current->link;
 -        return;
 -      }
+-
 -      old     = &current->link;
 -      current = *old;
 -    }
+-
 -    /* we should never get there, unless the profile was not part of */
 -    /* the list.                                                     */
 -  }
+-
+-
 -  /**************************************************************************
 -   *
 -   * Sort
 -   *
 -   *   Sorts a trace list.  In 95%, the list is already sorted.  We need
 -   *   an algorithm which is fast in this case.  Bubble sort is enough
 -   *   and simple.
 -   */
 -  static void
 -  Sort( PProfileList  list )
 +  Increment( PProfileList  list )
+   {
      PProfile  *old, current, next;
 -    /* First, set the new X coordinate of each profile */
 -    current = *list;
 -    while ( current )
 +    /* First, set the new X coordinates and remove exhausted profiles */
 +    old = list;
 +    while ( *old )
+     {
 -      current->X       = current->x[current->offset];
 -      current->offset += ( current->flags & Flow_Up ) ? 1 : -1;
 -      current->height--;
 -      current = current->link;
 +      current = *old;
 +      if ( --current->height )
 +      {
 +        current->offset += ( current->flags & Flow_Up ) ? 1 : -1;
 +        current->X       = current->x[current->offset];
 +        old = &current->link;
 +      }
 +      else
 +        *old = current->link;  /* remove */
+     }
      /* Then sort them */
@@ -2203,6 +2175,8 @@
      Long  e1, e2, pxl;
      Int   c1, f1;
 +    FT_UNUSED( y );
++
      FT_TRACE7(( "  y=%d x=[% .*f;% .*f]",
                  y,
@@ -2284,14 +2258,14 @@
            /* upper stub test */
            if ( left->next == right                &&
 -               left->height <= 0                  &&
 +               left->height == 1                  &&
                 !( left->flags & Overshoot_Top   &&
                    x2 - x1 >= ras.precision_half ) )
              goto Exit;
            /* lower stub test */
            if ( right->next == left                 &&
 -               left->start == y                    &&
 +               left->offset == 0                   &&
                 !( left->flags & Overshoot_Bottom &&
                    x2 - x1 >= ras.precision_half  ) )
              goto Exit;
@@ -2502,14 +2476,14 @@
            /* rightmost stub test */
            if ( left->next == right                &&
 -               left->height <= 0                  &&
 +               left->height == 1                  &&
                 !( left->flags & Overshoot_Top   &&
                    x2 - x1 >= ras.precision_half ) )
              goto Exit;
            /* leftmost stub test */
            if ( right->next == left                 &&
 -               left->start == y                    &&
 +               left->offset == 0                   &&
                 !( left->flags & Overshoot_Bottom &&
                    x2 - x1 >= ras.precision_half  ) )
              goto Exit;
@@ -2589,7 +2563,7 @@
      Int           min_Y, max_Y, dropouts;
      Int           y, y_change, y_height;
 -    PProfile      P, Q, P_Left, P_Right;
 +    PProfile      *Q, P, P_Left, P_Right;
      TProfileList  waiting    = ras.fProfile;
      TProfileList  draw_left  = NULL;
@@ -2610,7 +2584,7 @@
      P = waiting;
      while ( P )
+     {
 -      P->countL = P->start - min_Y;
 +      P->start -= min_Y;
        P->X      = P->x[P->offset];
        P = P->link;
@@ -2625,34 +2599,28 @@
+     {
        /* check waiting list for new profile activations */
 -      P = waiting;
+-
 -      while ( P )
 +      Q = &waiting;
 +      while ( *Q )
+       {
 -        Q = P->link;
 -        P->countL -= y_height;
 -        if ( P->countL == 0 )
 +        P = *Q;
 +        P->start -= y_height;
 +        if ( P->start == 0 )
+         {
 -          DelOld( &waiting, P );
 +          *Q = P->link;  /* remove */
            if ( P->flags & Flow_Up )
              InsNew( &draw_left,  P );
            else
              InsNew( &draw_right, P );
+         }
+-
 -        P = Q;
 +        else
 +          Q = &P->link;
+       }
 -      /* sort the drawing lists */
+-
 -      Sort( &draw_left );
 -      Sort( &draw_right );
+-
        y_change = (Int)*ras.maxBuff;
        y_height = y_change - y;
 -      while ( y < y_change )
 +      do
+       {
          /* let's trace */
@@ -2687,7 +2655,7 @@
                P_Right->X = x2;
                /* mark profile for drop-out processing */
 -              P_Left->countL = 1;
 +              P_Left->start = -1;
                dropouts++;
+             }
+           }
@@ -2708,34 +2676,10 @@
          ras.Proc_Sweep_Step( RAS_VAR );
 -        y++;
+-
 -        if ( y < y_change )
 -        {
 -          Sort( &draw_left  );
 -          Sort( &draw_right );
 -        }
 -      }
+-
 -      /* remove exhausted profiles */
+-
 -      P = draw_left;
 -      while ( P )
 -      {
 -        Q = P->link;
 -        if ( P->height == 0 )
 -          DelOld( &draw_left, P );
 -        P = Q;
 -      }
+-
 -      P = draw_right;
 -      while ( P )
 -      {
 -        Q = P->link;
 -        if ( P->height == 0 )
 -          DelOld( &draw_right, P );
 -        P = Q;
 +        Increment( &draw_left  );
 +        Increment( &draw_right );
+       }
 +      while ( ++y < y_change );
+     }
      return SUCCESS;
@@ -2747,9 +2691,9 @@
      while ( P_Left && P_Right )
+     {
 -      if ( P_Left->countL )
 +      if ( P_Left->start )
+       {
 -        P_Left->countL = 0;
 +        P_Left->start = 0;
  #if 0
          dropouts--;  /* -- this is useful when debugging only */
  #endif

From:	Alexei Podtelezhnikov (@apodtele)
Subject:	[Git][freetype/freetype][master] 3 commits: [raster] Instantly remove profiles from linked lists.
Date:	Sat, 04 Nov 2023 04:06:20 +0000