# Re: Bezier lengths w/o lots of resources

*From*: "Boudewijn Dijkstra" <sp4mtr4p.boudewijn@xxxxxxxxx>*Date*: Thu, 01 Jul 2010 16:17:35 +0200

Op Tue, 15 Jun 2010 03:23:44 +0200 schreef D Yuniskis

<not.going.to.be@xxxxxxxx>:

Not the *ideal* group for this post -- but the "right"

group would undoubtedly throw *way* more resources at

the solution... resources that I don't *have*! :<

I'm looking for a reasonably efficient (time + space)

technique at approximating Bezier curve lengths from

folks who may have already "been there"...

I was thinking of subdividing the curve per De Casteljau.

Then, computing the lengths of the individual segments

obtained therefrom. Summing these as a lower limit

on the curve length with the length of the control

polygon acting as an upper limit.

But, that's still a lot of number crunching! If I work

in a quasi fixed point representation of the space, it

still leaves me with lots of sqrt() operations (which

are hard to reduce to table lookups in all but a trivial

space! :< )

So, obviously, I need a "trick". Something to throw away

that gives me a "good enough" answer -- the sort of thing

the "ideal" group wouldn't consider settling for ;-)

Suggestions? Pointers?

Last week it dawned to me that any function, whether real or complex,

travels a path of which the distance can be calculated. (Except at

vertical asymptotes.) After some dabbling I came up with the following

definition.

The distance travelled by a function f(t) from t=t0 to t=t1 is given by:

length(f(t), t0, t1) =

int(abs(diff(f(t),t)),t=t0..t1)

where int=integrate, abs=absolute, diff=derivative

Note 1: the use of abs() yields sqrt() operations if f(t) is complex.

Note 2: for a complex function z(t)=x(t)+j*y(t):

length(z(t), t0, t1) != length(x(t), t0, t1) + length(y(t), t0, t1)

but it is usually a good guess for the upper bound.

Note 3: for the same complex function z(t):

length(z(t), t0, t1) != sqrt(length(x(t), t0, t1)^2 + length(y(t), t0,

t1)^2)

but it is usually a good ballpark estimate.

With the cubic Bezier curve function:

B[3](t) =

(1-t)^3*P[0]+3*(1-t)^2*t*P[1]+3*(1-t)*t^2*P[2]+t^3*P[3]

We get the following results when combining:

length(B[3](t), 0, 1) =

Int(abs(3*(1-t)^2*P[0]+6*(1-t)*t*P[1]-3*(1-t)^2*P[1]+3*t^2*P[2]-6*(1-t)*t*P[2]-3*t^2*P[3]),

t=0..1)

Unfortunately my old copy of Maple wasn't able to simplify this any

further. But the result can be calculated using numerical integration.

Note 4: if you know the roots of the x- and y-function (where the

derivative is zero), you can set up interpolation points.

--

Gemaakt met Opera's revolutionaire e-mailprogramma:

http://www.opera.com/mail/

(remove the obvious prefix to reply by mail)

.

- Prev by Date:
**Re: a hobby class on microcontrollers** - Next by Date:
**Re: Position independent code with position dependent data ?** - Previous by thread:
**Re: Bezier lengths w/o lots of resources** - Next by thread:
**Re: Bezier lengths w/o lots of resources** - Index(es):