source: OniSplit/Totoro/Animation.cs

using System;
using System.Collections.Generic;
using Oni.Physics;

namespace Oni.Totoro
{
    internal class Animation
    {
        public string Name;
        public AnimationFlags Flags;
        public readonly string[] DirectAnimations = new string[2];
        public float FinalRotation;
        public Direction Direction = Direction.Forward;
        public int Vocalization = 65535;
        public string Impact;
        public int HardPause;
        public int SoftPause;
        public AnimationType Type;
        public AnimationType AimingType;
        public AnimationState FromState;
        public AnimationState ToState;
        public AnimationVarient Varient;
        public int ActionFrame = 65535;
        public int FirstLevelAvailable;
        public BoneMask OverlayUsedBones;
        public BoneMask OverlayReplacedBones;
        public int AtomicStart;
        public int AtomicEnd;
        public int InvulnerableStart;
        public int InvulnerableEnd;
        public int InterpolationMax;
        public int InterpolationEnd;
        public int FrameSize;

        public readonly List<float> Heights = new List<float>();
        public readonly List<Vector2> Velocities = new List<Vector2>();
        public readonly List<List<KeyFrame>> Rotations = new List<List<KeyFrame>>();
        public readonly List<Shortcut> Shortcuts = new List<Shortcut>();
        public readonly List<Position> Positions = new List<Position>();
        public readonly List<Damage> SelfDamage = new List<Damage>();
        public ThrowInfo ThrowSource;
        public readonly List<Sound> Sounds = new List<Sound>();
        public readonly List<Footstep> Footsteps = new List<Footstep>();
        public readonly List<Particle> Particles = new List<Particle>();
        public readonly List<MotionBlur> MotionBlur = new List<MotionBlur>();
        public readonly List<Attack> Attacks = new List<Attack>();
        public readonly float[] AttackRing = new float[36];
        public readonly List<List<Vector3>> AllPoints = new List<List<Vector3>>();

        public void ValidateFrames()
        {
            var error = Console.Error;
            int frameCount = Heights.Count;

            foreach (var sound in Sounds.FindAll(s => s.Start >= frameCount))
            {
                error.WriteLine("Warning: sound start {0} is beyond the last animation frame", sound.Start);
                Sounds.Remove(sound);
            }

            foreach (var footstep in Footsteps.FindAll(f => f.Frame >= frameCount))
            {
                error.WriteLine("Warning: footstep frame {0} is beyond the last animation frame", footstep.Frame);
                Footsteps.Remove(footstep);
            }

            foreach (var damage in SelfDamage.FindAll(d => d.Frame > frameCount))
            {
                error.WriteLine("Warning: damage frame {0} is beyond the last animation frame", damage.Frame);
                SelfDamage.Remove(damage);
            }

            foreach (var attack in Attacks.FindAll(a => a.Start >= frameCount))
            {
                error.WriteLine("Warning: attack start frame {0} is beyond the last animation frame", attack.Start);
                Attacks.Remove(attack);
            }

            foreach (var particle in Particles.FindAll(p => p.Start >= frameCount))
            {
                error.WriteLine("Warning: particle start frame {0} is beyond the last animation frame", particle.Start);
                Particles.Remove(particle);
            }
        }

        public void ComputeExtents(Body body)
        {
            Positions.Clear();
            AllPoints.Clear();

            int frameCount = Heights.Count;
            int boneCount = Rotations.Count;

            var rotations = new Quaternion[frameCount, boneCount];

            //
            // Compute the quaternions for each bone and frame
            //

            for (int bone = 0; bone < boneCount; bone++)
            {
                var keys = Rotations[bone];

                for (int frame = 0; frame < keys.Count; frame++)
                    rotations[frame, bone] = new Quaternion(keys[frame].Rotation);
            }

            var transforms = new Matrix[boneCount];
            var offset = Vector2.Zero;

            for (int frame = 0; frame < frameCount; frame++)
            {
                //
                // Create transforms
                //

                for (int bone = 0; bone < boneCount; bone++)
                {
                    transforms[bone] = Matrix.CreateFromQuaternion(rotations[frame, bone]);
                    transforms[bone].Translation = body.Nodes[bone].Translation;
                }

                //
                // Propagate transforms through the hierarchy
                //

                PropagateTransforms(body.Root, transforms);

                //
                // Apply the root translation
                //

                for (int bone = 0; bone < boneCount; bone++)
                {
                    transforms[bone] *= Matrix.CreateTranslation(offset.X, Heights[frame], offset.Y);
                }

                //
                // Compute the vertical extent for this frame
                //

                var minY = 1e09f;
                var maxY = -1e09f;
                var allFramePoints = new List<Vector3>(8 * boneCount);

                for (int bone = 0; bone < boneCount; bone++)
                {
                    var points = body.Nodes[bone].Geometry.Points;
                    var box = BoundingBox.CreateFromPoints(points);
                    var sphere = BoundingSphere.CreateFromBoundingBox(box);
                    var worldCorners = Vector3.Transform(box.GetCorners(), ref transforms[bone]);
                    var worldCenter = Vector3.Transform(sphere.Center, ref transforms[bone]);

                    minY = Math.Min(minY, worldCenter.Y - sphere.Radius);
                    maxY = Math.Max(maxY, worldCenter.Y + sphere.Radius);
                    allFramePoints.AddRange(worldCorners);
                }

                Positions.Add(new Position {
                    Height = maxY - minY,
                    YOffset = minY,
                    X = offset.X,
                    Z = offset.Y
                });

                AllPoints.Add(allFramePoints);

                offset += Velocities[frame];
            }
        }

        private static void PropagateTransforms(BodyNode bodyNode, Matrix[] transforms)
        {
            foreach (var child in bodyNode.Nodes)
            {
                transforms[child.Index] *= transforms[bodyNode.Index];
                PropagateTransforms(child, transforms);
            }
        }

        public ObjectAnimation[] ToObjectAnimation(Body body)
        {
            var anims = new ObjectAnimation[body.Nodes.Count];

            foreach (var node in body.Nodes)
            {
                anims[node.Index] = new ObjectAnimation {
                    Name = Name + "_" + node.Name,
                    Length = Heights.Count,
                };
            }

            FillObjectAnimationFrames(anims, body.Root, null);

            return anims;
        }

        private void FillObjectAnimationFrames(ObjectAnimation[] anims, BodyNode node, BodyNode parentNode)
        {
            var frames = new ObjectAnimationKey[Velocities.Count];

            //
            // Scale is always 1. Frame length is always 1 too.
            //

            for (int i = 0; i < frames.Length; i++)
            {
                frames[i] = new ObjectAnimationKey {
                    Time = i,
                    Scale = Vector3.One
                };
            }

            //
            // Transform key frames to quaternions.
            //

            var keys = Rotations[node.Index];
            var quats = new Quaternion[keys.Count];
            var isCompressed = FrameSize == 6;

            for (int k = 0; k < keys.Count; k++)
            {
                var key = keys[k];

                if (isCompressed)
                {
                    quats[k] = Quaternion.CreateFromAxisAngle(Vector3.UnitX, MathHelper.ToRadians(key.Rotation.X))
                             * Quaternion.CreateFromAxisAngle(Vector3.UnitY, MathHelper.ToRadians(key.Rotation.Y))
                             * Quaternion.CreateFromAxisAngle(Vector3.UnitZ, MathHelper.ToRadians(key.Rotation.Z));
                }
                else
                {
                    quats[k] = new Quaternion(key.Rotation);
                }
            }

            //
            // Interpolate the quaternions.
            //

            int frame = 0;

            for (int k = 0; k < keys.Count; k++)
            {
                var duration = keys[k].Duration;

                var q1 = quats[k];
                var q2 = (k == keys.Count - 1) ? quats[k] : quats[k + 1];

                for (int t = 0; t < duration; t++)
                    frames[frame++].Rotation = Quaternion.Lerp(q1, q2, (float)t / (float)duration);
            }

            //
            // Build translation and merge with parent anim.
            //

            if (parentNode == null)
            {
                Vector2 offset = Vector2.Zero;

                for (int i = 0; i < frames.Length; i++)
                {
                    //frames[i].Translation = new Vector3(offset.X, 0.0f, offset.Y);
                    offset += Velocities[i];
                }
            }
            else
            {
                for (int i = 0; i < frames.Length; i++)
                {
                    frames[i].Translation = node.Translation;
                }

                var parentFrames = anims[parentNode.Index].Keys;

                for (int i = 0; i < frames.Length; i++)
                {
                    frames[i].Rotation = parentFrames[i].Rotation * frames[i].Rotation;
                    frames[i].Translation = parentFrames[i].Translation + Vector3.Transform(frames[i].Translation, parentFrames[i].Rotation);
                }
            }

            anims[node.Index].Keys = frames;

            foreach (var child in node.Nodes)
                FillObjectAnimationFrames(anims, child, node);
        }
    }
}