include/input/VelocityTracker.h

   1 /*
   2  * Copyright (C) 2012 The Android Open Source Project
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #ifndef _LIBINPUT_VELOCITY_TRACKER_H
  18 #define _LIBINPUT_VELOCITY_TRACKER_H
  19
  20 #include <input/Input.h>
  21 #include <utils/Timers.h>
  22 #include <utils/BitSet.h>
  23
  24 namespace android {
  25
  26 class VelocityTrackerStrategy;
  27
  28 /*
  29  * Calculates the velocity of pointer movements over time.
  30  */
  31 class VelocityTracker {
  32 public:
  33     struct Position {
  34         float x, y;
  35     };
  36
  37     struct Estimator {
  38         static const size_t MAX_DEGREE = 4;
  39
  40         // Estimator time base.
  41         nsecs_t time;
  42
  43         // Polynomial coefficients describing motion in X and Y.
  44         float xCoeff[MAX_DEGREE + 1], yCoeff[MAX_DEGREE + 1];
  45
  46         // Polynomial degree (number of coefficients), or zero if no information is
  47         // available.
  48         uint32_t degree;
  49
  50         // Confidence (coefficient of determination), between 0 (no fit) and 1 (perfect fit).
  51         float confidence;
  52
  53         inline void clear() {
  54             time = 0;
  55             degree = 0;
  56             confidence = 0;
  57             for (size_t i = 0; i <= MAX_DEGREE; i++) {
  58                 xCoeff[i] = 0;
  59                 yCoeff[i] = 0;
  60             }
  61         }
  62     };
  63
  64     // Creates a velocity tracker using the specified strategy.
  65     // If strategy is NULL, uses the default strategy for the platform.
  66     VelocityTracker(const char* strategy = NULL);
  67
  68     ~VelocityTracker();
  69
  70     // Resets the velocity tracker state.
  71     void clear();
  72
  73     // Resets the velocity tracker state for specific pointers.
  74     // Call this method when some pointers have changed and may be reusing
  75     // an id that was assigned to a different pointer earlier.
  76     void clearPointers(BitSet32 idBits);
  77
  78     // Adds movement information for a set of pointers.
  79     // The idBits bitfield specifies the pointer ids of the pointers whose positions
  80     // are included in the movement.
  81     // The positions array contains position information for each pointer in order by
  82     // increasing id.  Its size should be equal to the number of one bits in idBits.
  83     void addMovement(nsecs_t eventTime, BitSet32 idBits, const Position* positions);
  84
  85     // Adds movement information for all pointers in a MotionEvent, including historical samples.
  86     void addMovement(const MotionEvent* event);
  87
  88     // Gets the velocity of the specified pointer id in position units per second.
  89     // Returns false and sets the velocity components to zero if there is
  90     // insufficient movement information for the pointer.
  91     bool getVelocity(uint32_t id, float* outVx, float* outVy) const;
  92
  93     // Gets an estimator for the recent movements of the specified pointer id.
  94     // Returns false and clears the estimator if there is no information available
  95     // about the pointer.
  96     bool getEstimator(uint32_t id, Estimator* outEstimator) const;
  97
  98     // Gets the active pointer id, or -1 if none.
  99     inline int32_t getActivePointerId() const { return mActivePointerId; }
 100
 101     // Gets a bitset containing all pointer ids from the most recent movement.
 102     inline BitSet32 getCurrentPointerIdBits() const { return mCurrentPointerIdBits; }
 103
 104 private:
 105     static const char* DEFAULT_STRATEGY;
 106
 107     nsecs_t mLastEventTime;
 108     BitSet32 mCurrentPointerIdBits;
 109     int32_t mActivePointerId;
 110     VelocityTrackerStrategy* mStrategy;
 111
 112     bool configureStrategy(const char* strategy);
 113
 114     static VelocityTrackerStrategy* createStrategy(const char* strategy);
 115 };
 116
 117
 118 /*
 119  * Implements a particular velocity tracker algorithm.
 120  */
 121 class VelocityTrackerStrategy {
 122 protected:
 123     VelocityTrackerStrategy() { }
 124
 125 public:
 126     virtual ~VelocityTrackerStrategy() { }
 127
 128     virtual void clear() = 0;
 129     virtual void clearPointers(BitSet32 idBits) = 0;
 130     virtual void addMovement(nsecs_t eventTime, BitSet32 idBits,
 131             const VelocityTracker::Position* positions) = 0;
 132     virtual bool getEstimator(uint32_t id, VelocityTracker::Estimator* outEstimator) const = 0;
 133 };
 134
 135
 136 /*
 137  * Velocity tracker algorithm based on least-squares linear regression.
 138  */
 139 class LeastSquaresVelocityTrackerStrategy : public VelocityTrackerStrategy {
 140 public:
 141     enum Weighting {
 142         // No weights applied.  All data points are equally reliable.
 143         WEIGHTING_NONE,
 144
 145         // Weight by time delta.  Data points clustered together are weighted less.
 146         WEIGHTING_DELTA,
 147
 148         // Weight such that points within a certain horizon are weighed more than those
 149         // outside of that horizon.
 150         WEIGHTING_CENTRAL,
 151
 152         // Weight such that points older than a certain amount are weighed less.
 153         WEIGHTING_RECENT,
 154     };
 155
 156     // Degree must be no greater than Estimator::MAX_DEGREE.
 157     LeastSquaresVelocityTrackerStrategy(uint32_t degree, Weighting weighting = WEIGHTING_NONE);
 158     virtual ~LeastSquaresVelocityTrackerStrategy();
 159
 160     virtual void clear();
 161     virtual void clearPointers(BitSet32 idBits);
 162     virtual void addMovement(nsecs_t eventTime, BitSet32 idBits,
 163             const VelocityTracker::Position* positions);
 164     virtual bool getEstimator(uint32_t id, VelocityTracker::Estimator* outEstimator) const;
 165
 166 private:
 167     // Sample horizon.
 168     // We don't use too much history by default since we want to react to quick
 169     // changes in direction.
 170     static const nsecs_t HORIZON = 100 * 1000000; // 100 ms
 171
 172     // Number of samples to keep.
 173     static const uint32_t HISTORY_SIZE = 20;
 174
 175     struct Movement {
 176         nsecs_t eventTime;
 177         BitSet32 idBits;
 178         VelocityTracker::Position positions[MAX_POINTERS];
 179
 180         inline const VelocityTracker::Position& getPosition(uint32_t id) const {
 181             return positions[idBits.getIndexOfBit(id)];
 182         }
 183     };
 184
 185     float chooseWeight(uint32_t index) const;
 186
 187     const uint32_t mDegree;
 188     const Weighting mWeighting;
 189     uint32_t mIndex;
 190     Movement mMovements[HISTORY_SIZE];
 191 };
 192
 193
 194 /*
 195  * Velocity tracker algorithm that uses an IIR filter.
 196  */
 197 class IntegratingVelocityTrackerStrategy : public VelocityTrackerStrategy {
 198 public:
 199     // Degree must be 1 or 2.
 200     IntegratingVelocityTrackerStrategy(uint32_t degree);
 201     ~IntegratingVelocityTrackerStrategy();
 202
 203     virtual void clear();
 204     virtual void clearPointers(BitSet32 idBits);
 205     virtual void addMovement(nsecs_t eventTime, BitSet32 idBits,
 206             const VelocityTracker::Position* positions);
 207     virtual bool getEstimator(uint32_t id, VelocityTracker::Estimator* outEstimator) const;
 208
 209 private:
 210     // Current state estimate for a particular pointer.
 211     struct State {
 212         nsecs_t updateTime;
 213         uint32_t degree;
 214
 215         float xpos, xvel, xaccel;
 216         float ypos, yvel, yaccel;
 217     };
 218
 219     const uint32_t mDegree;
 220     BitSet32 mPointerIdBits;
 221     State mPointerState[MAX_POINTER_ID + 1];
 222
 223     void initState(State& state, nsecs_t eventTime, float xpos, float ypos) const;
 224     void updateState(State& state, nsecs_t eventTime, float xpos, float ypos) const;
 225     void populateEstimator(const State& state, VelocityTracker::Estimator* outEstimator) const;
 226 };
 227
 228
 229 /*
 230  * Velocity tracker strategy used prior to ICS.
 231  */
 232 class LegacyVelocityTrackerStrategy : public VelocityTrackerStrategy {
 233 public:
 234     LegacyVelocityTrackerStrategy();
 235     virtual ~LegacyVelocityTrackerStrategy();
 236
 237     virtual void clear();
 238     virtual void clearPointers(BitSet32 idBits);
 239     virtual void addMovement(nsecs_t eventTime, BitSet32 idBits,
 240             const VelocityTracker::Position* positions);
 241     virtual bool getEstimator(uint32_t id, VelocityTracker::Estimator* outEstimator) const;
 242
 243 private:
 244     // Oldest sample to consider when calculating the velocity.
 245     static const nsecs_t HORIZON = 200 * 1000000; // 100 ms
 246
 247     // Number of samples to keep.
 248     static const uint32_t HISTORY_SIZE = 20;
 249
 250     // The minimum duration between samples when estimating velocity.
 251     static const nsecs_t MIN_DURATION = 10 * 1000000; // 10 ms
 252
 253     struct Movement {
 254         nsecs_t eventTime;
 255         BitSet32 idBits;
 256         VelocityTracker::Position positions[MAX_POINTERS];
 257
 258         inline const VelocityTracker::Position& getPosition(uint32_t id) const {
 259             return positions[idBits.getIndexOfBit(id)];
 260         }
 261     };
 262
 263     uint32_t mIndex;
 264     Movement mMovements[HISTORY_SIZE];
 265 };
 266
 267 } // namespace android
 268
 269 #endif // _LIBINPUT_VELOCITY_TRACKER_H