[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [ft-devel] Fast bisecting BBox_Cubic_Check
From: |
Alexei Podtelezhnikov |
Subject: |
Re: [ft-devel] Fast bisecting BBox_Cubic_Check |
Date: |
Fri, 15 Feb 2013 21:16:32 -0500 |
Thanks to Werner, benchmarking FT_Outline_Get_BBox is now easy using
ftbench. I've added a rotation by 30 degrees to really challenge it.
These are results.
With the old code:
$ bin/ftbench -s 24 -b ej /usr/share/fonts/default/Type1/n019003l.pfb
Get_CBox : 0.257 us/op
Get_BBox : 1.821 us/op
$ bin/ftbench -s 24 -b ej /usr/share/fonts/default/Type1/n021003l.pfb
Get_CBox : 0.326 us/op
Get_BBox : 2.632 us/op
With the new code:
$ bin/ftbench -s 24 -b ej /usr/share/fonts/default/Type1/n019003l.pfb
Get_CBox : 0.245 us/op
Get_BBox : 0.915 us/op
$ bin/ftbench -s 24 -b ej /usr/share/fonts/default/Type1/n021003l.pfb
Get_CBox : 0.327 us/op
Get_BBox : 1.350 us/op
So the new code is twice as fast.
Reposting the code with fixed comments...
static void
BBox_Cubic_Check( FT_Pos p1,
FT_Pos p2,
FT_Pos p3,
FT_Pos p4,
FT_Pos* min,
FT_Pos* max )
{
FT_Pos q1, q2, q3, q4;
q1 = p1;
q2 = p2;
q3 = p3;
q4 = p4;
/* one of the off-points must be above the current maximum */
/* for the conic segment to possibly cross the threshold */
while ( q2 > *max || q3 > *max )
{
/* determine which half contains the maximum and split */
if (q1 + q2 > q3 + q4 ) /* first half */
{
q4 = q4 + q3;
q3 = q3 + q2;
q2 = q2 + q1;
q4 = ( q4 + 2 * q3 + q2 ) / 8;
q3 = ( q3 + q2 ) / 4;
q2 = q2 / 2;
}
else /* second half */
{
q1 = q1 + q2;
q2 = q2 + q3;
q3 = q3 + q4;
q1 = ( q1 + 2 * q2 + q3 ) / 8;
q2 = ( q2 + q3 ) / 4;
q3 = q3 / 2;
}
/* check if either end reached the maximum */
if ( q1 == q2 )
{
*max = q1;
break;
}
if ( q3 == q4 )
{
*max = q4;
break;
}
}
q1 = p1;
q2 = p2;
q3 = p3;
q4 = p4;
/* one of the off-points must be below the current minimum */
/* for the conic segment to possibly cross the threshold */
while ( q2 < *min || q3 < *min )
{
/* determine which half contains the minimum and split */
if (q1 + q2 < q3 + q4 ) /* first half */
{
q4 = q4 + q3;
q3 = q3 + q2;
q2 = q2 + q1;
q4 = ( q4 + 2 * q3 + q2 ) / 8;
q3 = ( q3 + q2 ) / 4;
q2 = q2 / 2;
}
else /* second half */
{
q1 = q1 + q2;
q2 = q2 + q3;
q3 = q3 + q4;
q1 = ( q1 + 2 * q2 + q3 ) / 8;
q2 = ( q2 + q3 ) / 4;
q3 = q3 / 2;
}
/* check if either end reached the minimum */
if ( q1 == q2 )
{
*min = q1;
break;
}
if ( q3 == q4 )
{
*min = q4;
break;
}
}
}
- [ft-devel] Fast bisecting BBox_Cubic_Check, Alexei Podtelezhnikov, 2013/02/12
- Re: [ft-devel] Fast bisecting BBox_Cubic_Check,
Alexei Podtelezhnikov <=
- Re: [ft-devel] Fast bisecting BBox_Cubic_Check, Alexei Podtelezhnikov, 2013/02/23
- Re: [ft-devel] Fast bisecting BBox_Cubic_Check, Werner LEMBERG, 2013/02/24
- Re: [ft-devel] Fast bisecting BBox_Cubic_Check, Alexei Podtelezhnikov, 2013/02/24
- Re: [ft-devel] Fast bisecting BBox_Cubic_Check, Werner LEMBERG, 2013/02/24
- Re: [ft-devel] Fast bisecting BBox_Cubic_Check, Alexei Podtelezhnikov, 2013/02/25
- Re: [ft-devel] Fast bisecting BBox_Cubic_Check, Werner LEMBERG, 2013/02/25