[ft-devel] rasterization without sorting

[GRAHAM ASHER]

I have been working on a new way to optimise anti-aliased rasterization in 
FreeType and other similar libraries. This arises from my need to make 
CartoType, my map rendering library, run as fast as possible. It uses FreeType 
for glyph rendering, and FreeType's smooth rasterization algorithm for drawing 
polygons.

Benchmarking showed that about half of all the time taken by rasterization of 
map shapes was taken by sorting the array of Cell objects (TRaster.cells). 
Sorting, even using quicksort, is not as fast as direct insertion by array 
index. I create array indexes using the x and y coordinates of the cell, then 
put the cell directly into its place. This leaves empty cells, and so requires 
a 
modified - but actually simpler - version of gray_sweep, and a change to the 
way 
gray_record_cell works.

The algorithm, in pseudo-code, is this:

if (clipped width in pixels + 1) * clipped height in pixels not greater than 
maximum number of cells
      zero the cells array
      when recording a cell, insert it at index (y * clipped width in pixels + 
1) + x + 1, and add cover and area to existing values in the array at that index
      do NOT call gray_quick_sort
      use a new version of gray_sweep that skips empty cells (cover = 0) (and 
does not need to accumulate coverage and area for cells with the same coords)
else
      do everything the old way

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.

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.

Graham Asher
CartoType Ltd

rasterizing-without-sorting.diff.txt
Description: Text document

ftgrays.c
Description: Text document