Can a Math genius please help me!? [modified]

[srev]

Hi Guys, I’m creating an animation program and have built a Bezier spline motion editor. The user-controllable curve plots time(x) against value(y). So my challenge is to retrieve the 'y' value from a given 'x' on the curve. However, all the articles I've been able to find/understand only give a formula for calculating an x or y from 't' - the percentage along the given cubic bezier curve. As 't' is more concentrated around areas which heavily curve (to make a smooth curve), it's not possible to calculate y from x. So I'm using what seems to be a recognised work around and iteratively guessing at which 't' value produces x, continually reducing the difference until I find the correct 't' which produces my required x. I then use this 't' to calculate y. This all works perfectly well. However, this is an animation program so I need to optimize this process. My current technique requires up to 15 iterations before it finds an accurate value for 't'. I found an article online by Don Lanaster, “Some more cubic spline math BEZMATH.PS”. He mentions using the Newton-Raphelson method to reduce this process down to 3 iterations. Apparently this technique uses the slope of the curve to make the approximation of 't' more accurate. However, the formula he uses doesn't match the formula I currently have working to calculate a value on the curve. I'm sure I'm misunderstanding it! At this point I have to confess I am a Math dummy. I can work my way around practical mathematical issues as long as I don’t have to resort to long formulas full of ancient Greek! Here's an extract from Don's article: --- Quote ---- Let's use a better ploy to get our approximation to close quickly. It is called the NEWTON-RAPHELSON method, but is much simpler than it sounds. Say we get an error of x - x1. x1 is the current x for our current guess. At x1, our spline curve has a slope. Find the slope. The slope is expressed as rise/run. Now, on any triangle... rise = run x (rise/run) This gives us a very good improvement for our next approximation. It turns out that the "adjust for slope" method converges very rapidly. Three passes are usually good enough. If our curve has an equation of... x = At^3 + Bt^2 + Ct + D ...its slope will be... x' = 3At^2 +2Bt + C And the dt/dx slope will be its inverse or 1/(3At^2 + 2Bt +C). This is easily calculated. The next guess will be... nextguess = currentt + (curentx - x)(currentslope) ----- end quote ----

[papa80]

You choose wrrong forum brother try it in google groups but math

when i want to read something good just seat and type it

[srev]

Thanks for the tip. I've posted on there too.

[Guffa]

Perhaps you should look for a better source of information. There is no such thing as "the Newton-Raphelson method". If you search for information about the Newton-Raphson method[^], you might have better luck.

--- b { font-weight: normal; }

[Ed Poore]

There is a Maths forum here as well.

---

As of how to accomplish this, have you ever tried Google?
Failing that try :badger::badger::badger:

[srev]

Guys, Thanks so much for everyone's feedback. From all the feedback on this and other forums I have the answer. The function CalcBezierValue() computes the cubic Bézier curve as the polynomial: x = A*t^3 + 3*B*(t^2)*(1-t) + 3*C*t*(1-t)^2 + D*(1-t)^3 To use the technique in the article I need the derivative: x' = 3*A*t^2 + 6*B*t*(1-t) - 3*B*t^2 + 3*C*(1-t)^2 - 6*C*t*(1-t) - 3*D*(1-t)^2 The final code looks like this: // Calc the derivative value of the curve at the specified percentage (rather than the polynomial) public float CalcBezierDerivative(float P, float A, float B, float C, float D) { P = 1 - P; // Reverse the normalised percentage float tR = 3 * A * (P * P); float tS = 6 * B * P * (1 - P); float tT = 3 * B * (P * P); float tU = 3 * C * ((1 - P) * (1 - P)); float tV = 6 * C * P * (1 - P); float tW = 3 * D * ((1 - P) * (1 - P)); return tR + tS - tT + tU - tV - tW; } Many thanks for all your responses. Simon