Keyframe->GetValue works on O(log n)

Previous code iterate whole key-frame to get interpolated progress value.
This patch make this job in O(log n).

So we can run animation faster even it have near 500 key-frames.

Change-Id: I14ee07db7aa75142aaaf323af7cfde9522d3851d
Signed-off-by: Eunki, Hong <eunkiki.hong@samsung.com>

diff --git a/dali/internal/event/animation/key-frame-channel.h b/dali/internal/event/animation/key-frame-channel.h
index 781ffff..c9ba8b3 100644 (file)
--- a/dali/internal/event/animation/key-frame-channel.h
+++ b/dali/internal/event/animation/key-frame-channel.h
@@ -2,7 +2,7 @@
 #define DALI_INTERNAL_KEY_FRAME_CHANNEL_H
 
 /*
- * Copyright (c) 2021 Samsung Electronics Co., Ltd.
+ * Copyright (c) 2022 Samsung Electronics Co., Ltd.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -54,7 +54,9 @@ struct KeyFrameChannel
     }
     else
     {
-      auto end   = std::find_if(mValues.begin(), mValues.end(), [=](const auto& element) { return element.GetProgress() > progress; });
+      // Find lowest element s.t. progress is greater than progress.
+      // So start->GetProgress() <= progress < end->GetProgress() is satisfied.
+      auto end   = std::lower_bound(mValues.begin(), mValues.end(), progress, [](const auto& element, const float& progress) { return element.GetProgress() <= progress; });
       auto start = end - 1;
 
       const bool validInterval = (end != mValues.end()) && (start->GetProgress() <= progress);