|
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 ----
So here's the function I call iteratively with varying values for 't' and it returns 'x' for me to compare with what I want:
public float CalcBezierValue(float t, float A, float B, float C, float D)
{
t = 1 - t; // Reverse the normalised percentage
float F1 = t * t * t; // These vars used purely for visual clarity
float F2 = 3 * t * t * (1 - t);
float F3 = 3 * t * (1 - t) * (1 - t);
float F4 = (1 - t) * (1 - t) * (1 - t);
return A * F1 + B * F2 + C * F3 + D * F4;
}
As you can see the base formula which produces the return value is quite different from the one in the article (x = At^3 + Bt^2 + Ct + D). Consequently I’m failing to comprehend how to calculate the slope value or its inverse which seem to be required to reduce the number of calls to this function.
Can anyone help me?
Many thanks for your time,
Simon
-- modified at 12:01 Wednesday 13th September, 2006
|
|
|
|
|
srev wrote: 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.
This is one of many, many reasons why I won't use a Bezier spline for camera or motion control. A) its always more difficult B) it is always more time-consuming and cpu-hogging.
I tend to use Catmull subdivision surface variants. Catmull-Rom for splines although I have my own variation of it. The original code was from a motion spline in AI Game Programming Wisdom[^] I modified it for uneven weighted distances and some other actions. If you are trying to do smooth motion cameras without a huge CPU overhead, I highly recommend the book. I use it for just about everything within, it's a great book all around, but in related to this there is a chapter on least-acceleration motion curves, PID controllers and subdivision splines, all slightly different approaches to motion control.
If you don't want the book, take a peek at these:
http://www.mvps.org/directx/articles/catmull/[^]
http://www.lighthouse3d.com/opengl/maths/index.php?catmullrom[^]
http://www.cubic.org/docs/hermite.htm[^]
_________________________
Asu no koto o ieba, tenjo de nezumi ga warau.
Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
|
|
|
|
|
Jeffry thanks for these links, they look really usefull. And Amazon has my money for the book you recommended.
Thanks again!
|
|
|
|
|
Hi,
If this is your function, y = CalcBezierValue(t, A, B, C, D), the slope function may be (I have not tested it at all)
public float CalcBezierSlope(float t, float A, float B, float C, float D)
{
t = 1 - t; // Reverse the normalised percentage
float F1 = 3 * t * t; // These vars used purely for visual clarity
float F2 = 6 * t - 9 * t * t;
float F3 = 3 * (1 - t) * (1 - t) - 6 * t * (1 - t);
float F4 = -3 * (1 - t) * (1 - t);
// I am not sure about the minus, but since there's function composition t = 1 - t ...
return ( -1 ) * A * F1 + B * F2 + C * F3 + D * F4;
}
and your iteration function may look like
public float CalcBezierNextGuess(float x0, float t, float A, float B, float C, float D)
{
// I am not sure about the minus sign, may be a plus
return t - (CalcBezierValue(t,A,B,C,D) - x0) / CalcBezierSlope(t, A, B, C, D);
}
I might be completely wrong, but I have no time to test this.
Regards,
|
|
|
|
|
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
|
|
|
|
|
|
|
My friend posed the following question to me, that a friend of his was given in her math class:
Suppose in a simplified game of (American) football that the only possible amount of points one can score at a time are 3 or 7. What is the highest score that is impossible to achieve?
For example, 17 is a possible score (7 + 7 + 3) but 11 is not (there is no combination of 3's and 7's you can add together to get 11). Of course, since this is given in the context of a game, there can be no negative scores, so (7 + 7 - 3) doesn't work.
I wrote a small program to brute-force the solution, and searching up to 1000 I found the maximum impossible score is 11. However, I am not able to prove it. This problem reminds me of some things we did in Number Theory class but it's been a while and I've hence forgotten a lot of it.
Any pointers?
--
Marcus Kwok
|
|
|
|
|
It's trivial to show that the score can never be 11, so you now just have to prove that all numbers greater than 11 can be scored. All numbers after 11 fall into one of 3 series:
12 + 3n + 0 = {12, 15, 18, ...}
12 + 3n + 1 = 13 + 3n = {13, 16, 19, ...}
12 + 3n + 2 = 14 + 3n = {14, 17, 20, ...}
So, now just show that 12 (4 field goals), 13 (2 field goals and a touchdown), and 14 (2 touchdowns) can be scored, then all other numbers can be scored by tacking on more field goals (3n).
|
|
|
|
|
Fantastic! Thanks. Of course, now that I know the answer, it seems so obvious ![Badger | [badger,badger,badger,badger...]](https://codeproject.freetls.fastly.net/script/Forums/Images/badger.gif)
--
Marcus Kwok
|
|
|
|
|
Anyone know of a way to take an inverse power to get the number a number was raised by?
x = 2^(20 - a) or x = 2^a
I need to determine a, but my math is way rusty. I think I need the nth root of x, but don't know how to write it, and actually need to find out what n is.
Do I need to do x^(1/a) = 2? I get stuck after that. Probably basic math, but it's slipped my brain. 
Any help would be greatly appreciated.
Found this mildly funny: http://mathworld.wolfram.com/Power.html[^]
A number to the first power is, by definition, equal to itself, i.e., z^1==z.
It is therefore impressive that Captain Kirk (William Shatner) is able to detect one more heartbeat aboard the starship Enterprise than can be accounted for by amplifying an auditory sensor intensified by a factor of "1 to the fourth power" in the Season 1 Star Trek episode "Court Martial" (1967).
- S
50 cups of coffee and you know it's on!
|
|
|
|
|
Hi,
x = 2^(20 - a) or x = 2^a
Use log
log x = (20 - a) * log 2 or log x = a * log 2
Regards
|
|
|
|
|
Thanks!
- S
50 cups of coffee and you know it's on!
|
|
|
|
|
you can do this:
if x=n^a
then a=log(x)/log(n)
Log is the logarithm ( base 10 or naturals, this works whith any base )
Greetings
|
|
|
|
|
Hi, probably a better place for this, hopefully someone can help.
For one of my programs i'm trying to impliment my own version of the RSA algorithm, the encryption works fine, however the decrption does not, even though it uses basically the same algorithm. The code is as follows:
<br />
<br />
<br />
#include <stdio.h><br />
#include <stdlib.h><br />
#include "math.h"<br />
<br />
<br />
int do_crypto(int M, int e, int N);<br />
<br />
int main()<br />
{<br />
<br />
printf("...\n");<br />
<br />
int p = 17;<br />
int q = 11;<br />
int e = 7;<br />
int N = p * q;
<br />
int M = 88;<br />
<br />
int C = do_crypto(M, e, N);
printf("C = %d \n", C);<br />
<br />
<br />
int d = ( ( (p-1) * (q-1) ) / e );<br />
printf("d = %d \n", d);<br />
<br />
<br />
int m = do_crypto(11, 23, 187);
printf("m = %d \n", m);<br />
<br />
<br />
return 0;<br />
}<br />
<br />
int do_crypto(int M, int e, int N)<br />
{<br />
int iret = int ( M * exp(e) ) % N;<br />
<br />
return iret;<br />
}<br />
<br />
When decrypting I have put in actual values for the keys etc, and the result should be 88.
The actual formulas are:
ENCRYPT: C = Me (Mod N)
DECRYPT: M = Cd (Mod N)
*** Please note the 'e' and 'd' are supposed to be superscript, e.g. raised to the power of...
|
|
|
|
|
Have you figured this out or still having trouble with it?
"Any sort of work in VB6 is bound to provide several WTF moments." - Christian Graus
|
|
|
|
|
i have a map that contain (22 * 18 ) images i don't want to add all of the images
i want have a 3 * 3 table
the problem is i want when user drag the map the images is load in the imagesboxes without user understand that all of the images dosn't load
How Can I do it(!!!!!)
MHF
|
|
|
|
|
Write a C program that accepts as input any of the following:
>> a listing of edges of a graph given as pairs of positive integers
>> the adjacency matrix
>> the incidence matrix
and outputs the other two...
|
|
|
|
|
robeelyn wrote:
Write a C program that accepts as input any of the following:
>> a listing of edges of a graph given as pairs of positive integers
>> the adjacency matrix
>> the incidence matrix
and outputs the other two...
What do you mean by this?
As of how to accomplish this, have you ever tried Google?
Failing that try
|
|
|
|
|
Sounds like homework!
That's no moon, it's a space station. - Obi-wan Kenobi
|
|
|
|
|
|
|
1) you don't ask a regular english question
2) this looks like homework
3) you didn't even choose the right forum
|
|
|
|
|
Hi everyone,
does anyone know where I can find a visual basic 6 code for wavelet image compression and decomposition ... I need it for my graduation project ... Help please ...
Luay Al-wesi
|
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
![Badger | [badger,badger,badger,badger...]](https://codeproject.global.ssl.fastly.net/script/Forums/Images/badger.gif)
