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 * @short_description: interpolation control source
28 * #GstInterpolationControlSource is a #GstControlSource, that interpolates values between user-given
29 * control points. It supports several interpolation modes and property types.
31 * To use #GstInterpolationControlSource get a new instance by calling
32 * gst_interpolation_control_source_new(), bind it to a #GParamSpec and set some
33 * control points by calling gst_timed_value_control_source_set().
35 * All functions are MT-safe.
39 #include <glib-object.h>
42 #include "gstinterpolationcontrolsource.h"
43 #include "gst/glib-compat-private.h"
44 #include "gst/math-compat.h"
46 #define GST_CAT_DEFAULT controller_debug
47 GST_DEBUG_CATEGORY_STATIC (GST_CAT_DEFAULT);
49 /* helper functions */
51 static inline gboolean
52 _get_nearest_control_points (GstTimedValueControlSource * self,
53 GstClockTime ts, GstControlPoint ** cp1, GstControlPoint ** cp2)
57 iter = gst_timed_value_control_source_find_control_point_iter (self, ts);
59 *cp1 = g_sequence_get (iter);
60 iter = g_sequence_iter_next (iter);
61 if (iter && !g_sequence_iter_is_end (iter)) {
62 *cp2 = g_sequence_get (iter);
72 _get_nearest_control_points2 (GstTimedValueControlSource * self,
73 GstClockTime ts, GstControlPoint ** cp1, GstControlPoint ** cp2,
74 GstClockTime * next_ts)
76 GSequenceIter *iter1, *iter2 = NULL;
79 iter1 = gst_timed_value_control_source_find_control_point_iter (self, ts);
81 *cp1 = g_sequence_get (iter1);
82 iter2 = g_sequence_iter_next (iter1);
84 if (G_LIKELY (self->values)) {
85 /* all values in the control point list come after the given timestamp */
86 iter2 = g_sequence_get_begin_iter (self->values);
87 /* why this? if !cp1 we don't interpolate anyway
88 * if we can eliminate this, we can also use _get_nearest_control_points()
89 * here, is this just to set next_ts? */
96 if (iter2 && !g_sequence_iter_is_end (iter2)) {
97 *cp2 = g_sequence_get (iter2);
98 *next_ts = (*cp2)->timestamp;
100 *next_ts = GST_CLOCK_TIME_NONE;
105 /* steps-like (no-)interpolation, default */
106 /* just returns the value for the most recent key-frame */
107 static inline gdouble
108 _interpolate_none (GstTimedValueControlSource * self, GstControlPoint * cp)
114 interpolate_none_get (GstTimedValueControlSource * self, GstClockTime timestamp,
117 gboolean ret = FALSE;
121 g_mutex_lock (&self->lock);
124 gst_timed_value_control_source_find_control_point_iter (self, timestamp);
126 cp = g_sequence_get (iter);
127 *value = _interpolate_none (self, cp);
130 g_mutex_unlock (&self->lock);
135 interpolate_none_get_value_array (GstTimedValueControlSource * self,
136 GstClockTime timestamp, GstClockTime interval, guint n_values,
139 gboolean ret = FALSE;
141 GstClockTime ts = timestamp;
142 GstClockTime next_ts = 0;
143 GstControlPoint *cp1 = NULL, *cp2 = NULL;
145 g_mutex_lock (&self->lock);
147 for (i = 0; i < n_values; i++) {
148 GST_LOG ("values[%3d] : ts=%" GST_TIME_FORMAT ", next_ts=%" GST_TIME_FORMAT,
149 i, GST_TIME_ARGS (ts), GST_TIME_ARGS (next_ts));
151 _get_nearest_control_points2 (self, ts, &cp1, &cp2, &next_ts);
154 *values = _interpolate_none (self, cp1);
156 GST_LOG ("values[%3d]=%lf", i, *values);
159 GST_LOG ("values[%3d]=-", i);
164 g_mutex_unlock (&self->lock);
170 /* linear interpolation */
171 /* smoothes inbetween values */
172 static inline gdouble
173 _interpolate_linear (GstClockTime timestamp1, gdouble value1,
174 GstClockTime timestamp2, gdouble value2, GstClockTime timestamp)
176 if (GST_CLOCK_TIME_IS_VALID (timestamp2)) {
180 (value2 - value1) / gst_guint64_to_gdouble (timestamp2 - timestamp1);
181 return value1 + (gst_guint64_to_gdouble (timestamp - timestamp1) * slope);
188 interpolate_linear_get (GstTimedValueControlSource * self,
189 GstClockTime timestamp, gdouble * value)
191 gboolean ret = FALSE;
192 GstControlPoint *cp1, *cp2;
194 g_mutex_lock (&self->lock);
196 if (_get_nearest_control_points (self, timestamp, &cp1, &cp2)) {
197 *value = _interpolate_linear (cp1->timestamp, cp1->value,
198 (cp2 ? cp2->timestamp : GST_CLOCK_TIME_NONE),
199 (cp2 ? cp2->value : 0.0), timestamp);
202 g_mutex_unlock (&self->lock);
207 interpolate_linear_get_value_array (GstTimedValueControlSource * self,
208 GstClockTime timestamp, GstClockTime interval, guint n_values,
211 gboolean ret = FALSE;
213 GstClockTime ts = timestamp;
214 GstClockTime next_ts = 0;
215 GstControlPoint *cp1 = NULL, *cp2 = NULL;
217 g_mutex_lock (&self->lock);
219 for (i = 0; i < n_values; i++) {
220 GST_LOG ("values[%3d] : ts=%" GST_TIME_FORMAT ", next_ts=%" GST_TIME_FORMAT,
221 i, GST_TIME_ARGS (ts), GST_TIME_ARGS (next_ts));
223 _get_nearest_control_points2 (self, ts, &cp1, &cp2, &next_ts);
226 *values = _interpolate_linear (cp1->timestamp, cp1->value,
227 (cp2 ? cp2->timestamp : GST_CLOCK_TIME_NONE),
228 (cp2 ? cp2->value : 0.0), ts);
230 GST_LOG ("values[%3d]=%lf", i, *values);
233 GST_LOG ("values[%3d]=-", i);
238 g_mutex_unlock (&self->lock);
244 /* cubic interpolation */
246 /* The following functions implement a natural cubic spline interpolator.
247 * For details look at http://en.wikipedia.org/wiki/Spline_interpolation
249 * Instead of using a real matrix with n^2 elements for the linear system
250 * of equations we use three arrays o, p, q to hold the tridiagonal matrix
251 * as following to save memory:
260 _interpolate_cubic_update_cache (GstTimedValueControlSource * self)
262 gint i, n = self->nvalues;
263 gdouble *o = g_new0 (gdouble, n);
264 gdouble *p = g_new0 (gdouble, n);
265 gdouble *q = g_new0 (gdouble, n);
267 gdouble *h = g_new0 (gdouble, n);
268 gdouble *b = g_new0 (gdouble, n);
269 gdouble *z = g_new0 (gdouble, n);
273 GstClockTime x, x_next;
274 gdouble y_prev, y, y_next;
276 /* Fill linear system of equations */
277 iter = g_sequence_get_begin_iter (self->values);
278 cp = g_sequence_get (iter);
284 iter = g_sequence_iter_next (iter);
285 cp = g_sequence_get (iter);
286 x_next = cp->timestamp;
288 h[0] = gst_guint64_to_gdouble (x_next - x);
290 for (i = 1; i < n - 1; i++) {
291 /* Shuffle x and y values */
295 iter = g_sequence_iter_next (iter);
296 cp = g_sequence_get (iter);
297 x_next = cp->timestamp;
300 h[i] = gst_guint64_to_gdouble (x_next - x);
302 p[i] = 2.0 * (h[i - 1] + h[i]);
304 b[i] = (y_next - y) / h[i] - (y - y_prev) / h[i - 1];
308 /* Use Gauss elimination to set everything below the diagonal to zero */
309 for (i = 1; i < n - 1; i++) {
310 gdouble a = o[i] / p[i - 1];
311 p[i] -= a * q[i - 1];
312 b[i] -= a * b[i - 1];
315 /* Solve everything else from bottom to top */
316 for (i = n - 2; i > 0; i--)
317 z[i] = (b[i] - q[i] * z[i + 1]) / p[i];
319 /* Save cache next in the GstControlPoint */
321 iter = g_sequence_get_begin_iter (self->values);
322 for (i = 0; i < n; i++) {
323 cp = g_sequence_get (iter);
324 cp->cache.cubic.h = h[i];
325 cp->cache.cubic.z = z[i];
326 iter = g_sequence_iter_next (iter);
329 /* Free our temporary arrays */
338 static inline gdouble
339 _interpolate_cubic (GstTimedValueControlSource * self, GstControlPoint * cp1,
340 gdouble value1, GstControlPoint * cp2, gdouble value2,
341 GstClockTime timestamp)
343 if (!self->valid_cache) {
344 _interpolate_cubic_update_cache (self);
345 self->valid_cache = TRUE;
349 gdouble diff1, diff2;
352 diff1 = gst_guint64_to_gdouble (timestamp - cp1->timestamp);
353 diff2 = gst_guint64_to_gdouble (cp2->timestamp - timestamp);
356 (cp2->cache.cubic.z * diff1 * diff1 * diff1 +
357 cp1->cache.cubic.z * diff2 * diff2 * diff2) / cp1->cache.cubic.h;
359 (value2 / cp1->cache.cubic.h -
360 cp1->cache.cubic.h * cp2->cache.cubic.z) * diff1;
362 (value1 / cp1->cache.cubic.h -
363 cp1->cache.cubic.h * cp1->cache.cubic.z) * diff2;
371 interpolate_cubic_get (GstTimedValueControlSource * self,
372 GstClockTime timestamp, gdouble * value)
374 gboolean ret = FALSE;
375 GstControlPoint *cp1, *cp2 = NULL;
377 if (self->nvalues <= 2)
378 return interpolate_linear_get (self, timestamp, value);
380 g_mutex_lock (&self->lock);
382 if (_get_nearest_control_points (self, timestamp, &cp1, &cp2)) {
383 *value = _interpolate_cubic (self, cp1, cp1->value, cp2,
384 (cp2 ? cp2->value : 0.0), timestamp);
387 g_mutex_unlock (&self->lock);
392 interpolate_cubic_get_value_array (GstTimedValueControlSource * self,
393 GstClockTime timestamp, GstClockTime interval, guint n_values,
396 gboolean ret = FALSE;
398 GstClockTime ts = timestamp;
399 GstClockTime next_ts = 0;
400 GstControlPoint *cp1 = NULL, *cp2 = NULL;
402 if (self->nvalues <= 2)
403 return interpolate_linear_get_value_array (self, timestamp, interval,
406 g_mutex_lock (&self->lock);
408 for (i = 0; i < n_values; i++) {
409 GST_LOG ("values[%3d] : ts=%" GST_TIME_FORMAT ", next_ts=%" GST_TIME_FORMAT,
410 i, GST_TIME_ARGS (ts), GST_TIME_ARGS (next_ts));
412 _get_nearest_control_points2 (self, ts, &cp1, &cp2, &next_ts);
415 *values = _interpolate_cubic (self, cp1, cp1->value, cp2,
416 (cp2 ? cp2->value : 0.0), ts);
418 GST_LOG ("values[%3d]=%lf", i, *values);
421 GST_LOG ("values[%3d]=-", i);
426 g_mutex_unlock (&self->lock);
431 /* monotonic cubic interpolation */
433 /* the following functions implement monotonic cubic spline interpolation.
434 * For details: http://en.wikipedia.org/wiki/Monotone_cubic_interpolation
436 * In contrast to the previous cubic mode, the values won't overshoot.
440 _interpolate_cubic_mono_update_cache (GstTimedValueControlSource * self)
442 gint i, n = self->nvalues;
443 gdouble *dxs = g_new0 (gdouble, n);
444 gdouble *dys = g_new0 (gdouble, n);
445 gdouble *ms = g_new0 (gdouble, n);
446 gdouble *c1s = g_new0 (gdouble, n);
450 GstClockTime x, x_next, dx;
451 gdouble y, y_next, dy;
453 /* Get consecutive differences and slopes */
454 iter = g_sequence_get_begin_iter (self->values);
455 cp = g_sequence_get (iter);
456 x_next = cp->timestamp;
458 for (i = 0; i < n - 1; i++) {
461 iter = g_sequence_iter_next (iter);
462 cp = g_sequence_get (iter);
463 x_next = cp->timestamp;
466 dx = gst_guint64_to_gdouble (x_next - x);
473 /* Get degree-1 coefficients */
475 for (i = 1; i < n; i++) {
476 gdouble m = ms[i - 1];
477 gdouble m_next = ms[i];
479 if (m * m_next <= 0) {
482 gdouble dx_next, dx_sum;
484 dx = dxs[i], dx_next = dxs[i + 1], dx_sum = dx + dx_next;
485 c1s[i] = 3.0 * dx_sum / ((dx_sum + dx_next) / m + (dx_sum + dx) / m_next);
488 c1s[n - 1] = ms[n - 1];
490 /* Get degree-2 and degree-3 coefficients */
491 iter = g_sequence_get_begin_iter (self->values);
492 for (i = 0; i < n - 1; i++) {
493 gdouble c1, m, inv_dx, common;
494 cp = g_sequence_get (iter);
498 inv_dx = 1.0 / dxs[i];
499 common = c1 + c1s[i + 1] - m - m;
501 cp->cache.cubic_mono.c1s = c1;
502 cp->cache.cubic_mono.c2s = (m - c1 - common) * inv_dx;
503 cp->cache.cubic_mono.c3s = common * inv_dx * inv_dx;
505 iter = g_sequence_iter_next (iter);
508 /* Free our temporary arrays */
515 static inline gdouble
516 _interpolate_cubic_mono (GstTimedValueControlSource * self,
517 GstControlPoint * cp1, gdouble value1, GstControlPoint * cp2,
518 gdouble value2, GstClockTime timestamp)
520 if (!self->valid_cache) {
521 _interpolate_cubic_mono_update_cache (self);
522 self->valid_cache = TRUE;
526 gdouble diff = gst_guint64_to_gdouble (timestamp - cp1->timestamp);
527 gdouble diff2 = diff * diff;
530 out = value1 + cp1->cache.cubic_mono.c1s * diff;
531 out += cp1->cache.cubic_mono.c2s * diff2;
532 out += cp1->cache.cubic_mono.c3s * diff * diff2;
540 interpolate_cubic_mono_get (GstTimedValueControlSource * self,
541 GstClockTime timestamp, gdouble * value)
543 gboolean ret = FALSE;
544 GstControlPoint *cp1, *cp2 = NULL;
546 if (self->nvalues <= 2)
547 return interpolate_linear_get (self, timestamp, value);
549 g_mutex_lock (&self->lock);
551 if (_get_nearest_control_points (self, timestamp, &cp1, &cp2)) {
552 *value = _interpolate_cubic_mono (self, cp1, cp1->value, cp2,
553 (cp2 ? cp2->value : 0.0), timestamp);
556 g_mutex_unlock (&self->lock);
561 interpolate_cubic_mono_get_value_array (GstTimedValueControlSource * self,
562 GstClockTime timestamp, GstClockTime interval, guint n_values,
565 gboolean ret = FALSE;
567 GstClockTime ts = timestamp;
568 GstClockTime next_ts = 0;
569 GstControlPoint *cp1 = NULL, *cp2 = NULL;
571 if (self->nvalues <= 2)
572 return interpolate_linear_get_value_array (self, timestamp, interval,
575 g_mutex_lock (&self->lock);
577 for (i = 0; i < n_values; i++) {
578 GST_LOG ("values[%3d] : ts=%" GST_TIME_FORMAT ", next_ts=%" GST_TIME_FORMAT,
579 i, GST_TIME_ARGS (ts), GST_TIME_ARGS (next_ts));
581 _get_nearest_control_points2 (self, ts, &cp1, &cp2, &next_ts);
584 *values = _interpolate_cubic_mono (self, cp1, cp1->value, cp2,
585 (cp2 ? cp2->value : 0.0), ts);
587 GST_LOG ("values[%3d]=%lf", i, *values);
590 GST_LOG ("values[%3d]=-", i);
595 g_mutex_unlock (&self->lock);
602 GstControlSourceGetValue get;
603 GstControlSourceGetValueArray get_value_array;
604 } interpolation_modes[] = {
606 (GstControlSourceGetValue) interpolate_none_get,
607 (GstControlSourceGetValueArray) interpolate_none_get_value_array}, {
608 (GstControlSourceGetValue) interpolate_linear_get,
609 (GstControlSourceGetValueArray) interpolate_linear_get_value_array}, {
610 (GstControlSourceGetValue) interpolate_cubic_get,
611 (GstControlSourceGetValueArray) interpolate_cubic_get_value_array}, {
612 (GstControlSourceGetValue) interpolate_cubic_mono_get,
613 (GstControlSourceGetValueArray)
614 interpolate_cubic_mono_get_value_array}};
616 static const guint num_interpolation_modes = G_N_ELEMENTS (interpolation_modes);
624 gst_interpolation_mode_get_type (void)
626 static gsize gtype = 0;
627 static const GEnumValue values[] = {
628 {GST_INTERPOLATION_MODE_NONE, "GST_INTERPOLATION_MODE_NONE", "none"},
629 {GST_INTERPOLATION_MODE_LINEAR, "GST_INTERPOLATION_MODE_LINEAR", "linear"},
630 {GST_INTERPOLATION_MODE_CUBIC, "GST_INTERPOLATION_MODE_CUBIC", "cubic"},
631 {GST_INTERPOLATION_MODE_CUBIC_MONO, "GST_INTERPOLATION_MODE_CUBIC_MONO",
636 if (g_once_init_enter (>ype)) {
637 GType tmp = g_enum_register_static ("GstInterpolationMode", values);
638 g_once_init_leave (>ype, tmp);
641 return (GType) gtype;
646 GST_DEBUG_CATEGORY_INIT (GST_CAT_DEFAULT, "interpolation control source", 0, \
647 "timeline value interpolating control source")
649 G_DEFINE_TYPE_WITH_CODE (GstInterpolationControlSource,
650 gst_interpolation_control_source, GST_TYPE_TIMED_VALUE_CONTROL_SOURCE,
653 struct _GstInterpolationControlSourcePrivate
655 GstInterpolationMode interpolation_mode;
659 * gst_interpolation_control_source_new:
661 * This returns a new, unbound #GstInterpolationControlSource.
663 * Returns: (transfer full): a new, unbound #GstInterpolationControlSource.
666 gst_interpolation_control_source_new (void)
668 return g_object_newv (GST_TYPE_INTERPOLATION_CONTROL_SOURCE, 0, NULL);
672 gst_interpolation_control_source_set_interpolation_mode
673 (GstInterpolationControlSource * self, GstInterpolationMode mode)
675 GstControlSource *csource = GST_CONTROL_SOURCE (self);
677 if (mode >= num_interpolation_modes || (int) mode < 0) {
678 GST_WARNING ("interpolation mode %d invalid or not implemented yet", mode);
682 GST_TIMED_VALUE_CONTROL_SOURCE_LOCK (self);
683 csource->get_value = interpolation_modes[mode].get;
684 csource->get_value_array = interpolation_modes[mode].get_value_array;
686 gst_timed_value_control_invalidate_cache ((GstTimedValueControlSource *)
688 self->priv->interpolation_mode = mode;
690 GST_TIMED_VALUE_CONTROL_SOURCE_UNLOCK (self);
696 gst_interpolation_control_source_init (GstInterpolationControlSource * self)
699 G_TYPE_INSTANCE_GET_PRIVATE (self, GST_TYPE_INTERPOLATION_CONTROL_SOURCE,
700 GstInterpolationControlSourcePrivate);
701 gst_interpolation_control_source_set_interpolation_mode (self,
702 GST_INTERPOLATION_MODE_NONE);
706 gst_interpolation_control_source_set_property (GObject * object, guint prop_id,
707 const GValue * value, GParamSpec * pspec)
709 GstInterpolationControlSource *self =
710 GST_INTERPOLATION_CONTROL_SOURCE (object);
714 gst_interpolation_control_source_set_interpolation_mode (self,
715 (GstInterpolationMode) g_value_get_enum (value));
718 G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
724 gst_interpolation_control_source_get_property (GObject * object, guint prop_id,
725 GValue * value, GParamSpec * pspec)
727 GstInterpolationControlSource *self =
728 GST_INTERPOLATION_CONTROL_SOURCE (object);
732 g_value_set_enum (value, self->priv->interpolation_mode);
735 G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
741 gst_interpolation_control_source_class_init (GstInterpolationControlSourceClass
744 GObjectClass *gobject_class = G_OBJECT_CLASS (klass);
745 //GstControlSourceClass *csource_class = GST_CONTROL_SOURCE_CLASS (klass);
747 g_type_class_add_private (klass,
748 sizeof (GstInterpolationControlSourcePrivate));
750 gobject_class->set_property = gst_interpolation_control_source_set_property;
751 gobject_class->get_property = gst_interpolation_control_source_get_property;
753 g_object_class_install_property (gobject_class, PROP_MODE,
754 g_param_spec_enum ("mode", "Mode", "Interpolation mode",
755 GST_TYPE_INTERPOLATION_MODE, GST_INTERPOLATION_MODE_NONE,
756 G_PARAM_READWRITE | G_PARAM_STATIC_STRINGS));