Bug 1457586 - Add an AndroidVelocityTracker class that implement Chrome's default velocity tracking strategy. r=kats
authorBotond Ballo <botond@mozilla.com>
Fri, 05 Oct 2018 16:51:14 +0000
changeset 495574 f266ca6d096a31445b53bcf314befaef06cae6c2
parent 495573 1507f6511c87bc7be36b864bde447d9da8bd4839
child 495575 77ace67c85de8eb18f5a364a2ffdd0f31e34454a
push id9984
push userffxbld-merge
push dateMon, 15 Oct 2018 21:07:35 +0000
treeherdermozilla-beta@183d27ea8570 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerskats
bugs1457586
milestone64.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1457586 - Add an AndroidVelocityTracker class that implement Chrome's default velocity tracking strategy. r=kats MozReview-Commit-ID: 6kteQv1KHDN Depends on D7658 Differential Revision: https://phabricator.services.mozilla.com/D7659
gfx/layers/apz/src/AndroidAPZ.cpp
gfx/layers/apz/src/AndroidAPZ.h
gfx/layers/apz/src/AndroidVelocityTracker.cpp
gfx/layers/apz/src/AndroidVelocityTracker.h
gfx/layers/moz.build
--- a/gfx/layers/apz/src/AndroidAPZ.cpp
+++ b/gfx/layers/apz/src/AndroidAPZ.cpp
@@ -2,21 +2,23 @@
 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "AndroidAPZ.h"
 
 #include "AndroidFlingPhysics.h"
+#include "AndroidVelocityTracker.h"
 #include "AsyncPanZoomController.h"
 #include "GeneratedJNIWrappers.h"
 #include "GenericFlingAnimation.h"
 #include "gfxPrefs.h"
 #include "OverscrollHandoffState.h"
+#include "SimpleVelocityTracker.h"
 #include "ViewConfiguration.h"
 
 #define ANDROID_APZ_LOG(...)
 // #define ANDROID_APZ_LOG(...) printf_stderr("ANDROID_APZ: " __VA_ARGS__)
 
 static float sMaxFlingSpeed = 0.0f;
 
 namespace mozilla {
@@ -59,16 +61,24 @@ AndroidSpecificState::CreateFlingAnimati
     return new StackScrollerFlingAnimation(aApzc,
         this,
         aHandoffState.mChain,
         aHandoffState.mIsHandoff,
         aHandoffState.mScrolledApzc);
   }
 }
 
+UniquePtr<VelocityTracker>
+AndroidSpecificState::CreateVelocityTracker(Axis* aAxis) {
+  if (gfxPrefs::APZUseChromeFlingPhysics()) {
+      return MakeUnique<AndroidVelocityTracker>();
+  }
+  return MakeUnique<SimpleVelocityTracker>(aAxis);
+}
+
 /* static */ void
 AndroidSpecificState::InitializeGlobalState() {
   // Not conditioned on gfxPrefs::APZUseChromeFlingPhysics() because
   // the pref is live.
   AndroidFlingPhysics::InitializeGlobalState();
 }
 
 
--- a/gfx/layers/apz/src/AndroidAPZ.h
+++ b/gfx/layers/apz/src/AndroidAPZ.h
@@ -20,16 +20,17 @@ public:
 
   virtual AndroidSpecificState* AsAndroidSpecificState() override {
     return this;
   }
 
   virtual AsyncPanZoomAnimation* CreateFlingAnimation(AsyncPanZoomController& aApzc,
                                                       const FlingHandoffState& aHandoffState,
                                                       float aPLPPI) override;
+  virtual UniquePtr<VelocityTracker> CreateVelocityTracker(Axis* aAxis) override;
 
   static void InitializeGlobalState();
 
   java::StackScroller::GlobalRef mOverScroller;
   TimeStamp mLastFling;
 };
 
 class StackScrollerFlingAnimation: public AsyncPanZoomAnimation {
new file mode 100644
--- /dev/null
+++ b/gfx/layers/apz/src/AndroidVelocityTracker.cpp
@@ -0,0 +1,308 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "AndroidVelocityTracker.h"
+
+#include "gfxPrefs.h"
+
+namespace mozilla {
+namespace layers {
+
+// This velocity tracker implementation was adapted from Chromium's
+// second-order unweighted least-squares velocity tracker strategy
+// (https://cs.chromium.org/chromium/src/ui/events/gesture_detection/velocity_tracker.cc?l=101&rcl=9ea9a086d4f54c702ec9a38e55fb3eb8bbc2401b).
+
+// Threshold between position updates for determining that a pointer has
+// stopped moving. Some input devices do not send move events in the
+// case where a pointer has stopped.  We need to detect this case so that we can
+// accurately predict the velocity after the pointer starts moving again.
+static const int kAssumePointerMoveStoppedTimeMs = 40;
+
+// The degree of the approximation.
+static const uint8_t kDegree = 2;
+
+// The degree of the polynomial used in SolveLeastSquares().
+// This should be the degree of the approximation plus one.
+static const uint8_t kPolyDegree = kDegree + 1;
+
+// Maximum size of position history.
+static const uint8_t kHistorySize = 20;
+
+AndroidVelocityTracker::AndroidVelocityTracker()
+  : mLastEventTime(0)
+{
+}
+
+void
+AndroidVelocityTracker::StartTracking(ParentLayerCoord aPos, uint32_t aTimestampMs)
+{
+  Clear();
+  mLastEventTime = aTimestampMs;
+}
+
+Maybe<float>
+AndroidVelocityTracker::AddPosition(ParentLayerCoord aPos,
+                                    uint32_t aTimestampMs,
+                                    bool aIsAxisLocked)
+{
+  if ((aTimestampMs - mLastEventTime) >= kAssumePointerMoveStoppedTimeMs) {
+    Clear();
+  }
+
+  mLastEventTime = aTimestampMs;
+
+  // If we are axis-locked, adjust the position to reflect the fact that
+  // no movement is happening.
+  if (aIsAxisLocked && !mHistory.IsEmpty()) {
+    aPos = mHistory[mHistory.Length() - 1].second;
+  }
+
+  mHistory.AppendElement(std::make_pair(aTimestampMs, aPos));
+  if (mHistory.Length() > kHistorySize) {
+    mHistory.RemoveElementAt(0);
+  }
+
+  if (mHistory.Length() < 2) {
+    return Nothing();
+  }
+
+  auto start = mHistory[mHistory.Length() - 2];
+  auto end = mHistory[mHistory.Length() - 1];
+  return Some((end.second - start.second) / (end.first - start.first));
+}
+
+float
+AndroidVelocityTracker::HandleDynamicToolbarMovement(uint32_t aStartTimestampMs,
+                                                     uint32_t aEndTimestampMs,
+                                                     ParentLayerCoord aDelta)
+{
+  // TODO: Implement fully.
+  float timeDelta = aEndTimestampMs - aStartTimestampMs;
+  MOZ_ASSERT(timeDelta != 0);
+  return aDelta / timeDelta;
+}
+
+static float VectorDot(const float* a, const float* b, uint32_t m) {
+  float r = 0;
+  while (m--) {
+    r += *(a++) * *(b++);
+  }
+  return r;
+}
+
+static float VectorNorm(const float* a, uint32_t m) {
+  float r = 0;
+  while (m--) {
+    float t = *(a++);
+    r += t * t;
+  }
+  return sqrtf(r);
+}
+
+/**
+ * Solves a linear least squares problem to obtain a N degree polynomial that
+ * fits the specified input data as nearly as possible.
+ *
+ * Returns true if a solution is found, false otherwise.
+ *
+ * The input consists of two vectors of data points X and Y with indices 0..m-1
+ * along with a weight vector W of the same size.
+ *
+ * The output is a vector B with indices 0..n that describes a polynomial
+ * that fits the data, such the sum of W[i] * W[i] * abs(Y[i] - (B[0] + B[1]
+ * X[i] * + B[2] X[i]^2 ... B[n] X[i]^n)) for all i between 0 and m-1 is
+ * minimized.
+ *
+ * Accordingly, the weight vector W should be initialized by the caller with the
+ * reciprocal square root of the variance of the error in each input data point.
+ * In other words, an ideal choice for W would be W[i] = 1 / var(Y[i]) = 1 /
+ * stddev(Y[i]).
+ * The weights express the relative importance of each data point.  If the
+ * weights are* all 1, then the data points are considered to be of equal
+ * importance when fitting the polynomial.  It is a good idea to choose weights
+ * that diminish the importance of data points that may have higher than usual
+ * error margins.
+ *
+ * Errors among data points are assumed to be independent.  W is represented
+ * here as a vector although in the literature it is typically taken to be a
+ * diagonal matrix.
+ *
+ * That is to say, the function that generated the input data can be
+ * approximated by y(x) ~= B[0] + B[1] x + B[2] x^2 + ... + B[n] x^n.
+ *
+ * The coefficient of determination (R^2) is also returned to describe the
+ * goodness of fit of the model for the given data.  It is a value between 0
+ * and 1, where 1 indicates perfect correspondence.
+ *
+ * This function first expands the X vector to a m by n matrix A such that
+ * A[i][0] = 1, A[i][1] = X[i], A[i][2] = X[i]^2, ..., A[i][n] = X[i]^n, then
+ * multiplies it by w[i].
+ *
+ * Then it calculates the QR decomposition of A yielding an m by m orthonormal
+ * matrix Q and an m by n upper triangular matrix R.  Because R is upper
+ * triangular (lower part is all zeroes), we can simplify the decomposition into
+ * an m by n matrix Q1 and a n by n matrix R1 such that A = Q1 R1.
+ *
+ * Finally we solve the system of linear equations given by
+ * R1 B = (Qtranspose W Y) to find B.
+ *
+ * For efficiency, we lay out A and Q column-wise in memory because we
+ * frequently operate on the column vectors.  Conversely, we lay out R row-wise.
+ *
+ * http://en.wikipedia.org/wiki/Numerical_methods_for_linear_least_squares
+ * http://en.wikipedia.org/wiki/Gram-Schmidt
+ */
+static bool SolveLeastSquares(const float* x,
+                              const float* y,
+                              const float* w,
+                              uint32_t m,
+                              uint32_t n,
+                              float* out_b) {
+  // MSVC does not support variable-length arrays (used by the original Android
+  // implementation of this function).
+#if defined(COMPILER_MSVC)
+  const uint32_t M_ARRAY_LENGTH =
+      VelocityTracker::kHistorySize;
+  const uint32_t N_ARRAY_LENGTH = VelocityTracker::kPolyDegree;
+  DCHECK_LE(m, M_ARRAY_LENGTH);
+  DCHECK_LE(n, N_ARRAY_LENGTH);
+#else
+  const uint32_t M_ARRAY_LENGTH = m;
+  const uint32_t N_ARRAY_LENGTH = n;
+#endif
+
+  // Expand the X vector to a matrix A, pre-multiplied by the weights.
+  float a[N_ARRAY_LENGTH][M_ARRAY_LENGTH];  // column-major order
+  for (uint32_t h = 0; h < m; h++) {
+    a[0][h] = w[h];
+    for (uint32_t i = 1; i < n; i++) {
+      a[i][h] = a[i - 1][h] * x[h];
+    }
+  }
+
+  // Apply the Gram-Schmidt process to A to obtain its QR decomposition.
+
+  // Orthonormal basis, column-major order.
+  float q[N_ARRAY_LENGTH][M_ARRAY_LENGTH];
+  // Upper triangular matrix, row-major order.
+  float r[N_ARRAY_LENGTH][N_ARRAY_LENGTH];
+  for (uint32_t j = 0; j < n; j++) {
+    for (uint32_t h = 0; h < m; h++) {
+      q[j][h] = a[j][h];
+    }
+    for (uint32_t i = 0; i < j; i++) {
+      float dot = VectorDot(&q[j][0], &q[i][0], m);
+      for (uint32_t h = 0; h < m; h++) {
+        q[j][h] -= dot * q[i][h];
+      }
+    }
+
+    float norm = VectorNorm(&q[j][0], m);
+    if (norm < 0.000001f) {
+      // vectors are linearly dependent or zero so no solution
+      return false;
+    }
+
+    float invNorm = 1.0f / norm;
+    for (uint32_t h = 0; h < m; h++) {
+      q[j][h] *= invNorm;
+    }
+    for (uint32_t i = 0; i < n; i++) {
+      r[j][i] = i < j ? 0 : VectorDot(&q[j][0], &a[i][0], m);
+    }
+  }
+
+  // Solve R B = Qt W Y to find B.  This is easy because R is upper triangular.
+  // We just work from bottom-right to top-left calculating B's coefficients.
+  float wy[M_ARRAY_LENGTH];
+  for (uint32_t h = 0; h < m; h++) {
+    wy[h] = y[h] * w[h];
+  }
+  for (uint32_t i = n; i-- != 0;) {
+    out_b[i] = VectorDot(&q[i][0], wy, m);
+    for (uint32_t j = n - 1; j > i; j--) {
+      out_b[i] -= r[i][j] * out_b[j];
+    }
+    out_b[i] /= r[i][i];
+  }
+
+  return true;
+}
+
+float
+AndroidVelocityTracker::ComputeVelocity(uint32_t aTimestampMs)
+{
+  // Default fallback value.
+  float velocity = 0;
+
+  if (mHistory.IsEmpty()) {
+    return velocity;
+  }
+
+  // Polynomial coefficients describing motion along the axis.
+  float xcoeff[kPolyDegree + 1];
+  for (size_t i = 0; i <= kPolyDegree; i++) {
+    xcoeff[i] = 0;
+  }
+
+  // Iterate over movement samples in reverse time order and collect samples.
+  float pos[kHistorySize];
+  float w[kHistorySize];
+  float time[kHistorySize];
+  uint32_t m = 0;
+  int index = mHistory.Length() - 1;
+  const uint32_t horizon = gfxPrefs::APZVelocityRelevanceTime();
+  const auto& newest_movement = mHistory[index];
+
+  do {
+    const auto& movement = mHistory[index];
+    uint32_t age = newest_movement.first - movement.first;
+    if (age > horizon)
+      break;
+
+    ParentLayerCoord position = movement.second;
+    pos[m] = position;
+    w[m] = 1.0f;
+    time[m] = -static_cast<float>(age) / 1000.0f;  // in seconds
+    index--;
+    m++;
+  } while (index > 0);
+
+  if (m == 0) {
+    return velocity;  // no data
+  }
+
+  // Calculate a least squares polynomial fit.
+
+  // Polynomial degree (number of coefficients), or zero if no information is
+  // available.
+  uint32_t degree = kDegree;
+  if (degree > m - 1) {
+    degree = m - 1;
+  }
+
+  if (degree >= 1) {  // otherwise, no velocity data available
+    uint32_t n = degree + 1;
+    if (SolveLeastSquares(time, pos, w, m, n, xcoeff)) {
+      velocity = xcoeff[1];
+    }
+  }
+
+  // The velocity needs to be negated because the positions represent
+  // touch positions, and the direction of scrolling is opposite to the
+  // direction of the finger's movement.
+  return -velocity / 1000.0f;  // convert to pixels per millisecond
+}
+
+void
+AndroidVelocityTracker::Clear()
+{
+  mHistory.Clear();
+}
+
+}
+}
+
new file mode 100644
--- /dev/null
+++ b/gfx/layers/apz/src/AndroidVelocityTracker.h
@@ -0,0 +1,45 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#ifndef mozilla_layers_AndroidVelocityTracker_h
+#define mozilla_layers_AndroidVelocityTracker_h
+
+#include <utility>
+#include <cstdint>
+
+#include "Axis.h"
+#include "mozilla/Attributes.h"
+#include "mozilla/Maybe.h"
+#include "nsTArray.h"
+
+namespace mozilla {
+namespace layers {
+
+class AndroidVelocityTracker : public VelocityTracker {
+public:
+  explicit AndroidVelocityTracker();
+  void StartTracking(ParentLayerCoord aPos, uint32_t aTimestamp) override;
+  Maybe<float> AddPosition(ParentLayerCoord aPos,
+                           uint32_t aTimestampMs,
+                           bool aIsAxisLocked) override;
+  float HandleDynamicToolbarMovement(uint32_t aStartTimestampMs,
+                                     uint32_t aEndTimestampMs,
+                                     ParentLayerCoord aDelta) override;
+  float ComputeVelocity(uint32_t aTimestampMs) override;
+  void Clear() override;
+private:
+  // A queue of (timestamp, position) pairs; these are the historical
+  // positions at the given timestamps. Timestamps are in milliseconds.
+  nsTArray<std::pair<uint32_t, ParentLayerCoord>> mHistory;
+  // The last time an event was added to the tracker (in milliseconds),
+  // or zero if no events have been added.
+  uint32_t mLastEventTime;
+};
+
+} // namespace layers
+} // namespace mozilla
+
+#endif
--- a/gfx/layers/moz.build
+++ b/gfx/layers/moz.build
@@ -292,16 +292,17 @@ if CONFIG['MOZ_WIDGET_TOOLKIT'] == 'coco
         'MacIOSurfaceImage.cpp',
     ]
 
 if CONFIG['MOZ_WIDGET_TOOLKIT'] == 'android':
     UNIFIED_SOURCES += [
         'apz/src/AndroidAPZ.cpp',
         'apz/src/AndroidDynamicToolbarAnimator.cpp',
         'apz/src/AndroidFlingPhysics.cpp',
+        'apz/src/AndroidVelocityTracker.cpp',
     ]
     EXPORTS.mozilla.layers += [
         'apz/src/AndroidDynamicToolbarAnimator.h',
     ]
 
 UNIFIED_SOURCES += [
     'AnimationHelper.cpp',
     'AnimationInfo.cpp',