[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Devel] Problems with bbox code and cubic bezier curves
From: |
Tom Kacvinsky |
Subject: |
Re: [Devel] Problems with bbox code and cubic bezier curves |
Date: |
Wed, 25 Apr 2001 18:03:28 -0400 (EDT) |
I would call the new function test_cubic_zero something different:
test_cubic_extrema
because we are testing the extrema of the cubic curve, not the the zeroes of the
cubic curve.
Tom
On Wed, 25 Apr 2001, David Turner wrote:
> Hello all,
>
> sorry for not answering earlier about this specific problem, but I
> was busy exercising my rusty math muscles ;-)
>
> I always thought that direct computations would be slower than
> sub-divisions, given that we can only work with 16.16 values;
> however, due to the recent traffic on this topic lately, I have
> finally committed a new version of BBox_Cubic_Check in "ftbbox.c"
> that performs just that !
>
> The code heavily relies on FT_MulFix, FT_DivFix and FT_SqrtFixed and
> thus runs 10% to 40% slower than the subdivision one on my
> Celeron 300.
>
> See the benchmark program I've used below. I've created two
> executables from it, switching the "#if 0" at line 209 of
> "ftbbox.c" to compare performances. I get:
>
> outline #1
> time = 0.19 cbox = [-37.88 535.32 455.89 786.22]
> time = 6.87 bbox = [115.62 535.32 412.08 672.25]
> outline #2
> time = 0.24 cbox = [100.00 100.00 200.00 200.00]
> time = 2.98 bbox = [100.00 100.00 200.00 179.74]
>
> for the subdivision routine, and:
>
> outline #1
> time = 0.19 cbox = [-37.88 535.32 455.89 786.22]
> time = 7.66 bbox = [115.64 535.32 412.08 672.25]
> outline #2
> time = 0.24 cbox = [100.00 100.00 200.00 200.00]
> time = 4.39 bbox = [100.00 100.00 200.00 179.74]
>
> for the direct computation one..
>
> Note that outline #1 is the one that Ivan sent.. !!
>
> I'm now going to compare the accuracy of each algorithm
> to see wether there's a real interest in keeping the
> direct computations. As already said, I'm more interested
> in pixel-exact bboxes, than "pure" ones :-)
>
> Please let me know if you have any questions, including
> optimisation suggestions regarding the source..
>
> Regards,
>
> - David
>
> ----------------------------------------------------------------------
> /* test_bbox.c - benchmark program for FT_Outline_Get_BBox */
> #include <ft2build.h>
> #include FT_FREETYPE_H
> #include FT_BBOX_H
>
>
> #include <time.h> /* for clock() */
>
> /* SunOS 4.1.* does not define CLOCKS_PER_SEC, so include <sys/param.h>
> */
> /* to get the HZ macro which is the equivalent.
> */
> #if defined(__sun__) && !defined(SVR4) && !defined(__SVR4)
> #include <sys/param.h>
> #define CLOCKS_PER_SEC HZ
> #endif
>
> static long
> get_time( void )
> {
> return clock() * 10000L / CLOCKS_PER_SEC;
> }
>
>
>
>
> /* test bbox computations */
>
> #define XSCALE 1000
> #define XX(x) ((FT_Pos)(x*XSCALE))
> #define XVEC(x,y) { XX(x), XX(y) }
> #define XVAL(x) ((x)/(1.0*XSCALE))
>
> /* dummy outline #1 */
> static FT_Vector dummy_vec_1[4] =
> {
> XVEC( 408.9111, 535.3164 ),
> XVEC( 455.8887, 634.396 ),
> XVEC( -37.8765, 786.2207 ),
> XVEC( 164.6074, 535.3164 )
> };
>
> static char dummy_tag_1[4] =
> {
> FT_Curve_Tag_On,
> FT_Curve_Tag_Cubic,
> FT_Curve_Tag_Cubic,
> FT_Curve_Tag_On
> };
>
> static short dummy_contour_1[1] =
> {
> 3
> };
>
> static FT_Outline dummy_outline_1 =
> {
> 1,
> 4,
> dummy_vec_1,
> dummy_tag_1,
> dummy_contour_1,
> 0
> };
>
>
> /* dummy outline #2 */
> static FT_Vector dummy_vec_2[4] =
> {
> XVEC( 100.0, 100.0 ),
> XVEC( 100.0, 200.0 ),
> XVEC( 200.0, 200.0 ),
> XVEC( 200.0, 133.0 )
> };
>
> static FT_Outline dummy_outline_2 =
> {
> 1,
> 4,
> dummy_vec_2,
> dummy_tag_1,
> dummy_contour_1,
> 0
> };
>
>
> static void
> dump_outline( FT_Outline* outline )
> {
> FT_BBox bbox;
>
> /* compute and display cbox */
> FT_Outline_Get_CBox( outline, &bbox );
> printf( "cbox = [%.2f %.2f %.2f %.2f]\n",
> XVAL( bbox.xMin ),
> XVAL( bbox.yMin ),
> XVAL( bbox.xMax ),
> XVAL( bbox.yMax ) );
>
> /* compute and display bbox */
> FT_Outline_Get_BBox( outline, &bbox );
> printf( "bbox = [%.2f %.2f %.2f %.2f]\n",
> XVAL( bbox.xMin ),
> XVAL( bbox.yMin ),
> XVAL( bbox.xMax ),
> XVAL( bbox.yMax ) );
> }
>
>
>
> static void
> profile_outline( FT_Outline* outline,
> long repeat )
> {
> FT_BBox bbox;
> long count;
> long time0;
>
> time0 = get_time();
> for ( count = repeat; count > 0; count-- )
> FT_Outline_Get_CBox( outline, &bbox );
>
> time0 = get_time() - time0;
> printf( "time = %5.2f cbox = [%.2f %.2f %.2f %.2f]\n",
> ((double)time0/10000.0),
> XVAL( bbox.xMin ),
> XVAL( bbox.yMin ),
> XVAL( bbox.xMax ),
> XVAL( bbox.yMax ) );
>
>
> time0 = get_time();
> for ( count = repeat; count > 0; count-- )
> FT_Outline_Get_BBox( outline, &bbox );
>
> time0 = get_time() - time0;
> printf( "time = %5.2f bbox = [%.2f %.2f %.2f %.2f]\n",
> ((double)time0/10000.0),
> XVAL( bbox.xMin ),
> XVAL( bbox.yMin ),
> XVAL( bbox.xMax ),
> XVAL( bbox.yMax ) );
> }
>
> #define REPEAT 1000000L
>
> int main( int argc, char** argv )
> {
> printf( "outline #1\n" );
> profile_outline( &dummy_outline_1, REPEAT );
>
> printf( "outline #2\n" );
> profile_outline( &dummy_outline_2, REPEAT );
> return 0;
> }
> /* ENDOF test_bbox.c */
>
> _______________________________________________
> Devel mailing list
> address@hidden
> http://www.freetype.org/mailman/listinfo/devel
>
- Re: [Devel] Problems with bbox code and cubic bezier curves, (continued)
- Re: [Devel] Problems with bbox code and cubic bezier curves, Werner LEMBERG, 2001/04/23
- Re: [Devel] Problems with bbox code and cubic bezier curves, Nathan Hurst, 2001/04/23
- Re: [Devel] Problems with bbox code and cubic bezier curves, Werner LEMBERG, 2001/04/24
- Re: [Devel] Problems with bbox code and cubic bezier curves, Tom Kacvinsky, 2001/04/24
- Re: [Devel] Problems with bbox code and cubic bezier curves, Nathan Hurst, 2001/04/24
- Re: [Devel] Problems with bbox code and cubic bezier curves, Tom Kacvinsky, 2001/04/24
- Re: [Devel] Problems with bbox code and cubic bezier curves, David Turner, 2001/04/25
- Re: [Devel] Problems with bbox code and cubic bezier curves,
Tom Kacvinsky <=
- Re: [Devel] Problems with bbox code and cubic bezier curves, Tom Kacvinsky, 2001/04/24
- Re: [Devel] Problems with bbox code and cubic bezier curves, Just van Rossum, 2001/04/24
- Re: [Devel] Problems with bbox code and cubic bezier curves, Tom Kacvinsky, 2001/04/24
RE: [Devel] Problems with bbox code and cubic bezier curves, Ivan Nincic, 2001/04/24
RE: [Devel] Problems with bbox code and cubic bezier curves, Ivan Nincic, 2001/04/24