1 files changed, 194 insertions, 8 deletions

diff --git a/libs/input/VelocityTracker.cpp b/libs/input/VelocityTracker.cpp
index 62acea360e..cc74b9b5cf 100644
--- a/libs/input/VelocityTracker.cpp
+++ b/libs/input/VelocityTracker.cpp
@@ -105,7 +105,7 @@ static std::string matrixToString(const float* a, uint32_t m, uint32_t n, bool r
 // this is the strategy that applications will actually use.  Be very careful
 // when adjusting the default strategy because it can dramatically affect
 // (often in a bad way) the user experience.
-const char* VelocityTracker::DEFAULT_STRATEGY = "lsq2";
+const char* VelocityTracker::DEFAULT_STRATEGY = "impulse";
 
 VelocityTracker::VelocityTracker(const char* strategy) :
         mLastEventTime(0), mCurrentPointerIdBits(0), mActivePointerId(-1) {
@@ -141,6 +141,11 @@ bool VelocityTracker::configureStrategy(const char* strategy) {
 }
 
 VelocityTrackerStrategy* VelocityTracker::createStrategy(const char* strategy) {
+    if (!strcmp("impulse", strategy)) {
+        // Physical model of pushing an object.  Quality: VERY GOOD.
+        // Works with duplicate coordinates, unclean finger liftoff.
+        return new ImpulseVelocityTrackerStrategy();
+    }
     if (!strcmp("lsq1", strategy)) {
         // 1st order least squares.  Quality: POOR.
         // Frequently underfits the touch data especially when the finger accelerates
@@ -352,9 +357,6 @@ bool VelocityTracker::getEstimator(uint32_t id, Estimator* outEstimator) const {
 
 // --- LeastSquaresVelocityTrackerStrategy ---
 
-const nsecs_t LeastSquaresVelocityTrackerStrategy::HORIZON;
-const uint32_t LeastSquaresVelocityTrackerStrategy::HISTORY_SIZE;
-
 LeastSquaresVelocityTrackerStrategy::LeastSquaresVelocityTrackerStrategy(
         uint32_t degree, Weighting weighting) :
         mDegree(degree), mWeighting(weighting) {
@@ -863,10 +865,6 @@ void IntegratingVelocityTrackerStrategy::populateEstimator(const State& state,
 
 // --- LegacyVelocityTrackerStrategy ---
 
-const nsecs_t LegacyVelocityTrackerStrategy::HORIZON;
-const uint32_t LegacyVelocityTrackerStrategy::HISTORY_SIZE;
-const nsecs_t LegacyVelocityTrackerStrategy::MIN_DURATION;
-
 LegacyVelocityTrackerStrategy::LegacyVelocityTrackerStrategy() {
     clear();
 }
@@ -979,4 +977,192 @@ bool LegacyVelocityTrackerStrategy::getEstimator(uint32_t id,
     return true;
 }
 
+// --- ImpulseVelocityTrackerStrategy ---
+
+ImpulseVelocityTrackerStrategy::ImpulseVelocityTrackerStrategy() {
+    clear();
+}
+
+ImpulseVelocityTrackerStrategy::~ImpulseVelocityTrackerStrategy() {
+}
+
+void ImpulseVelocityTrackerStrategy::clear() {
+    mIndex = 0;
+    mMovements[0].idBits.clear();
+}
+
+void ImpulseVelocityTrackerStrategy::clearPointers(BitSet32 idBits) {
+    BitSet32 remainingIdBits(mMovements[mIndex].idBits.value & ~idBits.value);
+    mMovements[mIndex].idBits = remainingIdBits;
+}
+
+void ImpulseVelocityTrackerStrategy::addMovement(nsecs_t eventTime, BitSet32 idBits,
+        const VelocityTracker::Position* positions) {
+    if (++mIndex == HISTORY_SIZE) {
+        mIndex = 0;
+    }
+
+    Movement& movement = mMovements[mIndex];
+    movement.eventTime = eventTime;
+    movement.idBits = idBits;
+    uint32_t count = idBits.count();
+    for (uint32_t i = 0; i < count; i++) {
+        movement.positions[i] = positions[i];
+    }
+}
+
+/**
+ * Calculate the total impulse provided to the screen and the resulting velocity.
+ *
+ * The touchscreen is modeled as a physical object.
+ * Initial condition is discussed below, but for now suppose that v(t=0) = 0
+ *
+ * The kinetic energy of the object at the release is E=0.5*m*v^2
+ * Then vfinal = sqrt(2E/m). The goal is to calculate E.
+ *
+ * The kinetic energy at the release is equal to the total work done on the object by the finger.
+ * The total work W is the sum of all dW along the path.
+ *
+ * dW = F*dx, where dx is the piece of path traveled.
+ * Force is change of momentum over time, F = dp/dt = m dv/dt.
+ * Then substituting:
+ * dW = m (dv/dt) * dx = m * v * dv
+ *
+ * Summing along the path, we get:
+ * W = sum(dW) = sum(m * v * dv) = m * sum(v * dv)
+ * Since the mass stays constant, the equation for final velocity is:
+ * vfinal = sqrt(2*sum(v * dv))
+ *
+ * Here,
+ * dv : change of velocity = (v[i+1]-v[i])
+ * dx : change of distance = (x[i+1]-x[i])
+ * dt : change of time = (t[i+1]-t[i])
+ * v : instantaneous velocity = dx/dt
+ *
+ * The final formula is:
+ * vfinal = sqrt(2) * sqrt(sum((v[i]-v[i-1])*|v[i]|)) for all i
+ * The absolute value is needed to properly account for the sign. If the velocity over a
+ * particular segment descreases, then this indicates braking, which means that negative
+ * work was done. So for two positive, but decreasing, velocities, this contribution would be
+ * negative and will cause a smaller final velocity.
+ *
+ * Initial condition
+ * There are two ways to deal with initial condition:
+ * 1) Assume that v(0) = 0, which would mean that the screen is initially at rest.
+ * This is not entirely accurate. We are only taking the past X ms of touch data, where X is
+ * currently equal to 100. However, a touch event that created a fling probably lasted for longer
+ * than that, which would mean that the user has already been interacting with the touchscreen
+ * and it has probably already been moving.
+ * 2) Assume that the touchscreen has already been moving at a certain velocity, calculate this
+ * initial velocity and the equivalent energy, and start with this initial energy.
+ * Consider an example where we have the following data, consisting of 3 points:
+ *                 time: t0, t1, t2
+ *                 x   : x0, x1, x2
+ *                 v   : 0 , v1, v2
+ * Here is what will happen in each of these scenarios:
+ * 1) By directly applying the formula above with the v(0) = 0 boundary condition, we will get
+ * vfinal = sqrt(2*(|v1|*(v1-v0) + |v2|*(v2-v1))). This can be simplified since v0=0
+ * vfinal = sqrt(2*(|v1|*v1 + |v2|*(v2-v1))) = sqrt(2*(v1^2 + |v2|*(v2 - v1)))
+ * since velocity is a real number
+ * 2) If we treat the screen as already moving, then it must already have an energy (per mass)
+ * equal to 1/2*v1^2. Then the initial energy should be 1/2*v1*2, and only the second segment
+ * will contribute to the total kinetic energy (since we can effectively consider that v0=v1).
+ * This will give the following expression for the final velocity:
+ * vfinal = sqrt(2*(1/2*v1^2 + |v2|*(v2-v1)))
+ * This analysis can be generalized to an arbitrary number of samples.
+ *
+ *
+ * Comparing the two equations above, we see that the only mathematical difference
+ * is the factor of 1/2 in front of the first velocity term.
+ * This boundary condition would allow for the "proper" calculation of the case when all of the
+ * samples are equally spaced in time and distance, which should suggest a constant velocity.
+ *
+ * Note that approach 2) is sensitive to the proper ordering of the data in time, since
+ * the boundary condition must be applied to the oldest sample to be accurate.
+ */
+static float calculateImpulseVelocity(const nsecs_t* t, const float* x, size_t count) {
+    // The input should be in reversed time order (most recent sample at index i=0)
+    // t[i] is in nanoseconds, but due to FP arithmetic, convert to seconds inside this function
+    static constexpr float NANOS_PER_SECOND = 1E-9;
+    static constexpr float sqrt2 = 1.41421356237;
+
+    if (count < 2) {
+        return 0; // if 0 or 1 points, velocity is zero
+    }
+    if (t[1] > t[0]) { // Algorithm will still work, but not perfectly
+        ALOGE("Samples provided to calculateImpulseVelocity in the wrong order");
+    }
+    if (count == 2) { // if 2 points, basic linear calculation
+        if (t[1] == t[0]) {
+            ALOGE("Events have identical time stamps t=%" PRId64 ", setting velocity = 0", t[0]);
+            return 0;
+        }
+        return (x[1] - x[0]) / (NANOS_PER_SECOND * (t[1] - t[0]));
+    }
+    // Guaranteed to have at least 3 points here
+    float work = 0;
+    float vprev, vcurr; // v[i-1] and v[i], respectively
+    vprev = 0;
+    for (size_t i = count - 1; i > 0 ; i--) { // start with the oldest sample and go forward in time
+        if (t[i] == t[i-1]) {
+            ALOGE("Events have identical time stamps t=%" PRId64 ", skipping sample", t[i]);
+            continue;
+        }
+        vcurr = (x[i] - x[i-1]) / (NANOS_PER_SECOND * (t[i] - t[i-1]));
+        work += (vcurr - vprev) * fabsf(vcurr);
+        if (i == count - 1) {
+            work *= 0.5; // initial condition, case 2) above
+        }
+        vprev = vcurr;
+    }
+    return (work < 0 ? -1.0 : 1.0) * sqrtf(fabsf(work)) * sqrt2;
+}
+
+bool ImpulseVelocityTrackerStrategy::getEstimator(uint32_t id,
+        VelocityTracker::Estimator* outEstimator) const {
+    outEstimator->clear();
+
+    // Iterate over movement samples in reverse time order and collect samples.
+    float x[HISTORY_SIZE];
+    float y[HISTORY_SIZE];
+    nsecs_t time[HISTORY_SIZE];
+    size_t m = 0; // number of points that will be used for fitting
+    size_t index = mIndex;
+    const Movement& newestMovement = mMovements[mIndex];
+    do {
+        const Movement& movement = mMovements[index];
+        if (!movement.idBits.hasBit(id)) {
+            break;
+        }
+
+        nsecs_t age = newestMovement.eventTime - movement.eventTime;
+        if (age > HORIZON) {
+            break;
+        }
+
+        const VelocityTracker::Position& position = movement.getPosition(id);
+        x[m] = position.x;
+        y[m] = position.y;
+        time[m] = movement.eventTime;
+        index = (index == 0 ? HISTORY_SIZE : index) - 1;
+    } while (++m < HISTORY_SIZE);
+
+    if (m == 0) {
+        return false; // no data
+    }
+    outEstimator->xCoeff[0] = 0;
+    outEstimator->yCoeff[0] = 0;
+    outEstimator->xCoeff[1] = calculateImpulseVelocity(time, x, m);
+    outEstimator->yCoeff[1] = calculateImpulseVelocity(time, y, m);
+    outEstimator->xCoeff[2] = 0;
+    outEstimator->yCoeff[2] = 0;
+    outEstimator->time = newestMovement.eventTime;
+    outEstimator->degree = 2; // similar results to 2nd degree fit
+    outEstimator->confidence = 1;
+#if DEBUG_STRATEGY
+    ALOGD("velocity: (%f, %f)", outEstimator->xCoeff[1], outEstimator->yCoeff[1]);
+#endif
+    return true;
+}
+
 } // namespace android