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 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 ;-)
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
The distance travelled by a function f(t) from t=t0 to t=t1 is given by:
length(f(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,
but it is usually a good ballpark estimate.
With the cubic Bezier curve function:
We get the following results when combining:
length(B(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:
(remove the obvious prefix to reply by mail)