Re: [ft-devel] Re: rasterization without sorting

[GRAHAM ASHER]

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