+Unity Runtime codeHEADmaster

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);
+}