[Devel] 8.16 and 16.16 [was: Problems with bbox code and cubic bezier curves]

[Tom Kacvinsky]

My worries lie elsewhere.  The code is actually shifting the whole 16.16 number
down by whatever amount is needed to get 8.16 numbers.  I cannot overlook the
fact we are using 16.16 numbers, because the FT_*Fix functions assume 16.16
input for some (but not all) of the arguments.

At least that is what I get out of the code.

Suppose we need to shift right by N bits to make each of a, b, and c have 24 bit
precision.  This means the crucial fractional part is losing N bits, and the
integer part has N bits stuffed into the fractional part.

For instance, if we need to shift right by 8 bits to make each of a, b, and c
fit into 24 bits of data, and a = FFFF8000 (-1.5), then a >> 8 is FFFF80.  But
since these are stuffed into signed integer variables and the sign bit is not
lost when bit shifting signed integers, this is really FFFFFF80 for 32 bit
integers, and FFFFFFFFFFFFFF80 for 64 bit integers.  As a 16.16 number, this
-0.0020 decimal.  This doesn't look right to me!

Unless I misunderstood the FT_*Fix functions.  I thought that FT_DivFix assumed
16.16 numbers, etc...

It wasn't precision I was worried about -- it was data "corruption" I was 
worried
about.

What am I missing here?  The code works, as demonstrated by the profiling code
you submitted, so I must have a few misfiring synapses!

Tom

On Thu, 26 Apr 2001, David Turner wrote:

> Hi Tom,
>
> >
> > Hmmm... I guess I should have been more precise.  If the control points
> > for a cubic Bezier curve are (x1,y1) -- (x4,y4) and t in [0,1], then the
> > parametric equations are:
> >
> >   x(t) = (substitute x_i for P_i in the equations below)
> >
> >   y(t) = (substitute y_i for P_i in the equations below)
> >
> > Correct?
> >
> Definitely, and of course, z(t) if you're in 3D ;-)
>
> > The only question I have is about normalising the 16.16 fixed floats to 8.16
> > fixed floats.  That only allows for integer parts between -128 and +127!
> >
> First of all, we're not normalising 16.16 fixed floats, but arbitrary
> 32-bit values.. (well, to be picky, that's probably 30-bits due to the
> multiplications and adds required to compute a, b, c).
>
> Second, we use 8 bits of integer part, but the fractional 16 bits are
> important in the rest of the computation. This means that we're really
> using 24 bits of precision to compute the zeros of our quadratic equation.
>
> That's largely enough in my opinion given that t is in (0..1) and is
> expressed with 16 bits anyway..
>
> If you need more accuracy, using doubles is the pratical solution :-)
>
> I have not the courage to compute the errors produced by the use of
> fixed-point arithmetic. It certainly wouldn't be trivial to compute,
> and I doubt that it would be too important... probably about 0.025%
> or even less..
>
> Regards,
>
> - David
>