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: Paul Keinanen on 16 Jun 2010 16:54 On Wed, 16 Jun 2010 07:45:51 -0700, D Yuniskis <not.going.to.be(a)seen.com> wrote: >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! :< ) >> 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. Adding/subtracting is easy to do in integer/fixed point arithmetic, but very nasty to do in floating point format due to demoralization and normalization stages. Also integer/fixed to float conversion is nasty due to normalization. Doing sqrt((Xs-Xe)^2+(Ys-Ye)^2) might be easiest to implement by doing the differences in integer, take abs of both (to reduce table size) and use a table for squaring and using integer arithmetic for the sum and then convert to float for sqrt, especially if the result is needed in floating point representation. Single cycle normalisation/denormalisation in hardware requires a barrel shifter capable of shifting multiple bits left or right. For normalization (to [0.5..1.0] or to [1..2]) a priority encoder is required to detect the highest bit set, so that the correct shift can be applied in the barrel shifter. In order to take the sqrt from a integer/fixed point argument and generate floating point sqrt, group two bits at a time starting from the binary point (left and right), take OR of each 2 bit group and feed the outputs to a priority encoder and use the barrel shifter to normalize the result to [0.25..1.0] or [1..4]. Use the normalized mantissa for table lookup and use the shift count (after shifting out the LSB) as the exponent. > >> 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). The floating point representation is very bad if you try to accumulate small increments to a huge sum. Sooner or later adding a small value does not change the sum at all. If you really have to use such incremental system, at least accumulate (say 100..1000) samples into a temporary sum, before adding to a final sum.
From: Bob on 16 Jun 2010 17:18 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"... if you're also drawing the curves, have the drawBezier() function add it up. Adjacent pixels in x or y are worth 1; diagonally adjacent are worth root 2. Almost free, computationally, but is it accurate enough? Bob
From: George Neuner on 16 Jun 2010 17:57 On Tue, 15 Jun 2010 15:23:45 -0700, D Yuniskis <not.going.to.be(a)seen.com> wrote: >Hi George, > >George Neuner wrote: >> On Mon, 14 Jun 2010 18:23:44 -0700, D Yuniskis >> <not.going.to.be(a)seen.com> wrote: >> >>> I'm looking for a reasonably efficient (time + space) >>> technique at approximating Bezier curve lengths from >>> folks who may have already "been there"... >>> >>> 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? >> >> I don't know if the code works but here's possible solution that >> doesn't look too involved: >> >> http://www.gamedev.net/community/forums/viewreply.asp?ID=2003096 > >That's a pretty straightforward "subdivide-and-sum-chords" >approach. Note that it hides lots of expensive math! > > flt l0 = p0.length(); > flt l1 = p1.length(); > flt l3 = p3.length(); > >(i.e., the "length" method computes euclidean distance... >two mults and a sqrt!) What chip? This is an article about fast computation of curve sections using fixed point. The discussion is quite interesting. http://www.mactech.com/articles/mactech/Vol.05/05.01/BezierCurve/ George
From: Peter Dickerson on 17 Jun 2010 05:41 "D Yuniskis" <not.going.to.be(a)seen.com> wrote in message news:hvbblq$2d9$1(a)speranza.aioe.org... > 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! Yes. Perhaps there is a better word than naive. It's poor on rounding error control and converges slowly. As a result there are a lot of calculations that are thown away. OK, I've had chance to try this out in the case of a cubic. Start with just the end points then subdivide in smaller steps of the control parameter. For simplicity one line segment then two, four etc. Then printed out the summed length and the romberg estimate. In the example below the path happens to be exactly 2.0, making it easy to see the errors. Control points (0.000000,0.000000) (0.000000,-1.000000) (1.000000,1.000000) (1.000000,0.000000) Control points (0.000000,0.000000) (0.000000,1.000000) (1.000000,1.000000) (1.000000,0.000000) sqrts length Romberg 1 1.000000 2 1.802776 2.070368 4 1.950719 2.000034 8 1.987716 2.000048 16 1.996931 2.000003 32 1.999233 2.000000 64 1.999808 2.000000 128 1.999952 2.000000 256 1.999988 2.000000 512 1.999997 2.000000 1024 1.999999 2.000000 so to get to 1 part per million the straightforward ('naive') method uses 1024 square roots for the result, and (assume no better way to start than from a single line segment) 1023 sqrt used getting there. The romberg method gets to a slightly better result using 48 square roots (32+16) and wastes 15. That seems like a worthwhile acceleration to me. The convergence power of h is 2 for the naive method and 4 for the romberg. >>> 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. The control points are hardly much of an upper bound in the case of a small number of control points. In my example, above, the upper board is 3. >>> 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). It might help to know the context. What is the purpose. What degree of polynomials are you talking about. I think you said 2-D in another post but... What hardware have you in mind? peter
From: D Yuniskis on 19 Jun 2010 13:06
Hi Peter, Peter Dickerson wrote: > OK, I've had chance to try this out in the case of a cubic. Start with just > the end points then subdivide in smaller steps of the control parameter. For > simplicity one line segment then two, four etc. Then printed out the summed > length and the romberg estimate. In the example below the path happens to be > exactly 2.0, making it easy to see the errors. > > Control points > (0.000000,0.000000) > (0.000000,-1.000000) > (1.000000,1.000000) > (1.000000,0.000000) I'll assume the above is NOT what you used but, rather, the one which follows (?) > Control points > (0.000000,0.000000) > (0.000000,1.000000) > (1.000000,1.000000) > (1.000000,0.000000) > > sqrts length Romberg > 1 1.000000 > 2 1.802776 2.070368 > 4 1.950719 2.000034 > 8 1.987716 2.000048 > 16 1.996931 2.000003 > 32 1.999233 2.000000 > 64 1.999808 2.000000 > 128 1.999952 2.000000 > 256 1.999988 2.000000 > 512 1.999997 2.000000 > 1024 1.999999 2.000000 I'm not sure we're on the same page, here. :-( (see below) I think you are playing solely with "t" (or whatever you are using as the control variable) and subdividing *that* (?) [did you run this in Maple/Mathematica/etc.? If so, can you post your code?] > so to get to 1 part per million the straightforward ('naive') method uses > 1024 square roots for the result, and (assume no better way to start than > from a single line segment) 1023 sqrt used getting there. The romberg method > gets to a slightly better result using 48 square roots (32+16) and wastes > 15. That seems like a worthwhile acceleration to me. The convergence power > of h is 2 for the naive method and 4 for the romberg. > >>>> 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. >>>> 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. > > The control points are hardly much of an upper bound in the case of a small > number of control points. In my example, above, the upper board is 3. No, you update the upper -- and lower! -- bounds as you subdivide the curve. E.g., the first iteration of "my" algorithm has the length of the segments in the control polygon as 3 (= 1+1+1) and the length of the *chord* as 1 (obvious). So, my initial estimate for length is 2 ((3+1)/2). Next, I subdivide the curve creating two curves: (0,0) (0,0.5) (0.25,0.75) (0.5,0.75) and (0.5,0.75) (0.75,0.75) (1,0.5) (1,0) (in this example, they are mirror images of each other) [apologies if I screw this up... I'm doing it in my head as I type :-/ ] The sum of the control polygon segments is ~1.103 (1/2 + sqrt(2)/4 + 1/4) and the length of the chord is ~0.901 (sqrt(0.5^2 + 0.75^2)). The estimate for the length of *this* curve (which is just the "left half" of the original curve) would the be ~1.002 ((1.103 + 0.901)/2). Since the left and right halves of the original curve are mirror images, the length of the *right* curve will be the same leaving the estimate for the total curve to be ~2.004 [sorry, going any further than that without a calculator and pen/paper is too hard for my little brain! :> ] Note that many of the calculations performed in the first curve's assessment can be salvaged in the assessment of the second curve. (I haven't sat down and counted how many sqrts are *required* at each subdivision of the curve and how many can be "inferred"). The problem with all of these is coming up with criteria that you can automagically use to stop the recursion. E.g., I would simply use something like |estimate[i+1]| < |estimate[i]| - epsilon But, this assumes the process converges monotonically... |