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

[David Bevan]

Graham,

I finally had a brief chance to look at the code yesterday, and hope to be able 
to spend most of the rest of today on it too. (So far I have only looked at the 
pre-2.4.0 code.)
 
gray_render_cubic is a (non-recursive implementation of) a recursive algorithm 
for splitting the curve into 2^n line segments. This is "forward differencing" 
rather than "recursive subdivision" (which determine whether each subdivision 
is required independently).

At the moment I don't understand the basis for the calculation of n, though I 
presume that it is some standard heuristic. You point 7 below rather brings 
that into doubt though!

This was probably state-of-the-art when it was first implemented, but is 
probably quite inefficient in the number of line segments created.
 

I've added further comments inline below, and some queries at the end.


> -----Original Message-----
> From: address@hidden
> [mailto:address@hidden On Behalf Of
> GRAHAM ASHER
> Sent: 3 September 2010 09:14
> To: FreeType
> Subject: [ft-devel] more thoughts on cubic spline flattening
> 
> David Bevan's citation of two papers on spline flattening
> (http://www.cis.southalabama.edu/~hain/general/Publications/Bezier/Camera-
> ready%20CISST02%202.pdf
>  and
> http://www.cis.usouthal.edu/~hain/general/Publications/Bezier/bezier%20ccc
> g04%20paper.pdf)
>  stimulated some more thoughts on the problem. To recapitulate some
> existing
> points, and ask some more questions, and point out another error in the
> current
> FreeType logic (point 6):
> 
> 1. The ideal flattening criterion is the maximum deviation (sideways
> distance)
> of any point on the curve from the chord (straight line from p0 to p3; not
> the
> line segment, but the whole infinite line).

This isn't quite the whole story. The curve may extend outside the infinite 
strip perpendicular to the chord P0P3 as seen in Hain's Figure 2. Indeed it may 
do so even if the curve never deviates from the chord in the s-direction by 
more than the maximum acceptable deviation value (because both control points 
are very close to the line which extends the chord).

This is the reason for Hain's section 3.2 on the longitudinal deviation. 
However, there's a simple approach for handling this: if P0 or P3 is (more than 
the maximum acceptable deviation value) outside the strip, subdivide. Hain 
mentions this at the end of his section 1.


> 2. Hain's paper shows that this can be approximated (yielding an estimate
> that
> is never too small, and always quite close) by a quadratic equation based
> on the
> ratio between the deviations of the two control points from the chord. If
> the
> ratio (smaller deviation divided by larger) is v, the expression
> 0.072(v^2) +
> 0.229v + 0.449, multiplied by the larger of the two deviations, gives this
> approximation.
> 
> 3. Calculating the expression in (2) is quite expensive because square
> root
> operations are required to get the deviations of the two control points,
> and
> some fixed-point arithmetic is needed to avoid or at least minimise
> overflow. (I
> have coded this experimentally.)

Perhaps I've missed something, but my reading of Hain's paper is that the 
evaluation of square roots is never actually needed.


> 4. There are a series of less accurate heuristics. The first relaxation is
> not
> to evaluate the expression in (2), but to use the value 0.75, which is the
> maximum value it can yield (v is always in the range 0...1, and v=1 yields
> 0.75;
> smaller values of v give smaller results). However, this heuristic still
> requires calculation of the deviations of the control points. A second
> relaxation uses the maximum coordinate distance (max of dx and dy) of a
> control
> point from the middle of the chord, which cannot be less than the actual
> deviation.

This looks like a variant of what Hain describes on pp1-2.


> 5. Therefore a usable fast heuristic is the maximum coordinate distance
> from the
> middle of the chord, multiplied by 0.75.

I don't think that will work. A control point can be sqrt(2) x max(dx,dy) from 
the chord (if dx=dy), so we need to factor that into the calculation.

An example:

  P0: 0,0
  P1: 0,99
  P2: 1,100
  P3: 100,100

v = 1 so the max deviation = 0.75 * 99 / sqrt(2) ~= 52.50

But max(dx,dy) = 50, so the heuristic would give 0.75 * 50 = 37.5.

You would need to use a factor at least 0.75 * sqrt(2) ~= 1.06, rather than 
0.75. For this example it would give an estimate of ~53.03.


For sensible estimates, it is necessary to work in Hain's r-s coordinate system.


> 6. Unfortunately the current logic in FreeType has another error. It
> assumes
> that the flattening criterion can be applied at the start, yielding the
> required
> number of bisections. That is, a ratio is calculated between the heuristic
> distance and a so-called 'cubic level'; and the number of bisections
> needed is
> calculated as the ceiling of the base-4 logarithm of the heuristic
> distance; in
> other words, there is an assumption that every bisection of a cubic spline
> increases its flatness fourfold.
> 
> 7. Here is the proof that the assumption in (6) is wrong. A cubic spline
> with
> control points on different sides of the chord, symmetrically arranged,
> will be
> bisected at the point where it crosses the chord. The two halves will have
> exactly the same maximum deviation as the whole.
> 
> This leads to the big question. Is it possible to determine the minimum
> number
> of bisections needed at the start, using a formula that does not itself
> apply
> the bisections - that is, something simpler than the exhaustive
> calculation?
> (Perhaps flatness does increase fourfold if the control points are the
> same side
> of the chord, so all we need do is add one iteration for an initial
> contrary
> case.) I suspect that the answer is no, but I am sure David Bevan will
> want to
> comment. If the answer is no, then I shall need to code up a fix that
> estimates
> flatness efficiently on each iteration of the bisection loop.


Some queries:

A. Perhaps it's obvious to someone familiar with the FreeType code, but (to 
save me time trying to work it out), in the units being used in 
gray_render_cubic, what is the maximum acceptable deviation value that should 
be used as a cut-off for stopping subdivision? Perhaps the answer could briefly 
explain the use of DOWNSCALE and UPSCALE.

B. Would it be possible to have a copy of the font that was the catalyst for 
the changes in 2.4.0, along with details of the character / resolution / 
point-size which shows the problem.

C. Similarly, would it be possible to have a copy of the font that showed up 
the bug in the changed code (with similar details).

Thanks.


David %^>

________________________________
David Bevan
Development Manager
Pitney Bowes Emtex Software
Tel: +44 (0)1923 279300
address@hidden
________________________________


> Comments please.
> 
> Thanks in advance,
> 
> Graham
> 
> _______________________________________________
> Freetype-devel mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/freetype-devel