[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [ft-devel] latest patch file for spline flattening
From: |
GRAHAM ASHER |
Subject: |
Re: [ft-devel] latest patch file for spline flattening |
Date: |
Tue, 7 Sep 2010 16:06:36 +0000 (GMT) |
Well done! I can't wait to try it out with my data. Unfortunately I am tied up
with something else right now, but I hope to be able to have a go tomorrow.
Graham
----- Original Message ----
From: David Bevan <address@hidden>
To: Graham Asher <address@hidden>; freetype-devel
<address@hidden>
Sent: Tuesday, 7 September, 2010 16:26:24
Subject: RE: [ft-devel] latest patch file for spline flattening
I've now implemented something based on Hain's research and it seems to be
measurably faster than previous FT approaches. I have used Hain's paper (now
available from http://tinyurl.com/HainBez) to provide some sensible heuristics
rather than implement all his stuff in detail, and done so without using square
roots or even any divisions.
First, here are the trace results:
OLD NEW HAIN
average line segs per arc 13.5 11.3 2.1
min line segs per arc 2 1 1
max line segs per arc 32 133 16
average deviation per line seg 0.29 0.44 6.5
min deviation per line seg 0 0 0
max deviation per line seg 22.2 15.8 15.7
By using reasonably accurate heuristics when deciding whether to split the
curve, we create 5.5 x fewer line segments. This cuts down the number of calls
to split_cubic and the number of iterations within render_cubic.
And now the performance results:
In gray_convert_glyph, the time is distributed as follows:
OLD NEW HAIN
render_line 20% 15% 12%
render_cubic 15% 33% 9%
render_scanline 14% 10% 10%
split_cubic 6% 9% 2%
The time spent in these functions has been significantly reduced as a fraction
of processing time.
Including children, we have the following actual times per call for handling
cubic curves:
OLD NEW HAIN
render_cubic 142us 220us 61us
render_cubic is now more than twice as fast as it ever has been.
The effect of the speed-up is even measurable as a 5-10% speed-up of my font
rasterisation program (which is reading and writing data on top of using FT to
do the actual rendering).
These tests are with the same Unicode font as before. I'll run some more test
with Latin-only fonts, though previous testing didn't show any significant
performance differences between Latin and CJK. CJK glyphs just have more cubic
Bezier curves on average, but a Bezier curve is a Bezier curve wherever it
comes
from.
The code is below. I hope I've tried to follow Werner's coding standards as far
as I know what they are.
Thanks.
David %^>
static void
gray_render_cubic( RAS_ARG_ const FT_Vector* control1,
const FT_Vector* control2,
const FT_Vector* to )
{
FT_Vector* arc;
arc = ras.bez_stack;
arc[0].x = UPSCALE( to->x );
arc[0].y = UPSCALE( to->y );
arc[1].x = UPSCALE( control2->x );
arc[1].y = UPSCALE( control2->y );
arc[2].x = UPSCALE( control1->x );
arc[2].y = UPSCALE( control1->y );
arc[3].x = ras.x;
arc[3].y = ras.y;
for (;;)
{
/* Check that the arc crosses the current band. */
TPos min, max, y;
min = max = arc[0].y;
y = arc[1].y;
if ( y < min ) min = y;
if ( y > max ) max = y;
y = arc[2].y;
if ( y < min ) min = y;
if ( y > max ) max = y;
y = arc[3].y;
if ( y < min ) min = y;
if ( y > max ) max = y;
if ( TRUNC( min ) >= ras.max_ey || TRUNC( max ) < 0 )
goto Draw;
/* Decide whether to split or draw */
/* See Hain's paper at http://tinyurl.com/HainBez for more info */
{
TPos dx, dy, L, dx1, dy1, dx2, dy2, s1, s2;
/* dx and dy are x- and y- components of the P0-P3 chord vector */
dx = arc[3].x - arc[0].x;
dy = arc[3].y - arc[0].y;
/* L is an (under)estimate of the Euclidean distance P0-P3 */
L = ( 236 * FT_MAX(labs(dx), labs(dy))
+ 97 * FT_MIN(labs(dx), labs(dy))) >> 8;
/* avoid possible arithmetic overflow below by splitting */
if (L > 32767)
goto Split;
/* s1 is L * the perpendicular distance from P1 to the line P0-P3 */
s1 = labs( dy * (dx1 = arc[1].x - arc[0].x)
- dx * (dy1 = arc[1].y - arc[0].y));
/* max deviation is at least (s1 / L) * sqrt(3)/6 (if v = -1) */
if (s1 > L * (TPos)(FT_MAX_CURVE_DEVIATION / 0.288675))
goto Split;
/* s2 is L * the perpendicular distance from P2 to the line P0-P3 */
s2 = labs( dy * (dx2 = arc[2].x - arc[0].x)
- dx * (dy2 = arc[2].y - arc[0].y));
/* max deviation may be as much as (max(s1,s2)/L) * 3/4 (if v = 1) */
if (FT_MAX(s1, s2) > L * (TPos)(FT_MAX_CURVE_DEVIATION / 0.75))
goto Split;
/* if P1 or P2 is outside P0-P3, split */
if ( dy * dy1 + dx * dx1 < 0
|| dy * dy2 + dx * dx2 < 0
|| dy * (arc[3].y - arc[1].y) + dx * (arc[3].x - arc[1].x) < 0
|| dy * (arc[3].y - arc[2].y) + dx * (arc[3].x - arc[2].x) < 0
)
goto Split;
/* no reason to split */
goto Draw;
}
Split:
gray_split_cubic( arc );
arc += 3;
continue;
Draw:
gray_render_line( RAS_VAR_ arc[0].x, arc[0].y );
if (arc == ras.bez_stack)
return;
arc -= 3;
}
}
- [ft-devel] latest patch file for spline flattening, Graham Asher, 2010/09/06
- RE: [ft-devel] latest patch file for spline flattening, David Bevan, 2010/09/06
- Re: [ft-devel] latest patch file for spline flattening, Graham Asher, 2010/09/06
- RE: [ft-devel] latest patch file for spline flattening, David Bevan, 2010/09/06
- Message not available
- RE: [ft-devel] latest patch file for spline flattening, David Bevan, 2010/09/07
- Re: [ft-devel] latest patch file for spline flattening, GRAHAM ASHER, 2010/09/07
- RE: [ft-devel] latest patch file for spline flattening, David Bevan, 2010/09/07
- Re: [ft-devel] latest patch file for spline flattening, GRAHAM ASHER, 2010/09/07
- Message not available
- RE: [ft-devel] latest patch file for spline flattening, David Bevan, 2010/09/07
- Re: [ft-devel] latest patch file for spline flattening,
GRAHAM ASHER <=
- Message not available
- RE: [ft-devel] latest patch file for spline flattening, David Bevan, 2010/09/07
- Message not available
- Message not available
- RE: [ft-devel] latest patch file for spline flattening, David Bevan, 2010/09/08
- Re: [ft-devel] latest patch file for spline flattening, GRAHAM ASHER, 2010/09/08
- RE: [ft-devel] latest patch file for spline flattening, David Bevan, 2010/09/08
- Re: [ft-devel] latest patch file for spline flattening, Graham Asher, 2010/09/12
- Re: [ft-devel] latest patch file for spline flattening, Werner LEMBERG, 2010/09/12
- Re: [ft-devel] latest patch file for spline flattening, Behdad Esfahbod, 2010/09/12
- RE: [ft-devel] latest patch file for spline flattening, David Bevan, 2010/09/13
- Re: [ft-devel] latest patch file for spline flattening, Graham Asher, 2010/09/12
- Re: [ft-devel] latest patch file for spline flattening, Graham Asher, 2010/09/12