blob: f6556d6712d6f72a86b40a2c523be829844fe840 [file] [log] [blame]
Jeff Brown5912f952013-07-01 19:10:31 -07001/*
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
Prabir Pradhanc08b0db2022-09-10 00:57:15 +000017#pragma once
Jeff Brown5912f952013-07-01 19:10:31 -070018
19#include <input/Input.h>
Jeff Brown5912f952013-07-01 19:10:31 -070020#include <utils/BitSet.h>
Chris Yef8591482020-04-17 11:49:17 -070021#include <utils/Timers.h>
Yeabkal Wubshit384ab0f2022-09-09 16:39:18 +000022#include <map>
23#include <set>
Jeff Brown5912f952013-07-01 19:10:31 -070024
25namespace android {
26
27class VelocityTrackerStrategy;
28
29/*
30 * Calculates the velocity of pointer movements over time.
31 */
32class VelocityTracker {
33public:
Chris Yef8591482020-04-17 11:49:17 -070034 enum class Strategy : int32_t {
35 DEFAULT = -1,
36 MIN = 0,
37 IMPULSE = 0,
38 LSQ1 = 1,
39 LSQ2 = 2,
40 LSQ3 = 3,
41 WLSQ2_DELTA = 4,
42 WLSQ2_CENTRAL = 5,
43 WLSQ2_RECENT = 6,
44 INT1 = 7,
45 INT2 = 8,
46 LEGACY = 9,
47 MAX = LEGACY,
48 };
49
Jeff Brown5912f952013-07-01 19:10:31 -070050 struct Estimator {
51 static const size_t MAX_DEGREE = 4;
52
53 // Estimator time base.
54 nsecs_t time;
55
Yeabkal Wubshit384ab0f2022-09-09 16:39:18 +000056 // Polynomial coefficients describing motion.
57 float coeff[MAX_DEGREE + 1];
Jeff Brown5912f952013-07-01 19:10:31 -070058
59 // Polynomial degree (number of coefficients), or zero if no information is
60 // available.
61 uint32_t degree;
62
63 // Confidence (coefficient of determination), between 0 (no fit) and 1 (perfect fit).
64 float confidence;
65
66 inline void clear() {
67 time = 0;
68 degree = 0;
69 confidence = 0;
70 for (size_t i = 0; i <= MAX_DEGREE; i++) {
Yeabkal Wubshit384ab0f2022-09-09 16:39:18 +000071 coeff[i] = 0;
Jeff Brown5912f952013-07-01 19:10:31 -070072 }
73 }
74 };
75
Yeabkal Wubshit384ab0f2022-09-09 16:39:18 +000076 /*
77 * Contains all available velocity data from a VelocityTracker.
78 */
79 struct ComputedVelocity {
80 inline std::optional<float> getVelocity(int32_t axis, uint32_t id) const {
81 const auto& axisVelocities = mVelocities.find(axis);
82 if (axisVelocities == mVelocities.end()) {
83 return {};
84 }
85
86 const auto& axisIdVelocity = axisVelocities->second.find(id);
87 if (axisIdVelocity == axisVelocities->second.end()) {
88 return {};
89 }
90
91 return axisIdVelocity->second;
92 }
93
94 inline void addVelocity(int32_t axis, uint32_t id, float velocity) {
95 mVelocities[axis][id] = velocity;
96 }
97
98 private:
99 std::map<int32_t /*axis*/, std::map<int32_t /*pointerId*/, float /*velocity*/>> mVelocities;
100 };
101
102 // Creates a velocity tracker using the specified strategy for each supported axis.
Chris Yef8591482020-04-17 11:49:17 -0700103 // If strategy is not provided, uses the default strategy for the platform.
Yeabkal Wubshit384ab0f2022-09-09 16:39:18 +0000104 // TODO(b/32830165): support axis-specific strategies.
Chris Yef8591482020-04-17 11:49:17 -0700105 VelocityTracker(const Strategy strategy = Strategy::DEFAULT);
Jeff Brown5912f952013-07-01 19:10:31 -0700106
107 ~VelocityTracker();
108
109 // Resets the velocity tracker state.
110 void clear();
111
112 // Resets the velocity tracker state for specific pointers.
113 // Call this method when some pointers have changed and may be reusing
114 // an id that was assigned to a different pointer earlier.
115 void clearPointers(BitSet32 idBits);
116
117 // Adds movement information for a set of pointers.
Yeabkal Wubshit384ab0f2022-09-09 16:39:18 +0000118 // The idBits bitfield specifies the pointer ids of the pointers whose data points
Jeff Brown5912f952013-07-01 19:10:31 -0700119 // are included in the movement.
Yeabkal Wubshit384ab0f2022-09-09 16:39:18 +0000120 // The positions map contains a mapping of an axis to positions array.
121 // The positions arrays contain information for each pointer in order by increasing id.
122 // Each array's size should be equal to the number of one bits in idBits.
123 void addMovement(nsecs_t eventTime, BitSet32 idBits,
124 const std::map<int32_t, std::vector<float>>& positions);
Jeff Brown5912f952013-07-01 19:10:31 -0700125
126 // Adds movement information for all pointers in a MotionEvent, including historical samples.
127 void addMovement(const MotionEvent* event);
128
Yeabkal Wubshit384ab0f2022-09-09 16:39:18 +0000129 // Returns the velocity of the specified pointer id and axis in position units per second.
130 // Returns empty optional if there is insufficient movement information for the pointer, or if
131 // the given axis is not supported for velocity tracking.
132 std::optional<float> getVelocity(int32_t axis, uint32_t id) const;
Jeff Brown5912f952013-07-01 19:10:31 -0700133
Yeabkal Wubshit384ab0f2022-09-09 16:39:18 +0000134 // Returns a ComputedVelocity instance with all available velocity data, using the given units
135 // (reference: units == 1 means "per millisecond"), and clamping each velocity between
136 // [-maxVelocity, maxVelocity], inclusive.
137 ComputedVelocity getComputedVelocity(int32_t units, float maxVelocity);
138
139 // Gets an estimator for the recent movements of the specified pointer id for the given axis.
Jeff Brown5912f952013-07-01 19:10:31 -0700140 // Returns false and clears the estimator if there is no information available
141 // about the pointer.
Yeabkal Wubshit384ab0f2022-09-09 16:39:18 +0000142 bool getEstimator(int32_t axis, uint32_t id, Estimator* outEstimator) const;
Jeff Brown5912f952013-07-01 19:10:31 -0700143
144 // Gets the active pointer id, or -1 if none.
145 inline int32_t getActivePointerId() const { return mActivePointerId; }
146
Jeff Brown5912f952013-07-01 19:10:31 -0700147private:
Jeff Brown5912f952013-07-01 19:10:31 -0700148 nsecs_t mLastEventTime;
149 BitSet32 mCurrentPointerIdBits;
150 int32_t mActivePointerId;
Jeff Brown5912f952013-07-01 19:10:31 -0700151
Yeabkal Wubshit47ff7082022-09-10 23:09:15 -0700152 // An override strategy passed in the constructor to be used for all axes.
153 // This strategy will apply to all axes, unless the default strategy is specified here.
154 // When default strategy is specified, then each axis will use a potentially different strategy
155 // based on a hardcoded mapping.
156 const Strategy mOverrideStrategy;
157 // Maps axes to their respective VelocityTrackerStrategy instances.
158 // Note that, only axes that have had MotionEvents (and not all supported axes) will be here.
159 std::map<int32_t /*axis*/, std::unique_ptr<VelocityTrackerStrategy>> mConfiguredStrategies;
160
161 void configureStrategy(int32_t axis);
Jeff Brown5912f952013-07-01 19:10:31 -0700162
Yeabkal Wubshit0bb5e592022-09-14 01:22:28 -0700163 static std::unique_ptr<VelocityTrackerStrategy> createStrategy(const Strategy strategy,
164 bool isCumulative);
Jeff Brown5912f952013-07-01 19:10:31 -0700165};
166
167
168/*
169 * Implements a particular velocity tracker algorithm.
170 */
171class VelocityTrackerStrategy {
172protected:
173 VelocityTrackerStrategy() { }
174
175public:
176 virtual ~VelocityTrackerStrategy() { }
177
Jeff Brown5912f952013-07-01 19:10:31 -0700178 virtual void clearPointers(BitSet32 idBits) = 0;
179 virtual void addMovement(nsecs_t eventTime, BitSet32 idBits,
Yeabkal Wubshit384ab0f2022-09-09 16:39:18 +0000180 const std::vector<float>& positions) = 0;
Jeff Brown5912f952013-07-01 19:10:31 -0700181 virtual bool getEstimator(uint32_t id, VelocityTracker::Estimator* outEstimator) const = 0;
182};
183
184
185/*
186 * Velocity tracker algorithm based on least-squares linear regression.
187 */
188class LeastSquaresVelocityTrackerStrategy : public VelocityTrackerStrategy {
189public:
190 enum Weighting {
191 // No weights applied. All data points are equally reliable.
192 WEIGHTING_NONE,
193
194 // Weight by time delta. Data points clustered together are weighted less.
195 WEIGHTING_DELTA,
196
197 // Weight such that points within a certain horizon are weighed more than those
198 // outside of that horizon.
199 WEIGHTING_CENTRAL,
200
201 // Weight such that points older than a certain amount are weighed less.
202 WEIGHTING_RECENT,
203 };
204
205 // Degree must be no greater than Estimator::MAX_DEGREE.
206 LeastSquaresVelocityTrackerStrategy(uint32_t degree, Weighting weighting = WEIGHTING_NONE);
207 virtual ~LeastSquaresVelocityTrackerStrategy();
208
Jeff Brown5912f952013-07-01 19:10:31 -0700209 virtual void clearPointers(BitSet32 idBits);
Siarhei Vishniakouae0f9902020-09-14 19:23:31 -0500210 void addMovement(nsecs_t eventTime, BitSet32 idBits,
Yeabkal Wubshit384ab0f2022-09-09 16:39:18 +0000211 const std::vector<float>& positions) override;
Jeff Brown5912f952013-07-01 19:10:31 -0700212 virtual bool getEstimator(uint32_t id, VelocityTracker::Estimator* outEstimator) const;
213
214private:
215 // Sample horizon.
216 // We don't use too much history by default since we want to react to quick
217 // changes in direction.
218 static const nsecs_t HORIZON = 100 * 1000000; // 100 ms
219
220 // Number of samples to keep.
221 static const uint32_t HISTORY_SIZE = 20;
222
223 struct Movement {
224 nsecs_t eventTime;
225 BitSet32 idBits;
Yeabkal Wubshit384ab0f2022-09-09 16:39:18 +0000226 float positions[MAX_POINTERS];
Jeff Brown5912f952013-07-01 19:10:31 -0700227
Yeabkal Wubshit384ab0f2022-09-09 16:39:18 +0000228 inline float getPosition(uint32_t id) const { return positions[idBits.getIndexOfBit(id)]; }
Jeff Brown5912f952013-07-01 19:10:31 -0700229 };
230
231 float chooseWeight(uint32_t index) const;
232
233 const uint32_t mDegree;
234 const Weighting mWeighting;
235 uint32_t mIndex;
236 Movement mMovements[HISTORY_SIZE];
237};
238
239
240/*
241 * Velocity tracker algorithm that uses an IIR filter.
242 */
243class IntegratingVelocityTrackerStrategy : public VelocityTrackerStrategy {
244public:
245 // Degree must be 1 or 2.
246 IntegratingVelocityTrackerStrategy(uint32_t degree);
247 ~IntegratingVelocityTrackerStrategy();
248
Jeff Brown5912f952013-07-01 19:10:31 -0700249 virtual void clearPointers(BitSet32 idBits);
Siarhei Vishniakouae0f9902020-09-14 19:23:31 -0500250 void addMovement(nsecs_t eventTime, BitSet32 idBits,
Yeabkal Wubshit384ab0f2022-09-09 16:39:18 +0000251 const std::vector<float>& positions) override;
Jeff Brown5912f952013-07-01 19:10:31 -0700252 virtual bool getEstimator(uint32_t id, VelocityTracker::Estimator* outEstimator) const;
253
254private:
255 // Current state estimate for a particular pointer.
256 struct State {
257 nsecs_t updateTime;
258 uint32_t degree;
259
Yeabkal Wubshit384ab0f2022-09-09 16:39:18 +0000260 float pos, vel, accel;
Jeff Brown5912f952013-07-01 19:10:31 -0700261 };
262
263 const uint32_t mDegree;
264 BitSet32 mPointerIdBits;
265 State mPointerState[MAX_POINTER_ID + 1];
266
Yeabkal Wubshit384ab0f2022-09-09 16:39:18 +0000267 void initState(State& state, nsecs_t eventTime, float pos) const;
268 void updateState(State& state, nsecs_t eventTime, float pos) const;
Jeff Brown5912f952013-07-01 19:10:31 -0700269 void populateEstimator(const State& state, VelocityTracker::Estimator* outEstimator) const;
270};
271
272
273/*
274 * Velocity tracker strategy used prior to ICS.
275 */
276class LegacyVelocityTrackerStrategy : public VelocityTrackerStrategy {
277public:
278 LegacyVelocityTrackerStrategy();
279 virtual ~LegacyVelocityTrackerStrategy();
280
Jeff Brown5912f952013-07-01 19:10:31 -0700281 virtual void clearPointers(BitSet32 idBits);
Siarhei Vishniakouae0f9902020-09-14 19:23:31 -0500282 void addMovement(nsecs_t eventTime, BitSet32 idBits,
Yeabkal Wubshit384ab0f2022-09-09 16:39:18 +0000283 const std::vector<float>& positions) override;
Jeff Brown5912f952013-07-01 19:10:31 -0700284 virtual bool getEstimator(uint32_t id, VelocityTracker::Estimator* outEstimator) const;
285
286private:
287 // Oldest sample to consider when calculating the velocity.
288 static const nsecs_t HORIZON = 200 * 1000000; // 100 ms
289
290 // Number of samples to keep.
291 static const uint32_t HISTORY_SIZE = 20;
292
293 // The minimum duration between samples when estimating velocity.
294 static const nsecs_t MIN_DURATION = 10 * 1000000; // 10 ms
295
296 struct Movement {
297 nsecs_t eventTime;
298 BitSet32 idBits;
Yeabkal Wubshit384ab0f2022-09-09 16:39:18 +0000299 float positions[MAX_POINTERS];
Jeff Brown5912f952013-07-01 19:10:31 -0700300
Yeabkal Wubshit384ab0f2022-09-09 16:39:18 +0000301 inline float getPosition(uint32_t id) const { return positions[idBits.getIndexOfBit(id)]; }
Jeff Brown5912f952013-07-01 19:10:31 -0700302 };
303
304 uint32_t mIndex;
305 Movement mMovements[HISTORY_SIZE];
306};
307
Siarhei Vishniakou00a4ea92017-06-08 21:43:20 +0100308class ImpulseVelocityTrackerStrategy : public VelocityTrackerStrategy {
309public:
Yeabkal Wubshit0bb5e592022-09-14 01:22:28 -0700310 ImpulseVelocityTrackerStrategy(bool deltaValues);
Siarhei Vishniakou00a4ea92017-06-08 21:43:20 +0100311 virtual ~ImpulseVelocityTrackerStrategy();
312
Siarhei Vishniakou00a4ea92017-06-08 21:43:20 +0100313 virtual void clearPointers(BitSet32 idBits);
Siarhei Vishniakouae0f9902020-09-14 19:23:31 -0500314 void addMovement(nsecs_t eventTime, BitSet32 idBits,
Yeabkal Wubshit384ab0f2022-09-09 16:39:18 +0000315 const std::vector<float>& positions) override;
Siarhei Vishniakou00a4ea92017-06-08 21:43:20 +0100316 virtual bool getEstimator(uint32_t id, VelocityTracker::Estimator* outEstimator) const;
317
318private:
319 // Sample horizon.
320 // We don't use too much history by default since we want to react to quick
321 // changes in direction.
322 static constexpr nsecs_t HORIZON = 100 * 1000000; // 100 ms
323
324 // Number of samples to keep.
325 static constexpr size_t HISTORY_SIZE = 20;
326
327 struct Movement {
328 nsecs_t eventTime;
329 BitSet32 idBits;
Yeabkal Wubshit384ab0f2022-09-09 16:39:18 +0000330 float positions[MAX_POINTERS];
Siarhei Vishniakou00a4ea92017-06-08 21:43:20 +0100331
Yeabkal Wubshit384ab0f2022-09-09 16:39:18 +0000332 inline float getPosition(uint32_t id) const { return positions[idBits.getIndexOfBit(id)]; }
Siarhei Vishniakou00a4ea92017-06-08 21:43:20 +0100333 };
334
Yeabkal Wubshit0bb5e592022-09-14 01:22:28 -0700335 // Whether or not the input movement values for the strategy come in the form of delta values.
336 // If the input values are not deltas, the strategy needs to calculate deltas as part of its
337 // velocity calculation.
338 const bool mDeltaValues;
339
Siarhei Vishniakou00a4ea92017-06-08 21:43:20 +0100340 size_t mIndex;
341 Movement mMovements[HISTORY_SIZE];
342};
343
Jeff Brown5912f952013-07-01 19:10:31 -0700344} // namespace android