3DS MAX Bezier Interpolation

Answer Part 1: Background info

The Bezier curve actually is a piecewise curve. There is a separate curve between every air of points. So, let us label your points:

A: { 0.0, 50.1135, 0.0, -1.0, 0.22815, 0.503991 },
B: { 0.5, 1.34401, 0.00154168, 0.4382, -0.00154168, 0.533158 },
C: { 1.0, 98.6768, 0.00082258, 0.998645, 0.0, -1.0 }

You have 3 points, which makes two pairs, AB and BC. You therefore have two Bezier curve pieces, one between points A and B, and the other between points B and C.

Each Bezier curve piece is a cubic Bezier curve, and has 4 control points. The first and last points are, for example, your points A and B. So, your fist Bezier curve segment looks like:

Bezier curve piece between points A and B
Pt 1: A
Pt 2: ?
Pt 3: ?
Pt 4: B

Point 2 is always determined with the out tangent from point 1, and point 3 is always determined from the in tangent from point 4. So, to continue this example:

Bezier curve piece between points A and B
Pt 1: A
Pt 2: determined from out tangent of A
Pt 3: determined from in tangent of B
Pt 4: B

Likewise, the other curve in your case would be:

Bezier curve piece between points A and B
Pt 1: B
Pt 2: determined from out tangent of B
Pt 3: determined from in tangent of C
Pt 4: C

So, that is the background info. I'll post another message to talk about how to compute points 2 and 3 from the in/out tangent info.

[Edited by - grhodes_at_work on February 9, 2008 4:52:27 PM]

Quote:

Original post by grhodes_at_work (...) So, that is the background info. I'll post another message to talk about how to compute points 2 and 3 from the in/out tangent info.

Thank you. Can't wait to see Part 2!

I have found some info on 3D Studio's Bezier keys, that might be useful...
http://dl3d.free.fr/phpBB2/viewtopic.php?t=32&highlight=bezier

Quote:

(...) It's the tangent of the angle from the tangent and the horizontal axis. And it is a quadratic interpolation.

Answer Part 2: The "semi-documented" way to compute the control points from the in/out tangents.

So, the 3ds max sdk docs are actually not so great. They do not (as of 3ds max version 9, which we are currently using) document IBezFloatKey. There is documentation for IBezPoint3Key, and I imagine things are supposed to be much the same. But, sadly, I do not believe the official max sdk documention for IBezPoint3Key is correct. It provides a function to compute the time value of the tangent-derived control point without mention of the tangent lengths. And when I apply their formula to your #'s, I am unable to reproduce what is on your chart. I do not trust the max sdk documentation!

So, here is what I believe. I believe this is how it should work, regardless of the max sdk docs.

To remind, your points for the first Bezier curve are:

A: { 0.0, 50.1135, 0.0, -1.0, 0.22815, 0.503991 },
B: { 0.5, 1.34401, 0.00154168, 0.4382, -0.00154168, 0.533158 },

And we are trying to compute 4 control points:

Bezier curve piece between points A and B
Pt 1: A
Pt 2: determined from out tangent of A
Pt 3: determined from in tangent of B
Pt 4: B

The time values for points 2 and 3 are easy. The time value of the out tangent is just time value of the point owning the tangent plus the length of the tangent multiplied by the difference between the time value of the next endpoint minus the time value of the endpoint owning the tangent. So, for point A, the next endpoint is B, and therefore the time value of point 2 is:

Given Point1 = AGiven Point4 = BPoint2.time = Point1.time +              (Point1.outTangentLength *(Point4.time -                                         Point1.time));

Plugging in numbers:

Point2.time = 0.0 + (0.503991 * (0.5 - 0.0)) = 0.2519955

That is in time units, not frames. You diagram is in frames, so multiply Point2.time times the total number of frames to get the frame time, or 0.2519955 * 120 = 30.24 frames....that looks just about right, so:

Pt 1: (0.0, 50.1135) (pt A)
Pt 2: (0.251995, ???) (from outtangent of A)
Pt 3: (???, ???) (from intangent of B)
Pt 4: (0.5, 1.344) (pt B)

The time value of point 3 is similar, but since it is an intangent, instead of adding the tangent time to the time value of B, you subtract, so:

Given Point1 = AGiven Point4 = BPoint3.time = Point4.time -              (Point4.outTangentLength *(Point4.time -                                         Point1.time));

Or,

Point3.time = 0.5 - (0.4382 * (0.5 - 0.0)) = 0.2809

To check your graph, multiply by 120 to get 33.71 frames, which looks just about a perfect match with your graph, so:

Pt 1: (0.0, 50.1135) (pt A)
Pt 2: (0.251995, ???) (from outtangent of A)
Pt 3: (0.2809, ???) (from intangent of B)
Pt 4: (0.5, 1.344) (pt B)

So, we have the time values of all 4 points. We need to get the float values to complete the control point set.

I'm going to have to trust the documentation here. I don't have a running copy of 3ds max (licenses all in use by our artists), so I can't verify/test any of this. The tangent values are supposed to actually be the tangent values of the angle between the horizontal axis and the tangent line itself. Which means, the tangent values are supposed to be something like df/dt, where df is the change in float value and dt is the change in time. dt is simply equal to the tangent length times the difference in times between point 4 and 1, so:

dt = tanLength * (Point4.time - Point1.time)

For point 2, dt is 0.503991 * (0.5 - 0.0) = 0.2519955

And since the tan value is (if the max sdk docs are correct - and I do not trust them) df/dt, then df = dt * tan value

And for point 2, df = 0.2519955 * 0.22815 = 0.057493

Add the value of the point owning the tangent to get the tan value, e.g.,

Point2.value = Point1.value + df = 50.1135 + 0.057493 = 50.171

Point 3 would be exactly the same, with dt = 0.4382 * (0.5 - 0.0) = 0.2191, and:

df = 0.2191 * 0.00154168 = 0.000338
Point3.value = Point4.value + df = 1.34401 + 0.000338 = 1.344348

And, with these calcs, the final 4 control points (time, value) are:

Pt 1: (0.0, 50.1135)
Pt 2: (0.251995, 50.171)
Pt 3: (0.2809, 1.344348)
Pt 4: (0.5, 1.344)

PROBLEM:

Now....Hmmmm...I can believe the time values for all the points. I can believe the float values of points 1 and 4---they match the graph, and maybe point 3 (hard to tell on graph since that tangent is nearly zero and so float value doesn't change much from owning point). BUT, it is obvious that the float value for point 2 is wrong. It does not match the graph.

I see one of two possibilities. EITHER my assumption about the actual underlying calculations for the float values are wrong. And it could be, although the way I've done it is fairly intuitive (to me). OR, you have copied in some numbers that don't exactly match the graph that you posted...maybe you changed the tangent after printing the numbers but forgot to update the numbers?

CONFUSION:

I actually spent quite a bit of time trying several different things to compute a reasonable looking float value for point 2. I was unable to do it. If your printed points in your original post are correct, the output created at the same time as the graph you posted, then I would say I have no idea what that tangent value means. I searched the web and found nothing useful. Autodesk has a 3ds max form. We have paid licenses and I could probably register. But I have not done so. I am hoping that someone else who already has solved this problem will post a final answer.

Quote:

Original post by minowa Quote: Original post by grhodes_at_work (...) So, that is the background info. I'll post another message to talk about how to compute points 2 and 3 from the in/out tangent info. Thank you. Can't wait to see Part 2! I have found some info on 3D Studio's Bezier keys, that might be useful... http://dl3d.free.fr/phpBB2/viewtopic.php?t=32&highlight=bezier Quote: (...) It's the tangent of the angle from the tangent and the horizontal axis. And it is a quadratic interpolation.

I saw that too. It isn't useful. I tried that already. It is what the 3ds max docs says, but I don't believe it. The docs are broken. The tangent values are, at this time, a mystery to me. But part 2 should take you another step closer, even if not all the way.

Thank you for your answer, Graham.

Quote:

I see one of two possibilities. EITHER my assumption about the actual underlying calculations for the float values are wrong. And it could be, although the way I've done it is fairly intuitive (to me). OR, you have copied in some numbers that don't exactly match the graph that you posted...maybe you changed the tangent after printing the numbers but forgot to update the numbers?

They were 100% correct.

Here's a MAXScript code I wrote to dump those values - you can paste it to MAXScript Listener and try it yourself (modify the last line to view other controller's numbers).






I found something else on Bezier keys in MAX - a guy, calling himself 'synopsis', wrote this :
http://www.gamedev.net/community/forums/topic.asp?topic_id=69547

Quote:

Well, I've been working on Max exporters for some time, but the documentation is incomplete, incorrect, the examples are too simple for real production environments and there seems to be no support, except for members of the Autodesk Developer Network. For example, export of Bezier controllers doesn't work, unless you multiply the value you get by some bogus constant.

Now check out what I discovered playing with tangents in CurveEditor window - if you multiply key's tangent value by 200 and pass is to atan() - you will get an angle between horizontal axis (time) and tangent direction vector!!

Here's the proof(?) - simple, one-segment curve. I modified first key's out-tangent...

[~90 degrees]

{ 0.0,0.0, 0.0,-1.0, 2966.03,2.08333e-006 },
{ 0.3,-0.0151639, 0.0,0.3333, 0.0,0.3333 },

atan (200 * 2966.03) = 89.9999



[~80 degrees]

{ 0.0,0.0, 0.0,-1.0, 0.0309055,0.201456 },
{ 0.3,-0.0151639, 0.0,0.3333, 0.0,0.3333 },

atan (200 * 0.0309055) = 80.8101



[~60 degrees]

{ 0.0,0.0, 0.0,-1.0, 0.00861794,0.725175 },
{ 0.3,-0.0151639, 0.0,0.3333, 0.0,0.3333 },

atan (200 * 0.00861794) = 59.8783



[~45 degrees]

{ 0.0,0.0, 0.0,-1.0, 0.00615916,0.981541 },
{ 0.3,-0.0151639, 0.0,0.3333, 0.0,0.3333 },

atan (200 * 0.00615916) = 50.9303



[~25 degrees]

{ 0.0,0.0, 0.0,-1.0, 0.00239052,0.992528 },
{ 0.3,-0.0151639, 0.0,0.3333, 0.0,0.3333 },

atan (200 * 0.00239052) = 25.5527

...and so on. But why we have to multiply tangent values by 200.0?! Weird...

What do you think about that?

I have found the way to calculate the control point's value from key's tangent data!!




Here's the example of that 60 degrees tangent...

{ 0.0,0.0, 0.0,-1.0, 0.00861794,0.725175 },
{ 0.3,-0.0151639, 0.0,0.3333, 0.0,0.3333 },



It works!

But now, how to calculate this curve? It isn't a standard Bezier Curve...

[Edited by - minowa on February 9, 2008 1:22:48 AM]

Quote:

Original post by minowa It works!

That, my friend, is the power of communication! Partial ideas, shared, lead to a solution! Congratulations! You taught me something also!

Quote:

Original post by minowa But now, how to calculate this curve? It isn't a standard Bezier Curve...

Aha!!!! It IS a standard Bezier curve! Remember, you have interior control points from two tangents, not just one. even though there is no displayed tangent control bar for the point @ 30 frames (that point is not selected), the tangent is there as given in your printed output.

So, your 4 points are:

Pt 1: (0.0,0.0)Pt 2: (0.725175, 1.01343) - which you computed using your formulasPt 3: (0.6667, 0.0) - which I computed. The value is obviously zeroPt 4: (1.0,-0.0151639)

The time for point 3 is computed using the formula I gave in my first reply:

Pt3.time = Point4.time -              (Point4.outTangentLength *(Point4.time -                                         Point1.time));         = 1.0 - (0.3333 * (1.0 - 0.0)) = 1.0 - 0.3333 = 0.6667

If you convert that into points with frame # instead of time (multiply time
times 30 frames for the curve fragment) to get:

Pt 1: (0,0.0)Pt 2: (21.76, 1.01343) - which you computed using your formulasPt 3: (20, 0.0) - which I computed. The value is obviously zeroPt 4: (30,-0.0151639)

Those #'s look just like your graph plot.

So, I don't have a handy dandy Bezier plotter. Used to have an Excel spreadsheet but its lost on a backup CD from 3 computers back, but no more. I just went to the following Java app and sketched the sequence of control points in the order above...just drawing something that looked like your sequence of points. The Bezier curve looks the same as yours. So, though I'm not comparing 3ds max's exact evaluation #'s to this Java app, and just quickly sketched a convex hull that is visually similar to yours, the curves look the same. And, so I have come to the conclusion that these are indeed standard Bezier curves. (See image below for my reproduction.)

Bezier Curve Demo (Java)

Quote:

Original post by minowa ...and so on. But why we have to multiply tangent values by 200.0?! Weird... What do you think about that?

I don't know what their logic would be to scale the tangents by 1/200. Maybe some real reason, and it might very well have to do with time transformations and/or internal max units that we aren't thinking about or don't know about. I'm not too pleased that their SDK documentation is broken and incomplete. But, most software documentation is broken and incomplete.

Just a small correction - the exact keyframe's unit duration is 6000 MAX ticks (1 tick is 1/4800 sec.). Now results are prefectly perfect! (^_^)

But why they just didn't used 1 second as an unit time?

Quote:

Original post by minowa Just a small correction - the exact keyframe's unit duration is 6000 MAX ticks (1 tick is 1/4800 sec.). Now results are prefectly perfect! (^_^) But why they just didn't used 1 second as an unit time?

Excellent! Hmmm....maybe things are coming together. Traditional cinema frame rates are 24 frames per second. 24 times 200 (!) is 4800. Hmmmm. So, the 4800 has ties to cinema frame rates. Now, 6000/4800 = 1.25. Multiply 24 times 1.25 and you get 30. So, the 6000 gets things back to traditional interlaced television broadcast frame rates of (approximately) 30fps. So, now, all of these numbers make sense now (or at least we see how they tie into media #'s). They just aren't properly documented in the max sdk docs.

Ok, now we got control point values, but how to evaluate this curve? Remember, that this isn't a 2D cubic Bezier curve - it's just have one dimension! Those "tangent lengths" influence control-point interpolation, they can't be treated as a second dimension... So is this a nonrational uniform Bezier spline (NURBS)?

Here are some examples of curves (with numbers)...
Point X (normalized_time) (value)

---

[00]

Point A 	0.0		0.0Point B 	0.352904	1.20318Point C 	0.616205	-1.2828Point D 	1.0		-0.0125875

---

[01]

Point A 	0.0		0.0Point B 	1.00556		1.00697Point C 	0.616205	-1.2828Point D 	1.0		-0.0125875

---

[02]

Point A 	0.0		0.0Point B 	0.13727		1.00559Point C 	0.0701051	-0.282257Point D 	1.0		-0.0125875

---

[03]

Point A 	0.0		0.0Point B 	1.08131		1.00561Point C 	-0.07618	-0.799426Point D 	1.0		-0.0125875

---

Any ideas?

Those shapes are indeed 2D cubic Bezier curves. The tangents and time values are indeed part of the curve definition. But, to evaluate, you have to treat this as two curves. One curve determines parameterized time and the other determines parameterized float value. If you evaluate points along a curve using the standard [0,1] parameterization, you will find that the shape you obtain is the shape you have drawn.

Now, the parameter used to evaluate the curve is linearly proportional to the arc length of the curve starting on the left and ending on the right. That is, the parameter you use is not time. You would, ideally, like to evaluate the curve something like this:

Value(time = t) = Evaluate_Curve(t);

But, instead, you have:

Time(parameter = p) = Evaluate_Curve_With_Time_Control_Pts(p)
Value(parameter = p) = Evaluate_Curve_With_Value_Control_Pts(p)

The idea here is that you're treating time as a cubic Bezier curve based on a linear parameter p being, well, x, and time being, well, y. Then the float value being a second cubic Bezier curve based on the same linear parameter p with p being x and the float value being y. You evaluate time and the float value separately with p being the same for each curve. Hmmm. I have a feeling you know all this. I'm just talking it through.

So, if you treat time and float value as two separate bezier curves, and evaluate both, you will get matching (Time, Value) pairs at any point along the curve.

Now, since the parameter is basically an arc length...it is not linearly proportional to time. You cannot simply substitute time = p * some_constant.

So, you have a choice. Either just sample the curve with some choice of parameter values, say p = 0.0, 0.1, 0.2, ..., 1.0, and take the (Time, Value) coordinates that happen to be evaluated. This would produce inconsistent velocities/speed for the float value since effectively time is slowing down and speeding up as p changes uniformly.

Or, you can find a reverse mapping, e.g., Choose time t = 0.0, 0.1, 0.2, ..., 1.0 and reverse map that to find the corresponding p's, then use the p's to go back and evaluate the float values.

There are a couple of ways you might approach doing the reverse mapping. The first is to sample the curve at a lot of points, getting lots of (p, t) points. Then, you can take your needed t value and interpolate the p value from the input t. Then once you have p, go evaluate the float value.

The other thing you could do, since time (should for these curves) is a montone function of p (e.g., t is a single-valued function of p and p is a single-valued function of t), would be to find the inverse function, e.g., p as a direct function of t instead of t as a function of p. If you find p(t), then you could also find float value(t) directly. I imagine there might be a nice way to do this for the case where t and p are monotonic. But, this isn't something that is currently in my head. It might be simply a matter of flipping the points for the time curve to be (t, p) instead of (p, t), though there's a certain logic in that. Not sure. Not in my head. You certainly could get more accurate numerical results using iterative solvers...and that would make for a more accurate lookup table.

Dave Eberly of Geometric Tools conveniently has a technical document that talks about this reparameterization issue in perhaps more detail. You might find his document helpful:

Moving Along a Curve with Specified Speed