[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Devel] Problems with bbox code and cubic bezier curves
From: |
Nathan Hurst |
Subject: |
Re: [Devel] Problems with bbox code and cubic bezier curves |
Date: |
Tue, 24 Apr 2001 10:49:45 +1000 (EST) |
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
- Re: [Devel] Problems with bbox code and cubic bezier curves, (continued)
- Re: [Devel] Problems with bbox code and cubic bezier curves, Tom Kacvinsky, 2001/04/23
- Re: [Devel] Problems with bbox code and cubic bezier curves, Toby J Sargeant, 2001/04/23
- Re: [Devel] Problems with bbox code and cubic bezier curves, David Turner, 2001/04/23
- Re: [Devel] Problems with bbox code and cubic bezier curves, Tom Kacvinsky, 2001/04/23
- Re: [Devel] Problems with bbox code and cubic bezier curves, David Turner, 2001/04/23
- Re: [Devel] Problems with bbox code and cubic bezier curves, Tom Kacvinsky, 2001/04/23
- Re: [Devel] Problems with bbox code and cubic bezier curves, Tom Kacvinsky, 2001/04/23
- Re: [Devel] Problems with bbox code and cubic bezier curves, Werner LEMBERG, 2001/04/23
- Re: [Devel] Problems with bbox code and cubic bezier curves,
Nathan Hurst <=
- Re: [Devel] Problems with bbox code and cubic bezier curves, Werner LEMBERG, 2001/04/24
- Re: [Devel] Problems with bbox code and cubic bezier curves, Tom Kacvinsky, 2001/04/24
- Re: [Devel] Problems with bbox code and cubic bezier curves, Nathan Hurst, 2001/04/24
- Re: [Devel] Problems with bbox code and cubic bezier curves, Tom Kacvinsky, 2001/04/24
- Re: [Devel] Problems with bbox code and cubic bezier curves, David Turner, 2001/04/25
- Re: [Devel] Problems with bbox code and cubic bezier curves, Tom Kacvinsky, 2001/04/25
- Re: [Devel] Problems with bbox code and cubic bezier curves, Tom Kacvinsky, 2001/04/24
- Re: [Devel] Problems with bbox code and cubic bezier curves, Just van Rossum, 2001/04/24
- Re: [Devel] Problems with bbox code and cubic bezier curves, Tom Kacvinsky, 2001/04/24
RE: [Devel] Problems with bbox code and cubic bezier curves, Ivan Nincic, 2001/04/24