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

[Nathan Hurst]

On Mon, 23 Apr 2001, Werner LEMBERG wrote:

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

Yes, and sqrt is pretty cheap.  you can do it something like 100
instructions.  Just look for code snippets (I found one here that is
written optimised pentium code that has a longest path of about 20
instructions.  Not that we would want to use asm).

The basic method is:

given A
find top 1 bit = tb 
get top 8 bits eb = A >> (tb - 8)
lookup sqrt approx from table = sqroot[eb]
shift to half way to top bit x = (sqroot[eb] << (tb/2)-8)
feed to newton-raphson approximation: 1/2(x+A/x)
this converges quadratically, so with a good initial guess(the shift and
lookup) we should have a sqrt in vert few cycles.

what could be easier?

njh