Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(2)

Side by Side Diff: ui/events/gesture_detection/velocity_tracker.cc

Issue 171773012: Port of Android platform gesture detection code to C++ (Closed) Base URL: https://chromium.googlesource.com/chromium/src.git@master
Patch Set: Code review Created 6 years, 10 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
(Empty)
1 // Copyright 2014 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "ui/events/gesture_detection/velocity_tracker.h"
6
7 #include <math.h>
8
9 #include "base/logging.h"
10 #include "ui/events/gesture_detection/motion_event.h"
11
12 using base::TimeDelta;
13 using base::TimeTicks;
14
15 namespace ui {
16
17 // Implements a particular velocity tracker algorithm.
18 class VelocityTrackerStrategy {
19 public:
20 virtual ~VelocityTrackerStrategy() {}
21
22 virtual void Clear() = 0;
23 virtual void ClearPointers(BitSet32 id_bits) = 0;
24 virtual void AddMovement(const base::TimeTicks& event_time,
25 BitSet32 id_bits,
26 const Position* positions) = 0;
27 virtual bool GetEstimator(uint32_t id, Estimator* out_estimator) const = 0;
28
29 protected:
30 VelocityTrackerStrategy() {}
31 };
32
33 namespace {
34
35 COMPILE_ASSERT(MotionEvent::MAX_POINTER_ID < 32, max_pointer_id_too_large);
36
37 struct Position {
38 float x, y;
39 };
40
41 struct Estimator {
42 enum { MAX_DEGREE = 4 };
43
44 // Estimator time base.
45 TimeTicks time;
46
47 // Polynomial coefficients describing motion in X and Y.
48 float xcoeff[MAX_DEGREE + 1], ycoeff[MAX_DEGREE + 1];
49
50 // Polynomial degree (number of coefficients), or zero if no information is
51 // available.
52 uint32_t degree;
53
54 // Confidence (coefficient of determination), between 0 (no fit)
55 // and 1 (perfect fit).
56 float confidence;
57
58 inline void Clear() {
59 time = TimeTicks();
60 degree = 0;
61 confidence = 0;
62 for (size_t i = 0; i <= MAX_DEGREE; i++) {
63 xcoeff[i] = 0;
64 ycoeff[i] = 0;
65 }
66 }
67 };
68
69 // Threshold for determining that a pointer has stopped moving.
70 // Some input devices do not send ACTION_MOVE events in the case where a pointer
71 // hasstopped. We need to detect this case so that we can accurately predict
72 // the velocity after the pointer starts moving again.
73 const TimeDelta ASSUME_POINTER_STOPPED_TIME = TimeDelta::FromMilliseconds(40);
74
75 static float VectorDot(const float* a, const float* b, uint32_t m) {
76 float r = 0;
77 while (m--) {
78 r += *(a++) * *(b++);
79 }
80 return r;
81 }
82
83 static float VectorNorm(const float* a, uint32_t m) {
84 float r = 0;
85 while (m--) {
86 float t = *(a++);
87 r += t * t;
88 }
89 return sqrtf(r);
90 }
91
92 // Velocity tracker algorithm based on least-squares linear regression.
93 class LeastSquaresVelocityTrackerStrategy : public VelocityTrackerStrategy {
94 public:
95 enum Weighting {
96 // No weights applied. All data points are equally reliable.
97 WEIGHTING_NONE,
98
99 // Weight by time delta. Data points clustered together are weighted less.
100 WEIGHTING_DELTA,
101
102 // Weight such that points within a certain horizon are weighed more than
103 // those outside of that horizon.
104 WEIGHTING_CENTRAL,
105
106 // Weight such that points older than a certain amount are weighed less.
107 WEIGHTING_RECENT,
108 };
109
110 // Degree must be no greater than Estimator::MAX_DEGREE.
111 LeastSquaresVelocityTrackerStrategy(uint32_t degree,
112 Weighting weighting = WEIGHTING_NONE);
113 virtual ~LeastSquaresVelocityTrackerStrategy();
114
115 virtual void Clear() OVERRIDE;
116 virtual void ClearPointers(BitSet32 id_bits) OVERRIDE;
117 virtual void AddMovement(const TimeTicks& event_time,
118 BitSet32 id_bits,
119 const Position* positions) OVERRIDE;
120 virtual bool GetEstimator(uint32_t id,
121 Estimator* out_estimator) const OVERRIDE;
122
123 private:
124 // Sample horizon.
125 // We don't use too much history by default since we want to react to quick
126 // changes in direction.
127 static const TimeDelta HORIZON;
128
129 // Number of samples to keep.
130 enum { HISTORY_SIZE = 20 };
131
132 struct Movement {
133 TimeTicks event_time;
134 BitSet32 id_bits;
135 Position positions[VelocityTracker::MAX_POINTERS];
136
137 inline const Position& GetPosition(uint32_t id) const {
138 return positions[id_bits.get_index_of_bit(id)];
139 }
140 };
141
142 float ChooseWeight(uint32_t index) const;
143
144 const uint32_t degree_;
145 const Weighting weighting_;
146 uint32_t index_;
147 Movement movements_[HISTORY_SIZE];
148 };
149
150 // Velocity tracker algorithm that uses an IIR filter.
151 class IntegratingVelocityTrackerStrategy : public VelocityTrackerStrategy {
152 public:
153 // Degree must be 1 or 2.
154 explicit IntegratingVelocityTrackerStrategy(uint32_t degree);
155 virtual ~IntegratingVelocityTrackerStrategy();
156
157 virtual void Clear() OVERRIDE;
158 virtual void ClearPointers(BitSet32 id_bits) OVERRIDE;
159 virtual void AddMovement(const TimeTicks& event_time,
160 BitSet32 id_bits,
161 const Position* positions) OVERRIDE;
162 virtual bool GetEstimator(uint32_t id,
163 Estimator* out_estimator) const OVERRIDE;
164
165 private:
166 // Current state estimate for a particular pointer.
167 struct State {
168 TimeTicks update_time;
169 uint32_t degree;
170
171 float xpos, xvel, xaccel;
172 float ypos, yvel, yaccel;
173 };
174
175 const uint32_t degree_;
176 BitSet32 pointer_id_bits_;
177 State mPointerState[MotionEvent::MAX_POINTER_ID + 1];
178
179 void InitState(State& state,
180 const TimeTicks& event_time,
181 float xpos,
182 float ypos) const;
183 void UpdateState(State& state,
184 const TimeTicks& event_time,
185 float xpos,
186 float ypos) const;
187 void PopulateEstimator(const State& state, Estimator* out_estimator) const;
188 };
189
190 VelocityTrackerStrategy* CreateStrategy(VelocityTracker::Strategy strategy) {
191 switch (strategy) {
192 case VelocityTracker::LSQ1:
193 return new LeastSquaresVelocityTrackerStrategy(1);
194 case VelocityTracker::LSQ2:
195 return new LeastSquaresVelocityTrackerStrategy(2);
196 case VelocityTracker::LSQ3:
197 return new LeastSquaresVelocityTrackerStrategy(3);
198 case VelocityTracker::WLSQ2_DELTA:
199 return new LeastSquaresVelocityTrackerStrategy(
200 2, LeastSquaresVelocityTrackerStrategy::WEIGHTING_DELTA);
201 case VelocityTracker::WLSQ2_CENTRAL:
202 return new LeastSquaresVelocityTrackerStrategy(
203 2, LeastSquaresVelocityTrackerStrategy::WEIGHTING_CENTRAL);
204 case VelocityTracker::WLSQ2_RECENT:
205 return new LeastSquaresVelocityTrackerStrategy(
206 2, LeastSquaresVelocityTrackerStrategy::WEIGHTING_RECENT);
207 case VelocityTracker::INT1:
208 return new IntegratingVelocityTrackerStrategy(1);
209 case VelocityTracker::INT2:
210 return new IntegratingVelocityTrackerStrategy(2);
211 }
212 NOTREACHED() << "Unrecognized velocity tracker strategy: " << strategy;
213 return CreateStrategy(VelocityTracker::STRATEGY_DEFAULT);
214 }
215
216 } // namespace
217
218 // --- VelocityTracker ---
219
220 VelocityTracker::VelocityTracker()
221 : current_pointer_id_bits_(0),
222 active_pointer_id_(-1),
223 strategy_(CreateStrategy(STRATEGY_DEFAULT)) {}
224
225 VelocityTracker::VelocityTracker(Strategy strategy)
226 : current_pointer_id_bits_(0),
227 active_pointer_id_(-1),
228 strategy_(CreateStrategy(strategy)) {}
229
230 VelocityTracker::~VelocityTracker() {}
231
232 void VelocityTracker::Clear() {
233 current_pointer_id_bits_.clear();
234 active_pointer_id_ = -1;
235 strategy_->Clear();
236 }
237
238 void VelocityTracker::ClearPointers(BitSet32 id_bits) {
239 BitSet32 remaining_id_bits(current_pointer_id_bits_.value & ~id_bits.value);
240 current_pointer_id_bits_ = remaining_id_bits;
241
242 if (active_pointer_id_ >= 0 && id_bits.has_bit(active_pointer_id_)) {
243 active_pointer_id_ = !remaining_id_bits.is_empty()
244 ? remaining_id_bits.first_marked_bit()
245 : -1;
246 }
247
248 strategy_->ClearPointers(id_bits);
249 }
250
251 void VelocityTracker::AddMovement(const TimeTicks& event_time,
252 BitSet32 id_bits,
253 const Position* positions) {
254 while (id_bits.count() > MAX_POINTERS)
255 id_bits.clear_last_marked_bit();
256
257 if ((current_pointer_id_bits_.value & id_bits.value) &&
258 event_time >= (last_event_time_ + ASSUME_POINTER_STOPPED_TIME)) {
259 // We have not received any movements for too long. Assume that all
260 // pointers
261 // have stopped.
262 strategy_->Clear();
263 }
264 last_event_time_ = event_time;
265
266 current_pointer_id_bits_ = id_bits;
267 if (active_pointer_id_ < 0 || !id_bits.has_bit(active_pointer_id_))
268 active_pointer_id_ = id_bits.is_empty() ? -1 : id_bits.first_marked_bit();
269
270 strategy_->AddMovement(event_time, id_bits, positions);
271 }
272
273 void VelocityTracker::AddMovement(const MotionEvent& event) {
274 int32_t actionMasked = event.GetAction();
275
276 switch (actionMasked) {
277 case MotionEvent::ACTION_DOWN:
278 // case MotionEvent::HOVER_ENTER:
279 // Clear all pointers on down before adding the new movement.
280 Clear();
281 break;
282 case MotionEvent::ACTION_POINTER_DOWN: {
283 // Start a new movement trace for a pointer that just went down.
284 // We do this on down instead of on up because the client may want to
285 // query the final velocity for a pointer that just went up.
286 BitSet32 downIdBits;
287 downIdBits.mark_bit(event.GetPointerId(event.GetActionIndex()));
288 ClearPointers(downIdBits);
289 break;
290 }
291 case MotionEvent::ACTION_MOVE:
292 // case MotionEvent::ACTION_HOVER_MOVE:
293 break;
294 default:
295 // Ignore all other actions because they do not convey any new information
296 // about pointer movement. We also want to preserve the last known
297 // velocity of the pointers.
298 // Note that ACTION_UP and ACTION_POINTER_UP always report the last known
299 // position of the pointers that went up. ACTION_POINTER_UP does include
300 // the new position of pointers that remained down but we will also
301 // receive an ACTION_MOVE with this information if any of them actually
302 // moved. Since we don't know how many pointers will be going up at once
303 // it makes sense to just wait for the following ACTION_MOVE before adding
304 // the movement.
305 return;
306 }
307
308 size_t pointer_count = event.GetPointerCount();
309 if (pointer_count > MAX_POINTERS) {
310 pointer_count = MAX_POINTERS;
311 }
312
313 BitSet32 id_bits;
314 for (size_t i = 0; i < pointer_count; i++) {
315 id_bits.mark_bit(event.GetPointerId(i));
316 }
317
318 uint32_t pointer_index[MAX_POINTERS];
319 for (size_t i = 0; i < pointer_count; i++) {
320 pointer_index[i] = id_bits.get_index_of_bit(event.GetPointerId(i));
321 }
322
323 Position positions[pointer_count];
324 size_t historySize = event.GetHistorySize();
325 for (size_t h = 0; h < historySize; h++) {
326 for (size_t i = 0; i < pointer_count; i++) {
327 uint32_t index = pointer_index[i];
328 positions[index].x = event.GetHistoricalX(i, h);
329 positions[index].y = event.GetHistoricalY(i, h);
330 }
331 AddMovement(event.GetHistoricalEventTime(h), id_bits, positions);
332 }
333
334 for (size_t i = 0; i < pointer_count; i++) {
335 uint32_t index = pointer_index[i];
336 positions[index].x = event.GetX(i);
337 positions[index].y = event.GetY(i);
338 }
339 AddMovement(event.GetEventTime(), id_bits, positions);
340 }
341
342 bool VelocityTracker::GetVelocity(uint32_t id,
343 float* out_vx,
344 float* out_vy) const {
345 Estimator estimator;
346 if (GetEstimator(id, &estimator) && estimator.degree >= 1) {
347 *out_vx = estimator.xcoeff[1];
348 *out_vy = estimator.ycoeff[1];
349 return true;
350 }
351 *out_vx = 0;
352 *out_vy = 0;
353 return false;
354 }
355
356 void LeastSquaresVelocityTrackerStrategy::AddMovement(
357 const TimeTicks& event_time,
358 BitSet32 id_bits,
359 const Position* positions) {
360 if (++index_ == HISTORY_SIZE) {
361 index_ = 0;
362 }
363
364 Movement& movement = movements_[index_];
365 movement.event_time = event_time;
366 movement.id_bits = id_bits;
367 uint32_t count = id_bits.count();
368 for (uint32_t i = 0; i < count; i++) {
369 movement.positions[i] = positions[i];
370 }
371 }
372
373 bool VelocityTracker::GetEstimator(uint32_t id,
374 Estimator* out_estimator) const {
375 return strategy_->GetEstimator(id, out_estimator);
376 }
377
378 // --- LeastSquaresVelocityTrackerStrategy ---
379
380 const TimeDelta LeastSquaresVelocityTrackerStrategy::HORIZON =
381 TimeDelta::FromMilliseconds(100);
382
383 LeastSquaresVelocityTrackerStrategy::LeastSquaresVelocityTrackerStrategy(
384 uint32_t degree,
385 Weighting weighting)
386 : degree_(degree), weighting_(weighting) {
387 Clear();
388 }
389
390 LeastSquaresVelocityTrackerStrategy::~LeastSquaresVelocityTrackerStrategy() {}
391
392 void LeastSquaresVelocityTrackerStrategy::Clear() {
393 index_ = 0;
394 movements_[0].id_bits.clear();
395 }
396
397 /**
398 * Solves a linear least squares problem to obtain a N degree polynomial that
399 * fits the specified input data as nearly as possible.
400 *
401 * Returns true if a solution is found, false otherwise.
402 *
403 * The input consists of two vectors of data points X and Y with indices 0..m-1
404 * along with a weight vector W of the same size.
405 *
406 * The output is a vector B with indices 0..n that describes a polynomial
407 * that fits the data, such the sum of W[i] * W[i] * abs(Y[i] - (B[0] + B[1]
408 * X[i] * + B[2] X[i]^2 ... B[n] X[i]^n)) for all i between 0 and m-1 is
409 * minimized.
410 *
411 * Accordingly, the weight vector W should be initialized by the caller with the
412 * reciprocal square root of the variance of the error in each input data point.
413 * In other words, an ideal choice for W would be W[i] = 1 / var(Y[i]) = 1 /
414 * stddev(Y[i]).
415 * The weights express the relative importance of each data point. If the
416 * weights are* all 1, then the data points are considered to be of equal
417 * importance when fitting the polynomial. It is a good idea to choose weights
418 * that diminish the importance of data points that may have higher than usual
419 * error margins.
420 *
421 * Errors among data points are assumed to be independent. W is represented
422 * here as a vector although in the literature it is typically taken to be a
423 * diagonal matrix.
424 *
425 * That is to say, the function that generated the input data can be
426 * approximated by y(x) ~= B[0] + B[1] x + B[2] x^2 + ... + B[n] x^n.
427 *
428 * The coefficient of determination (R^2) is also returned to describe the
429 * goodness of fit of the model for the given data. It is a value between 0
430 * and 1, where 1 indicates perfect correspondence.
431 *
432 * This function first expands the X vector to a m by n matrix A such that
433 * A[i][0] = 1, A[i][1] = X[i], A[i][2] = X[i]^2, ..., A[i][n] = X[i]^n, then
434 * multiplies it by w[i]./
435 *
436 * Then it calculates the QR decomposition of A yielding an m by m orthonormal
437 * matrix Q and an m by n upper triangular matrix R. Because R is upper
438 * triangular (lower part is all zeroes), we can simplify the decomposition into
439 * an m by n matrix Q1 and a n by n matrix R1 such that A = Q1 R1.
440 *
441 * Finally we solve the system of linear equations given by
442 * R1 B = (Qtranspose W Y) to find B.
443 *
444 * For efficiency, we lay out A and Q column-wise in memory because we
445 * frequently operate on the column vectors. Conversely, we lay out R row-wise.
446 *
447 * http://en.wikipedia.org/wiki/Numerical_methods_for_linear_least_squares
448 * http://en.wikipedia.org/wiki/Gram-Schmidt
449 */
450 static bool SolveLeastSquares(const float* x,
451 const float* y,
452 const float* w,
453 uint32_t m,
454 uint32_t n,
455 float* out_b,
456 float* out_det) {
457 // Expand the X vector to a matrix A, pre-multiplied by the weights.
458 float a[n][m]; // column-major order
459 for (uint32_t h = 0; h < m; h++) {
460 a[0][h] = w[h];
461 for (uint32_t i = 1; i < n; i++) {
462 a[i][h] = a[i - 1][h] * x[h];
463 }
464 }
465
466 // Apply the Gram-Schmidt process to A to obtain its QR decomposition.
467 float q[n][m]; // orthonormal basis, column-major order
468 float r[n][n]; // upper triangular matrix, row-major order
469 for (uint32_t j = 0; j < n; j++) {
470 for (uint32_t h = 0; h < m; h++) {
471 q[j][h] = a[j][h];
472 }
473 for (uint32_t i = 0; i < j; i++) {
474 float dot = VectorDot(&q[j][0], &q[i][0], m);
475 for (uint32_t h = 0; h < m; h++) {
476 q[j][h] -= dot * q[i][h];
477 }
478 }
479
480 float norm = VectorNorm(&q[j][0], m);
481 if (norm < 0.000001f) {
482 // vectors are linearly dependent or zero so no solution
483 return false;
484 }
485
486 float invNorm = 1.0f / norm;
487 for (uint32_t h = 0; h < m; h++) {
488 q[j][h] *= invNorm;
489 }
490 for (uint32_t i = 0; i < n; i++) {
491 r[j][i] = i < j ? 0 : VectorDot(&q[j][0], &a[i][0], m);
492 }
493 }
494
495 // Solve R B = Qt W Y to find B. This is easy because R is upper triangular.
496 // We just work from bottom-right to top-left calculating B's coefficients.
497 float wy[m];
498 for (uint32_t h = 0; h < m; h++) {
499 wy[h] = y[h] * w[h];
500 }
501 for (uint32_t i = n; i-- != 0;) {
502 out_b[i] = VectorDot(&q[i][0], wy, m);
503 for (uint32_t j = n - 1; j > i; j--) {
504 out_b[i] -= r[i][j] * out_b[j];
505 }
506 out_b[i] /= r[i][i];
507 }
508
509 // Calculate the coefficient of determination as 1 - (SSerr / SStot) where
510 // SSerr is the residual sum of squares (variance of the error),
511 // and SStot is the total sum of squares (variance of the data) where each
512 // has been weighted.
513 float ymean = 0;
514 for (uint32_t h = 0; h < m; h++) {
515 ymean += y[h];
516 }
517 ymean /= m;
518
519 float sserr = 0;
520 float sstot = 0;
521 for (uint32_t h = 0; h < m; h++) {
522 float err = y[h] - out_b[0];
523 float term = 1;
524 for (uint32_t i = 1; i < n; i++) {
525 term *= x[h];
526 err -= term * out_b[i];
527 }
528 sserr += w[h] * w[h] * err * err;
529 float var = y[h] - ymean;
530 sstot += w[h] * w[h] * var * var;
531 }
532 *out_det = sstot > 0.000001f ? 1.0f - (sserr / sstot) : 1;
533 return true;
534 }
535
536 void LeastSquaresVelocityTrackerStrategy::ClearPointers(BitSet32 id_bits) {
537 BitSet32 remaining_id_bits(movements_[index_].id_bits.value & ~id_bits.value);
538 movements_[index_].id_bits = remaining_id_bits;
539 }
540
541 bool LeastSquaresVelocityTrackerStrategy::GetEstimator(
542 uint32_t id,
543 Estimator* out_estimator) const {
544 out_estimator->Clear();
545
546 // Iterate over movement samples in reverse time order and collect samples.
547 float x[HISTORY_SIZE];
548 float y[HISTORY_SIZE];
549 float w[HISTORY_SIZE];
550 float time[HISTORY_SIZE];
551 uint32_t m = 0;
552 uint32_t index = index_;
553 const Movement& newest_movement = movements_[index_];
554 do {
555 const Movement& movement = movements_[index];
556 if (!movement.id_bits.has_bit(id))
557 break;
558
559 TimeDelta age = newest_movement.event_time - movement.event_time;
560 if (age > HORIZON)
561 break;
562
563 const Position& position = movement.GetPosition(id);
564 x[m] = position.x;
565 y[m] = position.y;
566 w[m] = ChooseWeight(index);
567 time[m] = -age.InSecondsF();
568 index = (index == 0 ? HISTORY_SIZE : index) - 1;
569 } while (++m < HISTORY_SIZE);
570
571 if (m == 0)
572 return false; // no data
573
574 // Calculate a least squares polynomial fit.
575 uint32_t degree = degree_;
576 if (degree > m - 1)
577 degree = m - 1;
578
579 if (degree >= 1) {
580 float xdet, ydet;
581 uint32_t n = degree + 1;
582 if (SolveLeastSquares(time, x, w, m, n, out_estimator->xcoeff, &xdet) &&
583 SolveLeastSquares(time, y, w, m, n, out_estimator->ycoeff, &ydet)) {
584 out_estimator->time = newest_movement.event_time;
585 out_estimator->degree = degree;
586 out_estimator->confidence = xdet * ydet;
587 return true;
588 }
589 }
590
591 // No velocity data available for this pointer, but we do have its current
592 // position.
593 out_estimator->xcoeff[0] = x[0];
594 out_estimator->ycoeff[0] = y[0];
595 out_estimator->time = newest_movement.event_time;
596 out_estimator->degree = 0;
597 out_estimator->confidence = 1;
598 return true;
599 }
600
601 float LeastSquaresVelocityTrackerStrategy::ChooseWeight(uint32_t index) const {
602 switch (weighting_) {
603 case WEIGHTING_DELTA: {
604 // Weight points based on how much time elapsed between them and the next
605 // point so that points that "cover" a shorter time span are weighed less.
606 // delta 0ms: 0.5
607 // delta 10ms: 1.0
608 if (index == index_) {
609 return 1.0f;
610 }
611 uint32_t next_index = (index + 1) % HISTORY_SIZE;
612 float delta_millis =
613 static_cast<float>((movements_[next_index].event_time -
614 movements_[index].event_time).InMillisecondsF());
615 if (delta_millis < 0)
616 return 0.5f;
617 if (delta_millis < 10)
618 return 0.5f + delta_millis * 0.05;
619
620 return 1.0f;
621 }
622
623 case WEIGHTING_CENTRAL: {
624 // Weight points based on their age, weighing very recent and very old
625 // points less.
626 // age 0ms: 0.5
627 // age 10ms: 1.0
628 // age 50ms: 1.0
629 // age 60ms: 0.5
630 float age_millis =
631 static_cast<float>((movements_[index_].event_time -
632 movements_[index].event_time).InMillisecondsF());
633 if (age_millis < 0)
634 return 0.5f;
635 if (age_millis < 10)
636 return 0.5f + age_millis * 0.05;
637 if (age_millis < 50)
638 return 1.0f;
639 if (age_millis < 60)
640 return 0.5f + (60 - age_millis) * 0.05;
641
642 return 0.5f;
643 }
644
645 case WEIGHTING_RECENT: {
646 // Weight points based on their age, weighing older points less.
647 // age 0ms: 1.0
648 // age 50ms: 1.0
649 // age 100ms: 0.5
650 float age_millis =
651 static_cast<float>((movements_[index_].event_time -
652 movements_[index].event_time).InMillisecondsF());
653 if (age_millis < 50) {
654 return 1.0f;
655 }
656 if (age_millis < 100) {
657 return 0.5f + (100 - age_millis) * 0.01f;
658 }
659 return 0.5f;
660 }
661
662 case WEIGHTING_NONE:
663 default:
664 return 1.0f;
665 }
666 }
667
668 // --- IntegratingVelocityTrackerStrategy ---
669
670 IntegratingVelocityTrackerStrategy::IntegratingVelocityTrackerStrategy(
671 uint32_t degree)
672 : degree_(degree) {}
673
674 IntegratingVelocityTrackerStrategy::~IntegratingVelocityTrackerStrategy() {}
675
676 void IntegratingVelocityTrackerStrategy::Clear() { pointer_id_bits_.clear(); }
677
678 void IntegratingVelocityTrackerStrategy::ClearPointers(BitSet32 id_bits) {
679 pointer_id_bits_.value &= ~id_bits.value;
680 }
681
682 void IntegratingVelocityTrackerStrategy::AddMovement(
683 const TimeTicks& event_time,
684 BitSet32 id_bits,
685 const Position* positions) {
686 uint32_t index = 0;
687 for (BitSet32 iter_id_bits(id_bits); !iter_id_bits.is_empty();) {
688 uint32_t id = iter_id_bits.clear_first_marked_bit();
689 State& state = mPointerState[id];
690 const Position& position = positions[index++];
691 if (pointer_id_bits_.has_bit(id))
692 UpdateState(state, event_time, position.x, position.y);
693 else
694 InitState(state, event_time, position.x, position.y);
695 }
696
697 pointer_id_bits_ = id_bits;
698 }
699
700 bool IntegratingVelocityTrackerStrategy::GetEstimator(
701 uint32_t id,
702 Estimator* out_estimator) const {
703 out_estimator->Clear();
704
705 if (pointer_id_bits_.has_bit(id)) {
706 const State& state = mPointerState[id];
707 PopulateEstimator(state, out_estimator);
708 return true;
709 }
710
711 return false;
712 }
713
714 void IntegratingVelocityTrackerStrategy::InitState(State& state,
715 const TimeTicks& event_time,
716 float xpos,
717 float ypos) const {
718 state.update_time = event_time;
719 state.degree = 0;
720 state.xpos = xpos;
721 state.xvel = 0;
722 state.xaccel = 0;
723 state.ypos = ypos;
724 state.yvel = 0;
725 state.yaccel = 0;
726 }
727
728 void IntegratingVelocityTrackerStrategy::UpdateState(
729 State& state,
730 const TimeTicks& event_time,
731 float xpos,
732 float ypos) const {
733 const base::TimeDelta MIN_TIME_DELTA = TimeDelta::FromMicroseconds(2);
734 const float FILTER_TIME_CONSTANT = 0.010f; // 10 milliseconds
735
736 if (event_time <= state.update_time + MIN_TIME_DELTA)
737 return;
738
739 float dt = static_cast<float>((event_time - state.update_time).InSecondsF());
740 state.update_time = event_time;
741
742 float xvel = (xpos - state.xpos) / dt;
743 float yvel = (ypos - state.ypos) / dt;
744 if (state.degree == 0) {
745 state.xvel = xvel;
746 state.yvel = yvel;
747 state.degree = 1;
748 } else {
749 float alpha = dt / (FILTER_TIME_CONSTANT + dt);
750 if (degree_ == 1) {
751 state.xvel += (xvel - state.xvel) * alpha;
752 state.yvel += (yvel - state.yvel) * alpha;
753 } else {
754 float xaccel = (xvel - state.xvel) / dt;
755 float yaccel = (yvel - state.yvel) / dt;
756 if (state.degree == 1) {
757 state.xaccel = xaccel;
758 state.yaccel = yaccel;
759 state.degree = 2;
760 } else {
761 state.xaccel += (xaccel - state.xaccel) * alpha;
762 state.yaccel += (yaccel - state.yaccel) * alpha;
763 }
764 state.xvel += (state.xaccel * dt) * alpha;
765 state.yvel += (state.yaccel * dt) * alpha;
766 }
767 }
768 state.xpos = xpos;
769 state.ypos = ypos;
770 }
771
772 void IntegratingVelocityTrackerStrategy::PopulateEstimator(
773 const State& state,
774 Estimator* out_estimator) const {
775 out_estimator->time = state.update_time;
776 out_estimator->confidence = 1.0f;
777 out_estimator->degree = state.degree;
778 out_estimator->xcoeff[0] = state.xpos;
779 out_estimator->xcoeff[1] = state.xvel;
780 out_estimator->xcoeff[2] = state.xaccel / 2;
781 out_estimator->ycoeff[0] = state.ypos;
782 out_estimator->ycoeff[1] = state.yvel;
783 out_estimator->ycoeff[2] = state.yaccel / 2;
784 }
785
786 } // namespace ui
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698