[libshumate] view: Add kinetic scrolling

[Corentin Noël <corentinnoel src gnome org>]

commit 61f35d433f22b89eecbca18d6d7ba27e8fb5a352
Author: Georges Basile Stavracas Neto <georges stavracas gmail com>
Date:   Fri Mar 5 15:19:09 2021 -0300

    view: Add kinetic scrolling
    
    Implement kinetic scrolling through a GtkGestureSwipe that is triggered
    after ending a drag. When triggered, it adds a tick callback to the view,
    and each tick calculates the new distance from the point where the drag
    end happened.
    
    The kinetic scrolling heuristic is copied and modified from GTK4.
    
    The deceleration rate is hardcoded for now, because the 'deceleration'
    property is stub, but that'll be fixed by the next commits.
    
    Fixes: https://gitlab.gnome.org/GNOME/libshumate/-/issues/7

 shumate/meson.build                         |   2 +
 shumate/shumate-kinetic-scrolling-private.h |  36 +++++++
 shumate/shumate-kinetic-scrolling.c         | 146 ++++++++++++++++++++++++++++
 shumate/shumate-view.c                      | 139 ++++++++++++++++++++++++++
 4 files changed, 323 insertions(+)
---
diff --git a/shumate/meson.build b/shumate/meson.build
index c6649a0..37db9a0 100644
--- a/shumate/meson.build
+++ b/shumate/meson.build
@@ -27,6 +27,7 @@ libshumate_public_h = [
 
 libshumate_private_h = [
   'shumate-debug.h',
+  'shumate-kinetic-scrolling-private.h',
   'shumate-marker-private.h',
 ]
 
@@ -35,6 +36,7 @@ libshumate_sources = [
   'shumate-debug.c',
   'shumate-error-tile-source.c',
   'shumate-file-cache.c',
+  'shumate-kinetic-scrolling.c',
   'shumate-layer.c',
   'shumate-license.c',
   'shumate-location.c',
diff --git a/shumate/shumate-kinetic-scrolling-private.h b/shumate/shumate-kinetic-scrolling-private.h
new file mode 100644
index 0000000..57ac581
--- /dev/null
+++ b/shumate/shumate-kinetic-scrolling-private.h
@@ -0,0 +1,36 @@
+/*
+ * Copyright (C) 2014 Lieven van der Heide
+ * Copyright (C) 2021 Georges Basile Stavracas Neto <georges stavracas gmail com>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
+ */
+
+#pragma once
+
+#include <glib.h>
+
+G_BEGIN_DECLS
+
+typedef struct _ShumateKineticScrolling ShumateKineticScrolling;
+
+ShumateKineticScrolling *shumate_kinetic_scrolling_new  (double decel_friction,
+                                                         double initial_velocity);
+void shumate_kinetic_scrolling_free (ShumateKineticScrolling  *kinetic);
+
+gboolean shumate_kinetic_scrolling_tick (ShumateKineticScrolling *data,
+                                         double                   time_delta_us,
+                                         double                  *position);
+
+G_END_DECLS
diff --git a/shumate/shumate-kinetic-scrolling.c b/shumate/shumate-kinetic-scrolling.c
new file mode 100644
index 0000000..eff1eff
--- /dev/null
+++ b/shumate/shumate-kinetic-scrolling.c
@@ -0,0 +1,146 @@
+/*
+ * Copyright (C) 2014 Lieven van der Heide
+ * Copyright (C) 2021 Georges Basile Stavracas Neto <georges stavracas gmail com>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
+ */
+
+#include "shumate-kinetic-scrolling-private.h"
+
+#include <math.h>
+#include <stdio.h>
+
+/*
+ * All our curves are second degree linear differential equations, and
+ * so they can always be written as linear combinations of 2 base
+ * solutions. c1 and c2 are the coefficients to these two base solutions,
+ * and are computed from the initial position and velocity.
+ *
+ * In the case of simple deceleration, the differential equation is
+ *
+ *   y'' = -my'
+ *
+ * With m the resistance factor. For this we use the following 2
+ * base solutions:
+ *
+ *   f1(x) = 1
+ *   f2(x) = exp(-mx)
+ *
+ * In the case of overshoot, the differential equation is
+ *
+ *   y'' = -my' - ky
+ *
+ * With m the resistance, and k the spring stiffness constant. We let
+ * k = m^2 / 4, so that the system is critically damped (ie, returns to its
+ * equilibrium position as quickly as possible, without oscillating), and offset
+ * the whole thing, such that the equilibrium position is at 0. This gives the
+ * base solutions
+ *
+ *   f1(x) = exp(-mx / 2)
+ *   f2(x) = t exp(-mx / 2)
+*/
+
+typedef enum {
+  SHUMATE_KINETIC_SCROLLING_PHASE_DECELERATING,
+  SHUMATE_KINETIC_SCROLLING_PHASE_FINISHED,
+} ShumateKineticScrollingPhase;
+
+struct _ShumateKineticScrolling
+{
+  ShumateKineticScrollingPhase phase;
+  double lower;
+  double upper;
+  double overshoot_width;
+  double decel_friction;
+  double overshoot_friction;
+
+  double c1;
+  double c2;
+  double equilibrium_position;
+
+  double t_s;
+  double position;
+  double velocity;
+};
+
+static inline double
+us_to_s (double t)
+{
+  return t / 1000000.0;
+}
+
+ShumateKineticScrolling *
+shumate_kinetic_scrolling_new (double decel_friction,
+                               double initial_velocity)
+{
+  ShumateKineticScrolling *data;
+
+  data = g_new0 (ShumateKineticScrolling, 1);
+  data->phase = SHUMATE_KINETIC_SCROLLING_PHASE_DECELERATING;
+  data->decel_friction = decel_friction;
+  data->c1 = initial_velocity / decel_friction;
+  data->c2 = -data->c1;
+  data->t_s = 0.0;
+  data->position = 0.0;
+  data->velocity = initial_velocity;
+
+  return data;
+}
+
+void
+shumate_kinetic_scrolling_free (ShumateKineticScrolling *kinetic)
+{
+  g_free (kinetic);
+}
+
+gboolean
+shumate_kinetic_scrolling_tick (ShumateKineticScrolling *data,
+                                double                   time_delta_us,
+                                double                  *position)
+{
+  switch(data->phase)
+    {
+    case SHUMATE_KINETIC_SCROLLING_PHASE_DECELERATING:
+      {
+        double last_position = data->position;
+        double last_time_ms = data->t_s;
+        double exp_part;
+
+        data->t_s += us_to_s (time_delta_us);
+
+        exp_part = exp (-data->decel_friction * data->t_s);
+        data->position = data->c1 + data->c2 * exp_part;
+        data->velocity = -data->decel_friction * data->c2 * exp_part;
+
+        if (fabs (data->velocity) < 1.0 ||
+            (last_time_ms != 0.0 && fabs (data->position - last_position) < 1.0))
+          {
+            data->phase = SHUMATE_KINETIC_SCROLLING_PHASE_FINISHED;
+            data->position = round (data->position);
+            data->velocity = 0;
+          }
+        break;
+      }
+
+    case SHUMATE_KINETIC_SCROLLING_PHASE_FINISHED:
+    default:
+      break;
+    }
+
+  if (position)
+    *position = data->position;
+
+  return data->phase != SHUMATE_KINETIC_SCROLLING_PHASE_FINISHED;
+}
diff --git a/shumate/shumate-view.c b/shumate/shumate-view.c
index 3b8d1db..6e0bd73 100644
--- a/shumate/shumate-view.c
+++ b/shumate/shumate-view.c
@@ -55,6 +55,7 @@
 
 #include "shumate.h"
 #include "shumate-enum-types.h"
+#include "shumate-kinetic-scrolling-private.h"
 #include "shumate-marshal.h"
 #include "shumate-map-layer.h"
 #include "shumate-map-source.h"
@@ -69,6 +70,8 @@
 #include <gtk/gtk.h>
 #include <math.h>
 
+#define DECELERATION_FRICTION 4.0
+
 enum
 {
   /* normal signals */
@@ -116,6 +119,15 @@ typedef struct
   int size;
 } FillTileCallbackData;
 
+typedef struct
+{
+  ShumateKineticScrolling *kinetic_scrolling;
+  ShumateView *view;
+  double start_lat;
+  double start_lon;
+  int64_t last_deceleration_time_us;
+  graphene_vec2_t direction;
+} KineticScrollData;
 
 typedef struct
 {
@@ -144,6 +156,8 @@ typedef struct
   // shumate_view_go_to's context, kept for stop_go_to
   GoToContext *goto_context;
 
+  guint deceleration_tick_id;
+
   int tiles_loading;
 
   guint zoom_timeout;
@@ -269,6 +283,115 @@ move_viewport_from_pixel_offset (ShumateView *self,
   shumate_location_set_location (SHUMATE_LOCATION (priv->viewport), lat, lon);
 }
 
+static void
+cancel_deceleration (ShumateView *self)
+{
+  ShumateViewPrivate *priv = shumate_view_get_instance_private (self);
+
+  if (priv->deceleration_tick_id > 0)
+    {
+      gtk_widget_remove_tick_callback (GTK_WIDGET (self), priv->deceleration_tick_id);
+      priv->deceleration_tick_id = 0;
+    }
+}
+
+static gboolean
+view_deceleration_tick_cb (GtkWidget     *widget,
+                           GdkFrameClock *frame_clock,
+                           gpointer       user_data)
+{
+  KineticScrollData *data = user_data;
+  ShumateView *view = data->view;
+  int64_t current_time_us;
+  double elapsed_us;
+  double position;
+
+  g_assert (SHUMATE_IS_VIEW (view));
+
+  current_time_us = gdk_frame_clock_get_frame_time (frame_clock);
+  elapsed_us = current_time_us - data->last_deceleration_time_us;
+
+  /* The frame clock can sometimes fire immediately after adding a tick callback,
+   * in which case no time has passed, making it impossible to calculate the
+   * kinetic factor. If this is the case, wait for the next tick.
+   */
+  if (G_APPROX_VALUE (elapsed_us, 0.0, FLT_EPSILON))
+    return G_SOURCE_CONTINUE;
+
+  data->last_deceleration_time_us = current_time_us;
+
+  if (data->kinetic_scrolling &&
+      shumate_kinetic_scrolling_tick (data->kinetic_scrolling, elapsed_us, &position))
+    {
+      graphene_vec2_t new_positions;
+
+      graphene_vec2_init (&new_positions, position, position);
+      graphene_vec2_multiply (&new_positions, &data->direction, &new_positions);
+
+      move_viewport_from_pixel_offset (view,
+                                       data->start_lat,
+                                       data->start_lon,
+                                       graphene_vec2_get_x (&new_positions),
+                                       graphene_vec2_get_y (&new_positions));
+    }
+  else
+    {
+      g_clear_pointer (&data->kinetic_scrolling, shumate_kinetic_scrolling_free);
+    }
+
+  if (!data->kinetic_scrolling)
+    {
+      cancel_deceleration (view);
+      return G_SOURCE_REMOVE;
+    }
+
+  return G_SOURCE_CONTINUE;
+}
+
+
+static void
+kinetic_scroll_data_free (KineticScrollData *data)
+{
+  if (data == NULL)
+    return;
+
+  g_clear_pointer (&data->kinetic_scrolling, shumate_kinetic_scrolling_free);
+  g_free (data);
+}
+
+static void
+start_deceleration (ShumateView *self,
+                    double       h_velocity,
+                    double       v_velocity)
+{
+  ShumateViewPrivate *priv = shumate_view_get_instance_private (self);
+  GdkFrameClock *frame_clock;
+  KineticScrollData *data;
+  graphene_vec2_t velocity;
+
+  g_assert (priv->deceleration_tick_id == 0);
+
+  frame_clock = gtk_widget_get_frame_clock (GTK_WIDGET (self));
+
+  graphene_vec2_init (&velocity, h_velocity, v_velocity);
+
+  data = g_new0 (KineticScrollData, 1);
+  data->view = self;
+  data->last_deceleration_time_us = gdk_frame_clock_get_frame_time (frame_clock);
+  data->start_lat = shumate_location_get_latitude (SHUMATE_LOCATION (priv->viewport));
+  data->start_lon = shumate_location_get_longitude (SHUMATE_LOCATION (priv->viewport));
+  graphene_vec2_normalize (&velocity, &data->direction);
+  data->kinetic_scrolling =
+    shumate_kinetic_scrolling_new (DECELERATION_FRICTION,
+                                   graphene_vec2_length (&velocity));
+
+  priv->deceleration_tick_id =
+    gtk_widget_add_tick_callback (GTK_WIDGET (self),
+                                  view_deceleration_tick_cb,
+                                  data,
+                                  (GDestroyNotify) kinetic_scroll_data_free);
+}
+
 static inline double
 ease_in_out_quad (double p)
 {
@@ -339,6 +462,8 @@ on_drag_gesture_drag_begin (ShumateView    *self,
 
   g_assert (SHUMATE_IS_VIEW (self));
 
+  cancel_deceleration (self);
+
   priv->drag_begin_lon = shumate_location_get_longitude (SHUMATE_LOCATION (priv->viewport));
   priv->drag_begin_lat = shumate_location_get_latitude (SHUMATE_LOCATION (priv->viewport));
 
@@ -382,6 +507,15 @@ on_drag_gesture_drag_end (ShumateView    *self,
   priv->drag_begin_lat = 0;
 }
 
+static void
+view_swipe_cb (GtkGestureSwipe *swipe_gesture,
+               double           velocity_x,
+               double           velocity_y,
+               ShumateView     *self)
+{
+  start_deceleration (self, velocity_x, velocity_y);
+}
+
 static gboolean
 on_scroll_controller_scroll (ShumateView              *self,
                              double                   dx,
@@ -767,6 +901,7 @@ shumate_view_init (ShumateView *view)
   GtkGesture *drag_gesture;
   GtkEventController *scroll_controller;
   GtkEventController *motion_controller;
+  GtkGesture *swipe_gesture;
 
   shumate_debug_set_flags (g_getenv ("SHUMATE_DEBUG"));
 
@@ -796,6 +931,10 @@ shumate_view_init (ShumateView *view)
   g_signal_connect_swapped (drag_gesture, "drag-end", G_CALLBACK (on_drag_gesture_drag_end), view);
   gtk_widget_add_controller (GTK_WIDGET (view), GTK_EVENT_CONTROLLER (drag_gesture));
 
+  swipe_gesture = gtk_gesture_swipe_new ();
+  g_signal_connect (swipe_gesture, "swipe", G_CALLBACK (view_swipe_cb), view);
+  gtk_widget_add_controller (GTK_WIDGET (view), GTK_EVENT_CONTROLLER (swipe_gesture));
+
   scroll_controller = gtk_event_controller_scroll_new 
(GTK_EVENT_CONTROLLER_SCROLL_VERTICAL|GTK_EVENT_CONTROLLER_SCROLL_DISCRETE);
   g_signal_connect_swapped (scroll_controller, "scroll", G_CALLBACK (on_scroll_controller_scroll), view);
   gtk_widget_add_controller (GTK_WIDGET (view), scroll_controller);