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
___
Freetype-devel mailing list
Freetype-devel@nongnu.org
http://lists.nongnu.org/mailman/listinfo/freetype-devel
