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: Peter Dickerson on 20 Jun 2010 03:25 "D Yuniskis" <not.going.to.be(a)seen.com> wrote in message news:hvkecf$843$1(a)speranza.aioe.org... [snip] > > De Casteljau's algorithm. > > Given a Start point (S), departing control point (D), arriving > control point (A), and End point (E), [i.e., these are P0 - P3], > the control points for the two half curve are: > M = (D+A)/2 > > L0 = S > R3 = E > > L1 = (S+D)/2 > R2 = (A+E)/2 > > L2 = (L1+M)/2 > R1 = (M+R2)/2 > > L3 = R0 = (L2+R1)/2 [snip] OK, so it is trivial for cubics. So, you can start with the first estimate as the average of the control point path and the start to end path. Then subdivide (binary, say) and get a new estimate. Then combine these estimates using the Romberg method. Assuming you know the convergence power you can also estimate the error. If the error is OK keep the result and pass it up, else recurse again. Somebody somewhere has to decide what good enough is, perhaps in fractional terms. The benefit of your scheme is that it doesn't need to recurse so deepy for some parts of the curve as others. Peter
From: Nobody on 20 Jun 2010 08:47 On Sun, 20 Jun 2010 07:35:40 +0100, Peter Dickerson wrote: > This is the bit I'm missing. How do you get the control points for the two > halves from the control points of the whole? b0 = a0 b1 = (a0 + a1)/2 b2 = (a0 + 2*a1 + a2)/4 c0 = b3 = (a0 + 3*a1 + 3*a2 + a3)/8 c1 = (a3 + 2*a2 + a1)/4 c2 = (a3 + a2)/2 c3 = a3 Or, using midpoints only: b0 = a0 c3 = a3 b1 = (a1 + a0)/2 c2 = (a3 + a2)/2 m = (a1 + a2)/2 b2 = (m + b1)/2 c1 = (m + c2)/2 c0 = b3 = (c1 + b2)/2
From: D Yuniskis on 21 Jun 2010 16:44 Hi Paul, Paul Keinanen wrote: > On Sat, 19 Jun 2010 10:20:31 -0700, D Yuniskis > <not.going.to.be(a)seen.com> wrote: > >>> Adding/subtracting is easy to do in integer/fixed point arithmetic, >>> but very nasty to do in floating point format due to demoralization >> Agreed. Hence my suggestion to leave results "demoralized" ^^^ ;-) >> at times. > > Addition in floating point representation must be done with equal > exponents, so the smaller value needs to be denormalized to have the > same exponent as the larger. Yes, I'm familiar with the issues (I've had to write many floating point "support" libraries over the years). I think that this would be a bad fit for a conventional "one-size-fits-all" floating point implementation. Too many operations are simple arithmetic (add/sub/div2) and using floats makes those disproportionately expensive. > In decimal notation 9.97E03+5.0E01 = 9.97E03+0.05E03 = 10.02E3 = > 1.002E04. Of course, you could postpone the overflow normalization, if > other additions/subtractions will immediately follow and if the > arithmetic unit has sufficient headroom bits. Exactly. You *know* you are going to compute <blah blah blah> so come up with a numerical representation that fits the complexity of the calculations regardless of how "clean" it is (gee, why bother supporting subnormals, NaN's, etc.?) >>> 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. >> Of course, "integer" is really "fixed point" as X(i) and Y(i) are >> real numbers. > > Fixed point add/sub is the same as integer, in multiplication, you > just have to shift right the result by the number of fractional bits > etc. > >> I don't think a naive "lets use this operator on all values" >> approach will work effectively. E.g., in regions of low curvature >> you can get away with bigger segment lengths (eats up a bigger >> portion of the workload quicker!). And, in high curvature, you >> quickly fall into the mud trying to get nice tight approximations >> to sharp curves. >> >> So, maybe use floats for the big numbers and a fixed point >> scheme for the small increments. (or, two different fixed >> point representations conveniently scaled :> ) > > As long as you avoid too frequent float/fixed or fixed/float > conversions in a single expression since (ne)normalization is > expensive using traditional instruction sets. For "commodity" processors and/or semicustom logic, I think a fixed point (though not "integer") scheme is probably going to be the winner. I need to look at how to cut costs in the basic algorithm(s). Then, see if there are any tricks I can employ to further constrain the domain. E.g., perhaps scaling the coordinates of the points before running the algorithm and then "de"-scaling the results... >>> 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. >> Or, do it all fixed point and just waste bits. E.g., using >> serial adders and multipliers means you just need to spend >> money on flip-flops. > > Addition, subtraction, multiplication and denormalization can be done > with right shifting shift registers, however, normalization (and > division) would also require left shifting shift registers. > > _Bit_ serial computing was used a lot in the tube era (and in the > HP-35 pocket scientific calculator), but I haven't seen it used more > recently. I like using serial adders/multipliers when designing dedicated processors -- i.e., where the algorithm is (literally?) hard-wired. It's small, easy to debug and scale, etc. E.g., handling 32 bit values is just as easy as 64 (just add more bits of "data store"). By contrast, going to wider parallel implementations means having to add *lots* of logic as you add each new bit. > These days, a huge number of bit serial processors might make sense if > each serial processor is controlling a single pixel or block of pixels > and some of these processors could be completely shut down to reduce > power consumption when no update is required. But otherwise, for equal > total throughput, both serial and parallel systems would require about > the same amount of arithmetic elements, but the more complex control > logic on serial processors would have to be duplicated on more > processors.
From: D Yuniskis on 22 Jun 2010 09:27 Hi Peter, Peter Dickerson wrote: > "D Yuniskis" <not.going.to.be(a)seen.com> wrote in message > news:hvkecf$843$1(a)speranza.aioe.org... > [snip] >> De Casteljau's algorithm. > > OK, so it is trivial for cubics. So, you can start with the first estimate > as the average of the control point path and the start to end path. Then > subdivide (binary, say) and get a new estimate. Then combine these estimates > using the Romberg method. Assuming you know the convergence power you can Sorry, you've lost me (easy to do, this early in the morning :< ) > also estimate the error. If the error is OK keep the result and pass it up, Well, I know that the error can't be more than half of the difference between the "polygon length" and chord length. I.e., once they are within 2*error of each other, I *know* the length fits to within "one error" (?) > else recurse again. Somebody somewhere has to decide what good enough is, > perhaps in fractional terms. The benefit of your scheme is that it doesn't > need to recurse so deepy for some parts of the curve as others. Well, it *could* not-need to recurse as deeply. It depends on how tight the curve is. E.g., a (pseudo) circle is probably the worst "overall" curve to follow as there are *no* "straight runs". The problem witht he algorithm is that the cost of recursion can quickly escalate (i.e., the cost of the computations for each level of recursion is high). And, there is no way of bounding this a priori. :<
From: Peter Dickerson on 23 Jun 2010 02:17
"D Yuniskis" <not.going.to.be(a)seen.com> wrote in message news:hvqdli$f0l$1(a)speranza.aioe.org... > Hi Peter, > > Peter Dickerson wrote: >> "D Yuniskis" <not.going.to.be(a)seen.com> wrote in message >> news:hvkecf$843$1(a)speranza.aioe.org... >> [snip] >>> De Casteljau's algorithm. >> >> OK, so it is trivial for cubics. So, you can start with the first >> estimate as the average of the control point path and the start to end >> path. Then subdivide (binary, say) and get a new estimate. Then combine >> these estimates using the Romberg method. Assuming you know the >> convergence power you can > > Sorry, you've lost me (easy to do, this early in the morning :< ) Oh! I thought I was reiterating what you were proposing to see if I had it right. >> also estimate the error. If the error is OK keep the result and pass it >> up, > > Well, I know that the error can't be more than half of the difference > between the "polygon length" and chord length. I.e., once they > are within 2*error of each other, I *know* the length fits to > within "one error" (?) Yes, but that bound is quite loose. >> else recurse again. Somebody somewhere has to decide what good enough is, >> perhaps in fractional terms. The benefit of your scheme is that it >> doesn't need to recurse so deepy for some parts of the curve as others. > > Well, it *could* not-need to recurse as deeply. It depends on how > tight the curve is. E.g., a (pseudo) circle is probably the worst > "overall" curve to follow as there are *no* "straight runs". Well, the curve can't be tight unless the poly is high order. The order of the poly, or number of control points hasn't been specified except that examples have been cubic. Anyway, if you specify that you want the final error be some small fraction of the initial upper bound then you can use that fraction on each division of the curve. Or you can assign half the limit to each half of the division. Not perfect because either way you'll probably do more work than strictly necessary (but you wouldn't know that until you'd done all the work...). > The problem witht he algorithm is that the cost of recursion can > quickly escalate (i.e., the cost of the computations for each > level of recursion is high). And, there is no way of bounding > this a priori. :< Actually, I don't see it that way at all. In terms of costs I think the biggest cost is square roots, then perhaps multiples, and then recursion. The problem that I see is that compute one estimate requires as many square roots as control points. So for a cubic thats four at the top level and 8 at the first binary subdivision. The test for whether the upper bound is sufficiently close to the lower bound can be done on the squared lengths to save one square root but. Peter |