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 02:35 "D Yuniskis" <not.going.to.be(a)seen.com> wrote in message news:hvitcs$h2j$1(a)speranza.aioe.org... > 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 (?) Sorry, yes. I pasted in one example and then decided that it would be clearer if I used an example with simple result. >> 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* (?) Probably not. Yes I'm using the control parameter, which is commonly called t. > [did you run this in Maple/Mathematica/etc.? If so, can you > post your code?] It's etc. I though the premise was a resource challenged system. So I wrote it in C - well its actually C++ but in C style. Pasted at the end, but only one line for the Romberg bit. >> 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 :-/ ] 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? I haven't thought about this so perhaps its trivial, in which case it's clearly a good way to go. Even so, you can still use the Romberg approach on the results of two subdivisions. Its all about getting a better estimate based on two other estimates and knowledge of how the algorithm converges (and assumption that it does converge in a regular manner, but we're integrating a curve that is continuous and differentable) > 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... Well the line segment summation is monotonic and bounded above, so that process must converge. The straight line segment between two points is always the shortest, so breaking it into two segments to better follow the curve must be longer (or equal). the code... sorry this is going to have the formatting destroyed... note that I am making no attempt to optimize the Bezier point calculations since that wasn't the point I was making. Beziers can be calculated using just additions once the paraeters are convertd to the relevent form. Nor do I use integers. I simply fill out an array with the points befor hand to separate that from the integration. The Rombergy bit is just one line -------------------------------------- // Bezier.cpp : Defines the entry point for the console application. // #include "stdio.h" #include "stdlib.h" #include "math.h" #define POINT_SHIFT 10 #define POINT_MAX (1<<POINT_SHIFT) struct POINT { double x; double y; }; POINT control[4]; POINT curve[POINT_MAX+1]; double lengths[POINT_SHIFT+1]; int main(int argc, char* argv[]) { // get control points control[1].x = 0.0; control[1].y = 1.0; control[2].x = 1.0; control[2].y = 1.0; control[3].x = 1.0; control[3].y = 0.0; if ( argc <= 4 ) { for (int i=1; i<argc; i++) { if ( sscanf( argv[i], "(%f,%f)", &control[i].x, &control[i].y ) != 2 ) { printf( "Invalid argument: %s\n", argv[i] ); } } } printf( "Control points\n" ); for (int i=0; i<4; i++) printf( " (%f,%f)\n", control[i].x, control[i].y ); printf( "\n" ); // fill in point array for (int i=0; i<=POINT_MAX; i++) { double t = (double)i/POINT_MAX; double t1 = 1.0-t; double x = control[0].x*t1*t1*t1 + control[1].x*3.0*t1*t1*t + control[2].x*3.0*t1*t*t + control[3].x*t*t*t; double y = control[0].y*t1*t1*t1 + control[1].y*3.0*t1*t1*t + control[2].y*3.0*t1*t*t + control[3].y*t*t*t; curve[i].x = x; curve[i].y = y; } printf( "sqrts length Romberg\n" ); // compute lengths for (int j=0; j<=POINT_SHIFT; j++) { int step = 1<<(POINT_SHIFT-j); double length = 0.0; for (int i=0; i<POINT_MAX; i += step) { double dx = curve[i+step].x - curve[i].x; double dy = curve[i+step].y - curve[i].y; length += sqrt( dx*dx+dy*dy ); } lengths[j] = length; printf( "%4d %10.6f", 1<<j, length ); // romberg improvement uses previous result, so not appricable to // first time round if ( j > 0 ) printf( " %10.6f", (lengths[j]*4 - lengths[j-1])/3.0 ); printf( "\n" ); } return 0; }
From: D Yuniskis on 14 Jun 2010 21:23 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 ;-) Suggestions? Pointers? Thx, --don
From: Walter Banks on 15 Jun 2010 12:06 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 Regards, Walter.. -- Walter Banks Byte Craft Limited http://www.bytecraft.com
From: George Neuner on 15 Jun 2010 13:22 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 George
From: D Yuniskis on 15 Jun 2010 18:23
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!) [and were they charging by the character when this guy wrote this code?? jeez, who the hell uses *ell* as a symbolic identifier?? esp lowercase! :-/ ] I have to sort out the criteria he is using to determine when the fit is "good enough". Appears to be looking at the shape of the control polygon at each instance to see if it is "too crooked", etc. (I suspect the magic numbers are truly magic!) The problem with this approach is it discards all of the computations "before the FIRST return" most of the time. If you think about it, the control polygon at this point defines an upper limit on the length of the (soon to be subdivided) curve. But, you also have points which can be used to create chords that bound the *lower* limit of the curve. This lets you get a better approximation "quicker" (assuming you can keep the cost of the math down). |