[Devel] Summary of BBox computation issues

[David Turner]

Hello,

  I've just commited some minor improvements to "ftbbox.c" and
  "ftcalc.c" and would like to sum up what I've found so far:

  I. Regarding algorithm performance:

    the direct computation seems to benefit greatly from the
    optimisation of FT_SqrtFixed with an algorithm that doesn't
    use multiplications.. (see "ftcalc.c")

    Actually, for compilers with 64-bit integers, the direct
    computation routines now seem to run as fast as the subdivision
    one, or even slightly faster :-)

    Without 64-bit integers, the slower FT_MulFix and FT_DivFix
    slow the routine significantly (10% to 50% slower than the
    subdivision routine, depending on the outline.)

    The benchmark seems to show that computing a bbox is about
    20 times slower than computing its cbox, when the boxes
    differ.. even with the best algorithm !!


  II. Regarding pixel-correct bbox computations:

    After careful examination, it appears that the two
    scanline-converters that come with FreeType do not use
    the same accuracy when performing bezier arc splits:

     - the monochrome raster uses 10 and 6 bits of precision
       to express point coordinates, depending on the
       "outline.high_precision" flag. bezier sub-division
       is performed either through

     - the anti-aliased raster uses 8 bits of precision, as
       well as an adaptive bezier sub-division algorithm
       based on the arc's dimensions..

    it is thus not possible to compute pixel-exact computations
    without using the exact-same subdivision algorithm.

    This is considered too much trouble for too little benefit,
    so let's forget about having pixel correct bboxes..

As usual, any comment is welcomed..

Cheers,

- David