[ft-devel] preliminary analysis of the problem with cubic spline optimisation
The aim is to draw a straight line between the start end end of a cubic spline, instead of rendering the curve correctly, if the curve deviates by less than a certain value from the straight line. The code in gray_render_cubic in ftgrays.c checks only the midpoint of the curve. However, this is not necessarily the furthest point from the straight line. If the sequence start, control1, control2, end is not monotonic in one of the dimensions x, y, an s-shaped curve is produced with points further from the line than the midpoint, which may even lie on the line. This situation occurs in 's' for the sample font. With this information I can easily produce a fix, simply by testing for non-monotonicity and disabling the optimisation in such circumstances, but I shall see if I can up with something slightly better. Graham ___ Freetype-devel mailing list Freetype-devel@nongnu.org http://lists.nongnu.org/mailman/listinfo/freetype-devel
[ft-devel] Re: preliminary analysis of the problem with cubic spline optimisation
Correction: it's not monotonicity that matters, but having the two control points on different sides of the straight line. Graham Asher wrote: The aim is to draw a straight line between the start end end of a cubic spline, instead of rendering the curve correctly, if the curve deviates by less than a certain value from the straight line. The code in gray_render_cubic in ftgrays.c checks only the midpoint of the curve. However, this is not necessarily the furthest point from the straight line. If the sequence start, control1, control2, end is not monotonic in one of the dimensions x, y, an s-shaped curve is produced with points further from the line than the midpoint, which may even lie on the line. This situation occurs in 's' for the sample font. With this information I can easily produce a fix, simply by testing for non-monotonicity and disabling the optimisation in such circumstances, but I shall see if I can up with something slightly better. Graham ___ Freetype-devel mailing list Freetype-devel@nongnu.org http://lists.nongnu.org/mailman/listinfo/freetype-devel
[ft-devel] tentative fix for cubic spline bug
Here's a fix that works. I'm trying to think of a faster way of doing
it. The fix splits the cubic spline in two, guaranteeing that the
resulting curves have their control points on the same side of the
straight lines from start to end, then performs the original test for
the distance (or rather maximum difference of x or y coord) of the curve
midpoints from the straight lines. Below is a modified version of the
start of gray_render_cubic. Suggestions for better fixes cheerfully
welcomed. At least we now know what the problem is.
Graham
-
static int
gray_render_cubic( RAS_ARG_ FT_Vector* control1,
FT_Vector* control2,
FT_Vector* to )
{
int top, level;
int*levels;
FT_Vector* arc;
int error = 0;
/*
Split the cubic into two, creating 7 points,
then find the midpoints of the first and second curves.
Find how far they are from the straight lines joining
the start and end of the two curves. If they are close enough
we can draw them as straight lines.
*/
int x0, x1, x2, x3, x4, x5, x6, midx0, midx1;
int y0, y1, y2, y3, y4, y5, y6, midy0, midy1;
TPos dx0, dx1, dy0, dy1;
x0 = DOWNSCALE(ras.x);
x6 = to-x;
x1 = (x0 + control1-x) / 2;
x3 = (control1-x + control2-x) / 2;
x5 = (control2-x + x6) / 2;
x2 = (x1 + x3) / 2;
x4 = (x3 + x5) / 2;
x3 = (x2 + x4) / 2;
midx0 = (x0 + x3 + 3 * (x1 + x2)) / 8;
midx1 = (x3 + x6 + 3 * (x4 + x5)) / 8;
dx0 = x0 + x3 - (midx0 1); if (dx0 0) dx0 = -dx0;
dx1 = x3 + x6 - (midx1 1); if (dx1 0) dx1 = -dx1;
y0 = DOWNSCALE(ras.y);
y6 = to-y;
y1 = (y0 + control1-y) / 2;
y3 = (control1-y + control2-y) / 2;
y5 = (control2-y + y6) / 2;
y2 = (y1 + y3) / 2;
y4 = (y3 + y5) / 2;
y3 = (y2 + y4) / 2;
midy0 = (y0 + y3 + 3 * (y1 + y2)) / 8;
midy1 = (y3 + y6 + 3 * (y4 + y5)) / 8;
dy0 = y0 + y3 - (midy0 1); if (dy0 0) dy0 = -dy0;
dy1 = y3 + y6 - (midy1 1); if (dy1 0) dy1 = -dy1;
if (dx0 dx1)
dx0 = dx1;
if (dx0 dy0)
dx0 = dy0;
if (dx0 dy1)
dx0 = dy1;
level = 1;
dx0 /= ras.cubic_level;
while ( dx0 0 )
{
dx0 = 2;
level++;
}
if ( level = 1 )
{
TPos to_x, to_y;
to_x = UPSCALE( to-x );
to_y = UPSCALE( to-y );
/* Recalculation of midpoint is needed only if UPSCALE and DOWNSCALE
have any effect. */
#if (PIXEL_BITS != 6)
x3 = ( ras.x + to_x +
3 * UPSCALE( control1-x + control2-x ) ) / 8;
y3 = ( ras.y + to_y +
3 * UPSCALE( control1-y + control2-y ) ) / 8;
#endif
error = gray_render_line( RAS_VAR_ x3, y3 );
if (!error)
error = gray_render_line( RAS_VAR_ to_x, to_y );
return error;
}
___
Freetype-devel mailing list
Freetype-devel@nongnu.org
http://lists.nongnu.org/mailman/listinfo/freetype-devel
Re: [ft-devel] Re: preliminary analysis of the problem with cubic spline optimisation
GA == Graham Asher graham.as...@btinternet.com writes: GA Correction: it's not monotonicity that matters, but having the two GA control points on different sides of the straight line. Wouldn't the midpoint also fail to be the furthest point from the line whenever the two off-curve control points are on the same side of the midpoint? -JimC -- James Cloos cl...@jhcloos.com OpenPGP: 1024D/ED7DAEA6 ___ Freetype-devel mailing list Freetype-devel@nongnu.org http://lists.nongnu.org/mailman/listinfo/freetype-devel
Re: [ft-devel] Re: preliminary analysis of the problem with cubic spline optimisation
It can happen, though. In fact I now don't think it can happen. If there are any good mathematicians out there (better than me at this, which sets quite a low bar), please confirm that no point on a cubic spline curve with both control points on the same side of the straight line from start to end can be further from the line than the curve's midpoint as defined by bisection of the curve. Graham Graham Asher wrote: No, in nearly all cases the midpoint is the point on the curve furthest from the straight line when both control points are on the same side. It can happen, though. I'm now working on a fix depending on finding how far the furthest control point is from the straight line. No point on the curve can be further from the straight line than both control points. Graham James Cloos wrote: GA == Graham Asher graham.as...@btinternet.com writes: GA Correction: it's not monotonicity that matters, but having the two GA control points on different sides of the straight line. Wouldn't the midpoint also fail to be the furthest point from the line whenever the two off-curve control points are on the same side of the midpoint? -JimC ___ Freetype-devel mailing list Freetype-devel@nongnu.org http://lists.nongnu.org/mailman/listinfo/freetype-devel ___ Freetype-devel mailing list Freetype-devel@nongnu.org http://lists.nongnu.org/mailman/listinfo/freetype-devel
