[Devel] Re: bug in BBox_Conic_Check?

[David Turner]

Hi Werner,

> 
> David,
> 
> where does line 124 in ftbbox.c come from?
> 
> According to my computations, I get:
> 
>   f(t)  = a(1-t)² + 2bt(1-t) +ct²
>         = t²(a-2b+c) + t(-2a+2b) + a
> 
>   f'(t) = 2t(a-2b+c) + (-2a+2b) = 0
> 
>       t =  (a-b) / (a-2b+c)
>     1-t = (-b+c) / (a-2b+c)
> 
> Substitution yields
> 
>   f(t) = [a(-b+c)² + 2b(a-b)(-b+c) + c(a-b)²] / (a-2b+c)²
>        = (-ab²+ac²+2b³-b²c+a²c-2abc) / (a-2b+c)²
>        = [-b²(a-2b+c) + ac(a-2b+c)] / (a-2b+c)²
>        = (-b²+ac) / (a-2b+c)
> 
> This is not (b²-2ab+a²) / (a-2b+c) as in line 124.
> 

Hummm.. you're right, and it's been a bit hard to understand
where this bugs comes from. I believe that the line should
read:

   y1 = y3 = y1 - FT_MulDiv( y2 - y1, y2 - y1, y1 - 2*y2 + y3 );

that's the only way to avoid using 64-bits values to compute
the sum "-b²+ac". and the proof is:

  f(t) = t²(a-2b+c) -2t(a-b) + a

let  "X = a-b" and "Y = a-2b+C", we have

  f(t)  = t²Y -2tX + a
  f'(t) = 2( tY - X )   => t0 = X/Y

  f(t0) = Y(X/Y)² - 2X²/Y + a
        = a - X²/Y

I've commited the change to the CVS..

> 
> PS: As already pointed out on the devel@ list, BBox_Cubic_Check() can
>     fail due to stack overflow.  After some discussion with Richard
>     Kinch, *the* expert on Bézier curves, I strongly believe that we
>     have to solve the first derivate (i.e., a quadratic equation)
>     directly to get the extrema, since bisection can fail miserably
>     resp. converge very slowly under certain circumstances.

I agree. At the time were this function was written, there was no
fixed square root function in FT2. Maybe this can be solved now that
we have FT_SqrtFixed ?? As you probably guess, I don't have much
time on it..

Thanks,

- David