Home | History | Annotate | Download | only in input
      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
    270