OpenShot Library | libopenshot  0.2.4
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 (abs(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::JsonValue 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, and find a matching coordinate
336  for (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(std::string value) {
346 
347  // Parse JSON string into JSON objects
348  Json::Value root;
349  Json::CharReaderBuilder rbuilder;
350  Json::CharReader* reader(rbuilder.newCharReader());
351 
352  std::string errors;
353  bool success = reader->parse( value.c_str(),
354  value.c_str() + value.size(), &root, &errors );
355  delete reader;
356 
357  if (!success)
358  // Raise exception
359  throw InvalidJSON("JSON could not be parsed (or is invalid)");
360 
361  try
362  {
363  // Set all values that match
364  SetJsonValue(root);
365  }
366  catch (const std::exception& e)
367  {
368  // Error parsing JSON (or missing keys)
369  throw InvalidJSON("JSON is invalid (missing keys or invalid data types)");
370  }
371 }
372 
373 // Load Json::JsonValue into this object
374 void Keyframe::SetJsonValue(Json::Value root) {
375  // Clear existing points
376  Points.clear();
377 
378  if (!root["Points"].isNull())
379  // loop through points
380  for (const auto existing_point : root["Points"]) {
381  // Create Point
382  Point p;
383 
384  // Load Json into Point
385  p.SetJsonValue(existing_point);
386 
387  // Add Point to Keyframe
388  AddPoint(p);
389  }
390 }
391 
392 // Get the fraction that represents how many times this value is repeated in the curve
393 // This is depreciated and will be removed soon.
394 Fraction Keyframe::GetRepeatFraction(int64_t index) const {
395  // Frame numbers (index) outside of the "defined" range of this
396  // keyframe result in a 1/1 default value.
397  if (index < 1 || (index + 1) >= GetLength()) {
398  return Fraction(1,1);
399  }
400  assert(Points.size() > 1); // Due to ! ((index + 1) >= GetLength) there are at least two points!
401 
402  // First, get the value at the given frame and the closest point
403  // to the right.
404  int64_t const current_value = GetLong(index);
405  std::vector<Point>::const_iterator const candidate =
406  std::lower_bound(begin(Points), end(Points), static_cast<double>(index), IsPointBeforeX);
407  assert(candidate != end(Points)); // Due to the (index + 1) >= GetLength check above!
408 
409  // Calculate how many of the next values are going to be the same:
410  int64_t next_repeats = 0;
411  std::vector<Point>::const_iterator i = candidate;
412  // If the index (frame number) is the X coordinate of the closest
413  // point, then look at the segment to the right; the "current"
414  // segement is not interesting because we're already at the last
415  // value of it.
416  if (i->co.X == index) {
417  ++i;
418  }
419  // Skip over "constant" (when rounded) segments.
420  bool all_constant = true;
421  for (; i != end(Points); ++i) {
422  if (current_value != round(i->co.Y)) {
423  all_constant = false;
424  break;
425  }
426  }
427  if (! all_constant) {
428  // Found a point which defines a segment which will give a
429  // different value than the current value. This means we
430  // moved at least one segment to the right, thus we cannot be
431  // at the first point.
432  assert(i != begin(Points));
433  Point const left = *(i - 1);
434  Point const right = *i;
435  int64_t change_at;
436  if (current_value < round(i->co.Y)) {
437  change_at = SearchBetweenPoints(left, right, current_value, std::less_equal<double>{});
438  } else {
439  assert(current_value > round(i->co.Y));
440  change_at = SearchBetweenPoints(left, right, current_value, std::greater_equal<double>{});
441  }
442  next_repeats = change_at - index;
443  } else {
444  // All values to the right are the same!
445  next_repeats = Points.back().co.X - index;
446  }
447 
448  // Now look to the left, to the previous values.
449  all_constant = true;
450  i = candidate;
451  if (i != begin(Points)) {
452  // The binary search below assumes i to be the left point;
453  // candidate is the right point of the current segment
454  // though. So change this if possible. If this branch is NOT
455  // taken, then we're at/before the first point and all is
456  // constant!
457  --i;
458  }
459  int64_t previous_repeats = 0;
460  // Skip over constant (when rounded) segments!
461  for (; i != begin(Points); --i) {
462  if (current_value != round(i->co.Y)) {
463  all_constant = false;
464  break;
465  }
466  }
467  // Special case when skipped until the first point, but the first
468  // point is actually different. Will not happen if index is
469  // before the first point!
470  if (current_value != round(i->co.Y)) {
471  assert(i != candidate);
472  all_constant = false;
473  }
474  if (! all_constant) {
475  // There are at least two points, and we're not at the end,
476  // thus the following is safe!
477  Point const left = *i;
478  Point const right = *(i + 1);
479  int64_t change_at;
480  if (current_value > round(left.co.Y)) {
481  change_at = SearchBetweenPoints(left, right, current_value, std::less<double>{});
482  } else {
483  assert(current_value < round(left.co.Y));
484  change_at = SearchBetweenPoints(left, right, current_value, std::greater<double>{});
485  }
486  previous_repeats = index - change_at;
487  } else {
488  // Every previous value is the same (rounded) as the current
489  // value.
490  previous_repeats = index;
491  }
492  int64_t total_repeats = previous_repeats + next_repeats;
493  return Fraction(previous_repeats, total_repeats);
494 }
495 
496 // Get the change in Y value (from the previous Y value)
497 double Keyframe::GetDelta(int64_t index) const {
498  if (index < 1) return 0;
499  if (index == 1 && ! Points.empty()) return Points[0].co.Y;
500  if (index >= GetLength()) return 0;
501  return GetLong(index) - GetLong(index - 1);
502 }
503 
504 // Get a point at a specific index
505 Point const & Keyframe::GetPoint(int64_t index) const {
506  // Is index a valid point?
507  if (index >= 0 && index < (int64_t)Points.size())
508  return Points[index];
509  else
510  // Invalid index
511  throw OutOfBoundsPoint("Invalid point requested", index, Points.size());
512 }
513 
514 // Get the number of values (i.e. coordinates on the X axis)
515 int64_t Keyframe::GetLength() const {
516  if (Points.empty()) return 0;
517  if (Points.size() == 1) return 1;
518  return round(Points.back().co.X) + 1;
519 }
520 
521 // Get the number of points (i.e. # of points)
522 int64_t Keyframe::GetCount() const {
523 
524  return Points.size();
525 }
526 
527 // Remove a point by matching a coordinate
528 void Keyframe::RemovePoint(Point p) {
529  // loop through points, and find a matching coordinate
530  for (std::vector<Point>::size_type x = 0; x < Points.size(); x++) {
531  // Get each point
532  Point existing_point = Points[x];
533 
534  // find a match
535  if (p.co.X == existing_point.co.X && p.co.Y == existing_point.co.Y) {
536  // Remove the matching point, and break out of loop
537  Points.erase(Points.begin() + x);
538  return;
539  }
540  }
541 
542  // no matching point found
543  throw OutOfBoundsPoint("Invalid point requested", -1, Points.size());
544 }
545 
546 // Remove a point by index
547 void Keyframe::RemovePoint(int64_t index) {
548  // Is index a valid point?
549  if (index >= 0 && index < (int64_t)Points.size())
550  {
551  // Remove a specific point by index
552  Points.erase(Points.begin() + index);
553  }
554  else
555  // Invalid index
556  throw OutOfBoundsPoint("Invalid point requested", index, Points.size());
557 }
558 
559 void Keyframe::UpdatePoint(int64_t index, Point p) {
560  // Remove matching point
561  RemovePoint(index);
562 
563  // Add new point
564  AddPoint(p);
565 }
566 
567 void Keyframe::PrintPoints() const {
568  cout << fixed << setprecision(4);
569  for (std::vector<Point>::const_iterator it = Points.begin(); it != Points.end(); it++) {
570  Point p = *it;
571  cout << p.co.X << "\t" << p.co.Y << endl;
572  }
573 }
574 
575 void Keyframe::PrintValues() const {
576  cout << fixed << setprecision(4);
577  cout << "Frame Number (X)\tValue (Y)\tIs Increasing\tRepeat Numerator\tRepeat Denominator\tDelta (Y Difference)\n";
578 
579  for (int64_t i = 1; i < GetLength(); ++i) {
580  cout << i << "\t" << GetValue(i) << "\t" << IsIncreasing(i) << "\t" ;
581  cout << GetRepeatFraction(i).num << "\t" << GetRepeatFraction(i).den << "\t" << GetDelta(i) << "\n";
582  }
583 }
584 
585 
586 // Scale all points by a percentage (good for evenly lengthening or shortening an openshot::Keyframe)
587 // 1.0 = same size, 1.05 = 5% increase, etc...
588 void Keyframe::ScalePoints(double scale)
589 {
590  // TODO: What if scale is small so that two points land on the
591  // same X coordinate?
592  // TODO: What if scale < 0?
593 
594  // Loop through each point (skipping the 1st point)
595  for (std::vector<Point>::size_type point_index = 1; point_index < Points.size(); point_index++) {
596  // Scale X value
597  Points[point_index].co.X = round(Points[point_index].co.X * scale);
598  }
599 }
600 
601 // Flip all the points in this openshot::Keyframe (useful for reversing an effect or transition, etc...)
602 void Keyframe::FlipPoints() {
603  for (std::vector<Point>::size_type point_index = 0, reverse_index = Points.size() - 1; point_index < reverse_index; point_index++, reverse_index--) {
604  // Flip the points
605  using std::swap;
606  swap(Points[point_index].co.Y, Points[reverse_index].co.Y);
607  // TODO: check that this has the desired effect even with
608  // regards to handles!
609  }
610 }
This class represents a Cartesian coordinate (X, Y) used in the Keyframe animation system...
Definition: Coordinate.h:55
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
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
void SetJsonValue(Json::Value root)
Load Json::JsonValue into this object.
Definition: Point.cpp:164
Constant curves jump from their previous position to a new one (with no interpolation).
Definition: Point.h:49