[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] patch to use of enums in ft2demos
> GCC 4.5 emits a new warning when an enum type is compared to a > numeric constant whose value isn't included in that enum. [...] > > we can extend the enum to have a full list of the values we care > about [...] Thanks for the patch! I've applied this your solution to the repository. Werner ___ 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 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 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
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 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
Re: [ft-devel] tentative fix for cubic spline bug
Here's a better fix that also works (below). I now check whether the control points are actually on different sides of the straight line from start to end. The only weak point is possible integer overflow here: suggestions, please: side0 = (x6 - x0) * (control1->y - y0) - (y6 - y0) * (control1->x - x0) <= 0; side1 = (x6 - x0) * (control2->y - y0) - (y6 - y0) * (control2->x - x0) <= 0; In this code, side0 and side1 are set to 0 or 1 according to whether the control points are on the left or the right of the straight line. But I am starting to wonder if a simpler approach might be better. Rather than calculating the number of iterations of the curve splitting loop in advance, perhaps it might be more efficient, and certainly simpler to code correctly, to iterate until neither of the two control points is further than 16 units from the start or end. That would, it is true, produce far too many iterations for very flat curves. 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; /* If the control points are on different sides of the curve, split the cubic into two, creating 7 points, then find the midpoints of the first and second curves. Splitting guarantees that the two curves' control points are both on the same side of the straight line from start to end. Find how far the midpoints 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; int dx0, dx1, dy0, dy1; int side0, side1; int mid_x, mid_y; x0 = DOWNSCALE(ras.x); x6 = to->x; y0 = DOWNSCALE(ras.y); y6 = to->y; side0 = (x6 - x0) * (control1->y - y0) - (y6 - y0) * (control1->x - x0) <= 0; side1 = (x6 - x0) * (control2->y - y0) - (y6 - y0) * (control2->x - x0) <= 0; if (side0 == side1) { mid_x = (x0 + x6 + 3 * (control1->x + control2->x)) / 8; mid_y = (y0 + y6 + 3 * (control1->y + control2->y)) / 8; dx0 = x0 + x6 - (mid_x << 1); if (dx0 < 0) dx0 = -dx0; dy0 = y0 + y6 - (mid_y << 1); if (dy0 < 0) dy0 = -dy0; if (dx0 < dy0) dx0 = dy0; } else { x1 = (x0 + control1->x) / 2; x3 = (control1->x + control2->x) / 2; x5 = (control2->x + x6) / 2; x2 = (x1 + x3) / 2; x4 = (x3 + x5) / 2; mid_x = 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; y1 = (y0 + control1->y) / 2; y3 = (control1->y + control2->y) / 2; y5 = (control2->y + y6) / 2; y2 = (y1 + y3) / 2; y4 = (y3 + y5) / 2; mid_y = 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) mid_x = ( ras.x + to_x + 3 * UPSCALE( control1->x + control2->x ) ) / 8; mid_y = ( ras.y + to_y + 3 * UPSCALE( control1->y + control2->y ) ) / 8; #endif error = gray_render_line( RAS_VAR_ mid_x, mid_y ); 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
"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 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