[ft-devel] Re: possible inefficiency in gray_render_cubic

[Graham Asher]

Correction (sorry, but this stuff gets confusing). Section 6 should read:


6. A POSSIBLE BETTER FIX

Calculate the midpoint and compare it with start and end:

{
int mid_x = (DOWNSCALE( ras.x ) + to->x + 3 * (control1->x + control2->x)) / 8; 
int mid_y = (DOWNSCALE( ras.y ) + to->y + 3 * (control1->y + control2->y)) / 8; 
dx = DOWNSCALE( ras.x ) + to->x - ( mid_x << 1 );
if ( dx < 0 )
    dx = -dx;
dy = DOWNSCALE( ras.y ) + to->y - ( mid_y << 1 );
if ( dy < 0 )
    dy = -dy;
if ( dx < dy )
    dx = dy;
    db = dx;
}

without those multiplications by 3, which crept in again.

Graham



Graham Asher wrote:

I have discovered a possible inefficiency in gray_render_cubic in ftsmooth.c. Removing it (by means of what I admit is a hack based on a limited understanding of the code) gives a vast speedup with no apparent loss of quality. The error is an incorrect method of calculating whether to use a short cut when all the points of a cubic spline are close together. There is also an obvious typo (see 4A below) in the current code. This is based on the current state of the code in the Git repository.

Here's my analysis so far.

1. LOOP PASSES

The number of passes through the main loop is controlled largely by the variable 'level'. Reducing that number increases the speed of the function. If 'level' is no greater than one there are no passes through the loop. Instead, there's a short cut that draws a straight line from the start to the mid point of the curve and another from the mid point to the end.

2. MEANING OF 'level'

It's evident from the nature of the short-cut code that 'level' is related to the maximum distance between the start, end and control points. If all the points are very close together, there is no point in generating a full curve, especially as the units used are normally 64ths of pixels; it's not very meaningful to create a curve inside a pixel, and probably won't affect its grey level, as compared with a straight line. Thus 'level' ought to be 0 or 1 if the points are very close together.

3. EXAMPLE

This example is taken from my CartoType map rendering code.

Coordinates: start = 16272, 24478, control1 = 16276, 24461, control2 = 16266, 24443, end = 16249, 24439
Calculated value of da after 'da = dx': 31
Calculated value of db after 'db = dx': 97795
Calculated value of 'level' (with ras.cubic_level == 64 and ras.conic_level = 128): 5.

Passes through the main loop: 16.

4. ANOMALOUS VALUE OF 'db'

Let's look at the value of 'db' again: 97795. This large value comes from the code

    dx = DOWNSCALE( ras.x ) + to->x - 3 * ( control1->x + control2->x );
    if ( dx < 0 )
      dx = -dx;
    dy = DOWNSCALE( ras.y ) + to->y - 3 * ( control1->x + control2->y );
    if ( dy < 0 )
      dy = -dy;
    if ( dx < dy )
      dx = dy;
    db = dx;

which is where I think the problem is. The idea seems to be to get the maximum distance of the midpoint from the start and end points, but the calculation is wrong: it adds two values (the start and end coordinates) then subtracts six coordinates (the control points, multiplied by three). Thus, if all 4 coordinates (x or y) are identical, the answer is 2x - 6x, or -4x. In our case we get a value for 'db' of ~100,000 because that is 4 times the y coordinate value; they are all ~25000.

(4A. AN OBVIOUS BUG: the code 'control1->x + control2->y' above should obviously be 'control1->y + control2->y'. That needs to be fixed if my suggestions here are rejected.) 

5. A SIMPLE HACK

My initial fix was to simply remove the multiplication by 3, which was probably cut and pasted from the later correct calculation of the curve's midpoint. Thus we have:

    dx = DOWNSCALE( ras.x ) + to->x - ( control1->x + control2->x );
    if ( dx < 0 )
      dx = -dx;
    dy = DOWNSCALE( ras.y ) + to->y - ( control1->y + control2->y );
    if ( dy < 0 )
      dy = -dy;
    if ( dx < dy )
      dx = dy;
    db = dx;

which, as mentioned above, seems to fix the trouble, without apparent bad consequences.

6. A POSSIBLE BETTER FIX

Calculate the midpoint and compare it with start and end:

{
int mid_x = (DOWNSCALE( ras.x ) + to->x + 3 * (control1->x + control2->x)) / 8; 
int mid_y = (DOWNSCALE( ras.y ) + to->y + 3 * (control1->y + control2->y)) / 8; 
dx = DOWNSCALE( ras.x ) + to->x - 3 * ( mid_x << 1 );
if ( dx < 0 )
    dx = -dx;
dy = DOWNSCALE( ras.y ) + to->y - 3 * ( mid_y << 1 );
if ( dy < 0 )
    dy = -dy;
if ( dx < dy )
    dx = dy;
    db = dx;
}

7. FURTHER WORK: WHY DO WE NEED da AND db?

I am sceptical about the need to calculate both da and db. Perhaps db only will suffice. I hope that David or Werner can comment.

Best regards,

Graham Asher
CartoType Ltd