3 * Copyright (C) 2007,2009 Sebastian Dröge <sebastian.droege@collabora.co.uk>
5 * gstinterpolationcontrolsource.c: Control source that provides several
6 * interpolation methods
8 * This library is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Library General Public
10 * License as published by the Free Software Foundation; either
11 * version 2 of the License, or (at your option) any later version.
13 * This library is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Library General Public License for more details.
18 * You should have received a copy of the GNU Library General Public
19 * License along with this library; if not, write to the
20 * Free Software Foundation, Inc., 51 Franklin St, Fifth Floor,
21 * Boston, MA 02110-1301, USA.
25 * SECTION:gstinterpolationcontrolsource
26 * @title: GstInterpolationControlSource
27 * @short_description: interpolation control source
29 * #GstInterpolationControlSource is a #GstControlSource, that interpolates values between user-given
30 * control points. It supports several interpolation modes and property types.
32 * To use #GstInterpolationControlSource get a new instance by calling
33 * gst_interpolation_control_source_new(), bind it to a #GParamSpec and set some
34 * control points by calling gst_timed_value_control_source_set().
36 * All functions are MT-safe.
40 #include <glib-object.h>
43 #include "gstinterpolationcontrolsource.h"
44 #include "gst/glib-compat-private.h"
45 #include "gst/math-compat.h"
47 #define GST_CAT_DEFAULT controller_debug
48 GST_DEBUG_CATEGORY_STATIC (GST_CAT_DEFAULT);
50 /* helper functions */
52 static inline gboolean
53 _get_nearest_control_points (GstTimedValueControlSource * self,
54 GstClockTime ts, GstControlPoint ** cp1, GstControlPoint ** cp2)
58 iter = gst_timed_value_control_source_find_control_point_iter (self, ts);
60 *cp1 = g_sequence_get (iter);
61 iter = g_sequence_iter_next (iter);
62 if (iter && !g_sequence_iter_is_end (iter)) {
63 *cp2 = g_sequence_get (iter);
73 _get_nearest_control_points2 (GstTimedValueControlSource * self,
74 GstClockTime ts, GstControlPoint ** cp1, GstControlPoint ** cp2,
75 GstClockTime * next_ts)
77 GSequenceIter *iter1, *iter2 = NULL;
80 iter1 = gst_timed_value_control_source_find_control_point_iter (self, ts);
82 *cp1 = g_sequence_get (iter1);
83 iter2 = g_sequence_iter_next (iter1);
85 if (G_LIKELY (self->values)) {
86 /* all values in the control point list come after the given timestamp */
87 iter2 = g_sequence_get_begin_iter (self->values);
88 /* why this? if !cp1 we don't interpolate anyway
89 * if we can eliminate this, we can also use _get_nearest_control_points()
90 * here, is this just to set next_ts? */
97 if (iter2 && !g_sequence_iter_is_end (iter2)) {
98 *cp2 = g_sequence_get (iter2);
99 *next_ts = (*cp2)->timestamp;
101 *next_ts = GST_CLOCK_TIME_NONE;
106 /* steps-like (no-)interpolation, default */
107 /* just returns the value for the most recent key-frame */
108 static inline gdouble
109 _interpolate_none (GstTimedValueControlSource * self, GstControlPoint * cp)
115 interpolate_none_get (GstTimedValueControlSource * self, GstClockTime timestamp,
118 gboolean ret = FALSE;
122 g_mutex_lock (&self->lock);
125 gst_timed_value_control_source_find_control_point_iter (self, timestamp);
127 cp = g_sequence_get (iter);
128 *value = _interpolate_none (self, cp);
131 g_mutex_unlock (&self->lock);
136 interpolate_none_get_value_array (GstTimedValueControlSource * self,
137 GstClockTime timestamp, GstClockTime interval, guint n_values,
140 gboolean ret = FALSE;
142 GstClockTime ts = timestamp;
143 GstClockTime next_ts = 0;
144 GstControlPoint *cp1 = NULL, *cp2 = NULL;
146 g_mutex_lock (&self->lock);
148 for (i = 0; i < n_values; i++) {
149 GST_LOG ("values[%3d] : ts=%" GST_TIME_FORMAT ", next_ts=%" GST_TIME_FORMAT,
150 i, GST_TIME_ARGS (ts), GST_TIME_ARGS (next_ts));
152 _get_nearest_control_points2 (self, ts, &cp1, &cp2, &next_ts);
155 *values = _interpolate_none (self, cp1);
157 GST_LOG ("values[%3d]=%lf", i, *values);
160 GST_LOG ("values[%3d]=-", i);
165 g_mutex_unlock (&self->lock);
171 /* linear interpolation */
172 /* smoothes inbetween values */
173 static inline gdouble
174 _interpolate_linear (GstClockTime timestamp1, gdouble value1,
175 GstClockTime timestamp2, gdouble value2, GstClockTime timestamp)
177 if (GST_CLOCK_TIME_IS_VALID (timestamp2)) {
181 (value2 - value1) / gst_guint64_to_gdouble (timestamp2 - timestamp1);
182 return value1 + (gst_guint64_to_gdouble (timestamp - timestamp1) * slope);
189 interpolate_linear_get (GstTimedValueControlSource * self,
190 GstClockTime timestamp, gdouble * value)
192 gboolean ret = FALSE;
193 GstControlPoint *cp1, *cp2;
195 g_mutex_lock (&self->lock);
197 if (_get_nearest_control_points (self, timestamp, &cp1, &cp2)) {
198 *value = _interpolate_linear (cp1->timestamp, cp1->value,
199 (cp2 ? cp2->timestamp : GST_CLOCK_TIME_NONE),
200 (cp2 ? cp2->value : 0.0), timestamp);
203 g_mutex_unlock (&self->lock);
208 interpolate_linear_get_value_array (GstTimedValueControlSource * self,
209 GstClockTime timestamp, GstClockTime interval, guint n_values,
212 gboolean ret = FALSE;
214 GstClockTime ts = timestamp;
215 GstClockTime next_ts = 0;
216 GstControlPoint *cp1 = NULL, *cp2 = NULL;
218 g_mutex_lock (&self->lock);
220 for (i = 0; i < n_values; i++) {
221 GST_LOG ("values[%3d] : ts=%" GST_TIME_FORMAT ", next_ts=%" GST_TIME_FORMAT,
222 i, GST_TIME_ARGS (ts), GST_TIME_ARGS (next_ts));
224 _get_nearest_control_points2 (self, ts, &cp1, &cp2, &next_ts);
227 *values = _interpolate_linear (cp1->timestamp, cp1->value,
228 (cp2 ? cp2->timestamp : GST_CLOCK_TIME_NONE),
229 (cp2 ? cp2->value : 0.0), ts);
231 GST_LOG ("values[%3d]=%lf", i, *values);
234 GST_LOG ("values[%3d]=-", i);
239 g_mutex_unlock (&self->lock);
245 /* cubic interpolation */
247 /* The following functions implement a natural cubic spline interpolator.
248 * For details look at http://en.wikipedia.org/wiki/Spline_interpolation
250 * Instead of using a real matrix with n^2 elements for the linear system
251 * of equations we use three arrays o, p, q to hold the tridiagonal matrix
252 * as following to save memory:
261 _interpolate_cubic_update_cache (GstTimedValueControlSource * self)
263 gint i, n = self->nvalues;
264 gdouble *o = g_new0 (gdouble, n);
265 gdouble *p = g_new0 (gdouble, n);
266 gdouble *q = g_new0 (gdouble, n);
268 gdouble *h = g_new0 (gdouble, n);
269 gdouble *b = g_new0 (gdouble, n);
270 gdouble *z = g_new0 (gdouble, n);
274 GstClockTime x, x_next;
275 gdouble y_prev, y, y_next;
277 /* Fill linear system of equations */
278 iter = g_sequence_get_begin_iter (self->values);
279 cp = g_sequence_get (iter);
285 iter = g_sequence_iter_next (iter);
286 cp = g_sequence_get (iter);
287 x_next = cp->timestamp;
289 h[0] = gst_guint64_to_gdouble (x_next - x);
291 for (i = 1; i < n - 1; i++) {
292 /* Shuffle x and y values */
296 iter = g_sequence_iter_next (iter);
297 cp = g_sequence_get (iter);
298 x_next = cp->timestamp;
301 h[i] = gst_guint64_to_gdouble (x_next - x);
303 p[i] = 2.0 * (h[i - 1] + h[i]);
305 b[i] = (y_next - y) / h[i] - (y - y_prev) / h[i - 1];
309 /* Use Gauss elimination to set everything below the diagonal to zero */
310 for (i = 1; i < n - 1; i++) {
311 gdouble a = o[i] / p[i - 1];
312 p[i] -= a * q[i - 1];
313 b[i] -= a * b[i - 1];
316 /* Solve everything else from bottom to top */
317 for (i = n - 2; i > 0; i--)
318 z[i] = (b[i] - q[i] * z[i + 1]) / p[i];
320 /* Save cache next in the GstControlPoint */
322 iter = g_sequence_get_begin_iter (self->values);
323 for (i = 0; i < n; i++) {
324 cp = g_sequence_get (iter);
325 cp->cache.cubic.h = h[i];
326 cp->cache.cubic.z = z[i];
327 iter = g_sequence_iter_next (iter);
330 /* Free our temporary arrays */
339 static inline gdouble
340 _interpolate_cubic (GstTimedValueControlSource * self, GstControlPoint * cp1,
341 gdouble value1, GstControlPoint * cp2, gdouble value2,
342 GstClockTime timestamp)
344 if (!self->valid_cache) {
345 _interpolate_cubic_update_cache (self);
346 self->valid_cache = TRUE;
350 gdouble diff1, diff2;
353 diff1 = gst_guint64_to_gdouble (timestamp - cp1->timestamp);
354 diff2 = gst_guint64_to_gdouble (cp2->timestamp - timestamp);
357 (cp2->cache.cubic.z * diff1 * diff1 * diff1 +
358 cp1->cache.cubic.z * diff2 * diff2 * diff2) / cp1->cache.cubic.h;
360 (value2 / cp1->cache.cubic.h -
361 cp1->cache.cubic.h * cp2->cache.cubic.z) * diff1;
363 (value1 / cp1->cache.cubic.h -
364 cp1->cache.cubic.h * cp1->cache.cubic.z) * diff2;
372 interpolate_cubic_get (GstTimedValueControlSource * self,
373 GstClockTime timestamp, gdouble * value)
375 gboolean ret = FALSE;
376 GstControlPoint *cp1, *cp2 = NULL;
378 if (self->nvalues <= 2)
379 return interpolate_linear_get (self, timestamp, value);
381 g_mutex_lock (&self->lock);
383 if (_get_nearest_control_points (self, timestamp, &cp1, &cp2)) {
384 *value = _interpolate_cubic (self, cp1, cp1->value, cp2,
385 (cp2 ? cp2->value : 0.0), timestamp);
388 g_mutex_unlock (&self->lock);
393 interpolate_cubic_get_value_array (GstTimedValueControlSource * self,
394 GstClockTime timestamp, GstClockTime interval, guint n_values,
397 gboolean ret = FALSE;
399 GstClockTime ts = timestamp;
400 GstClockTime next_ts = 0;
401 GstControlPoint *cp1 = NULL, *cp2 = NULL;
403 if (self->nvalues <= 2)
404 return interpolate_linear_get_value_array (self, timestamp, interval,
407 g_mutex_lock (&self->lock);
409 for (i = 0; i < n_values; i++) {
410 GST_LOG ("values[%3d] : ts=%" GST_TIME_FORMAT ", next_ts=%" GST_TIME_FORMAT,
411 i, GST_TIME_ARGS (ts), GST_TIME_ARGS (next_ts));
413 _get_nearest_control_points2 (self, ts, &cp1, &cp2, &next_ts);
416 *values = _interpolate_cubic (self, cp1, cp1->value, cp2,
417 (cp2 ? cp2->value : 0.0), ts);
419 GST_LOG ("values[%3d]=%lf", i, *values);
422 GST_LOG ("values[%3d]=-", i);
427 g_mutex_unlock (&self->lock);
432 /* monotonic cubic interpolation */
434 /* the following functions implement monotonic cubic spline interpolation.
435 * For details: http://en.wikipedia.org/wiki/Monotone_cubic_interpolation
437 * In contrast to the previous cubic mode, the values won't overshoot.
441 _interpolate_cubic_monotonic_update_cache (GstTimedValueControlSource * self)
443 gint i, n = self->nvalues;
444 gdouble *dxs = g_new0 (gdouble, n);
445 gdouble *dys = g_new0 (gdouble, n);
446 gdouble *ms = g_new0 (gdouble, n);
447 gdouble *c1s = g_new0 (gdouble, n);
451 GstClockTime x, x_next, dx;
452 gdouble y, y_next, dy;
454 /* Get consecutive differences and slopes */
455 iter = g_sequence_get_begin_iter (self->values);
456 cp = g_sequence_get (iter);
457 x_next = cp->timestamp;
459 for (i = 0; i < n - 1; i++) {
462 iter = g_sequence_iter_next (iter);
463 cp = g_sequence_get (iter);
464 x_next = cp->timestamp;
467 dx = gst_guint64_to_gdouble (x_next - x);
474 /* Get degree-1 coefficients */
476 for (i = 1; i < n; i++) {
477 gdouble m = ms[i - 1];
478 gdouble m_next = ms[i];
480 if (m * m_next <= 0) {
483 gdouble dx_next, dx_sum;
485 dx = dxs[i], dx_next = dxs[i + 1], dx_sum = dx + dx_next;
486 c1s[i] = 3.0 * dx_sum / ((dx_sum + dx_next) / m + (dx_sum + dx) / m_next);
489 c1s[n - 1] = ms[n - 1];
491 /* Get degree-2 and degree-3 coefficients */
492 iter = g_sequence_get_begin_iter (self->values);
493 for (i = 0; i < n - 1; i++) {
494 gdouble c1, m, inv_dx, common;
495 cp = g_sequence_get (iter);
499 inv_dx = 1.0 / dxs[i];
500 common = c1 + c1s[i + 1] - m - m;
502 cp->cache.cubic_monotonic.c1s = c1;
503 cp->cache.cubic_monotonic.c2s = (m - c1 - common) * inv_dx;
504 cp->cache.cubic_monotonic.c3s = common * inv_dx * inv_dx;
506 iter = g_sequence_iter_next (iter);
509 /* Free our temporary arrays */
516 static inline gdouble
517 _interpolate_cubic_monotonic (GstTimedValueControlSource * self,
518 GstControlPoint * cp1, gdouble value1, GstControlPoint * cp2,
519 gdouble value2, GstClockTime timestamp)
521 if (!self->valid_cache) {
522 _interpolate_cubic_monotonic_update_cache (self);
523 self->valid_cache = TRUE;
527 gdouble diff = gst_guint64_to_gdouble (timestamp - cp1->timestamp);
528 gdouble diff2 = diff * diff;
531 out = value1 + cp1->cache.cubic_monotonic.c1s * diff;
532 out += cp1->cache.cubic_monotonic.c2s * diff2;
533 out += cp1->cache.cubic_monotonic.c3s * diff * diff2;
541 interpolate_cubic_monotonic_get (GstTimedValueControlSource * self,
542 GstClockTime timestamp, gdouble * value)
544 gboolean ret = FALSE;
545 GstControlPoint *cp1, *cp2 = NULL;
547 if (self->nvalues <= 2)
548 return interpolate_linear_get (self, timestamp, value);
550 g_mutex_lock (&self->lock);
552 if (_get_nearest_control_points (self, timestamp, &cp1, &cp2)) {
553 *value = _interpolate_cubic_monotonic (self, cp1, cp1->value, cp2,
554 (cp2 ? cp2->value : 0.0), timestamp);
557 g_mutex_unlock (&self->lock);
562 interpolate_cubic_monotonic_get_value_array (GstTimedValueControlSource * self,
563 GstClockTime timestamp, GstClockTime interval, guint n_values,
566 gboolean ret = FALSE;
568 GstClockTime ts = timestamp;
569 GstClockTime next_ts = 0;
570 GstControlPoint *cp1 = NULL, *cp2 = NULL;
572 if (self->nvalues <= 2)
573 return interpolate_linear_get_value_array (self, timestamp, interval,
576 g_mutex_lock (&self->lock);
578 for (i = 0; i < n_values; i++) {
579 GST_LOG ("values[%3d] : ts=%" GST_TIME_FORMAT ", next_ts=%" GST_TIME_FORMAT,
580 i, GST_TIME_ARGS (ts), GST_TIME_ARGS (next_ts));
582 _get_nearest_control_points2 (self, ts, &cp1, &cp2, &next_ts);
585 *values = _interpolate_cubic_monotonic (self, cp1, cp1->value, cp2,
586 (cp2 ? cp2->value : 0.0), ts);
588 GST_LOG ("values[%3d]=%lf", i, *values);
591 GST_LOG ("values[%3d]=-", i);
596 g_mutex_unlock (&self->lock);
603 GstControlSourceGetValue get;
604 GstControlSourceGetValueArray get_value_array;
605 } interpolation_modes[] = {
607 (GstControlSourceGetValue) interpolate_none_get,
608 (GstControlSourceGetValueArray) interpolate_none_get_value_array}, {
609 (GstControlSourceGetValue) interpolate_linear_get,
610 (GstControlSourceGetValueArray) interpolate_linear_get_value_array}, {
611 (GstControlSourceGetValue) interpolate_cubic_get,
612 (GstControlSourceGetValueArray) interpolate_cubic_get_value_array}, {
613 (GstControlSourceGetValue) interpolate_cubic_monotonic_get,
614 (GstControlSourceGetValueArray)
615 interpolate_cubic_monotonic_get_value_array}};
617 static const guint num_interpolation_modes = G_N_ELEMENTS (interpolation_modes);
625 gst_interpolation_mode_get_type (void)
627 static gsize gtype = 0;
628 static const GEnumValue values[] = {
629 {GST_INTERPOLATION_MODE_NONE, "GST_INTERPOLATION_MODE_NONE", "none"},
630 {GST_INTERPOLATION_MODE_LINEAR, "GST_INTERPOLATION_MODE_LINEAR", "linear"},
631 {GST_INTERPOLATION_MODE_CUBIC, "GST_INTERPOLATION_MODE_CUBIC", "cubic"},
632 {GST_INTERPOLATION_MODE_CUBIC_MONOTONIC,
633 "GST_INTERPOLATION_MODE_CUBIC_MONOTONIC", "cubic-monotonic"},
637 if (g_once_init_enter (>ype)) {
638 GType tmp = g_enum_register_static ("GstInterpolationMode", values);
639 g_once_init_leave (>ype, tmp);
642 return (GType) gtype;
647 GST_DEBUG_CATEGORY_INIT (GST_CAT_DEFAULT, "interpolation control source", 0, \
648 "timeline value interpolating control source")
650 G_DEFINE_TYPE_WITH_CODE (GstInterpolationControlSource,
651 gst_interpolation_control_source, GST_TYPE_TIMED_VALUE_CONTROL_SOURCE,
654 struct _GstInterpolationControlSourcePrivate
656 GstInterpolationMode interpolation_mode;
660 * gst_interpolation_control_source_new:
662 * This returns a new, unbound #GstInterpolationControlSource.
664 * Returns: (transfer full): a new, unbound #GstInterpolationControlSource.
667 gst_interpolation_control_source_new (void)
669 return g_object_new (GST_TYPE_INTERPOLATION_CONTROL_SOURCE, NULL);
673 gst_interpolation_control_source_set_interpolation_mode
674 (GstInterpolationControlSource * self, GstInterpolationMode mode)
676 GstControlSource *csource = GST_CONTROL_SOURCE (self);
678 if (mode >= num_interpolation_modes || (int) mode < 0) {
679 GST_WARNING ("interpolation mode %d invalid or not implemented yet", mode);
683 GST_TIMED_VALUE_CONTROL_SOURCE_LOCK (self);
684 csource->get_value = interpolation_modes[mode].get;
685 csource->get_value_array = interpolation_modes[mode].get_value_array;
687 gst_timed_value_control_invalidate_cache ((GstTimedValueControlSource *)
689 self->priv->interpolation_mode = mode;
691 GST_TIMED_VALUE_CONTROL_SOURCE_UNLOCK (self);
697 gst_interpolation_control_source_init (GstInterpolationControlSource * self)
700 G_TYPE_INSTANCE_GET_PRIVATE (self, GST_TYPE_INTERPOLATION_CONTROL_SOURCE,
701 GstInterpolationControlSourcePrivate);
702 gst_interpolation_control_source_set_interpolation_mode (self,
703 GST_INTERPOLATION_MODE_NONE);
707 gst_interpolation_control_source_set_property (GObject * object, guint prop_id,
708 const GValue * value, GParamSpec * pspec)
710 GstInterpolationControlSource *self =
711 GST_INTERPOLATION_CONTROL_SOURCE (object);
715 gst_interpolation_control_source_set_interpolation_mode (self,
716 (GstInterpolationMode) g_value_get_enum (value));
719 G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
725 gst_interpolation_control_source_get_property (GObject * object, guint prop_id,
726 GValue * value, GParamSpec * pspec)
728 GstInterpolationControlSource *self =
729 GST_INTERPOLATION_CONTROL_SOURCE (object);
733 g_value_set_enum (value, self->priv->interpolation_mode);
736 G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
742 gst_interpolation_control_source_class_init (GstInterpolationControlSourceClass
745 GObjectClass *gobject_class = G_OBJECT_CLASS (klass);
746 //GstControlSourceClass *csource_class = GST_CONTROL_SOURCE_CLASS (klass);
748 g_type_class_add_private (klass,
749 sizeof (GstInterpolationControlSourcePrivate));
751 gobject_class->set_property = gst_interpolation_control_source_set_property;
752 gobject_class->get_property = gst_interpolation_control_source_get_property;
754 g_object_class_install_property (gobject_class, PROP_MODE,
755 g_param_spec_enum ("mode", "Mode", "Interpolation mode",
756 GST_TYPE_INTERPOLATION_MODE, GST_INTERPOLATION_MODE_NONE,
757 G_PARAM_READWRITE | G_PARAM_STATIC_STRINGS));