Animation: Bezier interpolation

Hi there,

Is anybody able to provide a good explanation/recommendation on how the output value should be determined when dealing with animation bezier interpolations (IE - when in-tangents and out-tangents are present and the interpolation type is bezier)?

I appreciate this is briefly covered in the specification and also discussed on the forum in places, but there appears to be some ambiguity.

Thanks in advance,
Richard.

In retrospect my original question was a bit vague, so I am going to be a bit more specific.

The animation section of the specification refers to Chapter 4 (which covers Curve Interpolation). The cubic bezier spline equation is given and most of the values are clearly defined. With regards to parameter ‘s’, the following is stated:

‘Equations are given as parametic equations. A parameter s that goes from 0 to 1 is used to calculate all the points on the curve. If s is 0 then the equation gives p0; if s is 1, then the equation gives p1. The equation is not defined outside of those values’.

Is it realistic to use the current time (IE - input) for ‘s’, providing that it is modified to be between 0 and 1? Some of the forum posts seem to indicate that this is too simplistic and would not work - further calculations are necessary.

What is the recommended approach please?

There has been a lot of confusion about this. Basically all the needed information is given in the Spec, and you will find some treatment on this on the forum, too.

You will find a complete description in the current spec on the following places:

http://www.khronos.org/files/collada_spec_1_4.pdf

See page 27 for information about curve interpolation math (Programming guide -> curve interpolation).

See page 136 for a description of the <sampler> element for animation. The newest spec has some additional background information on the animation curve and its interpretation.

But let me give you a hands-on example on what you can expect as an output and how to handle this since the spec might be a little confusing:

I will use a simple project export from Maya with the COLLADAMAYA exporter.

Consider the following scene:

We have a simple cube located in the origin of the scene. We will animate the Z-channel using a bezier curve. See the movie for how the animation looks like.

http://files.hfink.eu/collada/tutorials … xample.mov

We have two keys, one at frame 0 and one at frame 48 (with a framerate-setting of 24fps this equals 2 seconds of playback).

See the animation graph of the z-channel in the following image.

You can easily see we have got the TIME-domain on the horizontal axis, and the animated z-value on the vertical axis (point = (time, z) )

Now, to evaluate this curve we need the following data:

Two interpolation points (i.e. the key-frames) and either their two tangent-vectors, or the two control points of the bezier curve. (since you want to know about Bezier interpolation you want to have the control points).

Let’s see how this maps to Collada (excuse the mess of having images of XML-files…). The important data is highlighted.

As you can see in the image above, the <channel>-element tells us that we are animating the the target “pCube1/translate.Z”. No big surprise, that’s what we want. The <sampler> element binds the sources to sampling-evaluation. The semantics of the inputs describe the following:

INPUT: keypoints of the TIME domain, i.e. seconds, the horizontal axis in the graph above
OUTPUT: keypoints of the animated Z-values, the vertical axis in the graph above
INTERPOLATION: Tells us how to interpolate the INPUT and OUTPUT keypoints
IN_TANGENT:
depending on the INTERPOLATION-method this input holds control points (for INTERPOLATION=BEZIER), or the tangent IN vectors (for INTERPOLATION=HERMITE)

see the spec on pg. 29 for more details about this as this might be a little confusing

OUT_TANGENT: same as above, but for tangent OUT vectors

The input and output arrays of our example look like this:

Input TIME-domain is in seconds (meaning we are animating 2 seconds 48frames/24 fps)
Output is from 0 z-translation to 10 z-translation.

Our interpolation input is BEZIER, so we expect to retrieve Control points from IN_TANGENT and OUT_TANGENT arrays:

So let’s sum up the information we’ve got for interpolating this particular curve segment:

These points are in (time/z-value)-coords:

Let’s use the same naming as in this image from the spec:

P0 (0, 0) … keypoint 0
P1 (2, 10) … keypoint 1
C0 (0.666667, 42.6212) … control point 0
C1 (1.33333, 10) … control point 1

Like the spec says, we can easily define an implicit representation of this curve (meaning a parametric representation):

This introduces a new variable S which “drives” the parametric function. Now imagine the very likely scenario where you would want the following:

Find the animated value Z0 to a given time (input) T0. But this requires us to first find the right parameter value S0 to evaluate the parametric function, because S0 != T0.

Let’s take the following example:

For our particular example we want to retrieve the animated Z-value at time 1.0s (= at frame # 24).
Maya evaluates a Z-value of 20,983 at this particular time, so that’s the value we can use to check our algorithm for validity.

One might be tempted to simple linearly map the T0 value to S0-parameter, like this:

S0 = (T_BEGIN - T0)/(T_END-T_BEGIN)

For our example, S0 would be 0.5.

Confusingly enough, in our particular example (and all others from the Maya exporter using BEZIER interpolation) this even works. Evaluating the parametric function at S=0.5 returns a value of 20.983, just what we expect.

BUT this is a special case, the only reason it works with Maya, is because on the TIME-axis the “speed” of the parametric function does not change! Just look at the tangent vector of P0 and P1 in this example:

T0 = 3 * (C0 - P0) -> (2, 127.86)
T1 = 3 * (P1 - C1) -> (2, 0)

You can see that the TIME-values (X-axis) in T0 and T1 are the same, which could be interpreted as following: “The speed of how TIME input changes” when entering the curve (at P0) and leaving the curve (at P1) is the same, or its acceleration is 0 (my apologies for the wacky terms…) And ONLY because of this we could use the above approach of linear mapping between T and S.

Maya exports the control points with the above constraints by default, but what happens if another DCC-tools handles this differently?

To find the correct S0 matching your requested T0, you could use an algorithm that was previously posted on this forum ( https://collada.org/public_forum/viewtopic.php?p=2556 )

It’s basically an iterative De-casteljau algorithm that is subsequently applied until your given T0 is matched closely (and the mapped S0 will be returned).

I rewrote the posted code for this helper-function a bit for easier readability and understanding:

#define APPROXIMATION_EPSILON 1.0e-09 
#define VERYSMALL 1.0e-20 
#define MAXIMUM_ITERATIONS 1000

//simply clamps a value between 0 .. 1

float ClampToZeroOne(float value) {
	if (value < .0f)
		return .0f;
	else if (value > 1.0f)
		return 1.0f;
	else
		return value;
}

/**
 * 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 < VERYSMALL)
		return 0.0; 
	
	if (P1_X - atX < VERYSMALL)  
		return 1.0; 
	
	long iterationStep = 0; 
	
	float u = 0.0f; float v = 1.0f; 
	
	//iteratively apply subdivision to approach value atX
	while (iterationStep < 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) < APPROXIMATION_EPSILON) 
			return ClampToZeroOne((u + v)*0.5f); 
		
		//dichotomy
		if (f < 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); 
	
}


You would then apply this function like this:

float S0 =  ApproximateCubicBezierParameter ( T0, P0.X, C0.X, C1.X, P1.X);

Then use the parametric function posted above to finally evaluate the Z0 that you are looking for.

Btw, for our example using the latter approach compared to the linearly mapped approach yields the exact same results… but again, the way to handle every case is to use the approaching-technique. But you could check for the tangent constraints and apply the linearly mapped calculation which is less expensive to calculate.

You can download the export COLLADA-file for this example from here:

http://files.hfink.eu/collada/tutorials … xample.dae

Hope that answered your questions,

good luck,

  • h

[EDIT: fixed the calculated tangent values]

Is it realistic to use the current time (IE - input) for ‘s’, providing that it is modified to be between 0 and 1? Some of the forum posts seem to indicate that this is too simplistic and would not work - further calculations are necessary.

No you can’t do this, see my above post for the correct way how to deal with this.

Dear Heinzi,

Thank you so much for writing such a comprehensive and clearly written explanation, it is more than I expected and very much appreciated. The sample movie and dae file are the icing on the cake.

Have a great weekend!

Cheers,
Richard.

Is De-casteljau algorithm only one method to evaluate s or there others?

Is De-casteljau algorithm only one method to evaluate s or there others?

No, you can also solve a cubic equation instead. We have recently used this method to evaluate bezier curves in our renderer for http://hfink.eu/pixelnoir :

Utilities for solving these equations can be found here (that file is not originally by us):

https://github.com/hfink/pixelnoir/blob … rc/roots.h

Checkout the methods AnimEvaluator::AnimEntry::ChannelEntry::update, find_zero and eval_bezier in this source file to see how this is correctly applied on bezier curves:

https://github.com/hfink/pixelnoir/blob … luator.cpp

  • h