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

[David Turner]

Hi Nathan,

Nathan Hurst a écrit :
> 
> Toby pointed out that the bounding box of a bezier can be computed by
> computing the max and min of the x and y coords of the parametric equation
> of the curve, which for a cubic would occur at either the end points or
> the solutions of:
> t^2[A-3B-C-3D] + t[2B+6D] + [C-3D]
> where A,B,C,D are the x or y coords of the control points.
> 
> This requires 2 sqrts per curve, but I suspect that that would be cheaper
> than an unknown number of splits?
> 
There are _two_ reasons why the splits are used in these functions:

  - because computing square roots with 16.16 fixed numbers is hardly
    fast, and brings its own set of problems regarding rounding/accuracy

  - because, ideally, the function should return the bbox values that
    correspond to what would _really_ be rasterized on the screen if
    FT_Outline_Render is called.

    otherwise, you could compute a bbox that is 1 pixel wider/shorter
    than the equivalent rasterization, which would potentially create
    strange clipping artefacts..

I don't deny that the current code has some problems. For example,
Werner seems to think that the arc stack can overflow. I seem to
recall when I designed this code _long_ ago that this case couldn't
happen for some un-remembered properties of the split functions,
but it definitely needs a look.

One obvious solution is to simply limit the stack growth manually
though :-)

Note that the same algorithm is used by the rasterizers (in theory),
and these have never shown any kind of problem with the bezier stack..

And of course, there's the problem of accuracy/rounding..

Regards,

- David