[ft-devel] rasterization without sorting - in defence of my approach

[GRAHAM ASHER]

The current FreeType approach is definitely inefficient for some shapes. For 
example, imagine an almost horizontal stroke N pixels wide, which has a top 
edge 
starting at pixel T + 1 and ending at pixel T. (Such strokes occur frequently 
in 
Chinese ideographs.) This contour (the top edge) will generate N cells, all 
with 
a Y coordinate of T, and with X coordinates 0...N - 1, which will be inserted 
into the linked list for row T. The cells will be inserted in the worst 
possible 
order (reverse order), requiring (N^2) / 2 comparisons to find the correct 
place 
in the list. If the stroke is 128 pixels wide - which can easily happen when 
drawing large glyphs, or using high resolution for printing - there are thus 
8192 comparisons when sorting this line of cells.

My method (direct insertion into a sparse array) is almost certainly better 
when 
there is enough memory to create an array with a slot for every pixel in the 
bitmap, but if not, it falls back on quicksort.

So is the quicksort method always better? Unfortunately not. Quicksort is very 
slow when working on almost-sorted sequences, and that is the type of sequence 
generated by FreeType. We can probably improve matters by randomising the 
sequence before sorting. I haven't tried that method for FreeType, but it has 
worked dramatically well for me in other cases.

In conclusion, more benchmarking is needed to decide on an optimal approach, 
balanced for the average mix of cases.

I am also aware that FreeType's sole purpose is to rasterize glyphs, while mine 
is also to rasterize large arbitrary shapes. Nevertheless, these aims tend to 
converge as display resolution improves; at modern resolutions of around 
200dpi, 
18pt glyphs are as large as 50 x 50 pixels.

Graham Asher
CartoType Ltd.



----- Original Message ----
From: GRAHAM ASHER <address@hidden>
To: Werner LEMBERG <address@hidden>
Cc: FreeType <address@hidden>
Sent: Wednesday, 21 July, 2010 10:20:54
Subject: Re: [ft-devel] Re: rasterization without sorting

Werner,

I've just taken a look at the latest version of ftgrays.c in git, and to my 
surprise, it already uses a design which I considered and rejected! I am not 
claiming that I was right in rejecting it, though.

It avoids using quicksort by creating a list of cells for each scan line (i.e., 
for each y coordinate), then inserting each new cell in a singly linked list. 
Thus sorting on the major key is avoided, but there is still an insertion sort 
on the minor key. I rejected this design because the aim was to avoid all 
sorting, and I believed that an O(n^2) sort for each scan line would be 
inefficient for complicated shapes, where many contours cross the scan lines. 
However, I may be wrong, and I assume that somebody (David, probably) 
benchmarked and compared various approaches before choosing this one.

My design is still available if anyone wants it, but it looks as though it is 
not needed.

Best regards,

Graham




----- Original Message ----
From: Werner LEMBERG <address@hidden>
To: address@hidden
Cc: address@hidden
Sent: Tuesday, 20 July, 2010 13:28:50
Subject: Re: [ft-devel] Re: rasterization without sorting


> Panic over.  A small modification was needed to the criterion for
> skipping an empty cell.  Both cover and area should be zero.  I
> enclose new versions of the patch and complete file for ftgrays.c.

This looks indeed very straightforward.  However, your patch doesn't
apply to the current version of FreeType's ftgrays.c in a non-trivial
way.  May I ask for an update?


    Werner