I have just noticed that this doesn't work perfectly yet. I am sure the principle is sound, though. I'll send a revised version as soon as possible.
----- Original Message ---- From: GRAHAM ASHER <graham.as...@btinternet.com> To: freetype-devel@nongnu.org Sent: Monday, 19 July, 2010 16:11:35 Subject: rasterization without sorting 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 _______________________________________________ Freetype-devel mailing list Freetype-devel@nongnu.org http://lists.nongnu.org/mailman/listinfo/freetype-devel