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 10:45 Hi Paul, Paul Keinanen wrote: > 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 ? Part of the reason for the question is to see just how far into the mud I can drive these issues. Note that the precision of all the math plays a role in the magnitude of the error (and accumulated error) -- not just the "cost" of the operation (space + time). If the curve is constrained to an N.0 x N.0 bit rectangular space (2D curves, not the 3D curves illustrated in the example George posted), then the length of the longest such curve would probably be ~4N. Note, however, that the control points for such curves could conceivably lie beyond that NxN space -- without violating this constraint. I think 2Nx2N would be a safe assumption for them (i.e., this affects *some* of the math as the points must be representable, computationally). Sorting out how far to the right of the binary point to carry computations is a lot harder without constraints on the curves themselves. What I have been trying to do is just code a generic "text book" algorithm and allow me to pass masks to it that essentially discard precision after each (floating point) operation just so I can see how this affects the results FOR SAMPLE CURVES. I.e., an empirical analysis instead of a theoretical one. Hopefully, it will give me a handle on what I can get away with computationally. And, let me experiment with different characteristics of curves to see what aggravates the math the most/least! > How expensive is the sqrt using the hardware (if it exists) or using > the standard run time library (which must also handle special cases) ? Think in terms of "days of yore" :> I.e., I am trying to drive the algorithm to a point where I can get by with just shifts and adds (instead of multiplication, division, etc.). > A huge table could be replaced with a shift, two table lookups, one > multiply and one odd. Ideally, I can find a numeric representation and algorithm that I can push into silicon. I don't see any way to get around the sqrt operator but doing that via CORDIC wouldn't be too expensive if I *really* want to can the whole thing. > 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. I think you can cheat even more *knowing* what subsequent operations *will* be. E.g., postpone the normalization until after the sums have been computed, etc. Small optimizations but they might save a bit of time and precision. > A suitable floating point representation would be 1 byte 2's > complement exponent and 16 bit mantissa (without any hidden bit > tricks). The problem is deciding what constitutes "suitable" from a computational aspect -- as you accumulate "length", you can't sacrifice "resolution". E.g., even if N is only 10-12 bits, you quickly eat up that 16 bits as you are often summing very small segment lengths where you want to *carry* that precision in your sum (yet are forced to discard it as the accumulated length increases and consumes bits in your representation). I'm just trying to get a handle on how *best* to approach the algorithm itself so I can better evaluate the consequences of any representation scheme on the "goodness" of the results. Then, see what it all *costs* :-/
From: D Yuniskis on 16 Jun 2010 11:03 Hi Peter, Peter Dickerson wrote: > "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. Working the numbers from "t" leaves you burning through lots of iterations of "oops, too big!" before you can get to suitably small increments that give you close enough approximations (there has been a LOT of research on this problem as it is so commonly used to represent curves/surfaces :< ). Unless you can constrain the shapes of the curves, there is nothing you can do a priori (in your algorithm) to guarantee that an approach, choice of t, etc. will work. E.g., years ago, I wrote an algorithm to draw lines of constant time-difference for a LORAN-C pen plotter. Basically, families of "concentric" (?) hyperbolae. But, you can't know a priori where on the family of curves you will be operating so the algorithm had to handle all cases. Computing *a* point on the curve took a full second -- you can't compute many such points before the user will grow impatient with you :> But, this computation may just end up telling you, "I can't get to that point with a linear approximation as there is too much curvature here". So, you just *wasted* a second. Watching the algorithm creep into regions of increasing curvature was *painful* (as each successive estimate got "less good") So, you sort out how you can get *some* information from the datum that, hopefully, makes your next actions a *little* bit better -- or, maybe not as painfully *bad*! This algorithm (bezier length) isn't *nearly* as expensive. But, the same applies: make every computation "count" (towards achieving your final goal).
From: Peter Dickerson on 16 Jun 2010 12:39 "D Yuniskis" <not.going.to.be(a)seen.com> wrote in message news:hvap1i$vdt$1(a)speranza.aioe.org... > Hi Peter, > > Peter Dickerson wrote: >> "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. > > Working the numbers from "t" leaves you burning through lots of > iterations of "oops, too big!" before you can get to suitably > small increments that give you close enough approximations > (there has been a LOT of research on this problem as it is so > commonly used to represent curves/surfaces :< ). but probably fewer than the naive approach with the same the same degree of non-contraint on the problem. > Unless you can constrain the shapes of the curves, there is > nothing you can do a priori (in your algorithm) to guarantee > that an approach, choice of t, etc. will work. it isn't an algoritm per se, its an optimization to avoid finer step sizes. > E.g., years ago, I wrote an algorithm to draw lines of > constant time-difference for a LORAN-C pen plotter. Basically, > families of "concentric" (?) hyperbolae. But, you can't know > a priori where on the family of curves you will be operating > so the algorithm had to handle all cases. Computing *a* > point on the curve took a full second -- you can't > compute many such points before the user will grow impatient > with you :> years ago I wrote a rotine to plot mass spectra which involved solving cubics for it data point on an early 68k machine. A couple of thousand data points plotted as fast as anyone would care about, <1s. No hardware FP, avoided sqrt in most cases... > But, this computation may just end up telling you, "I can't > get to that point with a linear approximation as there is > too much curvature here". So, you just *wasted* a second. > Watching the algorithm creep into regions of increasing > curvature was *painful* (as each successive estimate got > "less good") in this case the previous and current result are used to improve the estimate in the hope of going to higher resolution. > So, you sort out how you can get *some* information from > the datum that, hopefully, makes your next actions a *little* > bit better -- or, maybe not as painfully *bad*! > > This algorithm (bezier length) isn't *nearly* as expensive. > But, the same applies: make every computation "count" > (towards achieving your final goal). peter
From: Hans-Bernhard Bröker on 16 Jun 2010 13:24 Tim Wescott wrote: > Since Bezier curves are polynomial, can't you find an exact solution for > each segment and solve it? For the polynomials you can't. The catch is that they're polynomial in the curve parameter, not in one of the coordinates. The exact solution for a third-degree Bezier spline would involve integrating the square root of a 4th-degree polynomial. Closed-form exact solutions for that don't exist.
From: D Yuniskis on 16 Jun 2010 16:21
Hi Peter, Peter Dickerson wrote: >>> 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. >> Working the numbers from "t" leaves you burning through lots of >> iterations of "oops, too big!" before you can get to suitably >> small increments that give you close enough approximations >> (there has been a LOT of research on this problem as it is so >> commonly used to represent curves/surfaces :< ). > > but probably fewer than the naive approach with the same the same degree of > non-contraint on the problem. What's the "naive approach"? The algorithm I outlined drills down to increasingly finer segment sizes until it achieves a desired level of "fit". If the curve is *linear*, the length is computed as the distance between the endpoints! >> Unless you can constrain the shapes of the curves, there is >> nothing you can do a priori (in your algorithm) to guarantee >> that an approach, choice of t, etc. will work. > > it isn't an algoritm per se, its an optimization to avoid finer step sizes. > >> E.g., years ago, I wrote an algorithm to draw lines of >> constant time-difference for a LORAN-C pen plotter. Basically, >> families of "concentric" (?) hyperbolae. But, you can't know >> a priori where on the family of curves you will be operating >> so the algorithm had to handle all cases. Computing *a* >> point on the curve took a full second -- you can't >> compute many such points before the user will grow impatient >> with you :> > > years ago I wrote a rotine to plot mass spectra which involved solving > cubics for it data point on an early 68k machine. A couple of thousand data > points plotted as fast as anyone would care about, <1s. No hardware FP, > avoided sqrt in most cases... Then you weren't working in a resource starved environment. :> (e.g., the plotter ran on a 3MHz 8085, 10KB of code and 512 bytes of RAM -- for the entire instrument!). I've found that failing to meet a ~300ms response time WITH A CLEVER ALGORITHM is a good shirtcuff definition for resource starved. E.g., if I push a button and can perceive the delay in the attendant action, then the code is struggling to do more than it can... >> But, this computation may just end up telling you, "I can't >> get to that point with a linear approximation as there is >> too much curvature here". So, you just *wasted* a second. >> Watching the algorithm creep into regions of increasing >> curvature was *painful* (as each successive estimate got >> "less good") > > in this case the previous and current result are used to improve the > estimate in the hope of going to higher resolution. Yes, as does the algorithm I proposed. If the points you end up with don't look to be a good fit, you subdivide and try again (recurse). Using the first control polygon and the subsequent subdivided points as upper and lower limits on the "actual" value lets you come up with a numerical factor that bounds your error: i.e., the length is in [a,b] - which you can examine at run time and use to decide if you need to further subdivide. Watching how a and b vary with each refinement lets you see when you are just spinning your wheels. >> So, you sort out how you can get *some* information from >> the datum that, hopefully, makes your next actions a *little* >> bit better -- or, maybe not as painfully *bad*! >> >> This algorithm (bezier length) isn't *nearly* as expensive. >> But, the same applies: make every computation "count" >> (towards achieving your final goal). |