Re: [ft-devel] rasterization without sorting

[GRAHAM ASHER]

Werner,

here's my latest version of this optimisation, and I think that's as far  as I 
am going at the moment. I have implemented the changes described below, and of 
course they double the area of glyphs that can be optimised. I have of course 
tested this code and it seems to work perfectly.

If someone can do some independent benchmarking it would be very nice. I am 
actually rather bad at benchmarking, partly because I am working in Windows but 
am not a fluent Windows programmer (I use it as a development platform) and 
often get inconsistent results. However, the profiling results were very clear 
in indicating the large proportion of time taken up by sorting.

To make these changes I introduced a new compact cell structure:

  typedef struct TCompactCell_
  {
    int     cover;
    TArea   area;
  } TCompactCell, *PCompactCell;

and TRaster acquires some new members:

    PCompactCell compact_cells;
    int     max_compact_cells;
    int     width;

with compact_cells being actually the same as cells, but of a different type; 
and the rest is fairly obvious. I enclose my latest version of ft_grays.c.

As to the question of using a #ifdef to enable the new feature, a simple way to 
do it is by forcing TRaster.sort_needed to true, thus:

#ifdef RASTERIZE_WITHOUT_SORTING
        ras.sort_needed = ras.width * (ras.max_ey - ras.min_ey) > 
ras.max_compact_cells;
        if (!ras.sort_needed)
            {
            ras.num_cells = ras.width * (ras.max_ey - ras.min_ey);
            memset(ras.compact_cells,0,sizeof(TCompactCell) * ras.num_cells);
            }
#else
          ras.sort_needed = FALSE;
#endif

but you may prefer a full implementation, with none of the new data members and 
functions being compiled unless needed.

Best regards,

Graham




----- Original Message ----
From: GRAHAM ASHER <address@hidden>
To: Werner LEMBERG <address@hidden>
Cc: address@hidden
Sent: Tuesday, 20 July, 2010 8:57:24
Subject: Re: [ft-devel] rasterization without sorting

I think using #ifdefs is a good idea for the moment. Also, there are two 
semi-obvious ways to make the optimisation even better, and I want to try to 
implement them:

1. Pre-calculate the width of the array, to avoid calculating it in every call 
to gray_record_cell.

2. (This is the big one). Use a variant of the TCell structure without x and y 
fields, making it half the size; thus twice as many cells can be stored. X and 
y 

can be calculated from the array index inside the new version of gray_sweep.

Graham



----- Original Message ----
From: Werner LEMBERG <address@hidden>
To: address@hidden
Cc: address@hidden
Sent: Monday, 19 July, 2010 16:49:20
Subject: Re: [ft-devel] rasterization without sorting


> I have been working on a new way to optimise anti-aliased
> rasterization in FreeType and other similar libraries.

Great!

> I am not completely certain that this is the best way to do things
> for *glyph* rasterization, because glyphs are special cases, being
> in general relatively small, but it speeds up CartoType by about 7%,
> and I believe will speed up FreeType.

Given that David already tried to optimize the AA rasterization, an
improvement of 7% is really impressive.

> I enclose a patch file based on my current version of ftgrays.c,
> which I think is very slightly different from the official version.
> I also enclose ftgrays.c itself, for clarity.  The differences are
> very simple and affect only this one file.

Thanks a lot!  Will have a look the next days.  What do you think
about embedding your changes into #ifdef's temporarily so that anxious
users could deactivate it if they are not in the mood of beta
testing? :-)


    Werner

ftgrays.c
Description: Text document