OpenShot Library | libopenshot  0.2.5
KeyFrame.cpp
Go to the documentation of this file.
1 /**
2  * @file
3  * @brief Source file for the Keyframe class
4  * @author Jonathan Thomas <jonathan@openshot.org>
5  *
6  * @ref License
7  */
8 
9 /* LICENSE
10  *
11  * Copyright (c) 2008-2019 OpenShot Studios, LLC
12  * <http://www.openshotstudios.com/>. This file is part of
13  * OpenShot Library (libopenshot), an open-source project dedicated to
14  * delivering high quality video editing and animation solutions to the
15  * world. For more information visit <http://www.openshot.org/>.
16  *
17  * OpenShot Library (libopenshot) is free software: you can redistribute it
18  * and/or modify it under the terms of the GNU Lesser General Public License
19  * as published by the Free Software Foundation, either version 3 of the
20  * License, or (at your option) any later version.
21  *
22  * OpenShot Library (libopenshot) is distributed in the hope that it will be
23  * useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
25  * GNU Lesser General Public License for more details.
26  *
27  * You should have received a copy of the GNU Lesser General Public License
28  * along with OpenShot Library. If not, see <http://www.gnu.org/licenses/>.
29  */
30 
31 #include "../include/KeyFrame.h"
32 #include <algorithm>
33 #include <functional>
34 #include <utility>
35 
36 using namespace std;
37 using namespace openshot;
38 
39 namespace {
40  bool IsPointBeforeX(Point const & p, double const x) {
41  return p.co.X < x;
42  }
43 
44  double InterpolateLinearCurve(Point const & left, Point const & right, double const target) {
45  double const diff_Y = right.co.Y - left.co.Y;
46  double const diff_X = right.co.X - left.co.X;
47  double const slope = diff_Y / diff_X;
48  return left.co.Y + slope * (target - left.co.X);
49  }
50 
51  double InterpolateBezierCurve(Point const & left, Point const & right, double const target, double const allowed_error) {
52  double const X_diff = right.co.X - left.co.X;
53  double const Y_diff = right.co.Y - left.co.Y;
54  Coordinate const p0 = left.co;
55  Coordinate const p1 = Coordinate(p0.X + left.handle_right.X * X_diff, p0.Y + left.handle_right.Y * Y_diff);
56  Coordinate const p2 = Coordinate(p0.X + right.handle_left.X * X_diff, p0.Y + right.handle_left.Y * Y_diff);
57  Coordinate const p3 = right.co;
58 
59  double t = 0.5;
60  double t_step = 0.25;
61  do {
62  // Bernstein polynoms
63  double B[4] = {1, 3, 3, 1};
64  double oneMinTExp = 1;
65  double tExp = 1;
66  for (int i = 0; i < 4; ++i, tExp *= t) {
67  B[i] *= tExp;
68  }
69  for (int i = 0; i < 4; ++i, oneMinTExp *= 1 - t) {
70  B[4 - i - 1] *= oneMinTExp;
71  }
72  double const x = p0.X * B[0] + p1.X * B[1] + p2.X * B[2] + p3.X * B[3];
73  double const y = p0.Y * B[0] + p1.Y * B[1] + p2.Y * B[2] + p3.Y * B[3];
74  if (fabs(target - x) < allowed_error) {
75  return y;
76  }
77  if (x > target) {
78  t -= t_step;
79  }
80  else {
81  t += t_step;
82  }
83  t_step /= 2;
84  } while (true);
85  }
86 
87 
88  double InterpolateBetween(Point const & left, Point const & right, double target, double allowed_error) {
89  assert(left.co.X < target);
90  assert(target <= right.co.X);
91  switch (right.interpolation) {
92  case CONSTANT: return left.co.Y;
93  case LINEAR: return InterpolateLinearCurve(left, right, target);
94  case BEZIER: return InterpolateBezierCurve(left, right, target, allowed_error);
95  }
96  }
97 
98 
99  template<typename Check>
100  int64_t SearchBetweenPoints(Point const & left, Point const & right, int64_t const current, Check check) {
101  int64_t start = left.co.X;
102  int64_t stop = right.co.X;
103  while (start < stop) {
104  int64_t const mid = (start + stop + 1) / 2;
105  double const value = InterpolateBetween(left, right, mid, 0.01);
106  if (check(round(value), current)) {
107  start = mid;
108  } else {
109  stop = mid - 1;
110  }
111  }
112  return start;
113  }
114 }
115 
116 
117 // Constructor which sets the default point & coordinate at X=1
118 Keyframe::Keyframe(double value) {
119  // Add initial point
120  AddPoint(Point(value));
121 }
122 
123 // Add a new point on the key-frame. Each point has a primary coordinate,
124 // a left handle, and a right handle.
125 void Keyframe::AddPoint(Point p) {
126  // candidate is not less (greater or equal) than the new point in
127  // the X coordinate.
128  std::vector<Point>::iterator candidate =
129  std::lower_bound(begin(Points), end(Points), p.co.X, IsPointBeforeX);
130  if (candidate == end(Points)) {
131  // New point X is greater than all other points' X, add to
132  // back.
133  Points.push_back(p);
134  } else if ((*candidate).co.X == p.co.X) {
135  // New point is at same X coordinate as some point, overwrite
136  // point.
137  *candidate = p;
138  } else {
139  // New point needs to be inserted before candidate; thus move
140  // candidate and all following one to the right and insert new
141  // point then where candidate was.
142  size_t const candidate_index = candidate - begin(Points);
143  Points.push_back(p); // Make space; could also be a dummy point. INVALIDATES candidate!
144  std::move_backward(begin(Points) + candidate_index, end(Points) - 1, end(Points));
145  Points[candidate_index] = p;
146  }
147 }
148 
149 // Add a new point on the key-frame, with some defaults set (BEZIER)
150 void Keyframe::AddPoint(double x, double y)
151 {
152  // Create a point
153  Point new_point(x, y, BEZIER);
154 
155  // Add the point
156  AddPoint(new_point);
157 }
158 
159 // Add a new point on the key-frame, with a specific interpolation type
160 void Keyframe::AddPoint(double x, double y, InterpolationType interpolate)
161 {
162  // Create a point
163  Point new_point(x, y, interpolate);
164 
165  // Add the point
166  AddPoint(new_point);
167 }
168 
169 // Get the index of a point by matching a coordinate
170 int64_t Keyframe::FindIndex(Point p) const {
171  // loop through points, and find a matching coordinate
172  for (std::vector<Point>::size_type x = 0; x < Points.size(); x++) {
173  // Get each point
174  Point existing_point = Points[x];
175 
176  // find a match
177  if (p.co.X == existing_point.co.X && p.co.Y == existing_point.co.Y) {
178  // Remove the matching point, and break out of loop
179  return x;
180  }
181  }
182 
183  // no matching point found
184  throw OutOfBoundsPoint("Invalid point requested", -1, Points.size());
185 }
186 
187 // Determine if point already exists
188 bool Keyframe::Contains(Point p) const {
189  std::vector<Point>::const_iterator i =
190  std::lower_bound(begin(Points), end(Points), p.co.X, IsPointBeforeX);
191  return i != end(Points) && i->co.X == p.co.X;
192 }
193 
194 // Get current point (or closest point) from the X coordinate (i.e. the frame number)
195 Point Keyframe::GetClosestPoint(Point p, bool useLeft) const {
196  if (Points.size() == 0) {
197  return Point(-1, -1);
198  }
199 
200  // Finds a point with an X coordinate which is "not less" (greater
201  // or equal) than the queried X coordinate.
202  std::vector<Point>::const_iterator candidate =
203  std::lower_bound(begin(Points), end(Points), p.co.X, IsPointBeforeX);
204 
205  if (candidate == end(Points)) {
206  // All points are before the queried point.
207  //
208  // Note: Behavior the same regardless of useLeft!
209  return Points.back();
210  }
211  if (candidate == begin(Points)) {
212  // First point is greater or equal to the queried point.
213  //
214  // Note: Behavior the same regardless of useLeft!
215  return Points.front();
216  }
217  if (useLeft) {
218  return *(candidate - 1);
219  } else {
220  return *candidate;
221  }
222 }
223 
224 // Get current point (or closest point to the right) from the X coordinate (i.e. the frame number)
225 Point Keyframe::GetClosestPoint(Point p) const {
226  return GetClosestPoint(p, false);
227 }
228 
229 // Get previous point (if any)
230 Point Keyframe::GetPreviousPoint(Point p) const {
231 
232  // Lookup the index of this point
233  try {
234  int64_t index = FindIndex(p);
235 
236  // If not the 1st point
237  if (index > 0)
238  return Points[index - 1];
239  else
240  return Points[0];
241 
242  } catch (const OutOfBoundsPoint& e) {
243  // No previous point
244  return Point(-1, -1);
245  }
246 }
247 
248 // Get max point (by Y coordinate)
249 Point Keyframe::GetMaxPoint() const {
250  Point maxPoint(-1, -1);
251 
252  for (Point const & existing_point: Points) {
253  if (existing_point.co.Y >= maxPoint.co.Y) {
254  maxPoint = existing_point;
255  }
256  }
257 
258  return maxPoint;
259 }
260 
261 // Get the value at a specific index
262 double Keyframe::GetValue(int64_t index) const {
263  if (Points.empty()) {
264  return 0;
265  }
266  std::vector<Point>::const_iterator candidate =
267  std::lower_bound(begin(Points), end(Points), static_cast<double>(index), IsPointBeforeX);
268 
269  if (candidate == end(Points)) {
270  // index is behind last point
271  return Points.back().co.Y;
272  }
273  if (candidate == begin(Points)) {
274  // index is at or before first point
275  return Points.front().co.Y;
276  }
277  if (candidate->co.X == index) {
278  // index is directly on a point
279  return candidate->co.Y;
280  }
281  std::vector<Point>::const_iterator predecessor = candidate - 1;
282  return InterpolateBetween(*predecessor, *candidate, index, 0.01);
283 }
284 
285 // Get the rounded INT value at a specific index
286 int Keyframe::GetInt(int64_t index) const {
287  return int(round(GetValue(index)));
288 }
289 
290 // Get the rounded INT value at a specific index
291 int64_t Keyframe::GetLong(int64_t index) const {
292  return long(round(GetValue(index)));
293 }
294 
295 // Get the direction of the curve at a specific index (increasing or decreasing)
296 bool Keyframe::IsIncreasing(int index) const
297 {
298  if (index < 1 || (index + 1) >= GetLength()) {
299  return true;
300  }
301  std::vector<Point>::const_iterator candidate =
302  std::lower_bound(begin(Points), end(Points), static_cast<double>(index), IsPointBeforeX);
303  if (candidate == end(Points)) {
304  return false; // After the last point, thus constant.
305  }
306  if ((candidate->co.X == index) || (candidate == begin(Points))) {
307  ++candidate;
308  }
309  int64_t const value = GetLong(index);
310  do {
311  if (value < round(candidate->co.Y)) {
312  return true;
313  } else if (value > round(candidate->co.Y)) {
314  return false;
315  }
316  ++candidate;
317  } while (candidate != end(Points));
318  return false;
319 }
320 
321 // Generate JSON string of this object
322 std::string Keyframe::Json() const {
323 
324  // Return formatted string
325  return JsonValue().toStyledString();
326 }
327 
328 // Generate Json::Value for this object
329 Json::Value Keyframe::JsonValue() const {
330 
331  // Create root json object
332  Json::Value root;
333  root["Points"] = Json::Value(Json::arrayValue);
334 
335  // loop through points
336  for (const auto existing_point : Points) {
337  root["Points"].append(existing_point.JsonValue());
338  }
339 
340  // return JsonValue
341  return root;
342 }
343 
344 // Load JSON string into this object
345 void Keyframe::SetJson(const std::string value) {
346 
347  // Parse JSON string into JSON objects
348  try
349  {
350  const Json::Value root = openshot::stringToJson(value);
351  // Set all values that match
352  SetJsonValue(root);
353  }
354  catch (const std::exception& e)
355  {
356  // Error parsing JSON (or missing keys)
357  throw InvalidJSON("JSON is invalid (missing keys or invalid data types)");
358  }
359 }
360 
361 // Load Json::Value into this object
362 void Keyframe::SetJsonValue(const Json::Value root) {
363  // Clear existing points
364  Points.clear();
365 
366  if (!root["Points"].isNull())
367  // loop through points
368  for (const auto existing_point : root["Points"]) {
369  // Create Point
370  Point p;
371 
372  // Load Json into Point
373  p.SetJsonValue(existing_point);
374 
375  // Add Point to Keyframe
376  AddPoint(p);
377  }
378 }
379 
380 // Get the fraction that represents how many times this value is repeated in the curve
381 // This is depreciated and will be removed soon.
382 Fraction Keyframe::GetRepeatFraction(int64_t index) const {
383  // Frame numbers (index) outside of the "defined" range of this
384  // keyframe result in a 1/1 default value.
385  if (index < 1 || (index + 1) >= GetLength()) {
386  return Fraction(1,1);
387  }
388  assert(Points.size() > 1); // Due to ! ((index + 1) >= GetLength) there are at least two points!
389 
390  // First, get the value at the given frame and the closest point
391  // to the right.
392  int64_t const current_value = GetLong(index);
393  std::vector<Point>::const_iterator const candidate =
394  std::lower_bound(begin(Points), end(Points), static_cast<double>(index), IsPointBeforeX);
395  assert(candidate != end(Points)); // Due to the (index + 1) >= GetLength check above!
396 
397  // Calculate how many of the next values are going to be the same:
398  int64_t next_repeats = 0;
399  std::vector<Point>::const_iterator i = candidate;
400  // If the index (frame number) is the X coordinate of the closest
401  // point, then look at the segment to the right; the "current"
402  // segement is not interesting because we're already at the last
403  // value of it.
404  if (i->co.X == index) {
405  ++i;
406  }
407  // Skip over "constant" (when rounded) segments.
408  bool all_constant = true;
409  for (; i != end(Points); ++i) {
410  if (current_value != round(i->co.Y)) {
411  all_constant = false;
412  break;
413  }
414  }
415  if (! all_constant) {
416  // Found a point which defines a segment which will give a
417  // different value than the current value. This means we
418  // moved at least one segment to the right, thus we cannot be
419  // at the first point.
420  assert(i != begin(Points));
421  Point const left = *(i - 1);
422  Point const right = *i;
423  int64_t change_at;
424  if (current_value < round(i->co.Y)) {
425  change_at = SearchBetweenPoints(left, right, current_value, std::less_equal<double>{});
426  } else {
427  assert(current_value > round(i->co.Y));
428  change_at = SearchBetweenPoints(left, right, current_value, std::greater_equal<double>{});
429  }
430  next_repeats = change_at - index;
431  } else {
432  // All values to the right are the same!
433  next_repeats = Points.back().co.X - index;
434  }
435 
436  // Now look to the left, to the previous values.
437  all_constant = true;
438  i = candidate;
439  if (i != begin(Points)) {
440  // The binary search below assumes i to be the left point;
441  // candidate is the right point of the current segment
442  // though. So change this if possible. If this branch is NOT
443  // taken, then we're at/before the first point and all is
444  // constant!
445  --i;
446  }
447  int64_t previous_repeats = 0;
448  // Skip over constant (when rounded) segments!
449  for (; i != begin(Points); --i) {
450  if (current_value != round(i->co.Y)) {
451  all_constant = false;
452  break;
453  }
454  }
455  // Special case when skipped until the first point, but the first
456  // point is actually different. Will not happen if index is
457  // before the first point!
458  if (current_value != round(i->co.Y)) {
459  assert(i != candidate);
460  all_constant = false;
461  }
462  if (! all_constant) {
463  // There are at least two points, and we're not at the end,
464  // thus the following is safe!
465  Point const left = *i;
466  Point const right = *(i + 1);
467  int64_t change_at;
468  if (current_value > round(left.co.Y)) {
469  change_at = SearchBetweenPoints(left, right, current_value, std::less<double>{});
470  } else {
471  assert(current_value < round(left.co.Y));
472  change_at = SearchBetweenPoints(left, right, current_value, std::greater<double>{});
473  }
474  previous_repeats = index - change_at;
475  } else {
476  // Every previous value is the same (rounded) as the current
477  // value.
478  previous_repeats = index;
479  }
480  int64_t total_repeats = previous_repeats + next_repeats;
481  return Fraction(previous_repeats, total_repeats);
482 }
483 
484 // Get the change in Y value (from the previous Y value)
485 double Keyframe::GetDelta(int64_t index) const {
486  if (index < 1) return 0;
487  if (index == 1 && ! Points.empty()) return Points[0].co.Y;
488  if (index >= GetLength()) return 0;
489  return GetLong(index) - GetLong(index - 1);
490 }
491 
492 // Get a point at a specific index
493 Point const & Keyframe::GetPoint(int64_t index) const {
494  // Is index a valid point?
495  if (index >= 0 && index < (int64_t)Points.size())
496  return Points[index];
497  else
498  // Invalid index
499  throw OutOfBoundsPoint("Invalid point requested", index, Points.size());
500 }
501 
502 // Get the number of values (i.e. coordinates on the X axis)
503 int64_t Keyframe::GetLength() const {
504  if (Points.empty()) return 0;
505  if (Points.size() == 1) return 1;
506  return round(Points.back().co.X) + 1;
507 }
508 
509 // Get the number of points (i.e. # of points)
510 int64_t Keyframe::GetCount() const {
511 
512  return Points.size();
513 }
514 
515 // Remove a point by matching a coordinate
516 void Keyframe::RemovePoint(Point p) {
517  // loop through points, and find a matching coordinate
518  for (std::vector<Point>::size_type x = 0; x < Points.size(); x++) {
519  // Get each point
520  Point existing_point = Points[x];
521 
522  // find a match
523  if (p.co.X == existing_point.co.X && p.co.Y == existing_point.co.Y) {
524  // Remove the matching point, and break out of loop
525  Points.erase(Points.begin() + x);
526  return;
527  }
528  }
529 
530  // no matching point found
531  throw OutOfBoundsPoint("Invalid point requested", -1, Points.size());
532 }
533 
534 // Remove a point by index
535 void Keyframe::RemovePoint(int64_t index) {
536  // Is index a valid point?
537  if (index >= 0 && index < (int64_t)Points.size())
538  {
539  // Remove a specific point by index
540  Points.erase(Points.begin() + index);
541  }
542  else
543  // Invalid index
544  throw OutOfBoundsPoint("Invalid point requested", index, Points.size());
545 }
546 
547 void Keyframe::UpdatePoint(int64_t index, Point p) {
548  // Remove matching point
549  RemovePoint(index);
550 
551  // Add new point
552  AddPoint(p);
553 }
554 
555 void Keyframe::PrintPoints() const {
556  cout << fixed << setprecision(4);
557  for (std::vector<Point>::const_iterator it = Points.begin(); it != Points.end(); it++) {
558  Point p = *it;
559  cout << p.co.X << "\t" << p.co.Y << endl;
560  }
561 }
562 
563 void Keyframe::PrintValues() const {
564  cout << fixed << setprecision(4);
565  cout << "Frame Number (X)\tValue (Y)\tIs Increasing\tRepeat Numerator\tRepeat Denominator\tDelta (Y Difference)\n";
566 
567  for (int64_t i = 1; i < GetLength(); ++i) {
568  cout << i << "\t" << GetValue(i) << "\t" << IsIncreasing(i) << "\t" ;
569  cout << GetRepeatFraction(i).num << "\t" << GetRepeatFraction(i).den << "\t" << GetDelta(i) << "\n";
570  }
571 }
572 
573 
574 // Scale all points by a percentage (good for evenly lengthening or shortening an openshot::Keyframe)
575 // 1.0 = same size, 1.05 = 5% increase, etc...
576 void Keyframe::ScalePoints(double scale)
577 {
578  // TODO: What if scale is small so that two points land on the
579  // same X coordinate?
580  // TODO: What if scale < 0?
581 
582  // Loop through each point (skipping the 1st point)
583  for (std::vector<Point>::size_type point_index = 1; point_index < Points.size(); point_index++) {
584  // Scale X value
585  Points[point_index].co.X = round(Points[point_index].co.X * scale);
586  }
587 }
588 
589 // Flip all the points in this openshot::Keyframe (useful for reversing an effect or transition, etc...)
590 void Keyframe::FlipPoints() {
591  for (std::vector<Point>::size_type point_index = 0, reverse_index = Points.size() - 1; point_index < reverse_index; point_index++, reverse_index--) {
592  // Flip the points
593  using std::swap;
594  swap(Points[point_index].co.Y, Points[reverse_index].co.Y);
595  // TODO: check that this has the desired effect even with
596  // regards to handles!
597  }
598 }
This class represents a Cartesian coordinate (X, Y) used in the Keyframe animation system...
Definition: Coordinate.h:55
void SetJsonValue(const Json::Value root)
Load Json::Value into this object.
Definition: Point.cpp:152
Bezier curves are quadratic curves, which create a smooth curve.
Definition: Point.h:47
InterpolationType interpolation
This is the interpolation mode.
Definition: Point.h:87
Coordinate handle_right
This is the right handle coordinate (in percentages from 0 to 1)
Definition: Point.h:86
STL namespace.
Coordinate handle_left
This is the left handle coordinate (in percentages from 0 to 1)
Definition: Point.h:85
A Point is the basic building block of a key-frame curve.
Definition: Point.h:82
const Json::Value stringToJson(const std::string value)
Definition: Json.cpp:33
double Y
The Y value of the coordinate (usually representing the value of the property being animated) ...
Definition: Coordinate.h:58
This class represents a fraction.
Definition: Fraction.h:45
double X
The X value of the coordinate (usually representing the frame #)
Definition: Coordinate.h:57
InterpolationType
This controls how a Keyframe uses this point to interpolate between two points.
Definition: Point.h:46
if(!codec) codec
This namespace is the default namespace for all code in the openshot library.
Linear curves are angular, straight lines between two points.
Definition: Point.h:48
Coordinate co
This is the primary coordinate.
Definition: Point.h:84
Exception for invalid JSON.
Definition: Exceptions.h:205
Exception for an out of bounds key-frame point.
Definition: Exceptions.h:303
Constant curves jump from their previous position to a new one (with no interpolation).
Definition: Point.h:49