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 16 Jun 2010 01:32 Hi Walter, Walter Banks 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. Yes, there are lots of academic papers, forum discussions, etc. re: this topic. But, they tend to be looking for general solutions *and* use "general computations" in getting to them! As with most things embedded, you (I) have a specific application domain to address. You don't need a general solution. There are often constraints that apply which can be exploited to give you an edge in solving the problem more "practically". So, finding the right combination of "tricks" is the name of the game :>
From: D Yuniskis on 16 Jun 2010 01:44 Hi Tim, Tim Wescott wrote: > On 06/14/2010 06:23 PM, D Yuniskis wrote: > >> 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? You can walk the curve (varying t over [0..1]) but that gives you more detail than you need -- and at a very high cost. So, you approach it as a simpler problem -- find some convenient points (easy to compute) that you know lie on the curve (*hoping* they are far enough apart that you can quickly progress along the length of the curve) and hope that consecutive points fit the curve "close enough" that you can skip everything in the middle :> Since you are then trying to do a piecewise linear approximation to the curve, you need to be able to compute the lengths of each of those segments (which is expensive "in general" and, since you need to use floats/doubles to get any accuracy, it's *really* expensive IN PARTICULAR!) So, you want to make sure *every* calculation you perform is used wisely -- even if the approximation(s) aren't currently good enough. A lot of the published algorithms concentrate on expressing the algorithm instead of expressing it in an efficient way. > (This could be a naive question -- I haven't done the math to see how > complicated the answer is).
From: D Yuniskis on 16 Jun 2010 01:51 Hi Walter, Walter Banks wrote: > 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. Yeah, the problem is that you can't (?) constrain the locations of the control points (shape of the curve) to ensure a particular maximum curvature, etc. As a result, you can end up with *very* short segments in order to keep the area between segment and curve small (i.e., good fit). So, you end up needing lots of bits to the right of the binary point. OTOH, you can't (?) constrain the total length of the curve so you can also need lots of bits to the *left* of the binary point. I.e., doing this on a machine with hardware floating point support is *much* easier than on a platform where that is implemented in a *library*! :<
From: Paul Keinanen on 16 Jun 2010 02:08 On Mon, 14 Jun 2010 18:23:44 -0700, D Yuniskis <not.going.to.be(a)seen.com> wrote: >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! :< ) What kind of representation are you using (number of bits, binary point location) and how many bits should the length have ? How expensive is the sqrt using the hardware (if it exists) or using the standard run time library (which must also handle special cases) ? A huge table could be replaced with a shift, two table lookups, one multiply and one odd. If the sqrt argument is in floating point format, the exponent is divided by 2 and the normalized could go through a table lookup. A single step normalization (increment exponent by one, shift right mantissa by one bit) may be required. A suitable floating point representation would be 1 byte 2's complement exponent and 16 bit mantissa (without any hidden bit tricks).
From: Peter Dickerson on 16 Jun 2010 02:13
"Walter Banks" <walter(a)bytecraft.com> wrote in message news:4C1828BA.DEF4C9(a)bytecraft.com... > > > 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. Yes, but that's like numerically integrating exp(x) step by step because you don't know how to do integration using algebra. Of course, it may be that its much more like exp(-x^2)... Even for numeric integration can't you use a Romberg style scheme: You can compute the length exactly by summing infinitely small linear segments. Call this L0. If instead you use finite step size h of the control parameter then the approximation will be L[h] = L0+O(h^n) for some n (n is typically an integer but haven't checked for Beziers). Let's say L[h] = L0 + k*(h^n) + O(h^m) with m > n the do the integration again with a different step size. For simplicity, say 2h, which has the advantage that it can share much of the calculation. Then we'd expect L[2h] = L0 + k*((2h)^n) + O(h^m). so now (2^n)*L[h] - L[2h] = ((2^n)-1)*L0 + O(h^m) i.e. h^n term has been cancelled. So a new estimate of L0 is L0 = ((2^n)*L[h] - L[2h])/((2^n)-1) + O(h^m) which converges more quickly with reducing h than does the original. Note that this says nothing about how you calculate the length only about how to get a better estimate from two poor estimates. The point being that the size of h you can get away with can be much larger and so the overall amount of work can be (much) less. Still, I'm with Tim on this one. Try some math(s) first. Peter |