[cairo] Survey of polygon rasterization techniques

Jeff Muizelaar jeff at infidigm.net
Thu Aug 9 18:28:29 PDT 2007


David,

I tried out a modification to tor8 where we use a linked list instead of
an array for storing the coverage values. I did this to pull some of the
time out of the gray_blit() function. It accomplished that as shown by
the results below. It (tor8x8_9) is slower for small sizes (100) and
faster for large sizes (600). I've attached a patch that implements it,
though it isn't the cleanest work.

./ftrasters -r8 -s100 /usr/share/fonts/truetype/ttf-dejavu/DejaVuSans.ttf

loading 3609 glyphs  = 0.040000 s
rasterizer                  time        throughput             global  relative
================================================================================
with dummy                :    0.100 s  (  288720 glyphs/s)
with analytical           :    1.490 s  (   19377 glyphs/s)    x 1.00  x 1.00
with mono1                :    0.530 s  (   54475 glyphs/s)    x 0.36  x 0.31
with tor15x17_8           :    3.210 s  (    8994 glyphs/s)    x 2.15  x 2.24
with tor16x16_8           :    3.240 s  (    8911 glyphs/s)    x 2.17  x 2.26
with tor16x16_7           :    3.590 s  (    8042 glyphs/s)    x 2.41  x 2.51
with kiia32_7             :    2.800 s  (   10311 glyphs/s)    x 1.88  x 1.94
with tor8x32_8            :    2.110 s  (   13683 glyphs/s)    x 1.42  x 1.45
with tor8x8_8             :    2.110 s  (   13683 glyphs/s)    x 1.42  x 1.45
with tor8x8_9             :    2.470 s  (   11689 glyphs/s)    x 1.66  x 1.71
with kiia16_7             :    1.870 s  (   15439 glyphs/s)    x 1.26  x 1.27
with kiia8_7              :    1.390 s  (   20771 glyphs/s)    x 0.93  x 0.93

./ftrasters -r3 -s600 /usr/share/fonts/truetype/ttf-dejavu/DejaVuSans.ttf

loading 3609 glyphs  = 0.040000 s
rasterizer                  time        throughput             global  relative
================================================================================
with dummy                :    0.170 s  (   63688 glyphs/s)
with analytical           :    4.320 s  (    2506 glyphs/s)    x 1.00  x 1.00
with mono1                :    1.950 s  (    5552 glyphs/s)    x 0.45  x 0.43
with tor15x17_8           :    9.010 s  (    1201 glyphs/s)    x 2.09  x 2.13
with tor16x16_8           :    9.590 s  (    1128 glyphs/s)    x 2.22  x 2.27
with tor16x16_7           :   10.310 s  (    1050 glyphs/s)    x 2.39  x 2.44
with kiia32_7             :    8.160 s  (    1326 glyphs/s)    x 1.89  x 1.93
with tor8x32_8            :    6.940 s  (    1560 glyphs/s)    x 1.61  x 1.63
with tor8x8_8             :    6.930 s  (    1562 glyphs/s)    x 1.60  x 1.63
with tor8x8_9             :    6.210 s  (    1743 glyphs/s)    x 1.44  x 1.46
with kiia16_7             :    5.910 s  (    1831 glyphs/s)    x 1.37  x 1.38
with kiia8_7              :    4.940 s  (    2191 glyphs/s)    x 1.14  x 1.15

-Jeff
-------------- next part --------------
diff --git a/Makefile b/Makefile
index b3405ed..68369ab 100644
--- a/Makefile
+++ b/Makefile
@@ -15,7 +15,7 @@ RASTERS := dummy mono1 analytical \
            kiia32_1 kiia32_2 kiia32_3 kiia32_4 kiia32_5 kiia32_6 kiia32_7 \
            kiia16_7 kiia8_7 \
            tor15x17_1 tor15x17_2 tor15x17_3 tor15x17_4 tor15x17_5 tor15x17_6 tor15x17_7 tor15x17_8\
-           tor16x16_7 tor16x16_8 tor8x8_7 tor8x32_7 tor8x8_8 tor8x32_8 \
+           tor16x16_7 tor16x16_8 tor8x8_7 tor8x32_7 tor8x8_8 tor8x32_8 tor8x8_9 \
 
 PROGRAM := ftrasters
 
diff --git a/ftgrays_tor9.h b/ftgrays_tor9.h
new file mode 100644
index 0000000..009d2bf
--- /dev/null
+++ b/ftgrays_tor9.h
@@ -0,0 +1,910 @@
+/***************************************************************************/
+/*                                                                         */
+/*  ftgrays_tor9.c                                                         */
+/*                                                                         */
+/*    An anti-aliasing rendered based on the Apparition library.           */
+/*    inspiration for this code can be found at:                           */
+/*                                                                         */
+/*    http://ccxvii.net/repos/fitz-stable/raster/pathscan.c                */
+/*                                                                         */
+/*    like ftgrays_tor8, with a linked list instead of an array for        */
+/*    coverage                                                             */
+/*                                                                         */
+/*  Copyright 2007 David Turner                                            */
+/*                                                                         */
+/*  This file is part of the FreeType project, and may only be used,       */
+/*  modified, and distributed under the terms of the FreeType project      */
+/*  license, LICENSE.TXT.  By continuing to use, modify, or distribute     */
+/*  this file you indicate that you have read the license and              */
+/*  understand and accept it fully.                                        */
+/*                                                                         */
+/***************************************************************************/
+
+#define  PIXEL_BITS  6
+#include "ftgrays_common.h"
+#include <assert.h>
+//#define dprintf(a, ...) printf(a, ## __VA_ARGS__)
+#define dprintf(a, ...)
+
+
+  /*************************************************************************/
+  /*                                                                       */
+  /*   TYPE DEFINITIONS                                                    */
+  /*                                                                       */
+
+#ifndef GRID_X
+#error GRID_X is not defined
+#endif
+#ifndef GRID_Y
+#error GRID_Y is not defined
+#endif
+
+#ifndef  GRID_E
+#define  GRID_E   GRID_Y    /* number of vertical samples in each yedges[] bucket */
+#endif
+
+#define  GRID_XY  (GRID_X*GRID_Y)
+
+#if GRID_XY == 255
+#  define  GRID_SCALE(c)  (c)
+#elif GRID_XY == 64
+#  define  GRID_SCALE(c)   (((c) << 2) | -(((c) & 0x40) >> 6))
+#elif GRID_XY == 128
+#  define  GRID_SCALE(c)  ((((c) << 1) | -((c) >> 7)) & 255)
+#elif GRID_XY == 256
+#  define  GRID_SCALE(c)  (((c) | -((c) >> 8)) & 255)
+#elif GRID_XY == 15
+#  define  GRID_SCALE(c)  ((c) << 4)
+#else
+#  define  GRID_SCALE(c)  ((c)*255 / GRID_XY)
+#endif
+
+/* convert from PIXEL_BITS coordinates to GRID_X/GRID_Y ones */
+#define  GRID_TO_X(x)   ((x)*GRID_X >> PIXEL_BITS)
+#define  GRID_TO_Y(y)   ((y)*GRID_Y >> PIXEL_BITS)
+
+#ifdef __GNUC__
+#define  __likely(x)    __builtin_expect(!!(x),1)
+#define  __unlikely(x)  __builtin_expect(!!(x),0)
+#else
+#define  __likely(x)    (x)
+#define  __unlikely(x)  (x)
+#endif
+
+  typedef struct TGrayWorker   *PGrayWorker;
+
+  typedef struct TEdge
+  {
+    int            x;
+    int            e;
+    int            x_incr;
+    int            e_incr;
+    signed char    xdir;
+    signed char    ydir;
+    long           y;
+    int            h;
+    int            dy;
+    struct TEdge*  next;
+
+  } TEdge, *PEdge;
+
+  typedef struct TEdgeList
+  {
+    int          num_edges;
+    int          max_edges;
+    PEdge        edges;
+    int          xmin;
+    int          xmax;
+    PGrayWorker  gworker;
+
+  } TEdgeList, *PEdgeList;
+
+
+  typedef struct TActiveList
+  {
+    PEdge  head;
+
+  } TActiveList, *PActiveList;
+
+  typedef  int   TCoverage, *PCoverage;
+
+  struct coverage {
+	  int value;
+	  int pixel;
+	  struct coverage *next;
+  };
+  struct cov_list {
+	  struct coverage *list;
+	  int count;
+  };
+
+  typedef struct TGrayWorker
+  {
+    TWORKER_FIELDS
+
+    TEdgeList     edges[1];
+    TActiveList   active[1];
+    struct cov_list  cov_span;
+
+    PEdge*        yedges;  /* edges sorting buckets */
+
+    PEdge         free_edges;
+    int           free_count;
+
+  } TGrayWorker;
+
+
+ /** CALCULUS
+  **/
+
+  /* returns (a/b) and (a%b); assumes b > 0 */
+  static __inline__ int
+  divrem( int  a, int  b, int  *remainder )
+  {
+    int  result, rem;
+
+#ifdef __arm__
+    result = a / b;
+    rem    = (a - result*b);
+#else
+    result = a / b;
+    rem    = a % b;
+#endif
+    *remainder = rem;
+    return result;
+  }
+
+  /* returns (a*b)/c and (a*b)%c, assumes 0 <= b <= c, c > 0 */
+  static __inline__ int
+  muldivrem( int  a, int  b,  int  c, int  *remainder )
+  {
+    long long  dd = a*b;
+    *remainder = dd % c;
+    return dd / c;
+  }
+
+ /** EDGE LISTS
+  **/
+
+  static void
+  edgelist_init( PEdgeList  list, PGrayWorker  gworker )
+  {
+    list->num_edges  = 0;
+    list->max_edges  = gworker->free_count;
+    list->edges      = gworker->free_edges;
+    list->xmin       = INT_MAX;
+    list->xmax       = INT_MIN;
+    list->gworker    = gworker;
+  }
+
+  static void
+  edgelist_reset( PEdgeList  list )
+  {
+    list->num_edges = 0;
+    list->xmin      = INT_MAX;
+    list->xmax      = INT_MIN;
+  }
+
+  static void
+  edgelist_done( PEdgeList  list )
+  {
+    list->num_edges = 0;
+    list->max_edges = 0;
+    list->edges     = NULL;
+    list->gworker   = NULL;
+  }
+
+
+  static PEdge
+  edgelist_insert( PEdgeList    list,
+                   TPos         x0,
+                   TPos         y0,
+                   TPos         x1,
+                   TPos         y1,
+                   TPos         min_y,
+                   TPos         max_y )
+  {
+    PEdge   edge;
+    TPos    dx, dy, adx;
+    int     ydir = +1;
+
+    if (y0 == y1)
+      return NULL;
+
+    if (y0 > y1) {
+        TPos  tmp;
+
+        tmp  = x0; x0 = x1; x1 = tmp;
+        tmp  = y0; y0 = y1; y1 = tmp;
+        ydir = -1;
+    }
+
+    if (y0 >= max_y || y1 <= min_y )
+        return NULL;
+
+    if (x0 < list->xmin) list->xmin = x0;
+    if (x0 > list->xmax) list->xmax = x0;
+    if (x1 < list->xmin) list->xmin = x1;
+    if (x1 > list->xmax) list->xmax = x1;
+
+    if ( list->num_edges >= list->max_edges )
+      ft_longjmp( ((PWorker)list->gworker)->jump_buffer, 1 );
+
+    edge = &list->edges[ list->num_edges++ ];
+
+    dx   = x1 - x0;
+    dy   = y1 - y0;
+    adx  = (dx >= 0) ? dx : -dx;
+
+    edge->next = NULL;
+    edge->xdir = (dx >= 0) ? 1 : -1;
+    edge->ydir = (signed char) ydir;
+    edge->x    = x0;
+    edge->y    = y0;
+    edge->h    = dy;
+    edge->dy   = dy;
+    edge->e    = -dy;
+
+    /* handle vertical clipping now */
+    if ( y0 < min_y )
+    {
+      int    ex;
+      int    dx = muldivrem( dx, min_y - y0, dy, &ex );
+      edge->x = x0 + dx;
+      edge->e = ex - dy;
+      edge->y = min_y;
+      edge->h = y1 - min_y;
+    }
+
+    edge->x_incr = divrem( dx, dy, &edge->e_incr );
+    if (edge->e_incr < 0) {
+      edge->x_incr -= 1;
+      edge->e_incr += dy;
+    }
+
+    return edge;
+  }
+
+ /** ACTIVE EDGE LIST
+  **/
+
+  static void
+  activelist_init( PActiveList  list )
+  {
+    list->head = NULL;
+  }
+
+
+  static void
+  activelist_reset( PActiveList  list )
+  {
+    list->head = NULL;
+  }
+
+  static void
+  activelist_done( PActiveList  list )
+  {
+    list->head = NULL;
+  }
+
+
+  static void
+  activelist_sort( PActiveList  list )
+  {
+    PEdge   new_head = NULL;
+    PEdge   head     = list->head;
+    PEdge   head_next;
+
+    /* insertion sort with a linked list is faster in practice !! */
+    for ( ; head != NULL; head = head_next )
+    {
+      PEdge*  pprev = &new_head;
+
+      head_next = head->next;
+
+      for (;;)
+      {
+        PEdge  prev = *pprev;
+
+        if ( prev == NULL || prev->x >= head->x )
+          break;
+
+        pprev = &prev->next;
+      }
+
+      head->next = *pprev;
+      *pprev     = head;
+    }
+
+    list->head = new_head;
+  }
+
+
+  static void
+  activelist_insert( PActiveList  list, int  y, PEdge*  yedges )
+  {
+    PEdge  *pedge = yedges;
+    PEdge  *pprev = &list->head;
+
+    for (;;)
+    {
+      PEdge edge = *pedge;
+
+      if (edge == NULL || edge->y != y)
+        break;
+
+      for (;;)
+      {
+        PEdge  prev = *pprev;
+
+        if (prev == NULL || prev->x >= edge->x )
+          break;
+
+        pprev = &prev->next;
+        prev  = prev->next;
+
+        if (prev == NULL || prev->x >= edge->x)
+          break;
+      }
+
+      *pedge     = edge->next;
+      edge->next = *pprev;
+      *pprev     = edge;
+    }
+  }
+
+
+  static void
+  activelist_next( PActiveList  list )
+  {
+    PEdge*  pprev = &list->head;
+
+   /* this is a very critical loop in this algorithm
+    * so we unroll it a little to make things go faster
+    * yes, this really helps
+    */
+    for (;;)
+    {
+      PEdge  edge = *pprev;
+
+      if (edge == NULL)
+        break;
+
+      if ( --edge->h == 0 )
+        *pprev = edge->next;
+      else
+      {
+        edge->x += edge->x_incr;
+        edge->e += edge->e_incr;
+        if (edge->e > 0)
+        {
+          edge->x ++;
+          edge->e -= edge->dy;
+        }
+        pprev = &edge->next;
+      }
+
+      edge = *pprev;
+      if (edge == NULL)
+        break;
+
+      if ( --edge->h == 0 )
+        *pprev = edge->next;
+      else
+      {
+        edge->x += edge->x_incr;
+        edge->e += edge->e_incr;
+        if (edge->e > 0)
+        {
+          edge->x ++;
+          edge->e -= edge->dy;
+        }
+        pprev = &edge->next;
+      }
+
+      edge = *pprev;
+      if (edge == NULL)
+        break;
+
+      if ( --edge->h == 0 )
+        *pprev = edge->next;
+      else
+      {
+        edge->x += edge->x_incr;
+        edge->e += edge->e_incr;
+        if (edge->e > 0)
+        {
+          edge->x ++;
+          edge->e -= edge->dy;
+        }
+        pprev = &edge->next;
+      }
+    }
+
+    /* sort if needed (pretty rare, so first make a linear scan check) */
+    {
+      PEdge  prev = list->head;
+
+      if (prev != NULL)
+      {
+        PEdge  edge;
+        TPos   prev_x = prev->x;
+
+        for ( edge = prev->next; edge != NULL; edge = edge->next )
+        {
+          TPos  x = edge->x;
+
+          if ( prev_x > x )
+          {
+            activelist_sort( list );
+            break;
+          }
+
+          prev_x = x;
+        }
+      }
+    }
+  }
+
+
+
+
+
+
+  static int
+  gray_move_to( const FT_Vector*  to,
+                PWorker           worker )
+  {
+    /* start to a new position */
+    ras.x = UPSCALE( to->x );
+    ras.y = UPSCALE( to->y );
+
+    return 0;
+  }
+
+
+  static void
+  gray_render_line( RAS_ARG_ TPos  to_x,
+                             TPos  to_y )
+  {
+    PGrayWorker  gworker = (PGrayWorker) worker;
+    TPos         y0, y1, tmp;
+
+    y0 = ras.y;
+    y1 = to_y;
+
+    if (y0 > y1) {
+      tmp = y0; y0 = y1; y1 = tmp;
+    }
+
+    if ( TRUNC(y0) < worker->max_ey &&
+         CEILING(y1)  > worker->min_ey )
+    {
+      PEdge*  bucket;
+      PEdge   edge = edgelist_insert( gworker->edges,
+                                      GRID_TO_X(ras.x), GRID_TO_Y(ras.y),
+                                      GRID_TO_X(to_x),  GRID_TO_Y(to_y),
+                                      worker->min_ey*GRID_Y,
+                                      worker->max_ey*GRID_Y );
+
+      if (edge != NULL)
+      {
+        TPos   y = edge->y;
+
+        bucket = &gworker->yedges[ (y - worker->min_ey*GRID_Y)/GRID_E ];
+
+#if GRID_E > 1
+        for (;;)
+        {
+          PEdge  prev = *bucket;
+
+          if (prev == NULL || prev->y > y)
+            break;
+
+          if (prev->y == y && prev->x > edge->x )
+            break;
+
+          bucket = &prev->next;
+        }
+#endif
+        edge->next = bucket[0];
+        bucket[0]  = edge;
+      }
+    }
+    ras.x = to_x;
+    ras.y = to_y;
+  }
+
+  static void  __inline__
+  gray_quick_span( unsigned char*  dst, int  x, int  len, int  coverage )
+  {
+    coverage = GRID_SCALE(coverage);
+
+    if ( len >= 8 )
+      FT_MEM_SET( dst + x, coverage, len );
+    else
+    {
+      unsigned char*  q = dst + x;
+
+      switch ( len )
+      {
+      case 7: *q++ = coverage;
+      case 6: *q++ = coverage;
+      case 5: *q++ = coverage;
+      case 4: *q++ = coverage;
+      case 3: *q++ = coverage;
+      case 2: *q++ = coverage;
+      case 1: *q   = coverage;
+      default:
+        ;
+      }
+    }
+  }
+
+  static void
+  gray_blit( RAS_ARG_ int  x, int  y, int count, struct coverage *first )
+  {
+    FT_Bitmap*      map       = &ras.target;
+    unsigned char*  dst;
+    int             old_x     = 0;
+    int             old_cover = 0;
+    int             cover     = old_cover;
+
+    dst = (unsigned char*)map->buffer - y * map->pitch + x;
+    if ( map->pitch >= 0 )
+      dst += ( map->rows - 1 ) * map->pitch;
+
+
+    struct coverage *i = first;
+    while (i && i->pixel < 0) {
+	    old_cover += i->value;
+	    struct coverage *n = i->next;
+	    i->pixel = 0;
+	    i->value = 0;
+	    i->next = 0;
+	    i = n;
+    }
+    while (i) {
+      while (i->value == 0) {
+	      //printf("cov: %d\n", old_cover);
+	      struct coverage *n = i->next;
+	      i->pixel = 0;
+	      i->value = 0;
+	      i->next = 0;
+	      i = n;
+	      if (!i)
+		      goto Out;
+      }
+      if (i->pixel >= count)
+	      goto Out;
+      x = i->pixel;
+      //printf("cov: %d\n", old_cover);
+      gray_quick_span(dst, old_x, x - old_x, old_cover);
+      cover += i->value;
+      old_cover = cover;
+      old_x = x;
+      struct coverage *n = i->next;
+      i->pixel = 0;
+      i->value = 0;
+      i->next = 0;
+      i = n;
+
+    }
+Out:
+    
+    while (i) {
+	    dprintf("erasing %d %p\n", i->pixel, i);
+	    struct coverage *n = i->next;
+	    i->pixel = 0;
+	    i->value = 0;
+	    i->next = 0;
+	    i = n;
+    }
+
+
+
+    x = count;
+    if (old_cover)
+      gray_quick_span( dst, old_x, x - old_x, old_cover );
+
+  }
+
+  static void
+  gray_span( RAS_ARG_  int x0, int  x1, struct cov_list *delta_spans, struct coverage **latest, int count)
+  {
+    int  x0pix = x0 / GRID_X;
+    int  x0sub = x0 % GRID_X;
+    int  x1pix = x1 / GRID_X;
+    int  x1sub = x1 % GRID_X;
+    struct coverage *current = *latest;
+    struct coverage *last = NULL;
+    dprintf("span (%d %d)\n", x0pix, x1pix);
+
+    if ( x1pix < 0 || x0pix >= count )
+      return;
+
+    while (current && current->pixel < x0pix) {
+	    last = current;
+	    current = current->next;
+    }
+    // current can be NULL here
+    // we need to insert a new pixel
+    if (!current || current->pixel != x0pix) {
+      struct coverage *n = &delta_spans->list[delta_spans->count++];
+      n->next = current;
+      last->next = n;
+      current = n;
+      current->pixel = x0pix;
+      dprintf("new pixel: %p %d(%d)\n",current, x0pix, current->coverage);
+    }
+    struct coverage *first = current;
+    last = current;
+    current = current->next;
+    if (!current || current->pixel != (x0pix + 1)) {
+	    struct coverage *n = &delta_spans->list[delta_spans->count++];
+	    n->next = current;
+	    last->next = n;
+	    current = n;
+	    current->pixel = x0pix + 1;
+    }
+
+    //XXX: should do some dealing with horizontal clipping?
+    if (x0pix == x1pix)
+    {
+      first->value += x1sub - x0sub;
+      current->value -= (x1sub - x0sub);
+    }
+    else
+    {
+      first->value += GRID_X - x0sub;
+      current->value += x0sub;
+
+      while (current && current->pixel < x1pix) {
+	last = current;
+	current = current->next;
+      }
+      // we need to insert a new pixel
+      if (!current || current->pixel != x1pix) {
+	struct coverage *n = &delta_spans->list[delta_spans->count++];
+	n->next = current;
+	last->next = n;
+	current = n;
+	current->pixel = x1pix;
+      }
+      current->value += x1sub - GRID_X;
+      last = current;
+      current = current->next;
+      if (!current || current->pixel != (x1pix + 1)) {
+	struct coverage *n = &delta_spans->list[delta_spans->count++];
+	n->next = current;
+	last->next = n;
+	current = n;
+	current->pixel = x1pix + 1;
+      }
+      current->value -= x1sub;
+    }
+
+    /* the next edge can come at x1 so don't use current which points at x1+1 */
+    *latest = last;
+  }
+
+
+  static void
+  gray_band_process( RAS_ARG )
+  {
+    FT_Bitmap*   target  = &worker->target;
+    PGrayWorker  gworker = (PGrayWorker) worker;
+    PEdgeList    edges  = gworker->edges;
+    PActiveList  active = gworker->active;
+
+    int  xmin   =  edges->xmin / GRID_X;
+    int  xmax   = (edges->xmax + GRID_X-1) / GRID_X;
+    int  ymin   = worker->min_ey;
+    int  ymax   = worker->max_ey;
+    int  xcount, xofs;
+    int  from  = 0;
+    TPos  y, yc, yd;
+
+    if (xmin < ras.min_ex)
+      xmin = ras.min_ex;
+
+    if (xmax > ras.max_ex)
+      xmax = ras.max_ex;
+
+    xcount = xmax - xmin;
+    xofs   = xmin*GRID_X;
+
+    if (edges->num_edges == 0 || xcount <= 0)
+      return;
+
+
+    /* edgelist_sort( edges ); */
+    activelist_reset( active );
+
+    for ( y = ymin; y < ymax; y++ )
+    {
+      PEdge*   line_edges = &gworker->yedges[y - ymin];
+      int      yy;
+
+      if (*line_edges == NULL && active->head == NULL)
+        continue;
+
+      //XXX: guarentee this is first
+      struct coverage *latest = &gworker->cov_span.list[gworker->cov_span.count++];
+      latest->pixel = 0;
+      latest->value = 0;
+      for (yy = 0; yy < GRID_Y; yy++)
+      {
+        /* non-zero winding only at the moment */
+        int  ii;
+        int  winding = 0;
+        int  x = 0;
+        PEdge  edge;
+
+	dprintf("new span\n");
+	latest = &gworker->cov_span.list[0];
+
+        activelist_insert( active, y*GRID_Y + yy, line_edges );
+
+        edge = active->head;
+        if (edge != NULL)
+        {
+          do
+          {
+            x       = edge->x;
+            winding = edge->ydir;
+
+            do
+            {
+              edge = edge->next;
+              if (edge == NULL)
+                goto NextSubLine;
+
+              winding += edge->ydir;
+            }
+            while (winding != 0);
+
+            if (edge->x > x) {
+              gray_span( RAS_VAR_  x - xofs, edge->x - xofs, &gworker->cov_span, &latest, xcount);
+	    }
+            edge = edge->next;
+          }
+          while (edge != NULL);
+        }
+
+      NextSubLine:
+        activelist_next( active );
+      }
+
+      gray_blit( RAS_VAR_  xmin, y, xcount, &gworker->cov_span.list[0]);
+      gworker->cov_span.count = 0;
+    }
+  }
+
+
+  static int
+  gray_convert_glyph_inner( RAS_ARG )
+  {
+    static
+    const FT_Outline_Funcs  func_interface =
+    {
+      (FT_Outline_MoveTo_Func) gray_move_to,
+      (FT_Outline_LineTo_Func) gray_line_to,
+      (FT_Outline_ConicTo_Func)gray_conic_to,
+      (FT_Outline_CubicTo_Func)gray_cubic_to,
+      0,
+      0
+    };
+
+    volatile int  error = 0;
+
+    if ( ft_setjmp( ras.jump_buffer ) == 0 )
+    {
+      error = FT_Outline_Decompose( &ras.outline, &func_interface, &ras );
+    }
+    else
+    {
+      error = ErrRaster_Memory_Overflow;
+    }
+
+    return error;
+  }
+
+
+  static int
+  gray_band_setup( RAS_ARG_ PBand  band )
+  {
+    PGrayWorker  gworker = (PGrayWorker) worker;
+
+    band=band; /* unused */
+
+    edgelist_reset( gworker->edges );
+
+    if (gworker->cov_span.list == NULL)
+    {
+      //XXX how much do we actually need?
+      gworker->cov_span.list = calloc( (ras.max_ex - ras.min_ex + 3), sizeof(struct coverage) );
+      if (gworker->cov_span.list == NULL)
+        return -1;
+    }
+    gworker->cov_span.count = 0;
+
+    free( gworker->yedges );
+    gworker->yedges = calloc( ((ras.max_ey - ras.min_ey)*GRID_Y + (GRID_E-1)) / GRID_E,
+                              sizeof(PEdge) );
+
+    return 0;
+  }
+
+
+
+  static int
+  gray_raster_render( PRaster                  raster,
+                      const FT_Raster_Params*  params )
+  {
+    int                error;
+    PGrayWorker        gworker = raster->worker;
+    const FT_Outline*  outline = (const FT_Outline*)params->source;
+
+    if ( outline->n_points == 0 || outline->n_contours == 0 )
+      return 0;
+
+    error = gray_raster_setup( raster, params );
+    if (!error)
+    {
+      edgelist_init( gworker->edges, gworker );
+      activelist_init( gworker->active );
+      gworker->yedges = NULL;
+      gworker->cov_span.list = NULL;
+
+      error = gray_convert_glyph( (PWorker)gworker );
+
+      activelist_done( gworker->active );
+      edgelist_done( gworker->edges );
+      free( gworker->yedges );
+      free( gworker->cov_span.list );
+    }
+    return error;
+  }
+
+
+  static void
+  gray_raster_reset( FT_Raster  raster,
+                     char*      pool_base,
+                     long       pool_size )
+  {
+    PRaster  rast = (PRaster)raster;
+
+
+    if ( raster )
+    {
+      if ( pool_base && pool_size >= (long)sizeof ( TGrayWorker ) + 2048 )
+      {
+        PGrayWorker  gworker = (PGrayWorker)pool_base;
+        long         offset, offset2, modulo;
+
+
+        rast->worker = gworker;
+
+        offset = (long)(void*)pool_base + sizeof(TGrayWorker);
+        modulo = offset % sizeof(TEdge);
+        if (modulo > 0)
+          offset += sizeof(TEdge) - modulo;
+
+        rast->buffer             = (void*)offset;
+        rast->buffer_size        = (long)( (pool_base + pool_size) - (char*)rast->buffer );
+
+        gworker->free_edges = (PEdge)(void*)offset;
+        gworker->free_count = rast->buffer_size / sizeof(TEdge);
+        rast->band_size     = gworker->free_count / 4;
+      }
+      else
+      {
+        rast->buffer      = NULL;
+        rast->buffer_size = 0;
+        rast->worker      = NULL;
+      }
+    }
+  }
+
+/* END */
diff --git a/rasters.h b/rasters.h
index 8bebee4..4571657 100644
--- a/rasters.h
+++ b/rasters.h
@@ -9,6 +9,7 @@ RASTER( tor16x16_7 )
 RASTER( kiia32_7 )
 RASTER( tor8x32_8 )
 RASTER( tor8x8_8 )
+RASTER( tor8x8_9 )
 RASTER( kiia16_7 )
 RASTER( kiia8_7 )
 #undef RASTER


More information about the cairo mailing list