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 <graham.as...@btinternet.com>
To: Werner LEMBERG <w...@gnu.org>
Cc: FreeType <freetype-devel@nongnu.org>
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 <w...@gnu.org>
To: graham.as...@btinternet.com
Cc: freetype-devel@nongnu.org
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
_______________________________________________
Freetype-devel mailing list
Freetype-devel@nongnu.org
http://lists.nongnu.org/mailman/listinfo/freetype-devel
