[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[ft-devel] Re: rasterization without sorting

Subject: [ft-devel] Re: rasterization without sorting
Date: Mon, 19 Jul 2010 15:30:58 +0000 (GMT)

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.


----- Original Message ----
From: GRAHAM ASHER <address@hidden>
To: address@hidden
Sent: Monday, 19 July, 2010 16:21:53
Subject: Re: rasterization without sorting

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 <address@hidden>
To: address@hidden
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 

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 

modified - but actually simpler - version of gray_sweep, and a change to the 

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)
      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 

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 

Graham Asher
CartoType Ltd

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

Attachment: ftgrays.c
Description: Text document

reply via email to

[Prev in Thread] Current Thread [Next in Thread]