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 
clearEstimator53         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.
getActivePointerId()99     inline int32_t getActivePointerId() const { return mActivePointerId; }
100 
101     // Gets a bitset containing all pointer ids from the most recent movement.
getCurrentPointerIdBits()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:
VelocityTrackerStrategy()123     VelocityTrackerStrategy() { }
124 
125 public:
~VelocityTrackerStrategy()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 
getPositionMovement180         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 
getPositionMovement258         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