[libhandy] swipe-tracker: Rework end point calculation

[Adrien Plazas <aplazas src gnome org>]

commit 056d92e7dfb9ce4e3e5aea855b5abf91ca62684b
Author: Alexander Mikhaylenko <alexm gnome org>
Date:   Thu Jul 9 18:04:49 2020 +0500

    swipe-tracker: Rework end point calculation
    
    Previously we used a bunch of heuristics for this. We checked if velocity
    was directed towards the nearest snap point and its value was larger than
    a threshold. If it is, we completed the swipe, otherwise we cancelled it.
    
    This was good enough at the time, because this code was originally written
    for back/forward swipe. Since then, the swipe tracker was extended to
    handle arbitrary snap points and not just 0 and 1, or -1 and 0, depending
    on text direction. After that it was iterated on, but never significantly
    redone.
    
    This worked well enough, but had two problems:
    
    1. In some cases, notably for HdyCarousel with non-expanded pages, it may
       be wanted to be able to swipe through multiple pages at once. This
       wasn't really possible because we always picked the adjacent snap
       point.
    
    2. Since we can't do that well, we want to restrict swipes to one page at a
       time. It was done in a rather hacky way by clamping the position into
       [-1, 1] range from the place where we started the swipe. This works
       if we start the swipe from idle position, but if an animation was
       already going, the range would be clamped to arbitrary values, and very
       likely containing only one snap point, which we already swiped past at
       this point. In this case, finishing the swipe would cancel it regardless
       of velocity. This means that if one tries to quickly move through
       carousel pages via swiping, half of the swipes will be inexplicably
       cancelled.
    
    We'll use the deceleration formula from
    https://medium.com/@esskeetit/how-uiscrollview-works-e418adc47060#10ce
    to calculate then projection point, then pick the nearest snap point and
    calculate the duration as we did before. It works well enough for short
    distances, but has two problems:
    
    1. It caps the maximum distance at a pretty low value - about 5 pages in my
    testing.
    
    2. With how we pick the nearest snap point, it's too easy to accidentally
    cancel the swipe,
    
    To combat the first problem, we can modify the curve: only use linear
    function at small distances, and smoothly transition it to a parabola
    further.
    
    For the second problem we can add two special cases: first, if the swipe
    ended up between the initial snap point and the next one, we always prefer
    the latter. Second, a good old velocity threshold for cancelling.
    
    We'll also use a slightly smaller deceleration value for touchpad: 0.997
    instead of 0.998.
    
    Now that we can pick any snap point, the [-1, 1] clamping doesn't make
    sense anymore, so instead let's replace it with a more flexible
    mechanism: if we're near a snap point, pick its adjacent snap points.
    Otherwise, take the two nearest snap points, and take their adjacent
    snap points. This way we have 3 snap points to choose from when
    starting a swipe from an idle position, and 4 if we start during an
    ongoing transition.
    
    This way, if we've just swiped from snap point n to n+1, the transition
    will pick snap points n-1, n, n+1, n+2 and if we swipe again, we will
    likely land on n+2. During that transition, if we swipe again, it will
    likely have already passed the snap point n+1, so this time the available
    snap points will be n, n+1, n+2, n+3, so we can swipe again and it will
    still complete, and so on.
    
    This will make it easy to allow multi-page swipes as well, by just
    removing the clamping.
    
    Signed-off-by: Alexander Mikhaylenko <alexm gnome org>

 src/hdy-swipe-tracker.c | 223 +++++++++++++++++++++++++++++++++---------------
 1 file changed, 155 insertions(+), 68 deletions(-)
---
diff --git a/src/hdy-swipe-tracker.c b/src/hdy-swipe-tracker.c
index 9525c66d..5133e7b6 100644
--- a/src/hdy-swipe-tracker.c
+++ b/src/hdy-swipe-tracker.c
@@ -18,10 +18,18 @@
 #define SCROLL_MULTIPLIER 10
 #define MIN_ANIMATION_DURATION 100
 #define MAX_ANIMATION_DURATION 400
-#define VELOCITY_THRESHOLD 0.4
+#define VELOCITY_THRESHOLD_TOUCH 0.3
+#define VELOCITY_THRESHOLD_TOUCHPAD 0.6
+#define DECELERATION_TOUCH 0.998
+#define DECELERATION_TOUCHPAD 0.997
+#define VELOCITY_CURVE_THRESHOLD 2
+#define DECELERATION_PARABOLA_MULTIPLIER 0.35
 #define DURATION_MULTIPLIER 3
 #define ANIMATION_BASE_VELOCITY 0.002
 #define DRAG_THRESHOLD_DISTANCE 16
+#define EPSILON 0.005
+
+#define SIGN(x) ((x) > 0.0 ? 1.0 : ((x) < 0.0 ? -1.0 : 0.0))
 
 /**
  * SECTION:hdy-swipe-tracker
@@ -280,89 +288,159 @@ gesture_begin (HdySwipeTracker *self)
   gtk_grab_add (GTK_WIDGET (self->swipeable));
 }
 
-static void
-gesture_update (HdySwipeTracker *self,
-                gdouble          delta)
+static gint
+find_closest_point (gdouble *points,
+                    gint     n,
+                    gdouble  pos)
 {
-  gdouble progress;
-  gdouble first_point, last_point;
+  guint i, min = 0;
 
-  if (self->state != HDY_SWIPE_TRACKER_STATE_SCROLLING)
-    return;
+  for (i = 1; i < n; i++)
+    if (ABS (points[i] - pos) < ABS (points[min] - pos))
+      min = i;
 
-  append_to_history (self, delta);
+  return min;
+}
 
-  get_range (self, &first_point, &last_point);
+static gint
+find_next_point (gdouble *points,
+                 gint     n,
+                 gdouble  pos)
+{
+  guint i;
 
-  progress = self->progress + delta;
+  for (i = 0; i < n; i++)
+    if (points[i] >= pos)
+      return i;
 
-  progress = CLAMP (progress, first_point, last_point);
+  return -1;
+}
 
-  /* FIXME: this is a hack to prevent swiping more than 1 page at once */
-  progress = CLAMP (progress, self->initial_progress - 1, self->initial_progress + 1);
+static gint
+find_previous_point (gdouble *points,
+                     gint     n,
+                     gdouble  pos)
+{
+  gint i;
 
-  self->progress = progress;
+  for (i = n - 1; i >= 0; i--)
+    if (points[i] <= pos)
+      return i;
 
-  hdy_swipe_tracker_emit_update_swipe (self, progress);
+  return -1;
+}
+
+static gint
+find_point_for_projection (HdySwipeTracker *self,
+                           gdouble         *points,
+                           gint             n,
+                           gdouble          pos,
+                           gdouble          velocity)
+{
+  gint initial = find_closest_point (points, n, self->initial_progress);
+  gint prev = find_previous_point (points, n, pos);
+  gint next = find_next_point (points, n, pos);
+
+  if ((velocity > 0 ? prev : next) == initial)
+    return velocity > 0 ? next : prev;
+
+  return find_closest_point (points, n, pos);
 }
 
 static void
-get_closest_snap_points (HdySwipeTracker *self,
-                         gdouble         *upper,
-                         gdouble         *lower)
+get_bounds (HdySwipeTracker *self,
+            gdouble         *points,
+            gint             n,
+            gdouble          pos,
+            gdouble         *lower,
+            gdouble         *upper)
 {
-  gint i, n;
-  gdouble *points;
+  gint prev, next;
+  gint closest = find_closest_point (points, n, self->initial_progress);
+
+  if (ABS (points[closest] - self->initial_progress) < EPSILON) {
+    prev = next = closest;
+  } else {
+    prev = find_previous_point (points, n, self->initial_progress);
+    next = find_next_point (points, n, self->initial_progress);
+  }
+
+  *lower = points[MAX (prev - 1, 0)];
+  *upper = points[MIN (next + 1, n - 1)];
+}
 
-  *upper = 0;
-  *lower = 0;
+static void
+gesture_update (HdySwipeTracker *self,
+                gdouble          delta)
+{
+  gdouble lower, upper;
+  gdouble progress;
+  g_autofree gdouble *points = NULL;
+  gint n;
+
+  if (self->state != HDY_SWIPE_TRACKER_STATE_SCROLLING)
+    return;
 
   points = hdy_swipeable_get_snap_points (self->swipeable, &n);
+  get_bounds (self, points, n, self->initial_progress, &lower, &upper);
 
-  for (i = 0; i < n; i++) {
-    if (points[i] >= self->progress) {
-      *upper = points[i];
-      break;
-    }
-  }
+  progress = self->progress + delta;
+  progress = CLAMP (progress, lower, upper);
 
-  for (i = n - 1; i >= 0; i--) {
-    if (points[i] <= self->progress) {
-      *lower = points[i];
-      break;
-    }
-  }
+  self->progress = progress;
 
-  g_free (points);
+  hdy_swipe_tracker_emit_update_swipe (self, progress);
 }
 
 static gdouble
 get_end_progress (HdySwipeTracker *self,
-                  gdouble          distance,
-                  gdouble          velocity)
+                  gdouble          velocity,
+                  gboolean         is_touchpad)
 {
-  gdouble upper, lower, middle;
+  gdouble pos, decel, slope, lower, upper;
+  g_autofree gdouble *points = NULL;
+  gint n;
 
   if (self->cancelled)
     return hdy_swipeable_get_cancel_progress (self->swipeable);
 
-  get_closest_snap_points (self, &upper, &lower);
-  middle = (upper + lower) / 2;
+  points = hdy_swipeable_get_snap_points (self->swipeable, &n);
+
+  if (ABS (velocity) < (is_touchpad ? VELOCITY_THRESHOLD_TOUCHPAD : VELOCITY_THRESHOLD_TOUCH))
+    return points[find_closest_point (points, n, self->progress)];
+
+  decel = is_touchpad ? DECELERATION_TOUCHPAD : DECELERATION_TOUCH;
+  slope = decel / (1.0 - decel) / 1000.0;
+
+  if (ABS (velocity) > VELOCITY_CURVE_THRESHOLD) {
+    const gdouble c = slope / 2 / DECELERATION_PARABOLA_MULTIPLIER;
+    const gdouble x = ABS (velocity) - VELOCITY_CURVE_THRESHOLD + c;
 
-  if (self->progress > middle)
-    return (velocity * distance > -VELOCITY_THRESHOLD ||
-            self->initial_progress > upper) ? upper : lower;
+    pos = DECELERATION_PARABOLA_MULTIPLIER * x * x
+        - DECELERATION_PARABOLA_MULTIPLIER * c * c
+        + slope * VELOCITY_CURVE_THRESHOLD;
+  } else {
+    pos = ABS (velocity) * slope;
+  }
+
+  pos = (pos * SIGN (velocity)) + self->progress;
+
+  get_bounds (self, points, n, self->initial_progress, &lower, &upper);
+
+  pos = CLAMP (pos, lower, upper);
 
-  return (velocity * distance < VELOCITY_THRESHOLD ||
-          self->initial_progress < lower) ? lower : upper;
+  pos = points[find_point_for_projection (self, points, n, pos, velocity)];
+
+  return pos;
 }
 
 static void
 gesture_end (HdySwipeTracker *self,
-             gdouble          distance)
+             gdouble          distance,
+             gboolean         is_touchpad)
 {
   gdouble end_progress, velocity;
-  gint64 duration;
+  gint64 duration, max_duration;
 
   if (self->state == HDY_SWIPE_TRACKER_STATE_NONE)
     return;
@@ -371,14 +449,18 @@ gesture_end (HdySwipeTracker *self,
 
   velocity = calculate_velocity (self);
 
-  end_progress = get_end_progress (self, distance, velocity);
+  end_progress = get_end_progress (self, velocity, is_touchpad);
+
+  velocity /= distance;
 
   if ((end_progress - self->progress) * velocity <= 0)
     velocity = ANIMATION_BASE_VELOCITY;
 
+  max_duration = MAX_ANIMATION_DURATION * log2 (1 + MAX (1, ceil (ABS (self->progress - end_progress))));
+
   duration = ABS ((self->progress - end_progress) / velocity * DURATION_MULTIPLIER);
   if (self->progress != end_progress)
-    duration = CLAMP (duration, MIN_ANIMATION_DURATION, MAX_ANIMATION_DURATION);
+    duration = CLAMP (duration, MIN_ANIMATION_DURATION, max_duration);
 
   hdy_swipe_tracker_emit_end_swipe (self, duration, end_progress);
 
@@ -390,7 +472,8 @@ gesture_end (HdySwipeTracker *self,
 
 static void
 gesture_cancel (HdySwipeTracker *self,
-                gdouble          distance)
+                gdouble          distance,
+                gboolean         is_touchpad)
 {
   if (self->state != HDY_SWIPE_TRACKER_STATE_PENDING &&
       self->state != HDY_SWIPE_TRACKER_STATE_SCROLLING) {
@@ -400,7 +483,7 @@ gesture_cancel (HdySwipeTracker *self,
   }
 
   self->cancelled = TRUE;
-  gesture_end (self, distance);
+  gesture_end (self, distance, is_touchpad);
 }
 
 static void
@@ -422,20 +505,20 @@ drag_update_cb (HdySwipeTracker *self,
                 gdouble          offset_y,
                 GtkGestureDrag  *gesture)
 {
-  gdouble offset, distance;
+  gdouble offset, distance, delta;
   gboolean is_vertical, is_offset_vertical;
 
   distance = hdy_swipeable_get_distance (self->swipeable);
 
   is_vertical = (self->orientation == GTK_ORIENTATION_VERTICAL);
-  if (is_vertical)
-    offset = -offset_y / distance;
-  else
-    offset = -offset_x / distance;
+  offset = is_vertical ? offset_y : offset_x;
 
-  if (self->reversed)
+  if (!self->reversed)
     offset = -offset;
 
+  delta = offset - self->prev_offset;
+  self->prev_offset = offset;
+
   is_offset_vertical = (ABS (offset_y) > ABS (offset_x));
 
   if (self->state == HDY_SWIPE_TRACKER_STATE_REJECTED) {
@@ -443,6 +526,8 @@ drag_update_cb (HdySwipeTracker *self,
     return;
   }
 
+  append_to_history (self, delta);
+
   if (self->state == HDY_SWIPE_TRACKER_STATE_NONE) {
     if (is_vertical == is_offset_vertical)
       gesture_prepare (self, offset > 0 ? HDY_NAVIGATION_DIRECTION_FORWARD : HDY_NAVIGATION_DIRECTION_BACK, 
TRUE);
@@ -473,10 +558,8 @@ drag_update_cb (HdySwipeTracker *self,
     }
   }
 
-  if (self->state == HDY_SWIPE_TRACKER_STATE_SCROLLING) {
-    gesture_update (self, offset - self->prev_offset);
-    self->prev_offset = offset;
-  }
+  if (self->state == HDY_SWIPE_TRACKER_STATE_SCROLLING)
+    gesture_update (self, delta / distance);
 }
 
 static void
@@ -497,12 +580,12 @@ drag_end_cb (HdySwipeTracker *self,
   }
 
   if (self->state != HDY_SWIPE_TRACKER_STATE_SCROLLING) {
-    gesture_cancel (self, distance);
+    gesture_cancel (self, distance, FALSE);
     gtk_gesture_set_state (self->touch_gesture, GTK_EVENT_SEQUENCE_DENIED);
     return;
   }
 
-  gesture_end (self, distance);
+  gesture_end (self, distance, FALSE);
 }
 
 static void
@@ -514,7 +597,7 @@ drag_cancel_cb (HdySwipeTracker  *self,
 
   distance = hdy_swipeable_get_distance (self->swipeable);
 
-  gesture_cancel (self, distance);
+  gesture_cancel (self, distance, FALSE);
   gtk_gesture_set_state (gesture, GTK_EVENT_SEQUENCE_DENIED);
 }
 
@@ -548,7 +631,7 @@ handle_scroll_event (HdySwipeTracker *self,
   is_delta_vertical = (ABS (dy) > ABS (dx));
 
   if (self->is_scrolling) {
-    gesture_cancel (self, distance);
+    gesture_cancel (self, distance, TRUE);
 
     if (gdk_event_is_scroll_stop_event (event))
       self->is_scrolling = FALSE;
@@ -593,16 +676,20 @@ handle_scroll_event (HdySwipeTracker *self,
     is_overshooting = (delta < 0 && self->progress <= first_point) ||
                       (delta > 0 && self->progress >= last_point);
 
+    append_to_history (self, delta * SCROLL_MULTIPLIER);
+
     if ((is_vertical == is_delta_vertical) && !is_overshooting)
       gesture_begin (self);
     else
-      gesture_cancel (self, distance);
+      gesture_cancel (self, distance, TRUE);
   }
 
   if (self->state == HDY_SWIPE_TRACKER_STATE_SCROLLING) {
     if (gdk_event_is_scroll_stop_event (event)) {
-      gesture_end (self, distance);
+      gesture_end (self, distance, TRUE);
     } else {
+      append_to_history (self, delta * SCROLL_MULTIPLIER);
+
       gesture_update (self, delta / distance * SCROLL_MULTIPLIER);
       return GDK_EVENT_STOP;
     }