Hi, I need an interpolation between 2 points, where I can specify x1,y1,x2,y2 as usual and also derivatives at both ends. I need it to be computed fast and accurate. It should be an interpolation with minimal (or small) curvature. Example: we have 2 staight lines in X range 0..4 and 6..10. I want to fill the interval 4..6 with a smooth curve joining both of them. My first idea was to use Bezier curves. The problem is that such curve is 2D and thus based on a "t" parameter. It is useful for graphics, but here I'd need to solve the equation for "x" which is my source parameter. It is ugly but possible for quadratic bezier curves, but for cubic no way. Unfortunately quadratic is not enough, consider this: First line in the example above (0,0)->(4,5), second line (6,0)->(10,5). Any ideas? (Maybe it is obvious, just I don't see it) Maybe some other interp. method... Thanks! dmnc
Interpolation with specified end derivatives
Started by ●January 2, 2009
Reply by ●January 2, 20092009-01-02
On 2 Jan, 21:00, "jungledmnc" <jungled...@gmail.com> wrote:> Hi, > > I need an interpolation between 2 points, where I can specify x1,y1,x2,y2 > as usual and also derivatives at both ends. I need it to be computed fast > and accurate. It should be an interpolation with minimal (or small) > curvature. > > Example: we have 2 staight lines in X range 0..4 and 6..10. I want to fill > the interval 4..6 with a smooth curve joining both of them. > > My first idea was to use Bezier curves. The problem is that such curve is > 2D and thus based on a "t" parameter. It is useful for graphics, but here > I'd need to solve the equation for "x" which is my source parameter. It is > ugly but possible for quadratic bezier curves, but for cubic no way. > Unfortunately quadratic is not enough, consider this: > First line in the example above (0,0)->(4,5), second line (6,0)->(10,5). > > Any ideas? (Maybe it is obvious, just I don't see it) > Maybe some other interp. method...Splines? Rune
Reply by ●January 2, 20092009-01-02
On 2 Jan., 21:00, "jungledmnc" <jungled...@gmail.com> wrote:> Hi, > > I need an interpolation between 2 points, where I can specify x1,y1,x2,y2 > as usual and also derivatives at both ends. I need it to be computed fast > and accurate. It should be an interpolation with minimal (or small) > curvature. > > Example: we have 2 staight lines in X range 0..4 and 6..10. I want to fill > the interval 4..6 with a smooth curve joining both of them. > > My first idea was to use Bezier curves. The problem is that such curve is > 2D and thus based on a "t" parameter. It is useful for graphics, but here > I'd need to solve the equation for "x" which is my source parameter. It is > ugly but possible for quadratic bezier curves, but for cubic no way. > Unfortunately quadratic is not enough, consider this: > First line in the example above (0,0)->(4,5), second line (6,0)->(10,5).You didn't explicitely state it, but if you want your interpolation to be a differentiable function, then you need at least four degrees of freedom (quadratic only gives you three). For your given example, try the polynomial -220+ 1715/12 x -355/12 x^2 + 95/48 x^3. Regards, Andor
Reply by ●January 2, 20092009-01-02
jungledmnc wrote:> Hi, > > I need an interpolation between 2 points, where I can specify x1,y1,x2,y2 > as usual and also derivatives at both ends. I need it to be computed fast > and accurate. It should be an interpolation with minimal (or small) > curvature.What is the physical meaning of this interpolation? Is it supposed to be a waveform, or some process, or what?> Example: we have 2 staight lines in X range 0..4 and 6..10. I want to fill > the interval 4..6 with a smooth curve joining both of them. > > My first idea was to use Bezier curves. The problem is that such curve is > 2D and thus based on a "t" parameter. It is useful for graphics, but here > I'd need to solve the equation for "x" which is my source parameter. It is > ugly but possible for quadratic bezier curves, but for cubic no way. > Unfortunately quadratic is not enough, consider this: > First line in the example above (0,0)->(4,5), second line (6,0)->(10,5).You got to match two values and two derivatives -> the interpolation should be the polynomial of the 3rd order.> Any ideas? (Maybe it is obvious, just I don't see it) > Maybe some other interp. method...Start with the definition of the process which this interpolation is supposed to represent. Vladimir Vassilevsky DSP and Mixed Signal Design Consultant http://www.abvolt.com
Reply by ●January 2, 20092009-01-02
jungledmnc wrote:> > Hi, > > I need an interpolation between 2 points, where I can specify x1,y1,x2,y2 > as usual and also derivatives at both ends. I need it to be computed fast > and accurate. It should be an interpolation with minimal (or small) > curvature. > > Example: we have 2 staight lines in X range 0..4 and 6..10. I want to fill > the interval 4..6 with a smooth curve joining both of them. > > My first idea was to use Bezier curves. The problem is that such curve is > 2D and thus based on a "t" parameter. It is useful for graphics, but here > I'd need to solve the equation for "x" which is my source parameter. It is > ugly but possible for quadratic bezier curves, but for cubic no way. > Unfortunately quadratic is not enough, consider this: > First line in the example above (0,0)->(4,5), second line (6,0)->(10,5).Cubic beziers will do what you want quadratic won't work except in some special cases. There are an infinite number of cubic curves that will connect the 2 lines with tangent continuity. The bezier method is as good as any to find the cubic you want. As you said cubic beziers have the t parameter, but that isn't a problem There are an infinite number of relationships between t and x creating an infinite number of cubics that fit your criteria. But since beziers are a cascade of linear interpolations, if you set it up right there can be simple relationship between x and t. To set it up right you just need to evenly distribute the control points along x. (Look up Bernstien polynomials to see why this is true) This is the formula for cubic bezier. (1-t)^3*P0+ 3*(1-t)^2*t*P1+ 3*(1-t)*t^2*P2+ t^3P3 P0-P3 are the control point locations in x and y. You can compute the x and y location of any point on the curve for parameter t. In your example you already have the points P0 and P3 (the start and end) and since you want to make x evenly spaced the x values for P1 and P2 will need to be 4.6666.. and 5.3333.. the y values can be calculated by extrapolating the lines to the x values so in your example the y values for P0-P3 will be [4 4.8 -.8 0] You only need to plug the y values of your control points into the the above formula to get the y value of the curve for any point on the curve at t (where t is in the interval 0-1). You said the curve always goes from x=4 to x=6 so you can use this formula to calculate t from x t=(x-4)/2. -jim> > Any ideas? (Maybe it is obvious, just I don't see it) > Maybe some other interp. method... > > Thanks! > dmnc
Reply by ●January 2, 20092009-01-02
On Jan 2, 12:00�pm, "jungledmnc" <jungled...@gmail.com> wrote:> Hi, > > I need an interpolation between 2 points, where I can specify x1,y1,x2,y2 > as usual and also derivatives at both ends. I need it to be computed fast > and accurate. It should be an interpolation with minimal (or small) > curvature. > > Example: we have 2 staight lines in X range 0..4 and 6..10. I want to fill > the interval 4..6 with a smooth curve joining both of them.I would look at Numerical Recipes in C. There is a chapter 3.3 on cubic splines. It is easy enough to compute a cubic curve between two points if you the location and the derivative. You have four equations and four unknowns. This can be easily solve. The problem is what should the derivative be at the interior points? This is were the cubic spline comes in handy. Peter Nachtwey
Reply by ●January 3, 20092009-01-03
On Jan 2, 3:00�pm, "jungledmnc" <jungled...@gmail.com> wrote:> Hi, > > I need an interpolation between 2 points, where I can specify x1,y1,x2,y2 > as usual and also derivatives at both ends....> Any ideas? (Maybe it is obvious, just I don't see it) > Maybe some other interp. method...i think it's called Hermite polynomial interpolation or something like that. Duane Wise and i did a paper about a decade ago about comparing different polynomial interpolations (Lagrange vs. Hermite vs. B- spline) for sampled audio but i can't find it. i can't make head nor tail out of the Wikipedia article ( http://en.wikipedia.org/wiki/Hermite_polynomials ), but this online article appears to be what i was thinking about: http://math.fullerton.edu/mathews/n2003/HermitePolyMod.html r b-j
Reply by ●January 3, 20092009-01-03
>I need an interpolation between 2 points, where I can specify x1,y1,x2,y2 >as usual and also derivatives at both ends. I need it to be computedfast>and accurate. It should be an interpolation with minimal (or small) >curvature.Hi, Could you elaborate a little more... 1) how fast? (real time / offline?) define "fast". 2) how accurate? could you specify a cost function? 3) what is "small curvature"? 4) do you know anything else about this function. is it band-limited? is it a polynomial? is it random with a known pdf / power spectrum?... (the more prior information, the "better" you can interpolate.) The following quotation was displayed inside the physics lab at our high school: "He who doesn't know what he's looking for can not understand what he finds." I'd hate to sound preachy, but I believe it applies here. Emre
Reply by ●January 3, 20092009-01-03
Thanks a lot guys! I expected cubic polynomials, but I just did not know how to satisfy my needs. I like the bezier and hermite interpolations. Btw. the thing is there is a book about interpolation with end derivatives so I thought it is quite complicated. So I tried to think about some weird stuff like aligning a circle, nonlinear (sine) interpolation between two lines defined by the derivatives and such :-))... So thanks again! Finally something to study. There were some questions about purpose - this should be very realtime and there may be many purposes - audio envelopes, signal shapes... dmnc
Reply by ●January 3, 20092009-01-03
robert bristow-johnson wrote:> > On Jan 2, 3:00 pm, "jungledmnc" <jungled...@gmail.com> wrote: > > Hi, > > > > I need an interpolation between 2 points, where I can specify x1,y1,x2,y2 > > as usual and also derivatives at both ends. > ... > > Any ideas? (Maybe it is obvious, just I don't see it) > > Maybe some other interp. method... > > i think it's called Hermite polynomial interpolation or something like > that. Duane Wise and i did a paper about a decade ago about comparing > different polynomial interpolations (Lagrange vs. Hermite vs. B- > spline) for sampled audio but i can't find it. i can't make head nor > tail out of the Wikipedia article > ( http://en.wikipedia.org/wiki/Hermite_polynomials ),Cubic Hermite spline is what you are looking for. This would be the wikipedia entry: http://en.wikipedia.org/wiki/Catmull-Rom_spline#Catmull.E2.80.93Rom_spline The cubic hermite is identical to the cubic Bezier I gave in my previous post. To get from the Bezier to Hermite you would simply need to substitute control points and tangent vectors like this: Hermite Bezier P0 P0 P1 P3 M0 3(P1-P0) M1 3(p3-P2) Plug those substitutions in and rearrange and simplify and the Bezier becomes the Hermite. To get from his x to the Hermite t parameter you would still need to convert with the same formula t=(x-4)/2 -jim> but this online article appears to be what i was thinking about: > > http://math.fullerton.edu/mathews/n2003/HermitePolyMod.html> > r b-j
