1//************************************ bs::framework - Copyright 2018 Marko Pintera **************************************//
2//*********** Licensed under the MIT license. See LICENSE.md for full terms. This notice is not to be removed. ***********//
3#include "Animation/BsAnimationCurve.h"
4#include "Private/RTTI/BsAnimationCurveRTTI.h"
5#include "Math/BsVector3.h"
6#include "Math/BsVector2.h"
7#include "Math/BsQuaternion.h"
8#include "Math/BsMath.h"
9#include "Animation/BsAnimationUtility.h"
10
11namespace bs
12{
13 namespace impl
14 {
15 /**
16 * Checks if any components of the keyframes are constant (step) functions and updates the hermite curve coefficients
17 * accordingly.
18 */
19 void setStepCoefficients(const TKeyframe<float>& lhs, const TKeyframe<float>& rhs, float(&coefficients)[4])
20 {
21 if (lhs.outTangent != std::numeric_limits<float>::infinity() &&
22 rhs.inTangent != std::numeric_limits<float>::infinity())
23 return;
24
25 coefficients[0] = 0.0f;
26 coefficients[1] = 0.0f;
27 coefficients[2] = 0.0f;
28 coefficients[3] = lhs.value;
29 }
30
31 void setStepCoefficients(const TKeyframe<Vector3>& lhs, const TKeyframe<Vector3>& rhs, Vector3(&coefficients)[4])
32 {
33 for (UINT32 i = 0; i < 3; i++)
34 {
35 if (lhs.outTangent[i] != std::numeric_limits<float>::infinity() &&
36 rhs.inTangent[i] != std::numeric_limits<float>::infinity())
37 continue;
38
39 coefficients[0][i] = 0.0f;
40 coefficients[1][i] = 0.0f;
41 coefficients[2][i] = 0.0f;
42 coefficients[3][i] = lhs.value[i];
43 }
44 }
45
46 void setStepCoefficients(const TKeyframe<Vector2>& lhs, const TKeyframe<Vector2>& rhs, Vector2(&coefficients)[4])
47 {
48 for (UINT32 i = 0; i < 2; i++)
49 {
50 if (lhs.outTangent[i] != std::numeric_limits<float>::infinity() &&
51 rhs.inTangent[i] != std::numeric_limits<float>::infinity())
52 continue;
53
54 coefficients[0][i] = 0.0f;
55 coefficients[1][i] = 0.0f;
56 coefficients[2][i] = 0.0f;
57 coefficients[3][i] = lhs.value[i];
58 }
59 }
60
61 void setStepCoefficients(const TKeyframe<Quaternion>& lhs, const TKeyframe<Quaternion>& rhs, Quaternion(&coefficients)[4])
62 {
63 for (UINT32 i = 0; i < 4; i++)
64 {
65 if (lhs.outTangent[i] != std::numeric_limits<float>::infinity() &&
66 rhs.inTangent[i] != std::numeric_limits<float>::infinity())
67 continue;
68
69 coefficients[0][i] = 0.0f;
70 coefficients[1][i] = 0.0f;
71 coefficients[2][i] = 0.0f;
72 coefficients[3][i] = lhs.value[i];
73 }
74 }
75
76 /** Checks if any components of the keyframes are constant (step) functions and updates the key value. */
77 void setStepValue(const TKeyframe<float>& lhs, const TKeyframe<float>& rhs, float& value)
78 {
79 if (lhs.outTangent != std::numeric_limits<float>::infinity() &&
80 rhs.inTangent != std::numeric_limits<float>::infinity())
81 return;
82
83 value = lhs.value;
84 }
85
86 void setStepValue(const TKeyframe<Vector3>& lhs, const TKeyframe<Vector3>& rhs, Vector3& value)
87 {
88 for (UINT32 i = 0; i < 3; i++)
89 {
90 if (lhs.outTangent[i] != std::numeric_limits<float>::infinity() &&
91 rhs.inTangent[i] != std::numeric_limits<float>::infinity())
92 continue;
93
94 value[i] = lhs.value[i];
95 }
96 }
97
98 void setStepValue(const TKeyframe<Vector2>& lhs, const TKeyframe<Vector2>& rhs, Vector2& value)
99 {
100 for (UINT32 i = 0; i < 2; i++)
101 {
102 if (lhs.outTangent[i] != std::numeric_limits<float>::infinity() &&
103 rhs.inTangent[i] != std::numeric_limits<float>::infinity())
104 continue;
105
106 value[i] = lhs.value[i];
107 }
108 }
109
110 void setStepValue(const TKeyframe<Quaternion>& lhs, const TKeyframe<Quaternion>& rhs, Quaternion& value)
111 {
112 for (UINT32 i = 0; i < 4; i++)
113 {
114 if (lhs.outTangent[i] != std::numeric_limits<float>::infinity() &&
115 rhs.inTangent[i] != std::numeric_limits<float>::infinity())
116 continue;
117
118 value[i] = lhs.value[i];
119 }
120 }
121
122 /** Checks if any components of the keyframes are constant (step) functions and updates the key tangent. */
123 void setStepTangent(const TKeyframe<float>& lhs, const TKeyframe<float>& rhs, float& tangent)
124 {
125 if (lhs.outTangent != std::numeric_limits<float>::infinity() &&
126 rhs.inTangent != std::numeric_limits<float>::infinity())
127 return;
128
129 tangent = std::numeric_limits<float>::infinity();
130 }
131
132 void setStepTangent(const TKeyframe<Vector3>& lhs, const TKeyframe<Vector3>& rhs, Vector3& tangent)
133 {
134 for (UINT32 i = 0; i < 3; i++)
135 {
136 if (lhs.outTangent[i] != std::numeric_limits<float>::infinity() &&
137 rhs.inTangent[i] != std::numeric_limits<float>::infinity())
138 continue;
139
140 tangent[i] = std::numeric_limits<float>::infinity();
141 }
142 }
143
144 void setStepTangent(const TKeyframe<Vector2>& lhs, const TKeyframe<Vector2>& rhs, Vector2& tangent)
145 {
146 for (UINT32 i = 0; i < 2; i++)
147 {
148 if (lhs.outTangent[i] != std::numeric_limits<float>::infinity() &&
149 rhs.inTangent[i] != std::numeric_limits<float>::infinity())
150 continue;
151
152 tangent[i] = std::numeric_limits<float>::infinity();
153 }
154 }
155
156 void setStepTangent(const TKeyframe<Quaternion>& lhs, const TKeyframe<Quaternion>& rhs, Quaternion& tangent)
157 {
158 for (UINT32 i = 0; i < 4; i++)
159 {
160 if (lhs.outTangent[i] != std::numeric_limits<float>::infinity() &&
161 rhs.inTangent[i] != std::numeric_limits<float>::infinity())
162 continue;
163
164 tangent[i] = std::numeric_limits<float>::infinity();
165 }
166 }
167
168 /** Calculates the difference between two values. */
169 float getDiff(float lhs, float rhs)
170 {
171 return lhs - rhs;
172 }
173
174 Vector3 getDiff(const Vector3& lhs, const Vector3& rhs)
175 {
176 return lhs - rhs;
177 }
178
179 Vector2 getDiff(const Vector2& lhs, const Vector2& rhs)
180 {
181 return lhs - rhs;
182 }
183
184 Quaternion getDiff(const Quaternion& lhs, const Quaternion& rhs)
185 {
186 return rhs.inverse() * lhs;
187 }
188
189 INT32 getDiff(INT32 lhs, INT32 rhs)
190 {
191 return lhs - rhs;
192 }
193
194 template <class T>
195 T getZero() { return 0.0f; }
196
197 template<>
198 float getZero<float>() { return 0.0f; }
199
200 template<>
201 Vector3 getZero<Vector3>() { return Vector3(BsZero); }
202
203 template<>
204 Vector2 getZero<Vector2>() { return Vector2(BsZero); }
205
206 template<>
207 Quaternion getZero<Quaternion>() { return Quaternion(BsZero); }
208
209 template<>
210 INT32 getZero<INT32>() { return 0; }
211
212 template <class T>
213 constexpr UINT32 getNumComponents() { return 1; }
214
215 template<>
216 constexpr UINT32 getNumComponents<Vector3>() { return 3; }
217
218 template<>
219 constexpr UINT32 getNumComponents<Vector2>() { return 2; }
220
221 template<>
222 constexpr UINT32 getNumComponents<Quaternion>() { return 4; }
223
224 template <class T>
225 float& getComponent(T& val, UINT32 idx) { return val; }
226
227 template<>
228 float& getComponent(Vector3& val, UINT32 idx) { return val[idx]; }
229
230 template<>
231 float& getComponent(Vector2& val, UINT32 idx) { return val[idx]; }
232
233 template<>
234 float& getComponent(Quaternion& val, UINT32 idx) { return val[idx]; }
235
236 template <class T>
237 float getComponent(const T& val, UINT32 idx) { return val; }
238
239 template<>
240 float getComponent(const Vector3& val, UINT32 idx) { return val[idx]; }
241
242 template<>
243 float getComponent(const Vector2& val, UINT32 idx) { return val[idx]; }
244
245 template<>
246 float getComponent(const Quaternion& val, UINT32 idx) { return val[idx]; }
247
248 template <class T>
249 void getMinMax(std::pair<T, T>& minmax, const T& value)
250 {
251 minmax.first = std::min(minmax.first, value);
252 minmax.second = std::max(minmax.second, value);
253 }
254
255 template <>
256 void getMinMax(std::pair<Vector3, Vector3>& minmax, const Vector3& value)
257 {
258 minmax.first = Vector3::min(minmax.first, value);
259 minmax.second = Vector3::max(minmax.second, value);
260 }
261
262 template <>
263 void getMinMax(std::pair<Vector2, Vector2>& minmax, const Vector2& value)
264 {
265 minmax.first = Vector2::min(minmax.first, value);
266 minmax.second = Vector2::max(minmax.second, value);
267 }
268
269 template <>
270 void getMinMax(std::pair<Quaternion, Quaternion>& minmax, const Quaternion& value)
271 {
272 minmax.first = Quaternion::min(minmax.first, value);
273 minmax.second = Quaternion::max(minmax.second, value);
274 }
275
276 template<class T>
277 TKeyframe<T> evaluateKey(const TKeyframe<T>& lhs, const TKeyframe<T>& rhs, float time)
278 {
279 float length = rhs.time - lhs.time;
280
281 if (Math::approxEquals(length, 0.0f))
282 return lhs;
283
284 // Resize tangents since we're not evaluating the curve over unit range
285 float invLength = 1.0f / length;
286 float t = (time - lhs.time) * invLength;
287 T leftTangent = lhs.outTangent * length;
288 T rightTangent = rhs.inTangent * length;
289
290 TKeyframe<T> output;
291 output.time = time;
292 output.value = Math::cubicHermite(t, lhs.value, rhs.value, leftTangent, rightTangent);
293 output.inTangent = Math::cubicHermiteD1(t, lhs.value, rhs.value, leftTangent, rightTangent) * invLength;
294
295 setStepValue(lhs, rhs, output.value);
296 setStepTangent(lhs, rhs, output.inTangent);
297
298 output.outTangent = output.inTangent;
299
300 return output;
301 }
302
303 template<>
304 TKeyframe<INT32> evaluateKey(const TKeyframe<INT32>& lhs, const TKeyframe<INT32>& rhs, float time)
305 {
306 TKeyframe<INT32> output;
307 output.time = time;
308 output.value = time >= rhs.time ? rhs.value : lhs.value;
309
310 return output;
311 }
312
313 template <class T>
314 T evaluateCubic(float time, float start, float end, T (&coeffs)[4])
315 {
316 float t = time - start;
317 return t * (t * (t * coeffs[0] + coeffs[1]) + coeffs[2]) + coeffs[3];
318 }
319
320 template <>
321 INT32 evaluateCubic(float time, float start, float end, INT32 (&coeffs)[4])
322 {
323 return time >= end ? coeffs[1] : coeffs[0];
324 }
325
326 template<class T>
327 void calculateCoeffs(const TKeyframe<T>& lhs, const TKeyframe<T>& rhs, float time, T (&coeffs)[4])
328 {
329 float length = rhs.time - lhs.time;
330
331 // Handle the case where both keys are identical, or close enough to cause precision issues
332 if (length < 0.000001f)
333 {
334 coeffs[0] = impl::getZero<T>();
335 coeffs[1] = impl::getZero<T>();
336 coeffs[2] = impl::getZero<T>();
337 coeffs[3] = lhs.value;
338 }
339 else
340 Math::cubicHermiteCoefficients(lhs.value, rhs.value, lhs.outTangent, rhs.inTangent, length, coeffs);
341
342 setStepCoefficients(lhs, rhs, coeffs);
343 }
344
345 template<>
346 void calculateCoeffs(const TKeyframe<INT32>& lhs, const TKeyframe<INT32>& rhs, float time, INT32 (&coeffs)[4])
347 {
348 coeffs[0] = lhs.value;
349 coeffs[1] = rhs.value;
350 }
351
352 template<class T>
353 T evaluateAndUpdateCache(const TKeyframe<T>& lhs, const TKeyframe<T>& rhs, float time, T (&coeffs)[4])
354 {
355 calculateCoeffs(lhs, rhs, time, coeffs);
356
357 return impl::evaluateCubic(time, lhs.time, rhs.time, coeffs);
358 }
359
360 template<>
361 INT32 evaluateAndUpdateCache(const TKeyframe<INT32>& lhs, const TKeyframe<INT32>& rhs, float time,
362 INT32 (&coeffs)[4])
363 {
364 coeffs[0] = lhs.value;
365 coeffs[1] = rhs.value;
366
367 return time >= rhs.time ? rhs.value : lhs.value;
368 }
369
370 template<class T>
371 T evaluate(const TKeyframe<T>& lhs, const TKeyframe<T>& rhs, float time)
372 {
373 float length = rhs.time - lhs.time;
374 assert(length > 0.0f);
375
376 float t;
377 T leftTangent;
378 T rightTangent;
379
380 if (Math::approxEquals(length, 0.0f))
381 {
382 t = 0.0f;
383 leftTangent = impl::getZero<T>();
384 rightTangent = impl::getZero<T>();
385 }
386 else
387 {
388 // Scale from arbitrary range to [0, 1]
389 t = (time - lhs.time) / length;
390 leftTangent = lhs.outTangent * length;
391 rightTangent = rhs.inTangent * length;
392 }
393
394 T output = Math::cubicHermite(t, lhs.value, rhs.value, leftTangent, rightTangent);
395 setStepValue(lhs, rhs, output);
396
397 return output;
398 }
399
400 template<>
401 INT32 evaluate(const TKeyframe<INT32>& lhs, const TKeyframe<INT32>& rhs, float time)
402 {
403 return time >= rhs.time ? rhs.value : lhs.value;
404 }
405
406 template <class T>
407 void integrate(T (&coeffs)[4])
408 {
409 coeffs[0] = (T)(coeffs[0] / 4.0f);
410 coeffs[1] = (T)(coeffs[1] / 3.0f);
411 coeffs[2] = (T)(coeffs[2] / 2.0f);
412 }
413
414 template <class T>
415 void calcMinMax(std::pair<T, T>& minmax, float start, float end, T(&coeffs)[4])
416 {
417 // Differentiate
418 T a = (T)(3.0f * coeffs[0]);
419 T b = (T)(2.0f * coeffs[1]);
420 T c = (T)(1.0f * coeffs[2]);
421
422 const UINT32 numComponents = getNumComponents<T>();
423
424 for (UINT32 i = 0; i < numComponents; i++)
425 {
426 float roots[2];
427 const UINT32 numRoots = Math::solveQuadratic(
428 getComponent(a, i),
429 getComponent(b, i),
430 getComponent(c, i),
431 roots);
432
433 for (UINT32 j = 0; j < numRoots; j++)
434 {
435 if ((roots[j] >= 0.0f) && ((start + roots[j]) < end))
436 {
437 float fltCoeffs[4] =
438 {
439 getComponent(coeffs[0], i),
440 getComponent(coeffs[1], i),
441 getComponent(coeffs[2], i),
442 getComponent(coeffs[3], i)
443 };
444
445 float value = evaluateCubic(roots[j], 0.0f, 0.0f, fltCoeffs);
446
447 getComponent(minmax.first, i) = std::min(getComponent(minmax.first, i), value);
448 getComponent(minmax.second, i) = std::max(getComponent(minmax.second, i), value);
449 }
450 }
451 }
452 }
453
454 template <>
455 void calcMinMax(std::pair<INT32, INT32>& minmax, float start, float end, INT32(&coeffs)[4])
456 {
457 getMinMax(minmax, coeffs[0]);
458 getMinMax(minmax, coeffs[1]);
459 }
460
461 template <class T>
462 void calcMinMaxIntegrated(std::pair<T, T>& minmax, float start, float end, const T& sum, T(&coeffs)[4])
463 {
464 // Differentiate
465 T a = 4.0f * coeffs[0];
466 T b = 3.0f * coeffs[1];
467 T c = 2.0f * coeffs[2];
468 T d = 1.0f * coeffs[3];
469
470 const UINT32 numComponents = getNumComponents<T>();
471
472 for (UINT32 i = 0; i < numComponents; i++)
473 {
474 float roots[3];
475 const UINT32 numRoots = Math::solveCubic(
476 getComponent(a, i),
477 getComponent(b, i),
478 getComponent(c, i),
479 getComponent(d, i),
480 roots);
481
482 for (UINT32 j = 0; j < numRoots; j++)
483 {
484 if ((roots[j] >= 0.0f) && ((start + roots[j]) < end))
485 {
486 float fltCoeffs[4] =
487 {
488 getComponent(coeffs[0], i),
489 getComponent(coeffs[1], i),
490 getComponent(coeffs[2], i),
491 getComponent(coeffs[3], i)
492 };
493
494 float value = getComponent(sum, i) + evaluateCubic(roots[j], 0.0f, 0.0f, fltCoeffs) * roots[j];
495
496 getComponent(minmax.first, i) = std::min(getComponent(minmax.first, i), value);
497 getComponent(minmax.second, i) = std::max(getComponent(minmax.second, i), value);
498 }
499 }
500 }
501 }
502
503 template <>
504 void calcMinMaxIntegrated(std::pair<INT32, INT32>& minmax, float start, float end, const INT32& sum,
505 INT32(&coeffs)[4])
506 {
507 assert(false && "Not implemented");
508 }
509
510 template <class T>
511 void calcMinMaxIntegratedDouble(std::pair<T, T>& minmax, float start, float end, const T& doubleSum,
512 const T& sum, T(&coeffs)[4])
513 {
514 // Differentiate
515 T a = 5.0f * coeffs[0];
516 T b = 4.0f * coeffs[1];
517 T c = 3.0f * coeffs[2];
518 T d = 2.0f * coeffs[3];
519
520 const UINT32 numComponents = getNumComponents<T>();
521
522 for (UINT32 i = 0; i < numComponents; i++)
523 {
524 float roots[4];
525 const UINT32 numRoots = Math::solveQuartic(
526 getComponent(a, i),
527 getComponent(b, i),
528 getComponent(c, i),
529 getComponent(d, i),
530 0.0f,
531 roots);
532
533 for (UINT32 j = 0; j < numRoots; j++)
534 {
535 if ((roots[j] >= 0.0f) && ((start + roots[j]) < end))
536 {
537 float fltCoeffs[4] =
538 {
539 getComponent(coeffs[0], i),
540 getComponent(coeffs[1], i),
541 getComponent(coeffs[2], i),
542 getComponent(coeffs[3], i)
543 };
544
545 float root = roots[j];
546 float value = getComponent(doubleSum, i) + getComponent(sum, i) * root +
547 evaluateCubic(root, 0.0f, 0.0f, fltCoeffs) * root * root;
548
549 getComponent(minmax.first, i) = std::min(getComponent(minmax.first, i), value);
550 getComponent(minmax.second, i) = std::max(getComponent(minmax.second, i), value);
551 }
552 }
553 }
554 }
555
556 template <>
557 void calcMinMaxIntegratedDouble(std::pair<INT32, INT32>& minmax, float start, float end,
558 const INT32& doubleSum, const INT32& sum, INT32(&coeffs)[4])
559 {
560 assert(false && "Not implemented");
561 }
562 }
563
564 template <class T>
565 const UINT32 TAnimationCurve<T>::CACHE_LOOKAHEAD = 3;
566
567 template <class T>
568 TAnimationCurve<T>::TAnimationCurve(const Vector<KeyFrame>& keyframes)
569 :mKeyframes(keyframes)
570 {
571#if BS_DEBUG_MODE
572 // Ensure keyframes are sorted
573 if(!keyframes.empty())
574 {
575 float time = keyframes[0].time;
576 for (UINT32 i = 1; i < (UINT32)keyframes.size(); i++)
577 {
578 assert(keyframes[i].time >= time);
579 time = keyframes[i].time;
580 }
581 }
582#endif
583
584 if (!keyframes.empty())
585 mEnd = keyframes.back().time;
586 else
587 mEnd = 0.0f;
588
589 mStart = 0.0f;
590 mLength = mEnd;
591 }
592
593 template <class T>
594 T TAnimationCurve<T>::evaluate(float time, const TCurveCache<T>& cache, bool loop) const
595 {
596 if (mKeyframes.empty())
597 return impl::getZero<T>();
598
599 if (Math::approxEquals(mLength, 0.0f))
600 time = 0.0f;
601
602 // Wrap time if looping
603 if(loop && mLength > 0.0f)
604 {
605 if (time < mStart)
606 time = time + (std::floor(mEnd - time) / mLength) * mLength;
607 else if (time > mEnd)
608 time = time - std::floor((time - mStart) / mLength) * mLength;
609 }
610
611 // If time is within cache, evaluate it directly
612 if (time >= cache.cachedCurveStart && time < cache.cachedCurveEnd)
613 return impl::evaluateCubic(time, cache.cachedCurveStart, cache.cachedCurveEnd, cache.cachedCubicCoefficients);
614
615 // Clamp to start, cache constant of the first key and return
616 if(time < mStart)
617 {
618 cache.cachedCurveStart = -std::numeric_limits<float>::infinity();
619 cache.cachedCurveEnd = mStart;
620 cache.cachedKey = 0;
621 cache.cachedCubicCoefficients[0] = impl::getZero<T>();
622 cache.cachedCubicCoefficients[1] = impl::getZero<T>();
623 cache.cachedCubicCoefficients[2] = impl::getZero<T>();
624 cache.cachedCubicCoefficients[3] = mKeyframes[0].value;
625
626 return mKeyframes[0].value;
627 }
628
629 if(time >= mEnd) // Clamp to end, cache constant of the final key and return
630 {
631 UINT32 lastKey = (UINT32)mKeyframes.size() - 1;
632
633 cache.cachedCurveStart = mEnd;
634 cache.cachedCurveEnd = std::numeric_limits<float>::infinity();
635 cache.cachedKey = lastKey;
636 cache.cachedCubicCoefficients[0] = impl::getZero<T>();
637 cache.cachedCubicCoefficients[1] = impl::getZero<T>();
638 cache.cachedCubicCoefficients[2] = impl::getZero<T>();
639 cache.cachedCubicCoefficients[3] = mKeyframes[lastKey].value;
640
641 return mKeyframes[lastKey].value;
642 }
643
644 // Since our value is not in cache, search for the valid pair of keys of interpolate
645 UINT32 leftKeyIdx;
646 UINT32 rightKeyIdx;
647
648 findKeys(time, cache, leftKeyIdx, rightKeyIdx);
649
650 // Calculate cubic hermite curve coefficients so we can store them in cache
651 const KeyFrame& leftKey = mKeyframes[leftKeyIdx];
652 const KeyFrame& rightKey = mKeyframes[rightKeyIdx];
653
654 cache.cachedCurveStart = leftKey.time;
655 cache.cachedCurveEnd = rightKey.time;
656
657 return impl::evaluateAndUpdateCache(leftKey, rightKey, time, cache.cachedCubicCoefficients);
658 }
659
660 template <class T>
661 T TAnimationCurve<T>::evaluate(float time, bool loop) const
662 {
663 if (mKeyframes.empty())
664 return impl::getZero<T>();
665
666 AnimationUtility::wrapTime(time, mStart, mEnd, loop);
667
668 UINT32 leftKeyIdx;
669 UINT32 rightKeyIdx;
670
671 findKeys(time, leftKeyIdx, rightKeyIdx);
672
673 // Evaluate curve as hermite cubic spline
674 const KeyFrame& leftKey = mKeyframes[leftKeyIdx];
675 const KeyFrame& rightKey = mKeyframes[rightKeyIdx];
676
677 if (leftKeyIdx == rightKeyIdx)
678 return leftKey.value;
679
680 return impl::evaluate(leftKey, rightKey, time);
681 }
682
683 template <class T>
684 T TAnimationCurve<T>::evaluateIntegrated(float time, const TCurveIntegrationCache<T>& integrationCache) const
685 {
686 const auto numKeyframes = (UINT32)mKeyframes.size();
687 if (numKeyframes == 0)
688 return impl::getZero<T>();
689
690 if(time < mStart)
691 time = mStart;
692
693 // Generate integration cache if required
694 if(!integrationCache.segmentSums)
695 buildIntegrationCache(integrationCache);
696
697 if(numKeyframes == 1)
698 return (T)(mKeyframes[0].value * (time - mKeyframes[0].time));
699
700 UINT32 leftKeyIdx;
701 UINT32 rightKeyIdx;
702
703 findKeys(time, leftKeyIdx, rightKeyIdx);
704
705 if(leftKeyIdx == rightKeyIdx)
706 return integrationCache.segmentSums[leftKeyIdx];
707
708 const KeyFrame& lhs = mKeyframes[leftKeyIdx];
709 T(&coeffs)[4] = integrationCache.coeffs[leftKeyIdx];
710
711 const float t = time - lhs.time;
712 return integrationCache.segmentSums[leftKeyIdx] + (T)(impl::evaluateCubic(t, 0.0f, 0.0f, coeffs) * t);
713 }
714
715 template <class T>
716 T TAnimationCurve<T>::evaluateIntegratedDouble(float time, const TCurveIntegrationCache<T>& integrationCache) const
717 {
718 const auto numKeyframes = (UINT32)mKeyframes.size();
719 if (numKeyframes == 0)
720 return impl::getZero<T>();
721
722 if(time < mStart)
723 time = mStart;
724
725 // Generate integration cache if required
726 if(!integrationCache.segmentSums)
727 buildDoubleIntegrationCache(integrationCache);
728
729 if(numKeyframes == 1)
730 {
731 float t = time - mKeyframes[0].time;
732 return (T)(mKeyframes[0].value * t * t * 0.5f);
733 }
734
735 UINT32 leftKeyIdx;
736 UINT32 rightKeyIdx;
737
738 findKeys(time, leftKeyIdx, rightKeyIdx);
739
740 const KeyFrame& lhs = mKeyframes[leftKeyIdx];
741 const float t = time - lhs.time;
742
743 const T sum = (T)(integrationCache.doubleSegmentSums[leftKeyIdx] + integrationCache.segmentSums[leftKeyIdx] * t);
744 if(leftKeyIdx == rightKeyIdx)
745 return sum;
746
747 T(&coeffs)[4] = integrationCache.coeffs[leftKeyIdx];
748 return sum + (T)(impl::evaluateCubic(t, 0.0f, 0.0f, coeffs) * t * t);
749 }
750
751 template <class T>
752 TKeyframe<T> TAnimationCurve<T>::evaluateKey(float time, bool loop) const
753 {
754 if (mKeyframes.empty())
755 return TKeyframe<T>();
756
757 AnimationUtility::wrapTime(time, mStart, mEnd, loop);
758
759 UINT32 leftKeyIdx;
760 UINT32 rightKeyIdx;
761
762 findKeys(time, leftKeyIdx, rightKeyIdx);
763
764 const KeyFrame& leftKey = mKeyframes[leftKeyIdx];
765 const KeyFrame& rightKey = mKeyframes[rightKeyIdx];
766
767 if (leftKeyIdx == rightKeyIdx)
768 return leftKey;
769
770 return evaluateKey(leftKey, rightKey, time);
771 }
772
773 template <class T>
774 void TAnimationCurve<T>::findKeys(float time, const TCurveCache<T>& animInstance, UINT32& leftKey, UINT32& rightKey) const
775 {
776 // Check nearby keys first if there is cached data
777 if (animInstance.cachedKey != (UINT32)-1)
778 {
779 const KeyFrame& curKey = mKeyframes[animInstance.cachedKey];
780 if (time >= curKey.time)
781 {
782 const UINT32 end = std::min((UINT32)mKeyframes.size(), animInstance.cachedKey + CACHE_LOOKAHEAD + 1);
783 for (UINT32 i = animInstance.cachedKey + 1; i < end; i++)
784 {
785 const KeyFrame& nextKey = mKeyframes[i];
786
787 if (time < nextKey.time)
788 {
789 leftKey = i - 1;
790 rightKey = i;
791
792 animInstance.cachedKey = leftKey;
793 return;
794 }
795 }
796 }
797 else
798 {
799 const UINT32 start = (UINT32)std::max(0, (INT32)animInstance.cachedKey - (INT32)CACHE_LOOKAHEAD);
800 for(UINT32 i = start; i < animInstance.cachedKey; i++)
801 {
802 const KeyFrame& prevKey = mKeyframes[i];
803
804 if (time >= prevKey.time)
805 {
806 leftKey = i;
807 rightKey = i + 1;
808
809 animInstance.cachedKey = leftKey;
810 return;
811 }
812 }
813 }
814 }
815
816 // Cannot find nearby ones, search all keys
817 findKeys(time, leftKey, rightKey);
818 animInstance.cachedKey = leftKey;
819 }
820
821 template <class T>
822 void TAnimationCurve<T>::findKeys(float time, UINT32& leftKey, UINT32& rightKey) const
823 {
824 INT32 start = 0;
825 auto searchLength = (INT32)mKeyframes.size();
826
827 while(searchLength > 0)
828 {
829 INT32 half = searchLength >> 1;
830 INT32 mid = start + half;
831
832 if(time < mKeyframes[mid].time)
833 {
834 searchLength = half;
835 }
836 else
837 {
838 start = mid + 1;
839 searchLength -= (half + 1);
840 }
841 }
842
843 leftKey = std::max(0, start - 1);
844 rightKey = std::min(start, (INT32)mKeyframes.size() - 1);
845 }
846
847 template <class T>
848 UINT32 TAnimationCurve<T>::findKey(float time)
849 {
850 UINT32 leftKeyIdx;
851 UINT32 rightKeyIdx;
852
853 findKeys(time, leftKeyIdx, rightKeyIdx);
854
855 const KeyFrame& leftKey = mKeyframes[leftKeyIdx];
856 const KeyFrame& rightKey = mKeyframes[rightKeyIdx];
857
858 if (Math::abs(leftKey.time - time) <= Math::abs(rightKey.time - time))
859 return leftKeyIdx;
860
861 return rightKeyIdx;
862 }
863
864 template <class T>
865 TKeyframe<T> TAnimationCurve<T>::evaluateKey(const KeyFrame& lhs, const KeyFrame& rhs, float time) const
866 {
867 return impl::evaluateKey(lhs, rhs, time);
868 }
869
870 template <class T>
871 TAnimationCurve<T> TAnimationCurve<T>::split(float start, float end)
872 {
873 Vector<TKeyframe<T>> keyFrames;
874
875 start = Math::clamp(start, mStart, mEnd);
876 end = Math::clamp(end, mStart, mEnd);
877
878 UINT32 startKeyIdx = findKey(start);
879 UINT32 endKeyIdx = findKey(end);
880
881 keyFrames.reserve(endKeyIdx - startKeyIdx + 2);
882
883 const KeyFrame& startKey = mKeyframes[startKeyIdx];
884
885 if (!Math::approxEquals(startKey.time, start))
886 {
887 if(start > startKey.time)
888 {
889 if (mKeyframes.size() > (startKeyIdx + 1))
890 keyFrames.push_back(evaluateKey(startKey, mKeyframes[startKeyIdx + 1], start));
891 else
892 {
893 TKeyframe<T> keyCopy = startKey;
894 keyCopy.time = start;
895
896 keyFrames.push_back(keyCopy);
897 }
898
899 startKeyIdx++;
900 }
901 else
902 {
903
904 if (startKeyIdx > 0)
905 keyFrames.push_back(evaluateKey(mKeyframes[startKeyIdx - 1], startKey , start));
906 else
907 {
908 TKeyframe<T> keyCopy = startKey;
909 keyCopy.time = start;
910
911 keyFrames.push_back(keyCopy);
912 }
913 }
914 }
915 else
916 {
917 keyFrames.push_back(startKey);
918 startKeyIdx++;
919 }
920
921 if (!Math::approxEquals(end - start, 0.0f))
922 {
923 const KeyFrame& endKey = mKeyframes[endKeyIdx];
924 if(!Math::approxEquals(endKey.time, end))
925 {
926 if(end > endKey.time)
927 {
928 if (mKeyframes.size() > (endKeyIdx + 1))
929 keyFrames.push_back(evaluateKey(endKey, mKeyframes[endKeyIdx + 1], end));
930 else
931 {
932 TKeyframe<T> keyCopy = endKey;
933 keyCopy.time = end;
934
935 keyFrames.push_back(keyCopy);
936 }
937 }
938 else
939 {
940 if(endKeyIdx > 0)
941 {
942 keyFrames.push_back(evaluateKey(mKeyframes[endKeyIdx - 1], endKey, end));
943 endKeyIdx--;
944 }
945 else
946 {
947 TKeyframe<T> keyCopy = endKey;
948 keyCopy.time = end;
949
950 keyFrames.push_back(keyCopy);
951 }
952 }
953 }
954
955 if (startKeyIdx < (UINT32)mKeyframes.size() && endKeyIdx > startKeyIdx)
956 keyFrames.insert(keyFrames.begin() + 1, mKeyframes.begin() + startKeyIdx, mKeyframes.begin() + endKeyIdx + 1);
957 }
958
959 for (auto& entry : keyFrames)
960 entry.time -= start;
961
962 return TAnimationCurve<T>(keyFrames);
963 }
964
965 template <class T>
966 void TAnimationCurve<T>::makeAdditive()
967 {
968 if (mKeyframes.size() < 2)
969 return;
970
971 const KeyFrame& refKey = mKeyframes[0];
972 const auto numKeys = (UINT32)mKeyframes.size();
973
974 for(UINT32 i = 1; i < numKeys; i++)
975 mKeyframes[i].value = impl::getDiff(mKeyframes[i].value, refKey.value);
976 }
977
978 template <class T>
979 std::pair<float, float> TAnimationCurve<T>::getTimeRange() const
980 {
981 if(mKeyframes.empty())
982 return std::make_pair(0.0f, 0.0f);
983
984 if(mKeyframes.size() == 1)
985 return std::make_pair(mKeyframes[0].time, mKeyframes[0].time);
986
987 return std::make_pair(mKeyframes[0].time, mKeyframes[mKeyframes.size() - 1].time);
988 }
989
990 template <class T>
991 std::pair<T, T> TAnimationCurve<T>::calculateRange() const
992 {
993 const auto numKeys = (UINT32)mKeyframes.size();
994 if(numKeys == 0)
995 return std::make_pair(impl::getZero<T>(), impl::getZero<T>());
996
997 std::pair<T, T> output = { std::numeric_limits<T>::infinity(), -std::numeric_limits<T>::infinity() };
998 impl::getMinMax(output, mKeyframes[0].value);
999
1000 for(UINT32 i = 1; i < numKeys; i++)
1001 {
1002 const KeyFrame& lhs = mKeyframes[i - 1];
1003 const KeyFrame& rhs = mKeyframes[i];
1004
1005 T coeffs[4];
1006 impl::calculateCoeffs(lhs, rhs, lhs.time, coeffs);
1007 impl::calcMinMax(output, lhs.time, rhs.time, coeffs);
1008
1009 T endVal = impl::evaluateCubic(rhs.time, lhs.time, 0.0f, coeffs);
1010 impl::getMinMax(output, endVal);
1011 }
1012
1013 return output;
1014 }
1015
1016 template <class T>
1017 std::pair<T, T> TAnimationCurve<T>::calculateRangeIntegrated(const TCurveIntegrationCache<T>& cache) const
1018 {
1019 std::pair<T, T> output = std::make_pair(impl::getZero<T>(), impl::getZero<T>());
1020
1021 const auto numKeys = (UINT32)mKeyframes.size();
1022 if(numKeys == 0)
1023 return output;
1024
1025 if(!cache.segmentSums)
1026 buildIntegrationCache(cache);
1027
1028 for(UINT32 i = 1; i < numKeys; i++)
1029 {
1030 const KeyFrame& lhs = mKeyframes[i - 1];
1031 const KeyFrame& rhs = mKeyframes[i];
1032
1033 T (&coeffs)[4] = cache.coeffs[i - 1];
1034 impl::calcMinMaxIntegrated(output, lhs.time, rhs.time, cache.segmentSums[i - 1], coeffs);
1035
1036 float t = rhs.time - lhs.time;
1037 T endVal = (T)(cache.segmentSums[i - 1] + impl::evaluateCubic(t, 0.0f, 0.0f, coeffs) * t);
1038 impl::getMinMax(output, endVal);
1039 }
1040
1041 return output;
1042 }
1043
1044 template <class T>
1045 std::pair<T, T> TAnimationCurve<T>::calculateRangeIntegratedDouble(const TCurveIntegrationCache<T>& cache) const
1046 {
1047 std::pair<T, T> output = std::make_pair(impl::getZero<T>(), impl::getZero<T>());
1048
1049 const auto numKeys = (UINT32)mKeyframes.size();
1050 if(numKeys == 0)
1051 return output;
1052
1053 if(!cache.segmentSums)
1054 buildDoubleIntegrationCache(cache);
1055
1056 for(UINT32 i = 1; i < numKeys; i++)
1057 {
1058 const KeyFrame& lhs = mKeyframes[i - 1];
1059 const KeyFrame& rhs = mKeyframes[i];
1060
1061 T (&coeffs)[4] = cache.coeffs[i - 1];
1062 impl::calcMinMaxIntegratedDouble(output, lhs.time, rhs.time, cache.doubleSegmentSums[i - 1],
1063 cache.segmentSums[i - 1], coeffs);
1064
1065 float t = rhs.time - lhs.time;
1066 T endVal = (T)(cache.doubleSegmentSums[i - 1] + cache.segmentSums[i - 1] * t +
1067 impl::evaluateCubic(t, 0.0f, 0.0f, coeffs) * t * t);
1068 impl::getMinMax(output, endVal);
1069 }
1070
1071 return output;
1072 }
1073
1074 template <class T>
1075 void TAnimationCurve<T>::buildIntegrationCache(const TCurveIntegrationCache<T>& cache) const
1076 {
1077 assert(!cache.segmentSums);
1078
1079 const auto numKeyframes = (UINT32)mKeyframes.size();
1080 if(numKeyframes <= 1)
1081 return;
1082
1083 cache.init(numKeyframes);
1084 cache.segmentSums[0] = impl::getZero<T>();
1085
1086 for (UINT32 i = 1; i < numKeyframes; i++)
1087 {
1088 const TKeyframe<T>& lhs = mKeyframes[i - 1];
1089 const TKeyframe<T>& rhs = mKeyframes[i];
1090
1091 T(&coeffs)[4] = cache.coeffs[i - 1];
1092 impl::calculateCoeffs(lhs, rhs, lhs.time, coeffs);
1093 impl::integrate(coeffs);
1094
1095 // Evaluate value at the end of the segment and add to the cache (this value is the total area under
1096 // the segment)
1097 const float t = rhs.time - lhs.time;
1098 const T value = (T)(impl::evaluateCubic(t, 0.0f, 0.0f, coeffs) * t);
1099 cache.segmentSums[i] = cache.segmentSums[i - 1] + value;
1100 }
1101 }
1102
1103 template <class T>
1104 void TAnimationCurve<T>::buildDoubleIntegrationCache(const TCurveIntegrationCache<T>& cache) const
1105 {
1106 assert(!cache.segmentSums);
1107
1108 const auto numKeyframes = (UINT32)mKeyframes.size();
1109 if(numKeyframes <= 1)
1110 return;
1111
1112 cache.initDouble(numKeyframes);
1113 cache.segmentSums[0] = impl::getZero<T>();
1114 cache.doubleSegmentSums[0] = impl::getZero<T>();
1115
1116 for (UINT32 i = 1; i < numKeyframes; i++)
1117 {
1118 const TKeyframe<T>& lhs = mKeyframes[i - 1];
1119 const TKeyframe<T>& rhs = mKeyframes[i];
1120
1121 T(&coeffs)[4] = cache.coeffs[i - 1];
1122 impl::calculateCoeffs(lhs, rhs, lhs.time, coeffs);
1123 impl::integrate(coeffs);
1124
1125 // Evaluate value at the end of the segment and add to the cache (this value is the total area under
1126 // the segment)
1127 const float t = rhs.time - lhs.time;
1128 T value = (T)(impl::evaluateCubic(t, 0.0f, 0.0f, coeffs) * t);
1129 cache.segmentSums[i] = cache.segmentSums[i - 1] + value;
1130
1131 // Double integrate the already integrated coeffs
1132 coeffs[0] = (T)(coeffs[0] / 5.0f);
1133 coeffs[1] = (T)(coeffs[1] / 4.0f);
1134 coeffs[2] = (T)(coeffs[2] / 3.0f);
1135 coeffs[3] = (T)(coeffs[3] / 2.0f);
1136
1137 value = (T)(impl::evaluateCubic(t, 0.0f, 0.0f, coeffs) * t * t + cache.segmentSums[i - 1] * t);
1138 cache.doubleSegmentSums[i] = cache.doubleSegmentSums[i - 1] + value;
1139 }
1140 }
1141
1142 template <class T>
1143 bool TAnimationCurve<T>::operator==(const TAnimationCurve<T>& rhs) const
1144 {
1145 if(mLength != rhs.mLength || mStart != rhs.mStart || mEnd != rhs.mEnd)
1146 return false;
1147
1148 return mKeyframes == rhs.mKeyframes;
1149 }
1150
1151 template class TAnimationCurve<Vector3>;
1152 template class TAnimationCurve<Vector2>;
1153 template class TAnimationCurve<Quaternion>;
1154 template class TAnimationCurve<float>;
1155 template class TAnimationCurve<INT32>;
1156}