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

[Tom Kacvinsky]

Hi,

On Mon, 23 Apr 2001, Werner LEMBERG wrote:

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

Well, I have heard of points of inflection (where a curve switches concavity, or
more to the point, from convex to concave), and I know that maxima and minima of
differentiable functions on closed bounded intervals occur at endpoints or zeros
of the derivative.  But I have never heard of "point of inflected slope."  I
assume that this means points where the slope changes sign.  Which can be found
by finding the zeroes of the derivative and testing to make sure the derivative
changes sign in an open interval around that point.  And splitting a Bezier arc
at such a point would ensure monoticity on the resulting sub-arcs.

I hope this is what Richard meant -- find the zeros of the first deriviative,
because at an inflection point, a curve does not necessarily change monoticity.
In fact, I *believe* (but have no theorem to cite) that a curve cannot have a
local max/min at a point of inflection, and vice versa.

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

Given that Richard writes *quadratic* root-finder, he must be talking about
finding zeroes of the first deriviative.  So all is well...

Tom