Source code

Revision control

Other Tools

1
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
3
/* This Source Code Form is subject to the terms of the Mozilla Public
4
* License, v. 2.0. If a copy of the MPL was not distributed with this
5
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6
7
#include "AndroidVelocityTracker.h"
8
9
#include "mozilla/StaticPrefs_apz.h"
10
11
namespace mozilla {
12
namespace layers {
13
14
// This velocity tracker implementation was adapted from Chromium's
15
// second-order unweighted least-squares velocity tracker strategy
17
18
// Threshold between position updates for determining that a pointer has
19
// stopped moving. Some input devices do not send move events in the
20
// case where a pointer has stopped. We need to detect this case so that we can
21
// accurately predict the velocity after the pointer starts moving again.
22
static const int kAssumePointerMoveStoppedTimeMs = 40;
23
24
// The degree of the approximation.
25
static const uint8_t kDegree = 2;
26
27
// The degree of the polynomial used in SolveLeastSquares().
28
// This should be the degree of the approximation plus one.
29
static const uint8_t kPolyDegree = kDegree + 1;
30
31
// Maximum size of position history.
32
static const uint8_t kHistorySize = 20;
33
34
AndroidVelocityTracker::AndroidVelocityTracker()
35
: mLastEventTime(0), mAdditionalDelta(0) {}
36
37
void AndroidVelocityTracker::StartTracking(ParentLayerCoord aPos,
38
uint32_t aTimestampMs) {
39
Clear();
40
mHistory.AppendElement(std::make_pair(aTimestampMs, aPos));
41
mLastEventTime = aTimestampMs;
42
}
43
44
Maybe<float> AndroidVelocityTracker::AddPosition(ParentLayerCoord aPos,
45
uint32_t aTimestampMs) {
46
if ((aTimestampMs - mLastEventTime) >= kAssumePointerMoveStoppedTimeMs) {
47
Clear();
48
}
49
50
aPos += mAdditionalDelta;
51
52
if (aTimestampMs == mLastEventTime) {
53
// If we get a sample with the same timestamp as the previous one,
54
// just update its position. Two samples in the history with the
55
// same timestamp can lead to things like infinite velocities.
56
if (mHistory.Length() > 0) {
57
mHistory[mHistory.Length() - 1].second = aPos;
58
}
59
} else {
60
mHistory.AppendElement(std::make_pair(aTimestampMs, aPos));
61
if (mHistory.Length() > kHistorySize) {
62
mHistory.RemoveElementAt(0);
63
}
64
}
65
66
mLastEventTime = aTimestampMs;
67
68
if (mHistory.Length() < 2) {
69
return Nothing();
70
}
71
72
auto start = mHistory[mHistory.Length() - 2];
73
auto end = mHistory[mHistory.Length() - 1];
74
return Some((end.second - start.second) / (end.first - start.first));
75
}
76
77
float AndroidVelocityTracker::HandleDynamicToolbarMovement(
78
uint32_t aStartTimestampMs, uint32_t aEndTimestampMs,
79
ParentLayerCoord aDelta) {
80
// If the dynamic toolbar is moving, the page content is moving relative
81
// to the screen. The positions passed to AddPosition() reflect the position
82
// of the finger relative to the page content, but we want the velocity we
83
// compute to be based on the physical movement of the finger (that is, its
84
// position relative to the screen). To accomplish this, we maintain
85
// |mAdditionalDelta|, a delta representing the amount by which the page has
86
// moved relative to the screen, and add it to every position recorded in
87
// the history in AddPosition().
88
mAdditionalDelta += aDelta;
89
90
float timeDelta = aEndTimestampMs - aStartTimestampMs;
91
MOZ_ASSERT(timeDelta != 0);
92
return aDelta / timeDelta;
93
}
94
95
static float VectorDot(const float* a, const float* b, uint32_t m) {
96
float r = 0;
97
while (m--) {
98
r += *(a++) * *(b++);
99
}
100
return r;
101
}
102
103
static float VectorNorm(const float* a, uint32_t m) {
104
float r = 0;
105
while (m--) {
106
float t = *(a++);
107
r += t * t;
108
}
109
return sqrtf(r);
110
}
111
112
/**
113
* Solves a linear least squares problem to obtain a N degree polynomial that
114
* fits the specified input data as nearly as possible.
115
*
116
* Returns true if a solution is found, false otherwise.
117
*
118
* The input consists of two vectors of data points X and Y with indices 0..m-1
119
* along with a weight vector W of the same size.
120
*
121
* The output is a vector B with indices 0..n that describes a polynomial
122
* that fits the data, such the sum of W[i] * W[i] * abs(Y[i] - (B[0] + B[1]
123
* X[i] * + B[2] X[i]^2 ... B[n] X[i]^n)) for all i between 0 and m-1 is
124
* minimized.
125
*
126
* Accordingly, the weight vector W should be initialized by the caller with the
127
* reciprocal square root of the variance of the error in each input data point.
128
* In other words, an ideal choice for W would be W[i] = 1 / var(Y[i]) = 1 /
129
* stddev(Y[i]).
130
* The weights express the relative importance of each data point. If the
131
* weights are* all 1, then the data points are considered to be of equal
132
* importance when fitting the polynomial. It is a good idea to choose weights
133
* that diminish the importance of data points that may have higher than usual
134
* error margins.
135
*
136
* Errors among data points are assumed to be independent. W is represented
137
* here as a vector although in the literature it is typically taken to be a
138
* diagonal matrix.
139
*
140
* That is to say, the function that generated the input data can be
141
* approximated by y(x) ~= B[0] + B[1] x + B[2] x^2 + ... + B[n] x^n.
142
*
143
* The coefficient of determination (R^2) is also returned to describe the
144
* goodness of fit of the model for the given data. It is a value between 0
145
* and 1, where 1 indicates perfect correspondence.
146
*
147
* This function first expands the X vector to a m by n matrix A such that
148
* A[i][0] = 1, A[i][1] = X[i], A[i][2] = X[i]^2, ..., A[i][n] = X[i]^n, then
149
* multiplies it by w[i].
150
*
151
* Then it calculates the QR decomposition of A yielding an m by m orthonormal
152
* matrix Q and an m by n upper triangular matrix R. Because R is upper
153
* triangular (lower part is all zeroes), we can simplify the decomposition into
154
* an m by n matrix Q1 and a n by n matrix R1 such that A = Q1 R1.
155
*
156
* Finally we solve the system of linear equations given by
157
* R1 B = (Qtranspose W Y) to find B.
158
*
159
* For efficiency, we lay out A and Q column-wise in memory because we
160
* frequently operate on the column vectors. Conversely, we lay out R row-wise.
161
*
164
*/
165
static bool SolveLeastSquares(const float* x, const float* y, const float* w,
166
uint32_t m, uint32_t n, float* out_b) {
167
// MSVC does not support variable-length arrays (used by the original Android
168
// implementation of this function).
169
#if defined(COMPILER_MSVC)
170
const uint32_t M_ARRAY_LENGTH = VelocityTracker::kHistorySize;
171
const uint32_t N_ARRAY_LENGTH = VelocityTracker::kPolyDegree;
172
DCHECK_LE(m, M_ARRAY_LENGTH);
173
DCHECK_LE(n, N_ARRAY_LENGTH);
174
#else
175
const uint32_t M_ARRAY_LENGTH = m;
176
const uint32_t N_ARRAY_LENGTH = n;
177
#endif
178
179
// Expand the X vector to a matrix A, pre-multiplied by the weights.
180
float a[N_ARRAY_LENGTH][M_ARRAY_LENGTH]; // column-major order
181
for (uint32_t h = 0; h < m; h++) {
182
a[0][h] = w[h];
183
for (uint32_t i = 1; i < n; i++) {
184
a[i][h] = a[i - 1][h] * x[h];
185
}
186
}
187
188
// Apply the Gram-Schmidt process to A to obtain its QR decomposition.
189
190
// Orthonormal basis, column-major order.
191
float q[N_ARRAY_LENGTH][M_ARRAY_LENGTH];
192
// Upper triangular matrix, row-major order.
193
float r[N_ARRAY_LENGTH][N_ARRAY_LENGTH];
194
for (uint32_t j = 0; j < n; j++) {
195
for (uint32_t h = 0; h < m; h++) {
196
q[j][h] = a[j][h];
197
}
198
for (uint32_t i = 0; i < j; i++) {
199
float dot = VectorDot(&q[j][0], &q[i][0], m);
200
for (uint32_t h = 0; h < m; h++) {
201
q[j][h] -= dot * q[i][h];
202
}
203
}
204
205
float norm = VectorNorm(&q[j][0], m);
206
if (norm < 0.000001f) {
207
// vectors are linearly dependent or zero so no solution
208
return false;
209
}
210
211
float invNorm = 1.0f / norm;
212
for (uint32_t h = 0; h < m; h++) {
213
q[j][h] *= invNorm;
214
}
215
for (uint32_t i = 0; i < n; i++) {
216
r[j][i] = i < j ? 0 : VectorDot(&q[j][0], &a[i][0], m);
217
}
218
}
219
220
// Solve R B = Qt W Y to find B. This is easy because R is upper triangular.
221
// We just work from bottom-right to top-left calculating B's coefficients.
222
float wy[M_ARRAY_LENGTH];
223
for (uint32_t h = 0; h < m; h++) {
224
wy[h] = y[h] * w[h];
225
}
226
for (uint32_t i = n; i-- != 0;) {
227
out_b[i] = VectorDot(&q[i][0], wy, m);
228
for (uint32_t j = n - 1; j > i; j--) {
229
out_b[i] -= r[i][j] * out_b[j];
230
}
231
out_b[i] /= r[i][i];
232
}
233
234
return true;
235
}
236
237
Maybe<float> AndroidVelocityTracker::ComputeVelocity(uint32_t aTimestampMs) {
238
if (mHistory.IsEmpty()) {
239
return Nothing{};
240
}
241
242
// Polynomial coefficients describing motion along the axis.
243
float xcoeff[kPolyDegree + 1];
244
for (size_t i = 0; i <= kPolyDegree; i++) {
245
xcoeff[i] = 0;
246
}
247
248
// Iterate over movement samples in reverse time order and collect samples.
249
float pos[kHistorySize];
250
float w[kHistorySize];
251
float time[kHistorySize];
252
uint32_t m = 0;
253
int index = mHistory.Length() - 1;
254
const uint32_t horizon = StaticPrefs::apz_velocity_relevance_time_ms();
255
const auto& newest_movement = mHistory[index];
256
257
do {
258
const auto& movement = mHistory[index];
259
uint32_t age = newest_movement.first - movement.first;
260
if (age > horizon) break;
261
262
ParentLayerCoord position = movement.second;
263
pos[m] = position;
264
w[m] = 1.0f;
265
time[m] = -static_cast<float>(age) / 1000.0f; // in seconds
266
index--;
267
m++;
268
} while (index >= 0);
269
270
if (m == 0) {
271
return Nothing{}; // no data
272
}
273
274
// Calculate a least squares polynomial fit.
275
276
// Polynomial degree (number of coefficients), or zero if no information is
277
// available.
278
uint32_t degree = kDegree;
279
if (degree > m - 1) {
280
degree = m - 1;
281
}
282
283
if (degree >= 1) { // otherwise, no velocity data available
284
uint32_t n = degree + 1;
285
if (SolveLeastSquares(time, pos, w, m, n, xcoeff)) {
286
float velocity = xcoeff[1];
287
288
// The velocity needs to be negated because the positions represent
289
// touch positions, and the direction of scrolling is opposite to the
290
// direction of the finger's movement.
291
return Some(-velocity / 1000.0f); // convert to pixels per millisecond
292
}
293
}
294
295
return Nothing{};
296
}
297
298
void AndroidVelocityTracker::Clear() {
299
mAdditionalDelta = 0;
300
mHistory.Clear();
301
}
302
303
} // namespace layers
304
} // namespace mozilla