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.

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

de Casteljau subdivision is fine, but that’s not really what I’m referring to. Let me post some snippets from the other thread.

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.

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.

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.

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.

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

Woah, I completely forgot about this whole topic. I just got an email notification because Kinobi posted. I can’t believe I forgot about this. Sorry about that.

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) = as^3 + bs^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.

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 + 3p1t*(1-t)^2 + 3p2t^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.

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

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.

The COLLADA 1.4.1 REVISION A Release Notes explains the curve interpolation semantics.

Is there something that needs further clarification?

I think so, yes. The documentation on Spline Curves is perfectly clear. However the documentation on Animation Curves is a bit vague. I understand the description of what’s going on with the input and output values. Then in the description of Bezier animation curves the spec says:

The same equations for cubic Bézier and Hermite interpolation already defined for <spline> are to be used, with the following geometry vector, for parameter j, segment[i]:
For Bézier:
• P0 is (INPUT[i] , OUTPUT[j][i])
• C0 (or T0) is (OUT_TANGENT[0][i] , OUT_TANGENT[j][i])
• C1 (or T1) is (IN_TANGENT[0][i+1], IN_TANGENT[j][i+1])
• P1 is (INPUT[i+1], OUTPUT[j][i+1])

The <spline> equation for Bezier curves is given as

B(s) = P0(1− s)^3 + 3C0s(1− s)^2 + 3C1s^2 (1− s) + P1s^3 ,s ∈ [0,1]

So I have my P0, C0, P1, and C1, but what s value do I use? Typically I’m given an input value and I want to find the corresponding output value. If I just evaluate B(s) using the input value I want then I’ll get incorrect results. This is what I tried to show two posts ago. I need to solve B(s) to get the s that corresponds to the input value I’m looking for, then plug that s into B(s) to get the output value. That extra step isn’t mentioned in the spec.

This is where you need to use a de Casteljau algorithm or other algorithms that are used for that exact purpose -> finding s and B(s) corresponding to the value you are looking for.

Regards

As I understand it, the de Casteljau algorithm is an alternative to Bernstein polynomials for evaluating Bezier curves. How would it help us find the roots of a cubic equation? Why not just use the method described here, say? (see Cardano’s method)

But in any case, can we agree that the spec could be more clear about this? If I follow the spec exactly, I end up with a curve B(s) and no s to evaluate it with. I can compute the s given the input value I want to evaluate, but that step isn’t mentioned at all. Shouldn’t we add a description of that to the spec for completeness?

Shouldn’t we add a description of that to the spec for completeness?

I think what we need is some sample code implementing the algorithm.

here’s our code to evaluate cubic Bezier curves using de Casteljau Subdivision, hoping this helps:


#define INVERTPARAMCUBIC_TOL 1.0e-09

#define INVERTPARAMCUBIC_SMALLERTOL 1.0e-20

#define INVERTPARAMCUBIC_MAXIT 100


...
  case SI_CUBIC:
  {
   CSLCubicKey *l_pPrevKey = ((CSLCubicKey*)(&GetCubicKeyListPtr()[prev_key])); 
   CSLCubicKey *l_pNextKey = ((CSLCubicKey*)(&GetCubicKeyListPtr()[next_key]));
 

   float v1 = l_pPrevKey->m_fRightTanX + l_pPrevKey->m_fTime; // OUT_TANGENT[n].X
   float v2 = l_pNextKey->m_fLeftTanX + l_pNextKey->m_fTime;  // IN_TANGENT[n+1].X
 
   // in_fTime = current_time
   // INPUT[n] = l_pPrevKey->m_fTime
   // INPUT[n+1] = l_pNextKey->m_fTime
   float u = InvertParamCubic ( in_fTime, l_pPrevKey->m_fTime, v1, v2, l_pNextKey->m_fTime );
 
   v1 = l_pPrevKey->m_fRightTanY + l_pPrevKey->m_fValue; // OUT_TANGENT[n].Y
   v2 = l_pNextKey->m_fLeftTanY + l_pNextKey->m_fValue;  // OUT_TANGENT[n+1].Y
 
   //
   // Bernstein Evaluation
   //
 
   // OUPUT[n] = l_pPrevKey->m_fValue
   // OUTPUT[n+1] = l_pNextKey->m_fValue
   float c = 3.0f*(v1 - l_pPrevKey->m_fValue);
   float e = 3.0f*(v2 - v1);
 
   m_fLastEvaluation = (((l_pNextKey->m_fValue - l_pPrevKey->m_fValue - e)*u + e - c)*u + c)*u + l_pPrevKey->m_fValue;
 
   
   if ( m_pParameter != NULL )
    m_pParameter->SetFloatValue( m_fLastEvaluation );
 
   break;
  }
...
 
 
float InvertParamCubic ( float Param, float x0, float x1, float x2, float x3 )
{
 if (Param - x0 < INVERTPARAMCUBIC_SMALLERTOL)
 {
  return 0.0;
 }
 if (x3 - Param < INVERTPARAMCUBIC_SMALLERTOL)
 {
  return 1.0;
 }
 
 long cnt2 = 0;
 
 // de Casteljau Subdivision.
 float u = 0.0f; float v = 1.0f;
 
 while (cnt2 < INVERTPARAMCUBIC_MAXIT) 
 {
  double a = (x0 + x1)*0.5f; double b = (x1 + x2)*0.5f; double c = (x2 + x3)*0.5f;
  double d = (a + b)*0.5f; double e = (b + c)*0.5f; 
  double f = (d + e)*0.5f;
 
  if (fabs(f - Param) < INVERTPARAMCUBIC_TOL) 
  {
   return ClampToZeroOne((u + v)*0.5f);
  }
 
  if (f < Param)
  { 
   x0 = f; x1 = e; x2 = c; u = (u + v)*0.5f;
  }
  else 
  {
   x1 = a; x2 = d; x3 = f; v = (u + v)*0.5f;
  }
 
  cnt2++;
 }
 
 return ClampToZeroOne((u + v)*0.5f);
}