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