Add support to get a bezier curve extreme values

Add logic to get the extreme values of a curve segment. This is used by
the studio to fit an animation curve.

Change-Id: I65564802524bfd49793624a560d98cc67d22e055
Reviewed-by: Miikka Heikkinen <miikka.heikkinen@qt.io>
Reviewed-by: Tomi Korpipää <tomi.korpipaa@qt.io>

6 files changed, 111 insertions, 6 deletions

diff --git a/src/dm/systems/Qt3DSDMAnimation.h b/src/dm/systems/Qt3DSDMAnimation.h
index d4a8f72..11da8dd 100644
--- a/src/dm/systems/Qt3DSDMAnimation.h
+++ b/src/dm/systems/Qt3DSDMAnimation.h
@@ -37,7 +37,7 @@ namespace qt3dsdm {
 
 struct SLinearKeyframe
 {
-    long m_time; // keyframe time in milliseconds
+    float m_time; // keyframe time in milliseconds
     float m_value;
 
     SLinearKeyframe() = default;
@@ -48,14 +48,14 @@ struct SLinearKeyframe
 
 struct SBezierKeyframe : public SLinearKeyframe
 {
-    long m_InTangentTime;
+    float m_InTangentTime;
     float m_InTangentValue;
-    long m_OutTangentTime;
+    float m_OutTangentTime;
     float m_OutTangentValue;
 
     SBezierKeyframe() = default;
-    SBezierKeyframe(long time, float value, long tangentInTime, float tangentInValue,
-                    long tangentOutTime, float tangentOutValue)
+    SBezierKeyframe(float time, float value, float tangentInTime, float tangentInValue,
+                    float tangentOutTime, float tangentOutValue)
     : SLinearKeyframe(time, value)
     , m_InTangentTime(tangentInTime)
     , m_InTangentValue(tangentInValue)
@@ -78,7 +78,7 @@ struct SEaseInEaseOutKeyframe : public SLinearKeyframe
     float m_EaseOut;
 
     SEaseInEaseOutKeyframe() = default;
-    SEaseInEaseOutKeyframe(long time, float value, float easeIn, float easeOut)
+    SEaseInEaseOutKeyframe(float time, float value, float easeIn, float easeOut)
     : SLinearKeyframe(time, value)
     , m_EaseIn(easeIn)
     , m_EaseOut(easeOut) {}
@@ -290,6 +290,8 @@ public:
 
     // Animation Evaluation.
     virtual float EvaluateAnimation(Qt3DSDMAnimationHandle animation, long time) const = 0;
+    virtual std::pair<float, float> getAnimationExtrema(Qt3DSDMAnimationHandle animation,
+                                                        long startTime, long endTime) const = 0;
 
     virtual bool KeyframeValid(Qt3DSDMKeyframeHandle inKeyframe) const = 0;
     virtual bool AnimationValid(Qt3DSDMAnimationHandle inAnimation) const = 0;
diff --git a/src/dm/systems/cores/AnimationCoreProducer.cpp b/src/dm/systems/cores/AnimationCoreProducer.cpp
index 6de5827..6168ccf 100644
--- a/src/dm/systems/cores/AnimationCoreProducer.cpp
+++ b/src/dm/systems/cores/AnimationCoreProducer.cpp
@@ -378,6 +378,13 @@ float CAnimationCoreProducer::EvaluateAnimation(Qt3DSDMAnimationHandle animation
     return m_Data->EvaluateAnimation(animation, time);
 }
 
+std::pair<float, float> CAnimationCoreProducer::getAnimationExtrema(
+                                                        Qt3DSDMAnimationHandle animation,
+                                                        long startTime, long endTime) const
+{
+    return m_Data->getAnimationExtrema(animation, startTime, endTime);
+}
+
 bool CAnimationCoreProducer::KeyframeValid(Qt3DSDMKeyframeHandle inKeyframe) const
 {
     return m_Data->KeyframeValid(inKeyframe);
diff --git a/src/dm/systems/cores/AnimationCoreProducer.h b/src/dm/systems/cores/AnimationCoreProducer.h
index fb54f45..62ea0df 100644
--- a/src/dm/systems/cores/AnimationCoreProducer.h
+++ b/src/dm/systems/cores/AnimationCoreProducer.h
@@ -109,6 +109,9 @@ public:
 
     // Animation Evaluation.
     float EvaluateAnimation(Qt3DSDMAnimationHandle animation, long time) const override;
+    std::pair<float, float> getAnimationExtrema(Qt3DSDMAnimationHandle animation,
+                                                long startTime = -1,
+                                                long endTime = -1) const override;
 
     bool KeyframeValid(Qt3DSDMKeyframeHandle inKeyframe) const override;
     bool AnimationValid(Qt3DSDMAnimationHandle inAnimation) const override;
diff --git a/src/dm/systems/cores/SimpleAnimationCore.cpp b/src/dm/systems/cores/SimpleAnimationCore.cpp
index 6749c74..471cf7f 100644
--- a/src/dm/systems/cores/SimpleAnimationCore.cpp
+++ b/src/dm/systems/cores/SimpleAnimationCore.cpp
@@ -424,6 +424,76 @@ float CSimpleAnimationCore::EvaluateAnimation(Qt3DSDMAnimationHandle animation,
     }
 }
 
+/**
+ * Get max and min values of a segment of an animation channel between startTime and endTime. If
+ * startTime or endTime is -1 the segment start/end is the starting/ending keyframe
+ *
+ * @param animation animation channel handle
+ * @param startTime only include keyframes in the range starting at this time value
+ * @param endTime only include keyframes in the range ending at this time value
+ * @return <max, min> values pair
+ */
+std::pair<float, float> CSimpleAnimationCore::getAnimationExtrema(
+                                                        Qt3DSDMAnimationHandle animation,
+                                                        long startTime, long endTime) const
+{
+    const SAnimationTrack *track = GetAnimationNF(animation, m_Objects);
+    TKeyframeHandleList keyframeHandles;
+    GetKeyframes(animation, keyframeHandles);
+    size_t idxFrom = 0;
+    size_t idxTo = keyframeHandles.size() - 1;
+
+    if (startTime != -1) {
+        for (size_t i = 1; i < keyframeHandles.size(); ++i) {
+            if (getKeyframeTime(GetKeyframeData(keyframeHandles[i])) > startTime) {
+                idxFrom = i - 1;
+                break;
+            }
+        }
+    }
+
+    if (endTime != -1) {
+        for (size_t i = idxFrom; i < keyframeHandles.size(); ++i) {
+            if (getKeyframeTime(GetKeyframeData(keyframeHandles[i])) > endTime) {
+                idxTo = i;
+                break;
+            }
+        }
+    }
+
+    std::pair<float, float> extrema {-FLT_MAX, FLT_MAX}; // <max, min>
+    if (track->m_AnimationType == EAnimationTypeBezier) {
+        for (size_t i = idxFrom + 1; i <= idxTo; ++i) {
+            SBezierKeyframe kf1 = get<SBezierKeyframe>(GetKeyframeData(keyframeHandles[i - 1]));
+            SBezierKeyframe kf2 = get<SBezierKeyframe>(GetKeyframeData(keyframeHandles[i]));
+            std::pair<float, float> extrema_i = Q3DStudio::getBezierCurveExtrema(
+                        kf1.m_time, kf1.m_value, kf1.m_OutTangentTime, kf1.m_OutTangentValue,
+                        kf2.m_InTangentTime, kf2.m_InTangentValue, kf2.m_time, kf2.m_value);
+
+            if (extrema_i.first > extrema.first)
+                extrema.first = extrema_i.first;
+            if (extrema_i.second < extrema.second)
+                extrema.second = extrema_i.second;
+        }
+    } else { // Linear and EaseInOut
+        for (size_t i = idxFrom; i <= idxTo; ++i) {
+            float kfValue = getKeyframeValue(GetKeyframeData(keyframeHandles[i]));
+
+            if (kfValue > extrema.first)
+                extrema.first = kfValue;
+            if (kfValue < extrema.second)
+                extrema.second = kfValue;
+        }
+    }
+
+    if (qFuzzyCompare(extrema.first, -FLT_MAX))
+        extrema.first = 0;
+    if (qFuzzyCompare(extrema.second, FLT_MAX))
+        extrema.second = 0;
+
+    return extrema;
+}
+
 bool CSimpleAnimationCore::KeyframeValid(Qt3DSDMKeyframeHandle inKeyframe) const
 {
     return HandleObjectValid<SKeyframe>(inKeyframe, m_Objects);
diff --git a/src/dm/systems/cores/SimpleAnimationCore.h b/src/dm/systems/cores/SimpleAnimationCore.h
index c204026..c782496 100644
--- a/src/dm/systems/cores/SimpleAnimationCore.h
+++ b/src/dm/systems/cores/SimpleAnimationCore.h
@@ -158,6 +158,9 @@ public: // Use
 
     // Animation Evaluation.
     float EvaluateAnimation(Qt3DSDMAnimationHandle animation, long time) const override;
+    std::pair<float, float> getAnimationExtrema(Qt3DSDMAnimationHandle animation,
+                                                long startTime = -1,
+                                                long endTime = -1) const override;
 
     bool KeyframeValid(Qt3DSDMKeyframeHandle inKeyframe) const override;
     bool AnimationValid(Qt3DSDMAnimationHandle inAnimation) const override;
diff --git a/src/system/Qt3DSBezierEval.h b/src/system/Qt3DSBezierEval.h
index ef99eec..8a6f6b0 100644
--- a/src/system/Qt3DSBezierEval.h
+++ b/src/system/Qt3DSBezierEval.h
@@ -166,4 +166,24 @@ inline float EvaluateBezierKeyframe(long inTime, long inTime1, float inValue1, l
     return 0.0;
 }
 
+inline std::pair<float, float> getBezierCurveExtrema(float inTime1, float inValue1,
+                                                     float inC1Time, float inC1Value,
+                                                     float inC2Time, float inC2Value,
+                                                     float inTime2, float inValue2)
+{
+        auto polynomial = CubicPolynomial(inValue1, inC1Value, inC2Value, inValue2);
+
+        std::pair<float, float> extrema {-FLT_MAX, FLT_MAX}; // <max, min>
+        for (double t : polynomial.extrema()) {
+            const float val = float(evaluateForT(t, inValue1, inC1Value, inC2Value, inValue2));
+
+            if (val > extrema.first)
+                extrema.first = val;
+            if (val < extrema.second)
+                extrema.second = val;
+        }
+
+    return extrema;
+}
+
 } // namespace Qt3DStudio