# Thread: Animations in 1.4.1 release notes revision A

1. ## Animations in 1.4.1 release notes revision A

It seems that Collada is adopting the DCC-style animation curves, particularly for <animation>/<sampler> elements (<mesh>/<spline> seems to be unchanged). However there's no real discussion of how to interpolate these curves. Remember that these types of curves are governed by an independent variable other than time (call it s), and that at each time step you need to solve a cubic equation to get the s-value that corresponds to a given time, and then use that to interpolate the curve and get the result. It's fundamentally different from the Bezier curves defined in standard computer graphics texts. This was discussed here and here.

I don't see an explanation of the proper way to interpolate these curves, and I think this will add more confusion to the situation. Are we on the same page about this issue? If so I'll be happy to write up a bug against the spec, but I wanted to make sure everyone understands and agrees on the problem because I've mentioned it before but it seems to have been ignored.

2. de Casteljau subdivision algorithm is often used to do the interpolation.

3. de Casteljau subdivision is fine, but that's not really what I'm referring to. Let me post some snippets from the other thread.
Originally Posted by sthomas
Ok, so I want to see if I can pin down exactly what Blender is doing. Let's just consider x animating over time for now. Blender allows for manipulation of a curve P(s) = [t(s), x(s)], where P is a cubic Bezier curve, and hence t(s) and x(s) are cubic polynomials of s, i.e. t(s) = a*s^3 + b*s^2 + c*s + d. However we're not concerned with looking up values of x given s, we want to find values of x given t. So somehow Blender must be able to take a t value and find the corresponding x.
Originally Posted by dsrbecky
That's all correct.
NB: We are saying Blender, but the same applies to most DCCs.
Originally Posted by sthomas
Since t(s) is a cubic polynomial of s, then you can solve the cubic equation for a particular t-value to get 3 possible s-values, only one of which should be real as long as the curve is shaped properly. Then you plug this s into x(s) to get x.
Originally Posted by dsrbecky
As you said, a cubic equation needs to be solved to find 's' - http://en.wikipedia.org/wiki/Cubic_equation (I guess that in practice some numerical method can be effective)
I think the issue that I'm raising here is the same issue that was discussed at the bottom of this thread over at the Feeling Software forums.
Originally Posted by Mark Shroders
Oke,

But does anyone has any idea how to interpolate this bezier, given 2D control points (x,t)? So what is the x given a certain t?
Originally Posted by Guillaume Laforte
Hi Mark,

To be calculate the resulting 'x' value for a given 'time' value, you need a way to find the correct 't' value in which the resulting Bezier interpolation will give you the wanted time value. The simplest method is fairly inefficient and we're currently discussing better ways to do that... so I don't have a definitive answer for you.

The simplest method is to calculate 't' using the 'time'-dimension of the Bezier interpolation formulae and then replace 't' in the 'value'-dimension in order to get the resulting 'x'.
The main point is that you need an additional step to interpolate these curves properly... simply evaluating a Bezier curve isn't enough. Perhaps either dsrbecky or Guillaume can confirm (or disconfirm of course ) what I'm saying here.

4. Generally such curve cannot be expressed asa y=f(x), because there may be several y values for a given x. Although in the COLLADA spec we ask that animation curves be monotone (can be expressed as y=f(x)

You can do the evaluation using a subdivision (recursive) algorithm. Since the curve is monotone, dichotomy search work as well. Memorizing the subdivision results will accelerate subsequent evaluations.

This processing does not need to be done in real time, you can sample the animation curve in a conditioner (in Refinery) for example.

Please let us know if you think other type of curves (in addition to the 1.4.1 spec) to be supported in COLLADA.

5. Originally Posted by remi
Generally such curve cannot be expressed asa y=f(x), because there may be several y values for a given x. Although in the COLLADA spec we ask that animation curves be monotone (can be expressed as y=f(x)
If I have a 2D Bezier curve with time on the x-axis and an object's x-position on the y-axis, I'm not sure that I can compute x=f(t) as a closed form function, even when the entire curve is monotonically increasing in time. For example, how can I compute x=f(t) with Bezier control points P0=(0,0) P1=(1,0) P2=(0,1), P3=(1,1) (P0 and P3 are the interpolated points). That curve is actually of the form P(s) = [t(s), x(s)], since t is no longer the independent parameter.

I should provide a more concrete example of what I'm talking about. When I get home tonight I'll work out an example where I think that if you follow the math described in the revision A spec you'll get incorrect results.

6. sthomas,

Did you ever figure out how to do this? I am suck trying to figure out how to play back this type of animation from our custom collada loader. I have bezier animation working for what I consider follows the spec, namely where the inTangents and outTangents have the tangent value in them, nothing else. I don't understand how to evaluate them when the inTangents and outTangents have the (x,y) values, which I take are (time, tangent?).

Is there some documentation on this method anywhere? Solve what cubic equation, the bezier one? I guess I'm a math newb or something.

Thanks,

Joe

I want to continue the discussion because I still believe it's an issue. I'm extremely busy with work right now and I can't post a detailed follow up, but I'll try to get to that tonight.

Kinobi, what you have is a cubic parametric curve in two dimensions. One dimension is time and the other dimension is the actual parameter value. Time isn't the independent parameter of the curve. The independent parameter is something else, call it s.

P(s) = [t(s), output(s)]

t(s) = a*s^3 + b*s^2 + c*s + d.

To evaluate at a particular time, first find the value of s that yields the time value you're looking for, then evaluate the curve with that s to get the output parameter. To find the necessary s-value you need to solve the cubic equation t(s) above. Info for that is available on Wikipedia and other places.

I may have gotten a few details wrong... I really have to get back to work.

8. Let me try to illustrate why solving a cubic equation is necessary to get the value you're looking for. Let's say I have a Bezier curve segment of the form P(t) = p0*(1-t)^3 + 3*p1*t*(1-t)^2 + 3*p2*t^2*(1-t) + p3*t^3. This is the definition of a parametric cubic Bezier curve given by Wikipedia. The one used by Collada is slightly different in that it uses two points and two tangents instead of four points, but they're equivalent and you can transform from one to the other.

Now Collada's curves as defined in Revision A of the spec describe P(t) as a two-dimensional curve where time is on the horizontal axis and the output value is on the vertical axis. I don't think the spec phrases it exactly like that, but that's the basic idea. This matches what most or all of the DCC apps do.

Now let's say I have a curve as described by P(t) above, with p0 = (0 0), p1 = (1 0), p2 = (0 1) and p3 = (1 1). I wish I had a diagram, but this curve should be easy to visualize. This is a valid curve in this context since at no point in time is there more than one output value. Now let's say I want to evaluate the curve at time 0.5. So I plug .5 into my formula and get (.5 .5) as the result. That's fine... at time .5 the output value is .5. But let's say I want to evaluate at time .2. I plug .2 into the equation and I get (.392 .104) as the result. Notice the time value of .392... I wanted to evaluate at .2, not .392. The same thing happens at other times. In general you can't plug a time value into the equation and expect to get the correct numbers back.

This is happening because time is no longer the independent parameter of the curve. The independent parameter is some other value (I call it s) which is different from time. To evaluate the curve given a time, you need to first find the s-value that yields that time, and this involves finding the root of a cubic equation.

My beef with the spec is just that this little complication isn't mentioned anywhere. Most graphics programmers are probably familiar with more traditional Bezier curves where time is the independent parameter. These are the curves that are described in standard computer graphics texts like Real-Time Rendering.

9. sthomas,

Thank you very much, I found out I had no idea what a parametric equation was. My thinking on this is getting very uptight!

So if I have this correct, remi is saying for practical purposes you don't have to solve the cubic equation as you can simply search for the answer using the de Casteljau algorithm because the curves are supposed to be monotonic? You are saying this is not true in some cases?

Joe

10. Originally Posted by Kinobi
My thinking on this is getting very uptight!
Hah, is that a Lebowski reference?

As I understand it, the de Casteljau algorithm is an alternative to Bernstein polynomials for evaluating Bezier curves. I'm not sure how they can help with the problem we have. Remi can probably clear that up for us.

The only thing I thought was incorrect was the idea that we can express the curve as a closed form function y=f(x), or in our terms, output=f(time). I don't think we can always do that, even with the constraint that each time have a single output value. If I'm wrong and we can always express output as a closed-form function of time, then everything I'm saying about solving cubic equations is moot, but we should still add a description of how to compute output=f(time) to the spec. As it currently stands, following the description laid out in the spec yields incorrect results, at least according to my understanding.

Page 1 of 2 12 Last

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•