OLD | NEW |
1 // Copyright 2014 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "ui/events/gesture_detection/velocity_tracker.h" | 5 #include "ui/events/gesture_detection/velocity_tracker.h" |
6 | 6 |
7 #include <cmath> | 7 #include <cmath> |
8 | 8 |
9 #include "base/logging.h" | 9 #include "base/logging.h" |
10 #include "ui/events/gesture_detection/motion_event.h" | 10 #include "ui/events/gesture_detection/motion_event.h" |
(...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
44 // determining that a pointer has stopped moving. This is a larger threshold | 44 // determining that a pointer has stopped moving. This is a larger threshold |
45 // than |kAssumePointerMoveStoppedTimeMs|, as some devices may delay synthesis | 45 // than |kAssumePointerMoveStoppedTimeMs|, as some devices may delay synthesis |
46 // of ACTION_{UP|POINTER_UP} to reduce risk of noisy release. | 46 // of ACTION_{UP|POINTER_UP} to reduce risk of noisy release. |
47 const int kAssumePointerUpStoppedTimeMs = 80; | 47 const int kAssumePointerUpStoppedTimeMs = 80; |
48 | 48 |
49 struct Position { | 49 struct Position { |
50 float x, y; | 50 float x, y; |
51 }; | 51 }; |
52 | 52 |
53 struct Estimator { | 53 struct Estimator { |
54 enum { MAX_DEGREE = 4 }; | 54 static const uint8_t kMaxDegree = 4; |
55 | 55 |
56 // Estimator time base. | 56 // Estimator time base. |
57 TimeTicks time; | 57 TimeTicks time; |
58 | 58 |
59 // Polynomial coefficients describing motion in X and Y. | 59 // Polynomial coefficients describing motion in X and Y. |
60 float xcoeff[MAX_DEGREE + 1], ycoeff[MAX_DEGREE + 1]; | 60 float xcoeff[kMaxDegree + 1], ycoeff[kMaxDegree + 1]; |
61 | 61 |
62 // Polynomial degree (number of coefficients), or zero if no information is | 62 // Polynomial degree (number of coefficients), or zero if no information is |
63 // available. | 63 // available. |
64 uint32_t degree; | 64 uint32_t degree; |
65 | 65 |
66 // Confidence (coefficient of determination), between 0 (no fit) | 66 // Confidence (coefficient of determination), between 0 (no fit) |
67 // and 1 (perfect fit). | 67 // and 1 (perfect fit). |
68 float confidence; | 68 float confidence; |
69 | 69 |
70 inline void Clear() { | 70 inline void Clear() { |
71 time = TimeTicks(); | 71 time = TimeTicks(); |
72 degree = 0; | 72 degree = 0; |
73 confidence = 0; | 73 confidence = 0; |
74 for (size_t i = 0; i <= MAX_DEGREE; i++) { | 74 for (size_t i = 0; i <= kMaxDegree; i++) { |
75 xcoeff[i] = 0; | 75 xcoeff[i] = 0; |
76 ycoeff[i] = 0; | 76 ycoeff[i] = 0; |
77 } | 77 } |
78 } | 78 } |
79 }; | 79 }; |
80 | 80 |
81 float VectorDot(const float* a, const float* b, uint32_t m) { | 81 float VectorDot(const float* a, const float* b, uint32_t m) { |
82 float r = 0; | 82 float r = 0; |
83 while (m--) { | 83 while (m--) { |
84 r += *(a++) * *(b++); | 84 r += *(a++) * *(b++); |
(...skipping 22 matching lines...) Expand all Loading... |
107 | 107 |
108 // Weight such that points within a certain horizon are weighed more than | 108 // Weight such that points within a certain horizon are weighed more than |
109 // those outside of that horizon. | 109 // those outside of that horizon. |
110 WEIGHTING_CENTRAL, | 110 WEIGHTING_CENTRAL, |
111 | 111 |
112 // Weight such that points older than a certain amount are weighed less. | 112 // Weight such that points older than a certain amount are weighed less. |
113 WEIGHTING_RECENT, | 113 WEIGHTING_RECENT, |
114 }; | 114 }; |
115 | 115 |
116 // Number of samples to keep. | 116 // Number of samples to keep. |
117 enum { HISTORY_SIZE = 20 }; | 117 static const uint8_t kHistorySize = 20; |
118 | 118 |
119 // Degree must be no greater than Estimator::MAX_DEGREE. | 119 // Degree must be no greater than Estimator::kMaxDegree. |
120 LeastSquaresVelocityTrackerStrategy(uint32_t degree, | 120 LeastSquaresVelocityTrackerStrategy(uint32_t degree, |
121 Weighting weighting = WEIGHTING_NONE); | 121 Weighting weighting = WEIGHTING_NONE); |
122 virtual ~LeastSquaresVelocityTrackerStrategy(); | 122 virtual ~LeastSquaresVelocityTrackerStrategy(); |
123 | 123 |
124 virtual void Clear() override; | 124 virtual void Clear() override; |
125 virtual void ClearPointers(BitSet32 id_bits) override; | 125 virtual void ClearPointers(BitSet32 id_bits) override; |
126 virtual void AddMovement(const TimeTicks& event_time, | 126 virtual void AddMovement(const TimeTicks& event_time, |
127 BitSet32 id_bits, | 127 BitSet32 id_bits, |
128 const Position* positions) override; | 128 const Position* positions) override; |
129 virtual bool GetEstimator(uint32_t id, | 129 virtual bool GetEstimator(uint32_t id, |
130 Estimator* out_estimator) const override; | 130 Estimator* out_estimator) const override; |
131 | 131 |
132 private: | 132 private: |
133 // Sample horizon. | 133 // Sample horizon. |
134 // We don't use too much history by default since we want to react to quick | 134 // We don't use too much history by default since we want to react to quick |
135 // changes in direction. | 135 // changes in direction. |
136 enum { HORIZON_MS = 100 }; | 136 static const uint8_t kHorizonMS = 100; |
137 | 137 |
138 struct Movement { | 138 struct Movement { |
139 TimeTicks event_time; | 139 TimeTicks event_time; |
140 BitSet32 id_bits; | 140 BitSet32 id_bits; |
141 Position positions[VelocityTracker::MAX_POINTERS]; | 141 Position positions[VelocityTracker::MAX_POINTERS]; |
142 | 142 |
143 inline const Position& GetPosition(uint32_t id) const { | 143 inline const Position& GetPosition(uint32_t id) const { |
144 return positions[id_bits.get_index_of_bit(id)]; | 144 return positions[id_bits.get_index_of_bit(id)]; |
145 } | 145 } |
146 }; | 146 }; |
147 | 147 |
148 float ChooseWeight(uint32_t index) const; | 148 float ChooseWeight(uint32_t index) const; |
149 | 149 |
150 const uint32_t degree_; | 150 const uint32_t degree_; |
151 const Weighting weighting_; | 151 const Weighting weighting_; |
152 uint32_t index_; | 152 uint32_t index_; |
153 Movement movements_[HISTORY_SIZE]; | 153 Movement movements_[kHistorySize]; |
154 }; | 154 }; |
155 | 155 |
156 // Velocity tracker algorithm that uses an IIR filter. | 156 // Velocity tracker algorithm that uses an IIR filter. |
157 class IntegratingVelocityTrackerStrategy : public VelocityTrackerStrategy { | 157 class IntegratingVelocityTrackerStrategy : public VelocityTrackerStrategy { |
158 public: | 158 public: |
159 // Degree must be 1 or 2. | 159 // Degree must be 1 or 2. |
160 explicit IntegratingVelocityTrackerStrategy(uint32_t degree); | 160 explicit IntegratingVelocityTrackerStrategy(uint32_t degree); |
161 virtual ~IntegratingVelocityTrackerStrategy(); | 161 virtual ~IntegratingVelocityTrackerStrategy(); |
162 | 162 |
163 virtual void Clear() override; | 163 virtual void Clear() override; |
(...skipping 200 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
364 } | 364 } |
365 *out_vx = 0; | 365 *out_vx = 0; |
366 *out_vy = 0; | 366 *out_vy = 0; |
367 return false; | 367 return false; |
368 } | 368 } |
369 | 369 |
370 void LeastSquaresVelocityTrackerStrategy::AddMovement( | 370 void LeastSquaresVelocityTrackerStrategy::AddMovement( |
371 const TimeTicks& event_time, | 371 const TimeTicks& event_time, |
372 BitSet32 id_bits, | 372 BitSet32 id_bits, |
373 const Position* positions) { | 373 const Position* positions) { |
374 if (++index_ == HISTORY_SIZE) { | 374 if (++index_ == kHistorySize) { |
375 index_ = 0; | 375 index_ = 0; |
376 } | 376 } |
377 | 377 |
378 Movement& movement = movements_[index_]; | 378 Movement& movement = movements_[index_]; |
379 movement.event_time = event_time; | 379 movement.event_time = event_time; |
380 movement.id_bits = id_bits; | 380 movement.id_bits = id_bits; |
381 uint32_t count = id_bits.count(); | 381 uint32_t count = id_bits.count(); |
382 for (uint32_t i = 0; i < count; i++) { | 382 for (uint32_t i = 0; i < count; i++) { |
383 movement.positions[i] = positions[i]; | 383 movement.positions[i] = positions[i]; |
384 } | 384 } |
385 } | 385 } |
386 | 386 |
387 bool VelocityTracker::GetEstimator(uint32_t id, | 387 bool VelocityTracker::GetEstimator(uint32_t id, |
388 Estimator* out_estimator) const { | 388 Estimator* out_estimator) const { |
389 return strategy_->GetEstimator(id, out_estimator); | 389 return strategy_->GetEstimator(id, out_estimator); |
390 } | 390 } |
391 | 391 |
392 // --- LeastSquaresVelocityTrackerStrategy --- | 392 // --- LeastSquaresVelocityTrackerStrategy --- |
393 | 393 |
394 LeastSquaresVelocityTrackerStrategy::LeastSquaresVelocityTrackerStrategy( | 394 LeastSquaresVelocityTrackerStrategy::LeastSquaresVelocityTrackerStrategy( |
395 uint32_t degree, | 395 uint32_t degree, |
396 Weighting weighting) | 396 Weighting weighting) |
397 : degree_(degree), weighting_(weighting) { | 397 : degree_(degree), weighting_(weighting) { |
398 DCHECK_LT(degree_, static_cast<uint32_t>(Estimator::MAX_DEGREE)); | 398 DCHECK_LT(degree_, static_cast<uint32_t>(Estimator::kMaxDegree)); |
399 Clear(); | 399 Clear(); |
400 } | 400 } |
401 | 401 |
402 LeastSquaresVelocityTrackerStrategy::~LeastSquaresVelocityTrackerStrategy() {} | 402 LeastSquaresVelocityTrackerStrategy::~LeastSquaresVelocityTrackerStrategy() {} |
403 | 403 |
404 void LeastSquaresVelocityTrackerStrategy::Clear() { | 404 void LeastSquaresVelocityTrackerStrategy::Clear() { |
405 index_ = 0; | 405 index_ = 0; |
406 movements_[0].id_bits.clear(); | 406 movements_[0].id_bits.clear(); |
407 } | 407 } |
408 | 408 |
(...skipping 53 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
462 static bool SolveLeastSquares(const float* x, | 462 static bool SolveLeastSquares(const float* x, |
463 const float* y, | 463 const float* y, |
464 const float* w, | 464 const float* w, |
465 uint32_t m, | 465 uint32_t m, |
466 uint32_t n, | 466 uint32_t n, |
467 float* out_b, | 467 float* out_b, |
468 float* out_det) { | 468 float* out_det) { |
469 // MSVC does not support variable-length arrays (used by the original Android | 469 // MSVC does not support variable-length arrays (used by the original Android |
470 // implementation of this function). | 470 // implementation of this function). |
471 #if defined(COMPILER_MSVC) | 471 #if defined(COMPILER_MSVC) |
472 enum { | 472 const uint32_t M_ARRAY_LENGTH = |
473 M_ARRAY_LENGTH = LeastSquaresVelocityTrackerStrategy::HISTORY_SIZE, | 473 LeastSquaresVelocityTrackerStrategy::kHistorySize; |
474 N_ARRAY_LENGTH = Estimator::MAX_DEGREE | 474 const uint32_t N_ARRAY_LENGTH = Estimator::kMaxDegree; |
475 }; | 475 DCHECK_LE(m, M_ARRAY_LENGTH); |
476 DCHECK_LE(m, static_cast<uint32_t>(M_ARRAY_LENGTH)); | 476 DCHECK_LE(n, N_ARRAY_LENGTH); |
477 DCHECK_LE(n, static_cast<uint32_t>(N_ARRAY_LENGTH)); | |
478 #else | 477 #else |
479 const uint32_t M_ARRAY_LENGTH = m; | 478 const uint32_t M_ARRAY_LENGTH = m; |
480 const uint32_t N_ARRAY_LENGTH = n; | 479 const uint32_t N_ARRAY_LENGTH = n; |
481 #endif | 480 #endif |
482 | 481 |
483 // Expand the X vector to a matrix A, pre-multiplied by the weights. | 482 // Expand the X vector to a matrix A, pre-multiplied by the weights. |
484 float a[N_ARRAY_LENGTH][M_ARRAY_LENGTH]; // column-major order | 483 float a[N_ARRAY_LENGTH][M_ARRAY_LENGTH]; // column-major order |
485 for (uint32_t h = 0; h < m; h++) { | 484 for (uint32_t h = 0; h < m; h++) { |
486 a[0][h] = w[h]; | 485 a[0][h] = w[h]; |
487 for (uint32_t i = 1; i < n; i++) { | 486 for (uint32_t i = 1; i < n; i++) { |
(...skipping 78 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
566 BitSet32 remaining_id_bits(movements_[index_].id_bits.value & ~id_bits.value); | 565 BitSet32 remaining_id_bits(movements_[index_].id_bits.value & ~id_bits.value); |
567 movements_[index_].id_bits = remaining_id_bits; | 566 movements_[index_].id_bits = remaining_id_bits; |
568 } | 567 } |
569 | 568 |
570 bool LeastSquaresVelocityTrackerStrategy::GetEstimator( | 569 bool LeastSquaresVelocityTrackerStrategy::GetEstimator( |
571 uint32_t id, | 570 uint32_t id, |
572 Estimator* out_estimator) const { | 571 Estimator* out_estimator) const { |
573 out_estimator->Clear(); | 572 out_estimator->Clear(); |
574 | 573 |
575 // Iterate over movement samples in reverse time order and collect samples. | 574 // Iterate over movement samples in reverse time order and collect samples. |
576 float x[HISTORY_SIZE]; | 575 float x[kHistorySize]; |
577 float y[HISTORY_SIZE]; | 576 float y[kHistorySize]; |
578 float w[HISTORY_SIZE]; | 577 float w[kHistorySize]; |
579 float time[HISTORY_SIZE]; | 578 float time[kHistorySize]; |
580 uint32_t m = 0; | 579 uint32_t m = 0; |
581 uint32_t index = index_; | 580 uint32_t index = index_; |
582 const base::TimeDelta horizon = base::TimeDelta::FromMilliseconds(HORIZON_MS); | 581 const base::TimeDelta horizon = base::TimeDelta::FromMilliseconds(kHorizonMS); |
583 const Movement& newest_movement = movements_[index_]; | 582 const Movement& newest_movement = movements_[index_]; |
584 do { | 583 do { |
585 const Movement& movement = movements_[index]; | 584 const Movement& movement = movements_[index]; |
586 if (!movement.id_bits.has_bit(id)) | 585 if (!movement.id_bits.has_bit(id)) |
587 break; | 586 break; |
588 | 587 |
589 TimeDelta age = newest_movement.event_time - movement.event_time; | 588 TimeDelta age = newest_movement.event_time - movement.event_time; |
590 if (age > horizon) | 589 if (age > horizon) |
591 break; | 590 break; |
592 | 591 |
593 const Position& position = movement.GetPosition(id); | 592 const Position& position = movement.GetPosition(id); |
594 x[m] = position.x; | 593 x[m] = position.x; |
595 y[m] = position.y; | 594 y[m] = position.y; |
596 w[m] = ChooseWeight(index); | 595 w[m] = ChooseWeight(index); |
597 time[m] = -age.InSecondsF(); | 596 time[m] = -age.InSecondsF(); |
598 index = (index == 0 ? HISTORY_SIZE : index) - 1; | 597 index = (index == 0 ? kHistorySize : index) - 1; |
599 } while (++m < HISTORY_SIZE); | 598 } while (++m < kHistorySize); |
600 | 599 |
601 if (m == 0) | 600 if (m == 0) |
602 return false; // no data | 601 return false; // no data |
603 | 602 |
604 // Calculate a least squares polynomial fit. | 603 // Calculate a least squares polynomial fit. |
605 uint32_t degree = degree_; | 604 uint32_t degree = degree_; |
606 if (degree > m - 1) | 605 if (degree > m - 1) |
607 degree = m - 1; | 606 degree = m - 1; |
608 | 607 |
609 if (degree >= 1) { | 608 if (degree >= 1) { |
(...skipping 21 matching lines...) Expand all Loading... |
631 float LeastSquaresVelocityTrackerStrategy::ChooseWeight(uint32_t index) const { | 630 float LeastSquaresVelocityTrackerStrategy::ChooseWeight(uint32_t index) const { |
632 switch (weighting_) { | 631 switch (weighting_) { |
633 case WEIGHTING_DELTA: { | 632 case WEIGHTING_DELTA: { |
634 // Weight points based on how much time elapsed between them and the next | 633 // Weight points based on how much time elapsed between them and the next |
635 // point so that points that "cover" a shorter time span are weighed less. | 634 // point so that points that "cover" a shorter time span are weighed less. |
636 // delta 0ms: 0.5 | 635 // delta 0ms: 0.5 |
637 // delta 10ms: 1.0 | 636 // delta 10ms: 1.0 |
638 if (index == index_) { | 637 if (index == index_) { |
639 return 1.0f; | 638 return 1.0f; |
640 } | 639 } |
641 uint32_t next_index = (index + 1) % HISTORY_SIZE; | 640 uint32_t next_index = (index + 1) % kHistorySize; |
642 float delta_millis = | 641 float delta_millis = |
643 static_cast<float>((movements_[next_index].event_time - | 642 static_cast<float>((movements_[next_index].event_time - |
644 movements_[index].event_time).InMillisecondsF()); | 643 movements_[index].event_time).InMillisecondsF()); |
645 if (delta_millis < 0) | 644 if (delta_millis < 0) |
646 return 0.5f; | 645 return 0.5f; |
647 if (delta_millis < 10) | 646 if (delta_millis < 10) |
648 return 0.5f + delta_millis * 0.05; | 647 return 0.5f + delta_millis * 0.05; |
649 | 648 |
650 return 1.0f; | 649 return 1.0f; |
651 } | 650 } |
(...skipping 41 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
693 default: | 692 default: |
694 return 1.0f; | 693 return 1.0f; |
695 } | 694 } |
696 } | 695 } |
697 | 696 |
698 // --- IntegratingVelocityTrackerStrategy --- | 697 // --- IntegratingVelocityTrackerStrategy --- |
699 | 698 |
700 IntegratingVelocityTrackerStrategy::IntegratingVelocityTrackerStrategy( | 699 IntegratingVelocityTrackerStrategy::IntegratingVelocityTrackerStrategy( |
701 uint32_t degree) | 700 uint32_t degree) |
702 : degree_(degree) { | 701 : degree_(degree) { |
703 DCHECK_LT(degree_, static_cast<uint32_t>(Estimator::MAX_DEGREE)); | 702 DCHECK_LT(degree_, static_cast<uint32_t>(Estimator::kMaxDegree)); |
704 } | 703 } |
705 | 704 |
706 IntegratingVelocityTrackerStrategy::~IntegratingVelocityTrackerStrategy() {} | 705 IntegratingVelocityTrackerStrategy::~IntegratingVelocityTrackerStrategy() {} |
707 | 706 |
708 void IntegratingVelocityTrackerStrategy::Clear() { pointer_id_bits_.clear(); } | 707 void IntegratingVelocityTrackerStrategy::Clear() { pointer_id_bits_.clear(); } |
709 | 708 |
710 void IntegratingVelocityTrackerStrategy::ClearPointers(BitSet32 id_bits) { | 709 void IntegratingVelocityTrackerStrategy::ClearPointers(BitSet32 id_bits) { |
711 pointer_id_bits_.value &= ~id_bits.value; | 710 pointer_id_bits_.value &= ~id_bits.value; |
712 } | 711 } |
713 | 712 |
(...skipping 95 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
809 out_estimator->degree = state.degree; | 808 out_estimator->degree = state.degree; |
810 out_estimator->xcoeff[0] = state.xpos; | 809 out_estimator->xcoeff[0] = state.xpos; |
811 out_estimator->xcoeff[1] = state.xvel; | 810 out_estimator->xcoeff[1] = state.xvel; |
812 out_estimator->xcoeff[2] = state.xaccel / 2; | 811 out_estimator->xcoeff[2] = state.xaccel / 2; |
813 out_estimator->ycoeff[0] = state.ypos; | 812 out_estimator->ycoeff[0] = state.ypos; |
814 out_estimator->ycoeff[1] = state.yvel; | 813 out_estimator->ycoeff[1] = state.yvel; |
815 out_estimator->ycoeff[2] = state.yaccel / 2; | 814 out_estimator->ycoeff[2] = state.yaccel / 2; |
816 } | 815 } |
817 | 816 |
818 } // namespace ui | 817 } // namespace ui |
OLD | NEW |