RE: [ft-devel] more thoughts on cubic spline flattening

[David Bevan]

Some brief comments inline.

More feedback from my investigations later.


> -----Original Message-----
> From: Graham Asher [mailto:address@hidden
> Sent: 3 September 2010 13:56
> To: David Bevan
> Cc: FreeType
> Subject: Re: [ft-devel] more thoughts on cubic spline flattening
> 
> David,
> 
> you are of course correct that my point 5 is wrong. That is just
> carelessness on my part.
> 
> Some clarifications:
> 
> You point out that p0 and p3 can have coordinates outside the range
> 0...1 in Hain's r/s system. I deliberately ignore that, and I should
> have explained why in more explicit terms. The aim of FreeType is to
> rasterize the outline of a closed curve, and for this purpose I believe
> that, just as we can ignore deviations from the curve of greater than a
> certain tolerance, we can ignore spikes with maximum width less than
> that tolerance. P0 and P3 coordinates of this type create such spikes.

That does not follow the recommended PostScript Language scan-conversion rules 
for path fills (PLRM3 7.5.1) - "a shape is scan-converted by painting any pixel 
whose square region intersects the shape, however small the intersection is".

Whether that rule should actually be applied to character shapes is another 
matter though (see the last paragraph of 7.5.1).


> But if we a heuristic based on the maximum distance of control point
> coordinates from the middle of the chord, the problem doesn't arise
> anyway. It arises only if we use Hain's algorithm fully.

That's a very good point.
 

> You said "my reading of Hain's paper is that the evaluation of square
> roots is never actually needed". To get the deviations of the control
> points we need to either (i) rotate the points into the r/s coordinate
> system, and the simplest way of creating a rotation transform requires
> square roots (convert chord vector to unit vector by dividing by vector
> length obtained by Pythagoras, then sine and cosine needed for transform
> are x and y coords of vector); or (ii) use the standard method of
> finding the distance of a point from a line, which again needs
> Pythagoras to get the lengths of vectors. I hope I've missed some
> simpler way of doing it, in which case please tell me.

Hain explains how to do the calculations in section 3.

The rotation is simply achieved by using the equation for s (where the 
denominator of L^2 can be ignored as Hain further explains).

The last paragraph of section 3 then describes how to do the necessary 
comparison "thereby avoiding a square root evaluation".


The challenge will be ensuring that we can use the widest range of integer 
values without overflow. Squaring the P0-P3 distance seems unavoidable. Using 
unsigned 32-bit values (which we should be able to use for values which are 
always positive) allows us up to 65536 = 1023 pixels = 1.7" at 600dpi.

However, there is one very simple heuristic solution to this: subdivide once 
automatically if the chord length is too great.


> In answer to your question A: the units are 64ths of a pixel, so 16 is a
> quarter pixel. That is for the normal case; FreeType can be configured
> to use different numbers of bits per pixel. The controlling macro is
> PIXEL_BITS in ftgrays.c

Thanks for the answer; obviously your previous email gave a big hint!


Regards,

David %^>