diff options
Diffstat (limited to 'Runtime/Animation/KeyframeReducer.cpp')
| -rw-r--r-- | Runtime/Animation/KeyframeReducer.cpp | 359 |
1 files changed, 359 insertions, 0 deletions
diff --git a/Runtime/Animation/KeyframeReducer.cpp b/Runtime/Animation/KeyframeReducer.cpp new file mode 100644 index 0000000..ac3650e --- /dev/null +++ b/Runtime/Animation/KeyframeReducer.cpp @@ -0,0 +1,359 @@ +#include "UnityPrefix.h" +#include "KeyframeReducer.h" +#include "AnimationClip.h" +#include "Runtime/Math/Quaternion.h" +#include "AnimationCurveUtility.h" +#include "Runtime/Input/TimeManager.h" +#include "Runtime/Animation/MecanimClipBuilder.h" +#include <sstream> +#include <vector> + +using namespace std; + +#define DEBUG_COMPRESSION 0 + +const float kPositionMinValue = 0.00001F; +const float kQuaternionNormalizationError = 0.001F;/// The sampled quaternion must be almost normalized. + +/// - We allow reduction if the reduced magnitude doesn't go off very far +/// - And the angle between the two rotations is similar +inline bool QuaternionDistanceError (Quaternionf value, Quaternionf reduced, const float quaternionDotError) +{ + float magnitude = Magnitude(reduced); + if (!CompareApproximately(1.0F, magnitude, kQuaternionNormalizationError)) + { + return false; + } + + value = NormalizeSafe(value); + reduced = reduced / magnitude; + + // float angle = Rad2Deg(acos (Dot(value, reduced))) * 2.0F; + // if (dot > kQuaternionAngleError) + // return false; + if (Dot(value, reduced) < quaternionDotError) + { + return false; + } + + return true; +} + +bool DeltaError(const float value, const float reducedValue, const float delta, const float percentage, const float minValue) +{ + const float absValue = Abs(value); + // (absValue > minValue || Abs(reducedValue) > minValue) part is necessary for reducing values which have tiny fluctuations around 0 + return (absValue > minValue || Abs(reducedValue) > minValue) && (delta > absValue * percentage); +} + +/// We allow reduction +// - the distance of the two vectors is low +// - the distance of each axis is low +inline bool PositionDistanceError (Vector3f value, Vector3f reduced, const float distancePercentageError) +{ + const float percentage = distancePercentageError; + const float minValue = kPositionMinValue * percentage; + + // Vector3 distance as a percentage + float distance = SqrMagnitude(value - reduced); + float length = SqrMagnitude(value); + float lengthReduced = SqrMagnitude(reduced); + //if (distance > length * Sqr(percentage)) + if (DeltaError(length, lengthReduced, distance, Sqr(percentage), Sqr(minValue))) + return false; + + // Distance of each axis + float distanceX = Abs(value.x - reduced.x); + float distanceY = Abs(value.y - reduced.y); + float distanceZ = Abs(value.z - reduced.z); + + //if (distanceX > Abs(value.x) * percentage) + if (DeltaError(value.x, reduced.x, distanceX, percentage, minValue)) + return false; + //if (distanceY > Abs(value.y) * percentage) + if (DeltaError(value.y, reduced.y, distanceY, percentage, minValue)) + return false; + //if (distanceZ > Abs(value.z) * percentage) + if (DeltaError(value.z, reduced.z, distanceZ, percentage, minValue)) + return false; + + return true; +} + +/// We allow reduction if the distance between the two values is low +inline bool FloatDistanceError (float value, float reduced, const float distancePercentageError) +{ + const float percentage = distancePercentageError; + const float minValue = kPositionMinValue * percentage; + + float distance = Abs(value - reduced); + //if (distance > Abs(value) * percentage) + if (DeltaError(value, reduced, distance, percentage, minValue)) + return false; + + return true; +} + +// Checks if reduced curve is valid at time "time" +template<class T, class ErrorFunction> +bool CanReduce(AnimationCurveTpl<T>& curve, const KeyframeTpl<T>& key0, const KeyframeTpl<T>& key1, float time, ErrorFunction canReduceFunction, const float allowedError) +{ + T value = curve.Evaluate(time); + T reduced_value = InterpolateKeyframe(key0, key1, time); + + return canReduceFunction(value, reduced_value, allowedError); +} + +/*template<class T> +void FitTangentsToCurve(AnimationCurveTpl<T>& curve, KeyframeTpl<T>& key0, KeyframeTpl<T>& key1) +{ + // perform curve fitting + + const float t0 = key0.time; + const float dt = key1.time - key0.time; + + float time1 = 0.3f; + float time2 = 1 - time1; + + // points on the curve at time1 and time2 + const T v0 = curve.Evaluate(t0 + time1 * dt); + const T v1 = curve.Evaluate(t0 + time2 * dt); + + FitTangents(key0, key1, time1, time2, v0, v1); +}*/ + +template<class T, class ErrorFunction> +bool CanReduce(const KeyframeTpl<T>& fromKey, const KeyframeTpl<T>& toKey, AnimationCurveTpl<T>& curve, ErrorFunction canReduceFunction, const float allowedError, const float delta, + int firstKey, int lastKey, bool useKeyframeLimit) +{ + const float beginTime = fromKey.time; + const float endTime = toKey.time; + + // We simply sample every frame and compare the original curve against, if we simply removed one key. + // If the error between the curves is not too big, we just remove the key + bool canReduce = true; + + for (float t = beginTime + delta; t < endTime; t += delta) + { + if (!(canReduce = CanReduce(curve, fromKey, toKey, t, canReduceFunction, allowedError))) + break; + } + + // we need to check that all keys can be reduced, because keys might be closer to each other than delta + // this happens when we have steps in curve + // TODO : we could skip the loop above if keyframes are close enough + + float lastTime = beginTime; + + for (int j = firstKey; canReduce && j < lastKey; ++j) + { + const float time = curve.GetKey(j).time; + + // validates point at keyframe (j) and point between (j) and and (j-1) keyframes + // TODO : For checking point at "time" it could just use keys[j].value instead - that would be faster than sampling the curve + canReduce = + CanReduce(curve, fromKey, toKey, time, canReduceFunction, allowedError) && + CanReduce(curve, fromKey, toKey, (lastTime + time) / 2, canReduceFunction, allowedError); + + lastTime = time; + } + + if (canReduce) + { + // validate point between last two keyframes + float time = curve.GetKey(lastKey).time; + canReduce = CanReduce(curve, fromKey, toKey, (lastTime + time) / 2, canReduceFunction, allowedError); + } + + // Don't reduce if we are about to reduce more than 50 samples at + // once to prevent n^2 performance impact + canReduce = canReduce && (!useKeyframeLimit || (endTime - beginTime < 50.0F * delta)); + + return canReduce; +} + +template<class T, class ErrorFunction> +float ReduceKeyframes (AnimationCurveTpl<T>& curve, float sampleRate, ErrorFunction canReduceFunction, const float allowedError, T zeroValue, bool optimalCurveRepresentation) +{ + AssertMsg(curve.GetKeyCount() >= 2, "Key count: %d", curve.GetKeyCount()); + + if (curve.GetKeyCount() <= 2) + return 100.0F; + + dynamic_array<typename AnimationCurveTpl<T>::Keyframe> output; + output.reserve(curve.GetKeyCount()); + + float delta = 1.f / sampleRate; + + // at first try to reduce to const curve + typename AnimationCurveTpl<T>::Keyframe firstKey = curve.GetKey(0); + typename AnimationCurveTpl<T>::Keyframe lastKey = curve.GetKey(curve.GetKeyCount() - 1); + firstKey.inSlope = firstKey.outSlope = zeroValue; + lastKey.inSlope = lastKey.outSlope = zeroValue; + lastKey.value = firstKey.value; + + const bool canReduceToConstCurve = CanReduce(firstKey, lastKey, curve, canReduceFunction, allowedError, delta, 0, curve.GetKeyCount() - 1, false); + if (canReduceToConstCurve) + { + output.reserve(2); + output.push_back(firstKey); + output.push_back(lastKey); + } + else + { + output.reserve(curve.GetKeyCount()); + // We always add the first key + output.push_back(curve.GetKey(0)); + + int lastUsedKey = 0; + + for (int i=1;i<curve.GetKeyCount() - 1;i++) + { + typename AnimationCurveTpl<T>::Keyframe fromKey = curve.GetKey(lastUsedKey); + typename AnimationCurveTpl<T>::Keyframe toKey = curve.GetKey(i + 1); + + //FitTangentsToCurve(curve, fromKey, toKey); + + const bool canReduce = CanReduce(fromKey, toKey, curve, canReduceFunction, allowedError, delta, lastUsedKey + 1, i + 1, true); + + if (!canReduce) + { + output.push_back(curve.GetKey(i)); + // fitting tangents between last two keys + //FitTangentsToCurve(curve, *(output.end() - 2), output.back()); + + lastUsedKey = i; + } + } + + // We always add the last key + output.push_back(curve.GetKey(curve.GetKeyCount() - 1)); + // fitting tangents between last and the one before last keys + //FitTangentsToCurve(curve, *(output.end() - 2), output.back()); + } + + float reduction = (float)output.size() / (float)curve.GetKeyCount() * 100.0F; + + curve.Swap(output); + + // if we want optimal curve representation and reduced curve can be represeted with a dense curve + // keep original curve for better quality sampling + if (optimalCurveRepresentation && IsDenseCurve(curve)) + { + curve.Swap(output); + reduction = 100.0F; + } + + return reduction; +} + +template <class T, class U, typename ReductionFunction> +float ReduceKeyframes (const float sampleRate, T& curves, ReductionFunction reductionFunction, const float allowedError, const U zeroValue, bool optimalCurveRepresentation) +{ + float totalRatio = 0; + for (typename T::iterator it = curves.begin(), end = curves.end(); it != end; ++it) + { + float compressionRatio = ReduceKeyframes(it->curve, sampleRate, reductionFunction, allowedError, zeroValue, optimalCurveRepresentation); + #if DEBUG_COMPRESSION + printf_console ("Compression %f%% of rotation %s\n", compressionRatio, i->path.c_str()); + #endif + + totalRatio += compressionRatio; + } + + return totalRatio; +} + +void ReduceKeyframes (AnimationClip& clip, float rotationError, float positionError, float scaleError, float floatError) +{ + AnimationClip::QuaternionCurves& rot = clip.GetRotationCurves(); + AnimationClip::Vector3Curves& pos = clip.GetPositionCurves(); + AnimationClip::Vector3Curves& scale = clip.GetScaleCurves(); + AnimationClip::FloatCurves& floats = clip.GetFloatCurves(); + AnimationClip::FloatCurves& editorCurves = clip.GetEditorCurvesNoConversion(); + + rotationError = cos(Deg2Rad(rotationError) / 2.0F); + positionError = positionError / 100.0F; + scaleError = scaleError / 100.0F; + floatError = floatError / 100.0F; + + float time = GetTimeSinceStartup(); + float averageCompressionRatio = 0; + + const float sampleRate = clip.GetSampleRate(); + + averageCompressionRatio += ReduceKeyframes (sampleRate, rot, QuaternionDistanceError, rotationError, Quaternionf(0, 0, 0, 0), clip.IsAnimatorMotion() && !clip.GetUseHighQualityCurve() ); + averageCompressionRatio += ReduceKeyframes (sampleRate, pos, PositionDistanceError, positionError, Vector3f::zero, clip.IsAnimatorMotion() && !clip.GetUseHighQualityCurve()); + averageCompressionRatio += ReduceKeyframes (sampleRate, scale, PositionDistanceError, scaleError, Vector3f::zero, clip.IsAnimatorMotion() && !clip.GetUseHighQualityCurve()); + averageCompressionRatio += ReduceKeyframes (sampleRate, floats, FloatDistanceError, floatError, 0.f, clip.IsAnimatorMotion() && !clip.GetUseHighQualityCurve()); + averageCompressionRatio += ReduceKeyframes (sampleRate, editorCurves, FloatDistanceError, floatError, 0.f, clip.IsAnimatorMotion() && !clip.GetUseHighQualityCurve()); + + // If all the curves are empty, we end up with zero reduction. + if (averageCompressionRatio == 0) + return; + + averageCompressionRatio /= (rot.size() + pos.size() + scale.size() + floats.size() + editorCurves.size()); + time = GetTimeSinceStartup() - time; + + { + std::ostringstream oss; + oss << "Keyframe reduction: Ratio: " << averageCompressionRatio << "%; Time: " << time << "s;\n"; + printf_console("%s", oss.str().c_str()); + } +} + +// TODO : use tangents from editor or perform curve fitting +// TODO : these should be removed eventually and custom settings should be used instead +const float kQuaternionAngleError = 0.5F;// The maximum angle deviation allowed in degrees +const float kQuaternionDotError = cos(Deg2Rad(kQuaternionAngleError) / 2.0F); +///@TODO: * Support step curves +/// * Improve keyframe reduction +/// * Make keyframe reduction faster +void EulerToQuaternionCurveBake (const AnimationCurve& curveX, const AnimationCurve& curveY, const AnimationCurve& curveZ, AnimationCurveQuat& collapsed, float sampleRate) +{ + float begin = std::numeric_limits<float>::infinity (); + float end = -std::numeric_limits<float>::infinity (); + + float delta = 1.0F / sampleRate; + + const AnimationCurve* curves[3] = { &curveX, &curveY, &curveZ }; + + for (int i=0;i<3;i++) + { + if (curves[i]->GetKeyCount() >= 1) + { + begin = min(curves[i]->GetKey(0).time, begin); + end = max(curves[i]->GetKey(curves[i]->GetKeyCount()-1).time, end); + } + } + if (!IsFinite(begin) || !IsFinite(end)) + return; + + + float deg2rad = Deg2Rad(1.0F); + for (float i=begin;i < end + delta;i += delta) + { + if (i + delta / 2.0F > end) + i = end; + + Vector3f euler = Vector3f (curveX.Evaluate(i), curveY.Evaluate(i), curveZ.Evaluate(i)) * deg2rad; + Quaternionf q = EulerToQuaternion(euler); + //Vector3f eulerBack = QuaternionToEuler (q) * Rad2Deg(1.0F); + //printf_console("%f : %f, %f, %f ----- %f, %f, %f\n", i, euler.x, euler.y, euler.z, eulerBack.x, eulerBack.y, eulerBack.z); + + KeyframeTpl<Quaternionf> key; + key.time = i; + key.value = q; + key.inSlope = key.outSlope = Quaternionf(0,0,0,0); + collapsed.AddKeyBackFast(key); + + if (i == end) + break; + } + + EnsureQuaternionContinuityAndRecalculateSlope (collapsed); + + //@TODO: Keyframe reduction is disabled for now, with keyframe reduction enabled iteration time + // in the animation window becomes unbearable + // ReduceKeyframes(collapsed, sampleRate, QuaternionDistanceError, kQuaternionDotError, Quaternionf(0, 0, 0, 0), false); +} |