Bezier lengths w/o lots of resources
in [Embedded]
|
Prev: Simple hack to get $600 to your home.
Next: Applied Computing 2010: 1st call extension until 25 June 2010
From: D Yuniskis on 15 Jun 2010 18:24 Hi Walter, Walter Banks wrote: > > D Yuniskis wrote: > >> 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? > > You might want to talk to some of the game groups like gamedev.net for algorthms > > http://www.gamedev.net/community/forums/topic.asp?topic_id=313018 Ah, good point! I have some friends in that industry. I'll see if they have any better pointers (note that they tend to have *lots* of resources, relatively speaking, to throw at the problem... :< )
From: Walter Banks on 15 Jun 2010 19:07 D Yuniskis wrote: > Hi Walter, > > Walter Banks wrote: > > > > D Yuniskis wrote: > > > >> 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? > > > > You might want to talk to some of the game groups like gamedev.net for algorthms > > > > http://www.gamedev.net/community/forums/topic.asp?topic_id=313018 > > Ah, good point! I have some friends in that industry. I'll > see if they have any better pointers (note that they tend to > have *lots* of resources, relatively speaking, to throw at > the problem... :< ) Lots of resources but not much time to do it. :) They know a lot about what is good enough for the problem. The link I posted is of a Bezier length discussion. Regards, Walter.. -- Walter Banks Byte Craft Limited http://www.bytecraft.com
From: Tim Wescott on 15 Jun 2010 20:48 On 06/14/2010 06:23 PM, D Yuniskis wrote: > Hi, > > 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 ;-) Since Bezier curves are polynomial, can't you find an exact solution for each segment and solve it? Or is that what you find too expensive? (This could be a naive question -- I haven't done the math to see how complicated the answer is). -- Tim Wescott Control system and signal processing consulting www.wescottdesign.com
From: Walter Banks on 15 Jun 2010 21:28 Tim Wescott wrote: > Since Bezier curves are polynomial, can't you find an exact solution for > each segment and solve it? Or is that what you find too expensive? > > (This could be a naive question -- I haven't done the math to see how > complicated the answer is). > The math everyone is avoiding is for each line segment Xl = Xs-Xe; // X end points Yl = Ys-Ye; // Y end points len = sqrt( (Xl * Xl) + (Yl *Yl)); For lots of short segments. w..
From: Nobody on 15 Jun 2010 23:43
On Tue, 15 Jun 2010 17:48:23 -0700, Tim Wescott wrote: > Since Bezier curves are polynomial, can't you find an exact solution for > each segment and solve it? There isn't a closed-form solution for a cubic (or higher) Bezier curve. The length of a curve is the integral of the length of the tangent vector, sqrt(x'(t)^2+y'(t)^2). For a cubic curve, x'(t) and y'(t) are quadratic, giving sqrt(f(t)) where f(t) is quartic. For a quadratic Bezier curve, the tangent length is the square root of a quadratic expression, for which the integral has a closed-form solution. |