blob: 6d51515cb340df472667239108c9359a7e81e09e [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:
Yeabkal Wubshit9b4443f2023-02-23 23:35:07 -080034 static const size_t MAX_DEGREE = 4;
35
Chris Yef8591482020-04-17 11:49:17 -070036 enum class Strategy : int32_t {
37 DEFAULT = -1,
38 MIN = 0,
39 IMPULSE = 0,
40 LSQ1 = 1,
41 LSQ2 = 2,
42 LSQ3 = 3,
43 WLSQ2_DELTA = 4,
44 WLSQ2_CENTRAL = 5,
45 WLSQ2_RECENT = 6,
46 INT1 = 7,
47 INT2 = 8,
48 LEGACY = 9,
49 MAX = LEGACY,
50 };
51
Yeabkal Wubshit384ab0f2022-09-09 16:39:18 +000052 /*
53 * Contains all available velocity data from a VelocityTracker.
54 */
55 struct ComputedVelocity {
Siarhei Vishniakou657a1732023-01-12 11:58:52 -080056 inline std::optional<float> getVelocity(int32_t axis, int32_t id) const {
Yeabkal Wubshit384ab0f2022-09-09 16:39:18 +000057 const auto& axisVelocities = mVelocities.find(axis);
58 if (axisVelocities == mVelocities.end()) {
59 return {};
60 }
61
62 const auto& axisIdVelocity = axisVelocities->second.find(id);
63 if (axisIdVelocity == axisVelocities->second.end()) {
64 return {};
65 }
66
67 return axisIdVelocity->second;
68 }
69
Siarhei Vishniakou657a1732023-01-12 11:58:52 -080070 inline void addVelocity(int32_t axis, int32_t id, float velocity) {
Yeabkal Wubshit384ab0f2022-09-09 16:39:18 +000071 mVelocities[axis][id] = velocity;
72 }
73
74 private:
75 std::map<int32_t /*axis*/, std::map<int32_t /*pointerId*/, float /*velocity*/>> mVelocities;
76 };
77
78 // Creates a velocity tracker using the specified strategy for each supported axis.
Chris Yef8591482020-04-17 11:49:17 -070079 // If strategy is not provided, uses the default strategy for the platform.
Yeabkal Wubshit384ab0f2022-09-09 16:39:18 +000080 // TODO(b/32830165): support axis-specific strategies.
Chris Yef8591482020-04-17 11:49:17 -070081 VelocityTracker(const Strategy strategy = Strategy::DEFAULT);
Jeff Brown5912f952013-07-01 19:10:31 -070082
83 ~VelocityTracker();
84
Yeabkal Wubshiteca273c2022-10-05 19:06:40 -070085 /** Return true if the axis is supported for velocity tracking, false otherwise. */
86 static bool isAxisSupported(int32_t axis);
87
Jeff Brown5912f952013-07-01 19:10:31 -070088 // Resets the velocity tracker state.
89 void clear();
90
Siarhei Vishniakou8d232032023-01-11 08:17:21 -080091 // Resets the velocity tracker state for a specific pointer.
Jeff Brown5912f952013-07-01 19:10:31 -070092 // Call this method when some pointers have changed and may be reusing
93 // an id that was assigned to a different pointer earlier.
Siarhei Vishniakou8d232032023-01-11 08:17:21 -080094 void clearPointer(int32_t pointerId);
Jeff Brown5912f952013-07-01 19:10:31 -070095
Siarhei Vishniakou8d232032023-01-11 08:17:21 -080096 // Adds movement information for a pointer for a specific axis
97 void addMovement(nsecs_t eventTime, int32_t pointerId, int32_t axis, float position);
Jeff Brown5912f952013-07-01 19:10:31 -070098
99 // Adds movement information for all pointers in a MotionEvent, including historical samples.
100 void addMovement(const MotionEvent* event);
101
Yeabkal Wubshit384ab0f2022-09-09 16:39:18 +0000102 // Returns the velocity of the specified pointer id and axis in position units per second.
103 // Returns empty optional if there is insufficient movement information for the pointer, or if
104 // the given axis is not supported for velocity tracking.
Siarhei Vishniakou657a1732023-01-12 11:58:52 -0800105 std::optional<float> getVelocity(int32_t axis, int32_t pointerId) const;
Jeff Brown5912f952013-07-01 19:10:31 -0700106
Yeabkal Wubshit384ab0f2022-09-09 16:39:18 +0000107 // Returns a ComputedVelocity instance with all available velocity data, using the given units
108 // (reference: units == 1 means "per millisecond"), and clamping each velocity between
109 // [-maxVelocity, maxVelocity], inclusive.
110 ComputedVelocity getComputedVelocity(int32_t units, float maxVelocity);
111
Jeff Brown5912f952013-07-01 19:10:31 -0700112 // Gets the active pointer id, or -1 if none.
Siarhei Vishniakou657a1732023-01-12 11:58:52 -0800113 inline int32_t getActivePointerId() const { return mActivePointerId.value_or(-1); }
Jeff Brown5912f952013-07-01 19:10:31 -0700114
Jeff Brown5912f952013-07-01 19:10:31 -0700115private:
Jeff Brown5912f952013-07-01 19:10:31 -0700116 nsecs_t mLastEventTime;
117 BitSet32 mCurrentPointerIdBits;
Siarhei Vishniakou657a1732023-01-12 11:58:52 -0800118 std::optional<int32_t> mActivePointerId;
Jeff Brown5912f952013-07-01 19:10:31 -0700119
Yeabkal Wubshit47ff7082022-09-10 23:09:15 -0700120 // An override strategy passed in the constructor to be used for all axes.
121 // This strategy will apply to all axes, unless the default strategy is specified here.
122 // When default strategy is specified, then each axis will use a potentially different strategy
123 // based on a hardcoded mapping.
124 const Strategy mOverrideStrategy;
125 // Maps axes to their respective VelocityTrackerStrategy instances.
126 // Note that, only axes that have had MotionEvents (and not all supported axes) will be here.
127 std::map<int32_t /*axis*/, std::unique_ptr<VelocityTrackerStrategy>> mConfiguredStrategies;
128
129 void configureStrategy(int32_t axis);
Jeff Brown5912f952013-07-01 19:10:31 -0700130
Yeabkal Wubshit73c95082022-09-22 10:12:33 +0000131 // Generates a VelocityTrackerStrategy instance for the given Strategy type.
132 // The `deltaValues` parameter indicates whether or not the created strategy should treat motion
133 // values as deltas (and not as absolute values). This the parameter is applicable only for
134 // strategies that support differential axes.
Yeabkal Wubshit0bb5e592022-09-14 01:22:28 -0700135 static std::unique_ptr<VelocityTrackerStrategy> createStrategy(const Strategy strategy,
Yeabkal Wubshit73c95082022-09-22 10:12:33 +0000136 bool deltaValues);
Jeff Brown5912f952013-07-01 19:10:31 -0700137};
138
139
140/*
141 * Implements a particular velocity tracker algorithm.
142 */
143class VelocityTrackerStrategy {
144protected:
145 VelocityTrackerStrategy() { }
146
147public:
148 virtual ~VelocityTrackerStrategy() { }
149
Siarhei Vishniakou8d232032023-01-11 08:17:21 -0800150 virtual void clearPointer(int32_t pointerId) = 0;
151 virtual void addMovement(nsecs_t eventTime, int32_t pointerId, float position) = 0;
Yeabkal Wubshit9b4443f2023-02-23 23:35:07 -0800152 virtual std::optional<float> getVelocity(int32_t pointerId) const = 0;
Jeff Brown5912f952013-07-01 19:10:31 -0700153};
154
Yeabkal Wubshita0e573c2023-03-02 21:08:14 -0800155/**
156 * A `VelocityTrackerStrategy` that accumulates added data points and processes the accumulated data
157 * points when getting velocity.
158 */
159class AccumulatingVelocityTrackerStrategy : public VelocityTrackerStrategy {
160public:
161 void addMovement(nsecs_t eventTime, int32_t pointerId, float position) override;
162 void clearPointer(int32_t pointerId) override;
163
164protected:
165 struct Movement {
166 nsecs_t eventTime;
167 float position;
168 };
169
170 // Number of samples to keep.
171 // If different strategies would like to maintain different history size, we can make this a
172 // protected const field.
173 static constexpr uint32_t HISTORY_SIZE = 20;
174
175 std::map<int32_t /*pointerId*/, size_t /*positionInArray*/> mIndex;
176 std::map<int32_t /*pointerId*/, std::array<Movement, HISTORY_SIZE>> mMovements;
177};
Jeff Brown5912f952013-07-01 19:10:31 -0700178
179/*
180 * Velocity tracker algorithm based on least-squares linear regression.
181 */
Yeabkal Wubshita0e573c2023-03-02 21:08:14 -0800182class LeastSquaresVelocityTrackerStrategy : public AccumulatingVelocityTrackerStrategy {
Jeff Brown5912f952013-07-01 19:10:31 -0700183public:
Siarhei Vishniakou657a1732023-01-12 11:58:52 -0800184 enum class Weighting {
Jeff Brown5912f952013-07-01 19:10:31 -0700185 // No weights applied. All data points are equally reliable.
Siarhei Vishniakou657a1732023-01-12 11:58:52 -0800186 NONE,
Jeff Brown5912f952013-07-01 19:10:31 -0700187
188 // Weight by time delta. Data points clustered together are weighted less.
Siarhei Vishniakou657a1732023-01-12 11:58:52 -0800189 DELTA,
Jeff Brown5912f952013-07-01 19:10:31 -0700190
191 // Weight such that points within a certain horizon are weighed more than those
192 // outside of that horizon.
Siarhei Vishniakou657a1732023-01-12 11:58:52 -0800193 CENTRAL,
Jeff Brown5912f952013-07-01 19:10:31 -0700194
195 // Weight such that points older than a certain amount are weighed less.
Siarhei Vishniakou657a1732023-01-12 11:58:52 -0800196 RECENT,
Jeff Brown5912f952013-07-01 19:10:31 -0700197 };
198
Yeabkal Wubshit9b4443f2023-02-23 23:35:07 -0800199 // Degree must be no greater than VelocityTracker::MAX_DEGREE.
Siarhei Vishniakou657a1732023-01-12 11:58:52 -0800200 LeastSquaresVelocityTrackerStrategy(uint32_t degree, Weighting weighting = Weighting::NONE);
201 ~LeastSquaresVelocityTrackerStrategy() override;
Jeff Brown5912f952013-07-01 19:10:31 -0700202
Yeabkal Wubshit9b4443f2023-02-23 23:35:07 -0800203 std::optional<float> getVelocity(int32_t pointerId) const override;
Jeff Brown5912f952013-07-01 19:10:31 -0700204
205private:
206 // Sample horizon.
207 // We don't use too much history by default since we want to react to quick
208 // changes in direction.
209 static const nsecs_t HORIZON = 100 * 1000000; // 100 ms
210
Siarhei Vishniakou8d232032023-01-11 08:17:21 -0800211 float chooseWeight(int32_t pointerId, uint32_t index) const;
Jeff Brown5912f952013-07-01 19:10:31 -0700212
213 const uint32_t mDegree;
214 const Weighting mWeighting;
Jeff Brown5912f952013-07-01 19:10:31 -0700215};
216
Jeff Brown5912f952013-07-01 19:10:31 -0700217/*
218 * Velocity tracker algorithm that uses an IIR filter.
219 */
220class IntegratingVelocityTrackerStrategy : public VelocityTrackerStrategy {
221public:
222 // Degree must be 1 or 2.
223 IntegratingVelocityTrackerStrategy(uint32_t degree);
Siarhei Vishniakou657a1732023-01-12 11:58:52 -0800224 ~IntegratingVelocityTrackerStrategy() override;
Jeff Brown5912f952013-07-01 19:10:31 -0700225
Siarhei Vishniakou8d232032023-01-11 08:17:21 -0800226 void clearPointer(int32_t pointerId) override;
227 void addMovement(nsecs_t eventTime, int32_t pointerId, float positions) override;
Yeabkal Wubshit9b4443f2023-02-23 23:35:07 -0800228 std::optional<float> getVelocity(int32_t pointerId) const override;
Jeff Brown5912f952013-07-01 19:10:31 -0700229
230private:
231 // Current state estimate for a particular pointer.
232 struct State {
233 nsecs_t updateTime;
234 uint32_t degree;
235
Yeabkal Wubshit384ab0f2022-09-09 16:39:18 +0000236 float pos, vel, accel;
Jeff Brown5912f952013-07-01 19:10:31 -0700237 };
238
239 const uint32_t mDegree;
240 BitSet32 mPointerIdBits;
241 State mPointerState[MAX_POINTER_ID + 1];
242
Yeabkal Wubshit384ab0f2022-09-09 16:39:18 +0000243 void initState(State& state, nsecs_t eventTime, float pos) const;
244 void updateState(State& state, nsecs_t eventTime, float pos) const;
Jeff Brown5912f952013-07-01 19:10:31 -0700245};
246
247
248/*
249 * Velocity tracker strategy used prior to ICS.
250 */
Yeabkal Wubshita0e573c2023-03-02 21:08:14 -0800251class LegacyVelocityTrackerStrategy : public AccumulatingVelocityTrackerStrategy {
Jeff Brown5912f952013-07-01 19:10:31 -0700252public:
253 LegacyVelocityTrackerStrategy();
Siarhei Vishniakou657a1732023-01-12 11:58:52 -0800254 ~LegacyVelocityTrackerStrategy() override;
Jeff Brown5912f952013-07-01 19:10:31 -0700255
Yeabkal Wubshit9b4443f2023-02-23 23:35:07 -0800256 std::optional<float> getVelocity(int32_t pointerId) const override;
Jeff Brown5912f952013-07-01 19:10:31 -0700257
258private:
259 // Oldest sample to consider when calculating the velocity.
260 static const nsecs_t HORIZON = 200 * 1000000; // 100 ms
261
Jeff Brown5912f952013-07-01 19:10:31 -0700262 // The minimum duration between samples when estimating velocity.
263 static const nsecs_t MIN_DURATION = 10 * 1000000; // 10 ms
Jeff Brown5912f952013-07-01 19:10:31 -0700264};
265
Yeabkal Wubshita0e573c2023-03-02 21:08:14 -0800266class ImpulseVelocityTrackerStrategy : public AccumulatingVelocityTrackerStrategy {
Siarhei Vishniakou00a4ea92017-06-08 21:43:20 +0100267public:
Yeabkal Wubshit0bb5e592022-09-14 01:22:28 -0700268 ImpulseVelocityTrackerStrategy(bool deltaValues);
Siarhei Vishniakou657a1732023-01-12 11:58:52 -0800269 ~ImpulseVelocityTrackerStrategy() override;
Siarhei Vishniakou00a4ea92017-06-08 21:43:20 +0100270
Yeabkal Wubshit9b4443f2023-02-23 23:35:07 -0800271 std::optional<float> getVelocity(int32_t pointerId) const override;
Siarhei Vishniakou00a4ea92017-06-08 21:43:20 +0100272
273private:
274 // Sample horizon.
275 // We don't use too much history by default since we want to react to quick
276 // changes in direction.
277 static constexpr nsecs_t HORIZON = 100 * 1000000; // 100 ms
278
Yeabkal Wubshit0bb5e592022-09-14 01:22:28 -0700279 // Whether or not the input movement values for the strategy come in the form of delta values.
280 // If the input values are not deltas, the strategy needs to calculate deltas as part of its
281 // velocity calculation.
282 const bool mDeltaValues;
Siarhei Vishniakou00a4ea92017-06-08 21:43:20 +0100283};
284
Jeff Brown5912f952013-07-01 19:10:31 -0700285} // namespace android