Results 1 to 5 of 5

Thread: Animation: TCB Spline Interpolation in COLLADA

  1. #1
    Junior Member
    Join Date
    Jul 2008
    Posts
    4

    Animation: TCB Spline Interpolation in COLLADA

    If I understood correctly, TCB spline interpolation is supported in Collada, however, I can find nothing in the specification about how it's implemented. It also could be that it's a 3d studio max specific "upgrade" to the collada standard. However, to support loading 3DSM models correctly, i'm forced to include support for TCB splines.

    Here's the interesting part in the collada file:
    Code :
          <source id="Bone14-node-rz_Bone14-node_RotZ.ANGLE-tcbs">
            <float_array id="Bone14-node-rz_Bone14-node_RotZ.ANGLE-tcbs-array" count="24">0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5</float_array>
            <technique_common>
              <accessor source="#Bone14-node-rz_Bone14-node_RotZ.ANGLE-tcbs-array" count="8" stride="3">
                <param type="float"/>
                <param type="float"/>
                <param type="float"/>
              </accessor>
            </technique_common>
          </source>
          <source id="Bone14-node-rz_Bone14-node_RotZ.ANGLE-eases">
            <float_array id="Bone14-node-rz_Bone14-node_RotZ.ANGLE-eases-array" count="16">0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5</float_array>
            <technique_common>
              <accessor source="#Bone14-node-rz_Bone14-node_RotZ.ANGLE-eases-array" count="8" stride="2">
                <param type="float"/>
                <param type="float"/>
              </accessor>
            </technique_common>
          </source>
     
          <sampler id="Bone14-node-rz_Bone14-node_RotZ.ANGLE-sampler">
            <input semantic="INPUT" source="#Bone14-node-rz_Bone14-node_RotZ.ANGLE-input"/>
            <input semantic="OUTPUT" source="#Bone14-node-rz_Bone14-node_RotZ.ANGLE-output"/>
            <input semantic="INTERPOLATION" source="#Bone14-node-rz_Bone14-node_RotZ.ANGLE-interpolations"/>
            <input semantic="TCB" source="#Bone14-node-rz_Bone14-node_RotZ.ANGLE-tcbs"/>
            <input semantic="EASE_IN_OUT" source="#Bone14-node-rz_Bone14-node_RotZ.ANGLE-eases"/>
          </sampler>

    I presume the three floats in TCB are Tension, Continuity, and Bias respectively, and the EASE_IN_OUT floats ease_in and ease_out. Now the only problem, what's the algorithm/mathematics used to get usable results from these values?

    My current implementation is as following, but it's not even close to acting in the way it's supposed to be (i used http://www.cubic.org/docs/hermite.htm as my reference) :

    Code :
    inline float TCBTangentEquationIncoming(float& pm1, float& p0, float& p1, float& t, float& c, float& b)
    {
    	return ((1-t)*(1-c)*(1+b))/2*(p0-pm1) + ((1-t)*(1+c)*(1-b))/2*(p1-p0);
    }
     
    inline float TCBTangentEquationOutgoing(float& pm1, float& p0, float& p1, float& t, float& c, float& b)
    {
    	return ((1-t)*(1+c)*(1+b))/2*(p0-pm1) + ((1-t)*(1-c)*(1-b))/2*(p1-p0);
    }
     
    float* CMatrix::ConcatFloat4Array(float* farr)
    {
    	float* V=new float[4];
     
    	V[0] = farr[0]*Matrix[0][0] + farr[1]*Matrix[1][0] + farr[2]*Matrix[2][0] + farr[3]*Matrix[3][0];
    	V[1] = farr[0]*Matrix[0][1] + farr[1]*Matrix[1][1] + farr[2]*Matrix[2][1] + farr[3]*Matrix[3][1];
    	V[2] = farr[0]*Matrix[0][2] + farr[1]*Matrix[1][2] + farr[2]*Matrix[2][2] + farr[3]*Matrix[3][2];
    	V[3] = farr[0]*Matrix[0][3] + farr[1]*Matrix[1][3] + farr[2]*Matrix[2][3] + farr[3]*Matrix[3][3];
     
    	return V;
    }
     
    CMatrix& GetHermiteMatrix()
    {
    	static bool matrixInited=false;
    	static CMatrix hm;
    	if(matrixInited)
    		return hm;
     
    	hm.Matrix[0][0] = 2; hm.Matrix[1][0] = -2; hm.Matrix[2][0] = 1; hm.Matrix[3][0] = 1;
    	hm.Matrix[0][1] = -3; hm.Matrix[1][1] = 3; hm.Matrix[2][1] = -2; hm.Matrix[3][1] = -1;
    	hm.Matrix[0][2] = 0; hm.Matrix[1][2] = 0; hm.Matrix[2][2] = 1; hm.Matrix[3][2] = 0;
    	hm.Matrix[0][3] = 1; hm.Matrix[1][3] = 0; hm.Matrix[2][3] = 0; hm.Matrix[3][3] = 0;
     
    	matrixInited = true;
    	return hm;
    }
     
    //! pm1 (y coordinate of the previous point)
    //! p0 (y coordinate of the current point)
    //! p1 (y coordinate of the next point)
    //! p2 (y coordinate of the next+1 point)
    //! s (interpolation value, use ApproximateCubicBezierParameter?...)
    //! to0 (tangent out of (p0))
    //! ti1 (tangent in of (p1))
    float InterpolateTCB(float pm1, float p0, float p1, float p2, float s, float to0, float ti1)
    {
    	float S[4], C[4];
    	S[3] = 1;
    	S[2] = s; // s
    	S[1] = s*s; // s^2
    	S[0] = S[1]*s; // s^3
     
    	C[0] = p0;
    	C[1] = p1;
    	C[2] = to0;
    	C[3] = ti1;
     
            // according to [url]http://www.cubic.org/docs/hermite.htm[/url]
            // resulting vector = S * MHermite * C;
            // [b](Vector * Matrix? Usually you do Matrix * Vector right?, this is probably where I went wrong in the TCB interpolation code...)[/b]
    	float* res=GetHermiteMatrix().ConcatFloat4Array(C); // MHermite * C
    	res[0] *= S[0]; res[1] *= S[1]; res[2] *= S[2]; res[3] *= S[3]; // S * PreviousResult
     
    	float y=res[1];
    	delete res; 
     
    	return y;
    }
     
     
    float CFormula::Value(float X)
    {
    	unsigned int ps=PointCount();
    	if(ps == 0)
    		return 0.0f;
    	else if(X &lt; points[0].x)
    		return points[0].y;
    	else if(X &gt;= points[ps - 1].x)
    		return points[ps - 1].y;
     
    	int segment=this-&gt;PointSegmentLocation(X);
     
    	if(InterpolationType == INTERPOLATE_CUBICBEZIER)
    	{
    		InterpolatePoint& p1=points[segment];
    		InterpolatePoint& p2=points[segment+1];
     
    		float s = ApproximateCubicBezierParameter( X, p1.x, p1.tangentOutX, p2.tangentInX, p2.x );
     
    		float s1 = (1-s);
    		float s2 = s1*s1;
    		float ss2 = s*s;
     
    		return p1.y*s2*s1+3*p1.tangentOutY*s*s2+3*p2.tangentInY*ss2*s1+p2.y*ss2*s;
    	}
    	else if (InterpolationType == INTERPOLATE_TCB)
    	{
                    // [b]the first and last points are duplicated when it's out of bounds. No idea if Collada/3DSM intended to do the same?![/b]
    		InterpolatePoint& pm1=points[segment-1&lt;0?segment:segment-1];
    		InterpolatePoint& p0=points[segment];
    		InterpolatePoint& p1=points[segment+1];
    		InterpolatePoint& p2=points[segment+2&gt;=PointCount()?segment+1:segment+2];
     
                    // reusing some point parameters here.., you can also see that there's [b]no ease-in and ease-out[/b] yet, as i had no clue how to implement those.
    		float& t= p0.tangentInX; 
    		float& c= p0.tangentInY;
    		float& b= p0.tangentOutX;
     
                    // ease variables.
                    //float& easein= p0.tangentOutY;
                    //float& easeout= p0.easeout;
     
    		float to0x = TCBTangentEquationOutgoing(pm1.x, p0.x, p1.x, t, c, b);
    		float to0y = TCBTangentEquationOutgoing(pm1.y, p0.y, p1.y, t, c, b);
    		float ti1x = TCBTangentEquationIncoming(p0.x, p1.x, p2.x, t, c, b);
    		float ti1y = TCBTangentEquationIncoming(p0.y, p1.y, p2.y, t, c, b);
                    // [b]this is probably very wrong, TCB != CubicBezier...[/b]
    		float s = ApproximateCubicBezierParameter( X, p0.x, to0x, ti1x, p1.x );
     
    		return InterpolateTCB(pm1.y, p0.y, p1.y, p2.y, s, to0y, ti1y);
    	}
     
    	float Factor=(X-points[segment].x) / (points[segment+1].x-points[segment].x);
     
    	switch(InterpolationType)
    	{
    	case INTERPOLATE_LINEAR:
    		return InterpolateLinear(points[segment].y, points[segment+1].y, Factor);
    	case INTERPOLATE_COSINE:
    		return InterpolateCosine(points[segment].y, points[segment+1].y, Factor);
    	case INTERPOLATE_CUBIC:
    		{
    		float y0 = points[segment-1&lt;0?segment:segment-1].y, y3=points[segment+2&gt;=PointCount()?segment+1:segment+2].y;
    		return InterpolateCubic(y0, points[segment].y, points[segment+1].y, y3, Factor);
    		}
    	case INTERPOLATE_CATMULLROM:
    		{
    		float y0 = points[segment-1&lt;0?segment:segment-1].y, y3=points[segment+2&gt;=PointCount()?segment+1:segment+2].y;
    		return InterpolateCatmullRom(y0, points[segment].y, points[segment+1].y, y3, Factor);
    		}
    	case INTERPOLATE_HERMITE:
    		{
    		float y0 = points[segment-1&lt;0?segment:segment-1].y, y3=points[segment+2&gt;=PointCount()?segment+1:segment+2].y;
    		return InterpolateHermite(y0, points[segment].y, points[segment+1].y, y3, HermiteTension, HermiteBias, Factor);
    		}
    	}
    }
     
    //simply clamps a value between 0 .. 1
     
    float ClampToZeroOne(float value) {
       if (value &lt; .0f)
          return .0f;
       else if (value &gt; 1.0f)
          return 1.0f;
       else
          return value;
    }
     
    // the following function i got from the collada specification, but it's intended for the "BEZIER" type of interpolation, which works fine by the way..
     
    /**
     * Returns the approximated parameter of a parametric curve for the value X
     * @param atX At which value should the parameter be evaluated
     * @param P0_X The first interpolation point of a curve segment
     * @param C0_X The first control point of a curve segment
     * @param C1_X The second control point of a curve segment
     * @param P1_x The second interpolation point of a curve segment
     * @return The parametric argument that is used to retrieve atX using the parametric function representation of this curve
     */
     
    float ApproximateCubicBezierParameter (
             float atX, float P0_X, float C0_X, float C1_X, float P1_X ) {
     
       if (atX - P0_X &lt; VERYSMALL)
          return 0.0;
     
       if (P1_X - atX &lt; VERYSMALL) 
          return 1.0;
     
       long iterationStep = 0;
     
       float u = 0.0f; float v = 1.0f;
     
       //iteratively apply subdivision to approach value atX
       while (iterationStep &lt; MAXIMUM_ITERATIONS) {
     
          // de Casteljau Subdivision.
          double a = (P0_X + C0_X)*0.5f;
          double b = (C0_X + C1_X)*0.5f;
          double c = (C1_X + P1_X)*0.5f;
          double d = (a + b)*0.5f;
          double e = (b + c)*0.5f;
          double f = (d + e)*0.5f; //this one is on the curve!
     
          //The curve point is close enough to our wanted atX
          if (fabs(f - atX) &lt; APPROXIMATION_EPSILON)
             return ClampToZeroOne((u + v)*0.5f);
     
          //dichotomy
          if (f &lt; atX) {
             P0_X = f;
             C0_X = e;
             C1_X = c;
             u = (u + v)*0.5f;
          } else {
             C0_X = a; C1_X = d; P1_X = f; v = (u + v)*0.5f;
          }
     
          iterationStep++;
       }
     
       return ClampToZeroOne((u + v)*0.5f);
     
    }

    So, is there any hope for me to get this thing to work?

  2. #2
    If I understood correctly, TCB spline interpolation is supported in Collada
    Yes, in so far as HERMITE interpolation is supported which is interchangeable with BEZIER interpolation (after converting the variables). TCB are also called Kochanek Bartels splines:

    http://en.wikipedia.org/wiki/Kochanek%E ... els_spline

    ...and just a special case of a HERMITE interpolation.

    In my understanding, you can always convert the hermite-interpolation into a bezier-interpolation by calculating the control points out of the tangents. So catmull-rom, kochanek-bartels and others are simply special conditions and ways how to calculate the tangents for hermite interpolation and thus interchangeable with bezier. This might simplify your code a bit, too.

    Can you post the whole <animation>...</animation> element? I tried to export something animated from 3dmax 2008 with ColladaMax 3.05B and never ran into TCB splines. The exporter always converts it to BEZIER interpolation (that's the reason I ask for the whole animation-element, as I wonder what your INTERPOLATION array looks like).

    Which 3dmax version are you using, more importantly which exporter?

  3. #3
    Junior Member
    Join Date
    Jul 2008
    Posts
    4
    Quote Originally Posted by heinzi
    Which 3dmax version are you using, more importantly which exporter?
    I'm currently using 3d Studio Max 8, but I can't seem to find the exact version, not in the plugin manager window, nor in the .dle file itself. I do have the date of the file though: 15 february 2008..

    It only gives TCB interpolation when explicitly asked in 3d studio max (by assigning a TCB controller in the Motion panel), and whilst most projects indeed only require bezier, i stumbled across some cases requiring TCB.

    Quote Originally Posted by heinzi
    TCB are also called Kochanek Bartels splines:

    http://en.wikipedia.org/wiki/Kochanek%E ... els_spline

    ...and just a special case of a HERMITE interpolation.
    Yes, I've seen the wiki page, in fact it was my first point of reference .

    In the meantime, I've gotten the Tension, Continuity and Bias part to work as well.

    One of the problems was that according to the website I was reading on, they wanted to multiply a vector by a vector. Which is undefined behavior, but it usually means dot product. After applying that, it works flawlessly.

    It also seems that the "s" variable, like in your cubic bezier example, is just a linearly interpolated value in this case, instead of needing to approximate. The linear sampled version that ColladaMax spits out, compared to the regular one, now looks virtually the same in my engine, which is good =)

    However, that's only because I didn't use the "ease from" and "ease to" values, since I still have no clue how to tackle those variables, so they're basically ignored in my interpolation code.

    Also, I've noticed that I had to invert the sign of the T, C and B values coming from the collada file. No idea where that difference comes from...

    Oh yes, the collada samples, I posted the entire file on rapidshare, so you can test it in whatever you're using to render, which might be easier

    http://rapidshare.com/files/128741208/t ... r.rar.html

    Four boxes, the first one uses TCB translation, and the other ones test the bezier interpolation type. (scaling, translation and rotation respectively)

    t2 is the same thing, but everything sampled linearly, for use as a point of reference.

    And umm, thanks for replying in such short notice, looking forward to your next reply

  4. #4
    If you look at the spec on page 137 it says the following:

    COLLADA recognizes the following interpolation types: LINEAR, BEZIER, CARDINAL, HERMITE,
    BSPLINE, and STEP. These symbolic names are held in a <source> element that contains a
    <Name_array> that stores them. These values are fed into the sampler by the INTERPOLATION
    <input> element.
    So I am a bit surprised that COLLADAMAX simply exports a TCB interpolation array and uses <technique_common> for that...

    however, since ColladaMax is opensource, you could simply download their sourcecode and look for TCB, if you still have problems:

    Download it from here:

    http://sourceforge.net/projects/colladamaya/

    You could start for example in:

    SVN_ROOT\trunk\FCollada\FCDocument\FCDAnimationCur ve.cpp(55):static void ComputeTCBTangent(..)

    You will probably find something about the ease in and ease out parameters, too.

    I'm not sure if the "s" variable of my previous Bezier example can be linearly mapped in a general TCB case. Are the TIME-value of the IN and OUT tangents the same?

    - h

  5. #5
    Junior Member
    Join Date
    Jul 2008
    Posts
    4
    Quote Originally Posted by heinzi
    however, since ColladaMax is opensource, you could simply download their sourcecode and look for TCB, if you still have problems:
    Cool, I didn't know they were open source, that'll probably help me a lot, will look into it later this afternoon.


    Quote Originally Posted by heinzi
    I'm not sure if the "s" variable of my previous Bezier example can be linearly mapped in a general TCB case. Are the TIME-value of the IN and OUT tangents the same?
    In my case, the time is mapped to the X coordinate (INPUT), and the output to the Y value...

    The computation of the tangents is as following:
    Code :
    // pm1: p(i-1), p0: p(i), p1: p(i+1), p2: p(i+2)
    // tangent out of point 0 (p(i))
    float to0x = TCBTangentEquationOutgoing(pm1.x, p0.x, p1.x, t, c, b);
    float to0y = TCBTangentEquationOutgoing(pm1.y, p0.y, p1.y, t, c, b);
    // tangent in of point 1 (p(i+1))
    float ti1x = TCBTangentEquationIncoming(p0.x, p1.x, p2.x, t, c, b);
    float ti1y = TCBTangentEquationIncoming(p0.y, p1.y, p2.y, t, c, b);

    So I think they're not equal, as they originate from two different points. However seemingly, linearly mapping the s variable seems to do the trick, as I can't find any differences compared to 3d studio max. As long as it works, I'm happy

    Now, I better get digging in ColladaMax then

    Edit: I checked the file you were suggesting me, and look what i found T_T

    463 if (is2DEvaluation) t = FindT(tkey1->input, bx, cx, endKey->input, input, t);
    464 // else { //Need to figure out algorithm for easing in and out.
    465 // t = Ease(t, tkey1->easeIn, tkey1->easeOut);
    466 // }

    Doesn't look really promising, however I think i'll just download the entire svn tree and do a Search In Files on it. Maybe that'll yield some results..

Posting Permissions

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