Loading...
Searching...
No Matches
KeyFrame.cpp
Go to the documentation of this file.
// Copyright (c) 2008-2019 OpenShot Studios, LLC
//
// SPDX-License-Identifier: LGPL-3.0-or-later
#include "KeyFrame.h"
#include "Exceptions.h"
#include <algorithm> // For std::lower_bound, std::move_backward
#include <functional> // For std::less, std::less_equal, etc…
#include <utility> // For std::swap
#include <numeric> // For std::accumulate
#include <cassert> // For assert()
#include <cmath> // For fabs, round
#include <iostream> // For std::cout
#include <iomanip> // For std::setprecision
using namespace std;
using namespace openshot;
namespace openshot{
// Check if the X coordinate of a given Point is lower than a given value
bool IsPointBeforeX(Point const & p, double const x) {
return p.co.X < x;
}
// Linear interpolation between two points
double InterpolateLinearCurve(Point const & left, Point const & right, double const target) {
double const diff_Y = right.co.Y - left.co.Y;
double const diff_X = right.co.X - left.co.X;
double const slope = diff_Y / diff_X;
return left.co.Y + slope * (target - left.co.X);
}
// Bezier interpolation between two points
double InterpolateBezierCurve(Point const & left, Point const & right, double const target, double const allowed_error) {
double const X_diff = right.co.X - left.co.X;
double const Y_diff = right.co.Y - left.co.Y;
Coordinate const p0 = left.co;
Coordinate const p1 = Coordinate(p0.X + left.handle_right.X * X_diff, p0.Y + left.handle_right.Y * Y_diff);
Coordinate const p2 = Coordinate(p0.X + right.handle_left.X * X_diff, p0.Y + right.handle_left.Y * Y_diff);
Coordinate const p3 = right.co;
double t = 0.5;
double t_step = 0.25;
do {
// Bernstein polynoms
double B[4] = {1, 3, 3, 1};
double oneMinTExp = 1;
double tExp = 1;
for (int i = 0; i < 4; ++i, tExp *= t) {
B[i] *= tExp;
}
for (int i = 0; i < 4; ++i, oneMinTExp *= 1 - t) {
B[4 - i - 1] *= oneMinTExp;
}
double const x = p0.X * B[0] + p1.X * B[1] + p2.X * B[2] + p3.X * B[3];
double const y = p0.Y * B[0] + p1.Y * B[1] + p2.Y * B[2] + p3.Y * B[3];
if (fabs(target - x) < allowed_error) {
return y;
}
if (x > target) {
t -= t_step;
}
else {
t += t_step;
}
t_step /= 2;
} while (true);
}
// Interpolate two points using the right Point's interpolation method
double InterpolateBetween(Point const & left, Point const & right, double target, double allowed_error) {
// check if target is outside of the extremities poits
// This can occur when moving fast the play head
if(left.co.X > target){
return left.co.Y;
}
if(target > right.co.X){
return right.co.Y;
}
switch (right.interpolation) {
case CONSTANT: return left.co.Y;
case LINEAR: return InterpolateLinearCurve(left, right, target);
case BEZIER: return InterpolateBezierCurve(left, right, target, allowed_error);
default: return InterpolateLinearCurve(left, right, target);
}
}
}
template<typename Check>
int64_t SearchBetweenPoints(Point const & left, Point const & right, int64_t const current, Check check) {
int64_t start = left.co.X;
int64_t stop = right.co.X;
while (start < stop) {
int64_t const mid = (start + stop + 1) / 2;
double const value = InterpolateBetween(left, right, mid, 0.01);
if (check(round(value), current)) {
start = mid;
} else {
stop = mid - 1;
}
}
return start;
}
// Constructor which sets the default point & coordinate at X=1
Keyframe::Keyframe(double value) {
// Add initial point
AddPoint(Point(1, value));
}
// Constructor which takes a vector of Points
Keyframe::Keyframe(const std::vector<openshot::Point>& points) : Points(points) {};
// Destructor
Keyframe::~Keyframe() {
Points.clear();
Points.shrink_to_fit();
}
// Add a new point on the key-frame. Each point has a primary coordinate,
// a left handle, and a right handle.
void Keyframe::AddPoint(Point p) {
// candidate is not less (greater or equal) than the new point in
// the X coordinate.
std::vector<Point>::iterator candidate =
std::lower_bound(begin(Points), end(Points), p.co.X, IsPointBeforeX);
if (candidate == end(Points)) {
// New point X is greater than all other points' X, add to
// back.
Points.push_back(p);
} else if ((*candidate).co.X == p.co.X) {
// New point is at same X coordinate as some point, overwrite
// point.
*candidate = p;
} else {
// New point needs to be inserted before candidate; thus move
// candidate and all following one to the right and insert new
// point then where candidate was.
size_t const candidate_index = candidate - begin(Points);
Points.push_back(p); // Make space; could also be a dummy point. INVALIDATES candidate!
std::move_backward(begin(Points) + candidate_index, end(Points) - 1, end(Points));
Points[candidate_index] = p;
}
}
// Add a new point on the key-frame, interpolate is optional (default: BEZIER)
void Keyframe::AddPoint(double x, double y, InterpolationType interpolate)
{
// Create a point
Point new_point(x, y, interpolate);
// Add the point
AddPoint(new_point);
}
// Get the index of a point by matching a coordinate
int64_t Keyframe::FindIndex(Point p) const {
// loop through points, and find a matching coordinate
for (std::vector<Point>::size_type x = 0; x < Points.size(); x++) {
// Get each point
Point existing_point = Points[x];
// find a match
if (p.co.X == existing_point.co.X && p.co.Y == existing_point.co.Y) {
// Remove the matching point, and break out of loop
return x;
}
}
// no matching point found
throw OutOfBoundsPoint("Invalid point requested", -1, Points.size());
}
// Determine if point already exists
bool Keyframe::Contains(Point p) const {
std::vector<Point>::const_iterator i =
std::lower_bound(begin(Points), end(Points), p.co.X, IsPointBeforeX);
return i != end(Points) && i->co.X == p.co.X;
}
// Get current point (or closest point) from the X coordinate (i.e. the frame number)
Point Keyframe::GetClosestPoint(Point p, bool useLeft) const {
if (Points.size() == 0) {
return Point(-1, -1);
}
// Finds a point with an X coordinate which is "not less" (greater
// or equal) than the queried X coordinate.
std::vector<Point>::const_iterator candidate =
std::lower_bound(begin(Points), end(Points), p.co.X, IsPointBeforeX);
if (candidate == end(Points)) {
// All points are before the queried point.
//
// Note: Behavior the same regardless of useLeft!
return Points.back();
}
if (candidate == begin(Points)) {
// First point is greater or equal to the queried point.
//
// Note: Behavior the same regardless of useLeft!
return Points.front();
}
if (useLeft) {
return *(candidate - 1);
} else {
return *candidate;
}
}
// Get current point (or closest point to the right) from the X coordinate (i.e. the frame number)
Point Keyframe::GetClosestPoint(Point p) const {
return GetClosestPoint(p, false);
}
// Get previous point (if any)
Point Keyframe::GetPreviousPoint(Point p) const {
// Lookup the index of this point
try {
int64_t index = FindIndex(p);
// If not the 1st point
if (index > 0)
return Points[index - 1];
else
return Points[0];
} catch (const OutOfBoundsPoint& e) {
// No previous point
return Point(-1, -1);
}
}
// Get max point (by Y coordinate)
Point Keyframe::GetMaxPoint() const {
Point maxPoint(-1, -1);
for (Point const & existing_point: Points) {
if (existing_point.co.Y >= maxPoint.co.Y) {
maxPoint = existing_point;
}
}
return maxPoint;
}
// Get the value at a specific index
double Keyframe::GetValue(int64_t index) const {
if (Points.empty()) {
return 0;
}
std::vector<Point>::const_iterator candidate =
std::lower_bound(begin(Points), end(Points), static_cast<double>(index), IsPointBeforeX);
if (candidate == end(Points)) {
// index is behind last point
return Points.back().co.Y;
}
if (candidate == begin(Points)) {
// index is at or before first point
return Points.front().co.Y;
}
if (candidate->co.X == index) {
// index is directly on a point
return candidate->co.Y;
}
std::vector<Point>::const_iterator predecessor = candidate - 1;
return InterpolateBetween(*predecessor, *candidate, index, 0.01);
}
// Get the rounded INT value at a specific index
int Keyframe::GetInt(int64_t index) const {
return int(round(GetValue(index)));
}
// Get the rounded INT value at a specific index
int64_t Keyframe::GetLong(int64_t index) const {
return long(round(GetValue(index)));
}
// Get the direction of the curve at a specific index (increasing or decreasing)
bool Keyframe::IsIncreasing(int index) const
{
if (index <= 1) {
// Determine direction of frame 1 (and assume previous frames have same direction)
index = 1;
} else if (index >= GetLength()) {
// Determine direction of last valid frame # (and assume next frames have same direction)
index = GetLength() - 1;
}
// Get current index value
const double current_value = GetValue(index);
// Iterate from current index to next significant value change
int attempts = 1;
while (attempts < 600 && index + attempts <= GetLength()) {
// Get next value
const double next_value = GetValue(index + attempts);
// Is value significantly different
const double diff = next_value - current_value;
if (fabs(diff) > 0.0001) {
if (diff < 0.0) {
// Decreasing value found next
return false;
} else {
// Increasing value found next
return true;
}
}
// increment attempt
attempts++;
}
// If no next value found, assume increasing values
return true;
}
// Generate JSON string of this object
std::string Keyframe::Json() const {
// Return formatted string
return JsonValue().toStyledString();
}
// Generate Json::Value for this object
Json::Value Keyframe::JsonValue() const {
// Create root json object
Json::Value root;
root["Points"] = Json::Value(Json::arrayValue);
// loop through points
for (const auto existing_point : Points) {
root["Points"].append(existing_point.JsonValue());
}
// return JsonValue
return root;
}
// Load JSON string into this object
void Keyframe::SetJson(const std::string value) {
// Parse JSON string into JSON objects
try
{
const Json::Value root = openshot::stringToJson(value);
// Set all values that match
SetJsonValue(root);
}
catch (const std::exception& e)
{
// Error parsing JSON (or missing keys)
throw InvalidJSON("JSON is invalid (missing keys or invalid data types)");
}
}
// Load Json::Value into this object
void Keyframe::SetJsonValue(const Json::Value root) {
// Clear existing points
Points.clear();
Points.shrink_to_fit();
if (!root["Points"].isNull())
// loop through points
for (const auto existing_point : root["Points"]) {
// Create Point
Point p;
// Load Json into Point
p.SetJsonValue(existing_point);
// Add Point to Keyframe
AddPoint(p);
}
}
// Get the change in Y value (from the previous Y value)
double Keyframe::GetDelta(int64_t index) const {
if (index < 1) return 0.0;
if (index == 1 && !Points.empty()) return Points[0].co.Y;
if (index >= GetLength()) return 0.0;
return GetValue(index) - GetValue(index - 1);
}
// Get a point at a specific index
Point const & Keyframe::GetPoint(int64_t index) const {
// Is index a valid point?
if (index >= 0 && index < (int64_t)Points.size())
return Points[index];
else
// Invalid index
throw OutOfBoundsPoint("Invalid point requested", index, Points.size());
}
// Get the number of values (i.e. coordinates on the X axis)
int64_t Keyframe::GetLength() const {
if (Points.empty()) return 0;
if (Points.size() == 1) return 1;
return round(Points.back().co.X);
}
// Get the number of points (i.e. # of points)
int64_t Keyframe::GetCount() const {
return Points.size();
}
// Remove a point by matching a coordinate
void Keyframe::RemovePoint(Point p) {
// loop through points, and find a matching coordinate
for (std::vector<Point>::size_type x = 0; x < Points.size(); x++) {
// Get each point
Point existing_point = Points[x];
// find a match
if (p.co.X == existing_point.co.X && p.co.Y == existing_point.co.Y) {
// Remove the matching point, and break out of loop
Points.erase(Points.begin() + x);
return;
}
}
// no matching point found
throw OutOfBoundsPoint("Invalid point requested", -1, Points.size());
}
// Remove a point by index
void Keyframe::RemovePoint(int64_t index) {
// Is index a valid point?
if (index >= 0 && index < (int64_t)Points.size())
{
// Remove a specific point by index
Points.erase(Points.begin() + index);
}
else
// Invalid index
throw OutOfBoundsPoint("Invalid point requested", index, Points.size());
}
// Replace an existing point with a new point
void Keyframe::UpdatePoint(int64_t index, Point p) {
// Remove matching point
RemovePoint(index);
// Add new point
AddPoint(p);
}
void Keyframe::PrintPoints(std::ostream* out) const {
*out << std::right << std::setprecision(4) << std::setfill(' ');
for (const auto& p : Points) {
*out << std::defaultfloat
<< std::setw(6) << p.co.X
<< std::setw(14) << std::fixed << p.co.Y
<< '\n';
}
*out << std::flush;
}
void Keyframe::PrintValues(std::ostream* out) const {
// Column widths
std::vector<int> w{10, 12, 8, 11, 19};
*out << std::right << std::setfill(' ') << std::setprecision(4);
// Headings
*out << "│"
<< std::setw(w[0]) << "Frame# (X)" << " │"
<< std::setw(w[1]) << "Y Value" << " │"
<< std::setw(w[2]) << "Delta Y" << " │ "
<< std::setw(w[3]) << "Increasing?" << std::right
<< "│\n";
// Divider
*out << "├───────────"
<< "┼─────────────"
<< "┼─────────"
<< "┼────────────┤\n";
for (int64_t i = 1; i <= GetLength(); ++i) {
*out << "│"
<< std::setw(w[0]-2) << std::defaultfloat << i
<< (Contains(Point(i, 1)) ? " *" : " ") << " │"
<< std::setw(w[1]) << std::fixed << GetValue(i) << " │"
<< std::setw(w[2]) << std::defaultfloat << std::showpos
<< GetDelta(i) << " │ " << std::noshowpos
<< std::setw(w[3])
<< (IsIncreasing(i) ? "true" : "false") << std::right << "│\n";
}
*out << " * = Keyframe point (non-interpolated)\n";
*out << std::flush;
}
// Scale all points by a percentage (good for evenly lengthening or shortening an openshot::Keyframe)
// 1.0 = same size, 1.05 = 5% increase, etc...
void Keyframe::ScalePoints(double scale)
{
// TODO: What if scale is small so that two points land on the
// same X coordinate?
// TODO: What if scale < 0?
// Loop through each point (skipping the 1st point)
for (std::vector<Point>::size_type point_index = 1; point_index < Points.size(); point_index++) {
// Scale X value
Points[point_index].co.X = round(Points[point_index].co.X * scale);
}
}
// Flip all the points in this openshot::Keyframe (useful for reversing an effect or transition, etc...)
void Keyframe::FlipPoints() {
for (std::vector<Point>::size_type point_index = 0, reverse_index = Points.size() - 1; point_index < reverse_index; point_index++, reverse_index--) {
// Flip the points
using std::swap;
swap(Points[point_index].co.Y, Points[reverse_index].co.Y);
// TODO: check that this has the desired effect even with
// regards to handles!
}
}
Exceptions.h
Header file for all Exception classes.
SearchBetweenPoints
int64_t SearchBetweenPoints(Point const &left, Point const &right, int64_t const current, Check check)
Definition KeyFrame.cpp:99
KeyFrame.h
Header file for the Keyframe class.
openshot::Coordinate
A Cartesian coordinate (X, Y) used in the Keyframe animation system.
Definition Coordinate.h:38
openshot::Coordinate::X
double X
The X value of the coordinate (usually representing the frame #)
Definition Coordinate.h:40
openshot::Coordinate::Y
double Y
The Y value of the coordinate (usually representing the value of the property being animated)
Definition Coordinate.h:41
openshot::InvalidJSON
Exception for invalid JSON.
Definition Exceptions.h:218
openshot::Keyframe::FindIndex
int64_t FindIndex(Point p) const
Get the index of a point by matching a coordinate.
Definition KeyFrame.cpp:166
openshot::Keyframe::RemovePoint
void RemovePoint(Point p)
Remove a point by matching a coordinate.
Definition KeyFrame.cpp:423
openshot::Keyframe::SetJson
void SetJson(const std::string value)
Load JSON string into this object.
Definition KeyFrame.cpp:355
openshot::Keyframe::Contains
bool Contains(Point p) const
Does this keyframe contain a specific point.
Definition KeyFrame.cpp:184
openshot::Keyframe::~Keyframe
~Keyframe()
Destructor.
Definition KeyFrame.cpp:124
openshot::Keyframe::PrintValues
void PrintValues(std::ostream *out=&std::cout) const
Print just the Y value of the point's primary coordinate.
Definition KeyFrame.cpp:474
openshot::Keyframe::GetMaxPoint
Point GetMaxPoint() const
Get max point (by Y coordinate)
Definition KeyFrame.cpp:245
openshot::Keyframe::GetInt
int GetInt(int64_t index) const
Get the rounded INT value at a specific index.
Definition KeyFrame.cpp:282
openshot::Keyframe::SetJsonValue
void SetJsonValue(const Json::Value root)
Load Json::Value into this object.
Definition KeyFrame.cpp:372
openshot::Keyframe::AddPoint
void AddPoint(Point p)
Add a new point on the key-frame. Each point has a primary coordinate, a left handle,...
Definition KeyFrame.cpp:131
openshot::Keyframe::GetDelta
double GetDelta(int64_t index) const
Get the change in Y value (from the previous Y value)
Definition KeyFrame.cpp:392
openshot::Keyframe::GetPoint
Point const & GetPoint(int64_t index) const
Get a point at a specific index.
Definition KeyFrame.cpp:400
openshot::Keyframe::GetLength
int64_t GetLength() const
Definition KeyFrame.cpp:410
openshot::Keyframe::PrintPoints
void PrintPoints(std::ostream *out=&std::cout) const
Print a list of points.
Definition KeyFrame.cpp:463
openshot::Keyframe::GetPreviousPoint
Point GetPreviousPoint(Point p) const
Get previous point (.
Definition KeyFrame.cpp:226
openshot::Keyframe::GetLong
int64_t GetLong(int64_t index) const
Get the rounded LONG value at a specific index.
Definition KeyFrame.cpp:287
openshot::Keyframe::UpdatePoint
void UpdatePoint(int64_t index, Point p)
Replace an existing point with a new point.
Definition KeyFrame.cpp:455
openshot::Keyframe::ScalePoints
void ScalePoints(double scale)
Definition KeyFrame.cpp:509
openshot::Keyframe::Json
std::string Json() const
Generate JSON string of this object.
Definition KeyFrame.cpp:332
openshot::Keyframe::GetValue
double GetValue(int64_t index) const
Get the value at a specific index.
Definition KeyFrame.cpp:258
openshot::Keyframe::JsonValue
Json::Value JsonValue() const
Generate Json::Value for this object.
Definition KeyFrame.cpp:339
openshot::Keyframe::FlipPoints
void FlipPoints()
Flip all the points in this openshot::Keyframe (useful for reversing an effect or transition,...
Definition KeyFrame.cpp:523
openshot::Keyframe::Keyframe
Keyframe()=default
Default constructor for the Keyframe class.
openshot::Keyframe::IsIncreasing
bool IsIncreasing(int index) const
Get the direction of the curve at a specific index (increasing or decreasing)
Definition KeyFrame.cpp:292
openshot::Keyframe::GetCount
int64_t GetCount() const
Get the number of points (i.e. # of points)
Definition KeyFrame.cpp:417
openshot::Keyframe::GetClosestPoint
Point GetClosestPoint(Point p) const
Get current point (or closest point to the right) from the X coordinate (i.e. the frame number)
Definition KeyFrame.cpp:221
openshot::OutOfBoundsPoint
Exception for an out of bounds key-frame point.
Definition Exceptions.h:325
openshot::Point
A Point is the basic building block of a key-frame curve.
Definition Point.h:64
openshot::Point::handle_left
Coordinate handle_left
This is the left handle coordinate (in percentages from 0 to 1)
Definition Point.h:67
openshot::Point::co
Coordinate co
This is the primary coordinate.
Definition Point.h:66
openshot::Point::interpolation
InterpolationType interpolation
This is the interpolation mode.
Definition Point.h:69
openshot::Point::handle_right
Coordinate handle_right
This is the right handle coordinate (in percentages from 0 to 1)
Definition Point.h:68
openshot::Point::SetJsonValue
void SetJsonValue(const Json::Value root)
Load Json::Value into this object.
Definition Point.cpp:104
openshot
This namespace is the default namespace for all code in the openshot library.
Definition Compressor.h:29
openshot::InterpolateLinearCurve
double InterpolateLinearCurve(Point const &left, Point const &right, double const target)
Linear interpolation between two points.
Definition KeyFrame.cpp:36
openshot::InterpolateBezierCurve
double InterpolateBezierCurve(Point const &left, Point const &right, double const target, double const allowed_error)
Bezier interpolation between two points.
Definition KeyFrame.cpp:44
openshot::IsPointBeforeX
bool IsPointBeforeX(Point const &p, double const x)
Check if the X coordinate of a given Point is lower than a given value.
Definition KeyFrame.cpp:31
openshot::InterpolateBetween
double InterpolateBetween(Point const &left, Point const &right, double target, double allowed_error)
Interpolate two points using the right Point's interpolation method.
Definition KeyFrame.cpp:80
openshot::stringToJson
const Json::Value stringToJson(const std::string value)
Definition Json.cpp:16
openshot::InterpolationType
InterpolationType
This controls how a Keyframe uses this point to interpolate between two points.
Definition Point.h:28
openshot::CONSTANT
@ CONSTANT
Constant curves jump from their previous position to a new one (with no interpolation).
Definition Point.h:31
openshot::BEZIER
@ BEZIER
Bezier curves are quadratic curves, which create a smooth curve.
Definition Point.h:29
openshot::LINEAR
@ LINEAR
Linear curves are angular, straight lines between two points.
Definition Point.h:30