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
24namespace android {
25
26class VelocityTrackerStrategy;
27
28/*
29 * Calculates the velocity of pointer movements over time.
30 */
31class VelocityTracker {
32public:
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
104private:
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 */
121class VelocityTrackerStrategy {
122protected:
123    VelocityTrackerStrategy() { }
124
125public:
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 */
139class LeastSquaresVelocityTrackerStrategy : public VelocityTrackerStrategy {
140public:
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
166private:
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 */
197class IntegratingVelocityTrackerStrategy : public VelocityTrackerStrategy {
198public:
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
209private:
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 */
232class LegacyVelocityTrackerStrategy : public VelocityTrackerStrategy {
233public:
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
243private:
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