Re: Bezier lengths w/o lots of resources



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