freetype-devel
[Top][All Lists]

## Re: [ft-devel] tentative fix for cubic spline bug

 From: Graham Asher Subject: Re: [ft-devel] tentative fix for cubic spline bug Date: Sun, 29 Aug 2010 20:42:49 +0100 User-agent: Thunderbird 2.0.0.24 (Windows/20100228)

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;
}

```