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

[Tom Kacvinsky]

Hi David,

>
> 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.
>

Werner, or me?  Yes, the arc stack can overflow...  There are only 33 slots open
in the arc stack, which, according to the code, means we can only go through 9
iterations:

  33 slots available

  4 slots taken for the first iteration
  3 slots taken for each subsequent iteration

  33 = 3(number of subsequent iterations) + 4
  number of subsequent iterations = 9

Now, Werner posted a statement from Richard Kinch that a Bezier cubic can be
split into monotonic cubic Beziers (or at least that is what I thought was
said), but there are some arcs which, when split in such a fashion, result in
o(n) (is that supposed to be O(n)?) sub arcs, where n is the width or height of
the orignal curve's bbox (cbox?).  That could be a *lot* of subarcs, or at least
more than 9 iterations allows for.

> 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..
>

Well, that is interesting.  Isn't the cbox good enough for the rasterizers?

Tom