Re: [Devel] Error in new FT_SqrtFixed?

[Tom Kacvinsky]

OK, I did some more investigative footwork.

I used David's supplied test_bbox.c file, but I made a change.  He was used
the following:

#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 ) )

  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 )
  };

I used:

#define  XVAL(x)   ( (x) / 65536.0 )

  static FT_Vector  dummy_vec_1[4] =
  {
    { (FT_Int32)0x0198E93DL , (FT_Int32)0x021750FFL },  /* 408.9111, 535.3164 */
    { (FT_Int32)0x01C7E312L , (FT_Int32)0x027A6560L },  /* 455.8887, 634.3960 */
    { (FT_Int32)0xFFDA1F9EL , (FT_Int32)0x0312387FL },  /* -37.8765, 786.2207 */
    { (FT_Int32)0x00A49B7EL , (FT_Int32)0x021750FFL }   /* 164.6074, 535.3164 */
  };

As you can see, I used a full 16.16 representation.  That is where the problem
lie.  If I changed the code back to what David originally supplied, I got the
correct results.

If I use my changes, the bounding box for that curve is way off.

The problem is in the new bbox calculation code.  I made a change so that each
of a, b, and c are shifted right by 8 bits.  I then got the correct results.

I guess the loop to determine the bit shift amount was not doing the right
thing with full 16.16 numbers, but was good enough for the numbers that
David provided.

So, what shall we do?

Tom

On Thu, 26 Apr 2001, Tom Kacvinsky wrote:

> I'd like to rescind this...  It wasn't the optimizations to FT_SqrtFixed that
> were throwing my results off.  More on this later, when I have a more detailed
> analysis of the problem.
>
> On Thu, 26 Apr 2001, Tom Kacvinsky wrote:
>
> > However, there seems to be an error with the new optimizations.  At least I 
> > am
> > not getting the correct results with the new FT_SqrtFixed.
> >
> > On Thu, 26 Apr 2001, David Turner wrote:
> >
> > > 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
> > >
> > > _______________________________________________
> > > Devel mailing list
> > > address@hidden
> > > http://www.freetype.org/mailman/listinfo/devel
> > >
> >
> >
> > _______________________________________________
> > Devel mailing list
> > address@hidden
> > http://www.freetype.org/mailman/listinfo/devel
> >
>
>
> _______________________________________________
> Devel mailing list
> address@hidden
> http://www.freetype.org/mailman/listinfo/devel
>