Re: [Devel] Problems with bbox code and cubic bezier curves

[David Turner]

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 */