From: Tom Lowe <thomas.lowe@na...>  20060526 16:56:11

Granted, however I was considering that the differentiated function would be reverted back into the bezier form. So keeping the same accuracy. This is of course then equivalent to your method.. ie equivalent to getDiff then quadraticBezier in one function. I agree the bezier form is more accurate than the (1,t,t*t,t*t*t) form. >> As for the efficiency: .... well ok, there's lots of things that improve efficiency. One of them actually being to convert the spline to (1,t,t*t,t*t*t) form, from which you can iterate along a spline with only 4 vector additions per step if necessary. Anyway, I appreciate the points you made in your earlier post, it makes sense now. Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...]On Behalf Of Mark Duchaineau Sent: 26 May 2006 16:13 To: gdalgorithmslist@... Subject: Re: [Algorithms] Finding the slope of a point on a bezier curve Hi Tom, The numerical accuracy of the diff is generally higher than looking at the monomial basis representation (1,t,t*t,t*t*t) and performing math relative to that. It has to do with the stability of these different bases. You tend to get really big and small numbers mixed into the monomial math, leading to less numerical precision, compared to keeping everything in the Bezier basis, where all the numbers stay within the same scale as the function (the control points "hug" the curve). Indeed Bezier is known as one of the most stable bases in existence. As for the efficiency: if you are making many evaluations of the derivatives, it is faster to preprocess the control points of the curve into control points of the derivative, then evaluate the derivative queries using that. Also, if you need something like the convex hull of the tangent vectors, then the Bezier tangent control points give you that convex hull (from which you can make bounding boxes etc). Using the bounding box, for some applications, allows you to avoid evaluating the tangents at individual t parameters altogether unless the bounding box overlaps some region of interest. Cheers, Mark D. Tom Lowe wrote: > I would argue that it is no simpler or more accurate than taking the > derivative of the bezier curve function. But it is a nice alternative. So if > the function is: > > x = cubicBezier(control points, t) > > then your method for the 'velocity' is: > > new control points = getDiff(control points) > v = quadraticBezier(new control points, t) > > or as previously suggested, making the derivative of the curve into a > function: > > v = cubicBezierVelocity(control points, t) > > equally valid > > > Original Message > From: gdalgorithmslistadmin@... > [mailto:gdalgorithmslistadmin@...]On Behalf Of Mark > Duchaineau > Sent: 26 May 2006 01:57 > To: gdalgorithmslist@... > Subject: Re: [Algorithms] Finding the slope of a point on a bezier curve > > > Hi Alias, > > The simplest and most numerically accurate way to get the derivative > of a Bezier curve of any degree (including cubics) is to just take > the differences of adjacent control points. These are the "control > vectors" of the Bezier "derviative curve", which is one less degree > polynomial that the original curve. So for cubics, you get three > control vectors from the four control points, resulting in a > quadratic Bezier curve of tangent vectors. There is a constant > scaling factor as well, depending on the parametization and degree. > > Here is a code snippet to do this for arbitrary degree Bezier curves: > > void bezc_diff(bezc c,bezc dc) > { > int i,j,deg,m; > double *cx,*cx0,*cx1,q; > > deg=c>deg; m=c>m; > q=(double)(dc>deg); > for (i=0;i<deg;i++) { > cx=dc>pp[i]; cx0=c>pp[i]; cx1=c>pp[i+1]; > for (j=0;j<m;j++) cx[j]=q*(cx1[j]cx0[j]); > } > } > > This assumes a t in [0,1] parameterization. > > Cheers, > > Mark D. > > Alias wrote: > >>Hi there, >> >>This is perhaps more of a math/calculus question, but I wondered if >>someone on the list might know the answer to this one. >> >>For various reasons, I've wanted to get the gradient of a point on a >>bezier curve. I can compute any point at t from the control point >>data, by standard means, but I'm at a bit of a loss as to how to get >>the slope at that particular point. If it were a quadratic curve, I'd >>expect to be able to use differentiation on equation of the curve, but >>I'm not really sure how to apply that approach to a bezier curve  I >>know it must be possible and much more efficient to do it this way >>rather than the slightly unreliable method of using arctan of points >>slightly above the curve. >> >>So, does anyone know how I would go about this? Should I create a >>modified version of my bezier point routine to find the slope at a >>point t? Would this be possible in parallel with finding the point? >> >>Any help much appreciated, >>Thanks in advance, >>Alias >> >> >> >>All the advantages of Linux Managed HostingWithout the Cost and Risk! >>Fully trained technicians. The highest number of Red Hat certifications in >>the hosting industry. Fanatical Support. Click to learn more >>http://sel.asus.falkag.net/sel?cmd=lnk&kid=107521&bid=248729&dat=121642 >>_______________________________________________ >>GDAlgorithmslist mailing list >>GDAlgorithmslist@... >>https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist >>Archives: >>http://sourceforge.net/mailarchive/forum.php?forum_id=6188 >> > > > >  > All the advantages of Linux Managed HostingWithout the Cost and Risk! > Fully trained technicians. The highest number of Red Hat certifications in > the hosting industry. Fanatical Support. Click to learn more > http://sel.asus.falkag.net/sel?cmd=lnk&kid=107521&bid=248729&dat=121642 > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > >  > All the advantages of Linux Managed HostingWithout the Cost and Risk! > Fully trained technicians. The highest number of Red Hat certifications in > the hosting industry. Fanatical Support. Click to learn more > http://sel.asus.falkag.net/sel?cmd=lnk&kid=107521&bid=248729&dat=121642 > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 >  All the advantages of Linux Managed HostingWithout the Cost and Risk! Fully trained technicians. The highest number of Red Hat certifications in the hosting industry. Fanatical Support. Click to learn more http://sel.asus.falkag.net/sel?cmd=lnk&kid=107521&bid=248729&dat=121642 _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 