[ft-devel] rasterization without sorting - in defence of my approach
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
RE: [ft-devel] rasterization without sorting - in defence of my approach
-Original Message- From: freetype-devel-bounces+david.bevan=pb@nongnu.org [mailto:freetype-devel-bounces+david.bevan=pb@nongnu.org] On Behalf Of GRAHAM ASHER Sent: 23 July 2010 08:57 To: Werner LEMBERG Cc: FreeType Subject: [ft-devel] rasterization without sorting - in defence of my approach ... 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, Since some of us use FreeType to render glyphs at printer (300dpi or 600dpi) resolutions, any performance improvement, especially for Far Eastern fonts will be appreciated. Thanks. David %^ ___ Freetype-devel mailing list Freetype-devel@nongnu.org http://lists.nongnu.org/mailman/listinfo/freetype-devel
Re: [ft-devel] rasterization without sorting - in defence of my approach
DB == David Bevan david.be...@pb.com writes: DB Since some of us use FreeType to render glyphs at printer (300dpi, DB 600dpi [or 1200+ dpi, for that matter -JimC]) resolutions, any DB performance improvement, especially for Far Eastern fonts will DB be appreciated. And many more will do so in the coming months; ghostscript trunk (which is expected to be released in the next few weeks as gs 9.0) defaults to freetype for type1, cff and sfnt fonts. -JimC -- James Cloos cl...@jhcloos.com OpenPGP: 1024D/ED7DAEA6 ___ Freetype-devel mailing list Freetype-devel@nongnu.org http://lists.nongnu.org/mailman/listinfo/freetype-devel
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 w...@gnu.org To: graham.as...@btinternet.com Cc: freetype-devel@nongnu.org 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 ___ Freetype-devel mailing list Freetype-devel@nongnu.org http://lists.nongnu.org/mailman/listinfo/freetype-devel
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 ___ Freetype-devel mailing list Freetype-devel@nongnu.org http://lists.nongnu.org/mailman/listinfo/freetype-devel
