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

[Werner LEMBERG]

> > I don't deny that the current code has some problems. For example,
> > Werner seems to think that the arc stack can overflow.

I don't `think'.  This was a bug report. :-)

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

I withdraw my O(n) stuff -- don't talk about things which you don't
know exactly...

Instead, I'm citing my questions to Richard and his answers.

  W: What is the maximal number of bisections of an arbitrary
     third-order Bézier curve to get only monotonous arcs?  Is there a
     limit at all (my feelings say yes)?

  R: The slope of a cubic Bézier is a quadratic having two roots.
     Each root can be a point where the monotonicity breaks.  Thus the
     maximal number of optimally chosen pieces is three.

  W: Yes, `optimally chosen'.  But I'm mainly interested in
     `bisectioned' segments (doing the usual (x1 + x2)/2 stuff with
     the control points).  Tests have shown that more than 11 of such
     operations can be necessary, and I'm curious whether there is a
     reliable limit since I want to avoid recursion if possible.  Or
     maybe there is a simple and fast computer logic without taking
     roots to find better split points?

  R: There is no such limit.  To ensure monotonicity, you MUST bisect
     EXACTLY AT the point of the inflected slope.  In the worst case,
     that point can be where any number of bisections will not find
     it.

     You MUST solve for the inflection points, you cannot simply
     approximate them numerically.  What could be simpler than finding
     them with a closed form quadratic root-finder?


    Werner