01082006, 11:37 PM  #1 
User

Interpolation in the MDL/X
This was written as two posts in reply to a question on another thread, so it's not written in the best style and it's in the two following posts:
__________________ 
Sponsored Links  Login to hide this ad! 

01082006, 11:38 PM  #2 
User

A (not quite) brief tutorial on Interpolation
A (not quite) brief tutorial on Interpolation:
__________________Interpolation is a group of methods for using some information you have in order to guess about information you don't have. For warcraft 3 models, that means taking two coordinates that each have an associated time and creating a coordinate at some time in between using some formula. For math purposes, the time used for the first coordinate is 0, and the time used for the second coordinate is 1, but using some algebra you can use any other time values you want. For translation, scaling, and anything else(like alpha values) that isn't isn't a rotation: The basic method, Linear Interpolation, uses a formula based on making a line between two points: MiddleValue = (Time * (EndValue  StartValue)) + StartValue which, can be simplified to: MiddleValue = ((1  Time) * StartValue) + (Time * EndValue) Basically, you take some part of StartValue and some part of EndValue, and add them together. If Time is 0, you get StartValue If Time is 1 you get EndValue For Time values in between, you get more of StartValue the closer Time is to 0, and more of EndValue the closer Time is to 1. Another way to understand it is that you're taking an average, except that instead of multiplying each part by 0.5 (same as dividing by 2), you're giving each half different importance depending on how much time has passed (because you want to start one place, and end at the other). Ok, so how do InTan and OutTan factor into this? They're used in higher order interpolation, which means interpolation that uses more information than just two points to make shapes other than a straight line. Warcraft 3 allows the use of two types of spline interpolation: 3rddegree (cubic) hermite curves, and 3rddegree(cubic) bezier curves. 3rddegree means (in this context) that they work with 4 pieces of information. Cubic Hermite curves take the two endpoints, just like linear interpolation, but also take a tangent for each point. The tangent is the direction the curve is going at that point. For example, a tangent of (0, 0, 1) would mean that at the point, the curve is going straight up (because Z=1 means up). The longer the tangent (meaning if you take the vector length, which means square all parts, add them up, then take the square root), the more the curve will travel in that direction. The curve blends between the two tangents in addition to the two coordinates to create a more rounded transistion. For Hermite Curves, InTan is the tangent when a coordinate is used as the end point, and OutTan is the tangent when a coordinate is used as the start point. For example, blending between an animation at time 0 to animation at time 500, it uses the coordinate for 0 as the start point, the OutTan for 0 as the start tangent, the coordinate for 500 as the ending point, and the InTan for 500 as the ending tangent. Cubic Bezier curves are essentially the same thing, but in a different format. Instead of giving tangents directly, you have to give control points instead. At the start point, the curve is going straight toward the first control point, and at the end point, the curve is coming straight from the second control point. You can think of it as FirstControlPoint = StartPoint + StartTangent and SecondControlPoint = EndPoint + EndTangent It's just like a Cubic Hermite Curve, except that instead of specifying a tangent directly, you have to add the related coordinate to the value. For Bezier Curves, InTan is the second control point when a coordinate is used as the end point, and OutTan is the first control point when a coordinate is used as the start point. For example, blending between an animation at time 0 to animation at time 500, it uses the coordinate for 0 as the start point, the OutTan for 0 as the first control point, the coordinate for 500 as the ending point, and the InTan for 500 as the second control point. The curve blends between two lines (from a coordinate to the related control point) to create a more rounded transistion. For rotation, things are more difficult because rotation is not stored in vectors (which are easy to manipulate), but in Quaternions, which can be a difficult mathematical beast. Put simply, they're like a special kind of vector that holds rotations (Quaternion Rotation) instead of positions. Instead of linear interpolation,a method called Spherical Linear Interpolation must be used to get smooth rotations. This doesn't have any affect in what you put in an MDL file if you use Linear  you still just put the values you want and the game blends between them, but the information might help you understand Quaternions. I'm not sure how Cubic Hermite or Cubic Bezier interpolation applies to rotation, but I'm fairly certain just sticking quaternions into the normal curve formulas would not work. 
01082006, 11:38 PM  #3 
User

A (still not) brief tutorial on creating rotations
A (still not) brief tutorial on creating rotations:
__________________Ok, so you know Quaternion Rotation is how rotations are represented, but still have no idea how to use them. There are two things you need to know to use basic quaternions  how to do a basic rotation, and how to combine rotations. First, to make a basic rotation that spins in circles, you need to know that a rotation quaternion has basically 4 parts: XR, YR, ZR, and WR. Note that I put an R after them because they're not the same thing as the parts of a vector. Lets say you have a vector, like (0, 0, 1) which is straight up, and you want to rotate around that in a circle constantly. Well, to rotate in a complete circle, you'll need to animate a rotation starting at 0 degrees, then to 120 degrees, then to 240 degrees, then to 360 degrees (which is the same as 0). Why did I pick these numbers? Well, for a circle, you have to go from 0 to 360, but if you just put 0 then 360 there will be no rotation because they are the same rotation. Why not do a simple halfway point and do 0, 180, 360? There are two ways to go from 0 to 180, either clockwise or counterclockwise, and there is no telling which way the math will come out when you do that, so you can get the wrong rotation any time you try to rotate exactly 180 degrees. Maybe do something like 0, 1, then 360? That doesn't work because the math always picks the shortest rotation, so it would rotate 1 degree, then 2 degrees the other way. All this means that it takes at least 4 frames to do a full rotation, and while you can pick other numbers (as long as each rotation is less than 180 degrees), if you want a smooth rotation at constant speed it's easiest to just use equallyspaced numbers and equallyspaced frames. Ok, so we want to rotate around (0, 0, 1) and go from angle 0 to 120 to 240 to 360. Convert an axis and angle pair to a quaternion is simple: XR = Sine(Angle/2) * X YR = Sine(Angle/2) * Y ZR = Sine(Angle/2) * Z WR = Cosine(Angle/2) So what are X, Y, and Z? They're not just the parts of the axis, they're parts of the normalized axis vector. Sine and Cosine are the standard Trigonometric Functions. Ok, so we have a formula, now what? Well, first the rotation should apply all the time, for any animation, so it needs an entry in the GlobalSequences section. Let's make it take 3 seconds to do a full rotation: Code:
GlobalSequences 1 { Duration 3000, } Code:
Rotation 4 { Linear, //Linear Interpolation works fine for rotations GlobalSeqId 0,//Only global sequence there is //Axis = X 0.00000000 / Y 0.00000000 / Z 1.00000000 0: { 0.00000000, 0.00000000, 0.00000000, 1.00000000 },//@ 0.00 1000: { 0.00000000, 0.00000000, 0.86602540, 0.50000000 },//@ 120.00 2000: { 0.00000000, 0.00000000, 0.86602540, 0.50000000 },//@ 240.00 3000: { 0.00000000, 0.00000000, 0.00000000, 1.00000000 },//@ 360.00 } Ok, now for the actual rotations: Applying the formula for axis of (0, 0, 1) and angle 120, we get: XR = Sine(120/2) * 0 = 0 YR = Sine(120/2) * 0 = 0 ZR = Sine(120/2) * 1 = 0.866... WR = Cosine(120/2) = 0.5 And there you have it, the quaternion for a 120 degree turn around the Z (vertical) axis Apply the formula with the angle 240 degrees, and the only thing that changes is that WR is 0.5 Make a special note that specifying 3000 for the duration means the animation goes from frame 0 to 2999, and frame 3000 is never displayed. The reason we specify a rotation for frame 3000 is that frame 2000 needs to blend back to frame 0 to make a smooth cycle, but warcraft 3 won't do that automatically. Instead, we put frame 3000 the same as frame 0 so it blends from frame 2000 up to 2999 with a frame just like frame 0, so the effect is the same (but more work). One final thing to note about this is that it's not just rotating the model, it's rotating it's axis also. What does that mean? It means that if you rotate around the horizontal axis X (1, 0, 0) by 90 degrees, you just swapped the Y and Z axis, and Y is up/down and Z is horizontal! Remeber this when you combine rotations, because you'll get the wrong result if you don't take it into consideration. Ok, now to combine rotations(quite a bit longer) Code:
A = (FirstWR + FirstXR)*(SecondWR + SecondXR); B = (FirstZR  FirstYR)*(SecondYR  SecondZR); C = (FirstWR  FirstXR)*(SecondYR + SecondZR); D = (FirstYR + FirstZR)*(SecondWR  SecondXR); E = (FirstXR + FirstZR)*(SecondXR + SecondYR); F = (FirstXR  FirstZR)*(SecondXR  SecondYR); G = (FirstWR + FirstYR)*(SecondWR  SecondZR); H = (FirstWR  FirstYR)*(SecondWR + SecondZR); WR = B + (E  F + G + H) / 2 XR = A  ( E + F + G + H) / 2 YR = C + ( E  F + G  H) / 2 ZY = D + ( E  F  G + H) / 2 Lets say we want to rotate an object 90 degrees on the X axis (to tip it over on it's side), and then have it rotate it in a horizontal circle. You might think we could use the information from above where we rotated the object around the Z axis (making a horixontal circle), but because of the Xaxis rotation here, the Z axis isn't the vertical axis any more. So first, we need to do the Xaxis rotation, then make the circle around the Yaxis because it is the vertical axis now. This gives: Code:
Rotation 4 { Linear, //Linear Interpolation works fine for rotations GlobalSeqId 0,//Only global sequence there is 0: { 0.70710678, 0.00000000, 0.00000000, 0.70710678 }, 1000: { 0.35355339, 0.61237244, 0.61237244, 0.35355339 }, 2000: { 0.35355339, 0.61237244, 0.61237244, 0.35355339 }, 3000: { 0.70710678, 0.00000000, 0.00000000, 0.70710678 }, } 
01132006, 04:38 AM  #4 
User
Join Date: May 2004
Posts: 132

I will add all of the knowledge that I have on bone rotations, SLerp, Hermite interpolation, and the InTan, OutTan in MDLs.
As you may have discovered, WarcraftIII models mainly have hermite in bone rotations and use SLerp (Spherical Linear Interpolation) for interpolating bone rotation...I think. Here is a formula off of http://numbernone.com/product/Under...%20Using%20It/ Written in C++ Quaternion slerp(Quaternion const &v0, Quaternion const &v1, double t) { v0 is the initial bone position and v1 is next bone position and t is a scalar value // v0 and v1 should be unit length or else // something broken will happen. // Compute the cosine of the angle between the two vectors. double dot = dot_product(v0, v1); This pertains to omega which represents cos theta = v0 (dot product) v1 and is found in wikipedia's formula for SLerp const double DOT_THRESHOLD = 0.9995; if (dot > DOT_THRESHOLD) { // If the inputs are too close for comfort, linearly interpolate // and normalize the result. Quaternion result = v0 + t*(v1 – v0); result.normalize(); return result; } Clamp(dot, 1, 1); // Robustness: Stay within domain of acos() double theta_0 = acos(dot); // theta_0 = angle between input vectors double theta = theta_0*t; // theta = angle between v0 and result Quaternion v2 = v1 – v0*dot; v2.normalize(); // { v0, v2 } is now an orthonormal basis return v0*cos(theta) + v2*sin(theta); } How SLerp works and how it improves the smoothness of a rotation: "Figure 1: We want to find the vector r that is at angle θ from v0." "Figure 2: Using v1, we build the orthonormal basis { v0, v2 }, which allows us to easily compute r." Linear Interpolation is good for easy rotations, but is choppy for most rotations. Now for those hermite splines and what not: From my extensive research on hermite stuff, hermite splines are used in keyframing to create a smooth transition from keyframe to keyframe. I believe 3dsMax uses TCB (tension, bias, continuity) splines in their interpolation. TCB splines As a side note, tension pertains to the speed at which a position is interpolated to another position (smooth bellcurve at tension = 1 and sharp pointy curve at tension = 1), bias pertains to the skewedness of the spline (curve slopes up fast on the left at bias = 1 and slopes down slowly and the curve initially slopes slowly but then drops quickly on the right when bias = 1), and continuity pertains to the continuity of the derivative of the curve or, in the common tongue, the smoothness of the curve as it approaches the next position and the smoothness as it leaves that position (continuity of 1 is a smooth curve throught the next position and a continuity of 1 curves sharply into the next position and sharply curves out of it). Hermite splines Finally, hermite splines use 4 formulas to interpolate keyframes. The formulas are the function for the initial position, the function for the derviative (tangent) of the initial position, the function for the next position, and the function for the derivative (tangent) of the next position. There are also formulas for calculating hermite spline interpolation, but they are complex and are everywhere on the internet. Google "hermite spline""interpolation." Now if we could only figure out a way to export this "knowledge" from MilkShape3d.......that would help me LOTS. 
Thread Tools  Search this Thread 

