Chromium Code Reviews| 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 }; | |
| 476 DCHECK_LE(m, static_cast<uint32_t>(M_ARRAY_LENGTH)); | |
|
tdresser
2014/10/20 14:27:31
These DCHECKs are still relevant, aren't they?
Chris Masone
2014/10/20 16:05:22
Yes, you're right
| |
| 477 DCHECK_LE(n, static_cast<uint32_t>(N_ARRAY_LENGTH)); | |
| 478 #else | 475 #else |
| 479 const uint32_t M_ARRAY_LENGTH = m; | 476 const uint32_t M_ARRAY_LENGTH = m; |
| 480 const uint32_t N_ARRAY_LENGTH = n; | 477 const uint32_t N_ARRAY_LENGTH = n; |
| 481 #endif | 478 #endif |
| 482 | 479 |
| 483 // Expand the X vector to a matrix A, pre-multiplied by the weights. | 480 // 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 | 481 float a[N_ARRAY_LENGTH][M_ARRAY_LENGTH]; // column-major order |
| 485 for (uint32_t h = 0; h < m; h++) { | 482 for (uint32_t h = 0; h < m; h++) { |
| 486 a[0][h] = w[h]; | 483 a[0][h] = w[h]; |
| 487 for (uint32_t i = 1; i < n; i++) { | 484 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); | 563 BitSet32 remaining_id_bits(movements_[index_].id_bits.value & ~id_bits.value); |
| 567 movements_[index_].id_bits = remaining_id_bits; | 564 movements_[index_].id_bits = remaining_id_bits; |
| 568 } | 565 } |
| 569 | 566 |
| 570 bool LeastSquaresVelocityTrackerStrategy::GetEstimator( | 567 bool LeastSquaresVelocityTrackerStrategy::GetEstimator( |
| 571 uint32_t id, | 568 uint32_t id, |
| 572 Estimator* out_estimator) const { | 569 Estimator* out_estimator) const { |
| 573 out_estimator->Clear(); | 570 out_estimator->Clear(); |
| 574 | 571 |
| 575 // Iterate over movement samples in reverse time order and collect samples. | 572 // Iterate over movement samples in reverse time order and collect samples. |
| 576 float x[HISTORY_SIZE]; | 573 float x[kHistorySize]; |
| 577 float y[HISTORY_SIZE]; | 574 float y[kHistorySize]; |
| 578 float w[HISTORY_SIZE]; | 575 float w[kHistorySize]; |
| 579 float time[HISTORY_SIZE]; | 576 float time[kHistorySize]; |
| 580 uint32_t m = 0; | 577 uint32_t m = 0; |
| 581 uint32_t index = index_; | 578 uint32_t index = index_; |
| 582 const base::TimeDelta horizon = base::TimeDelta::FromMilliseconds(HORIZON_MS); | 579 const base::TimeDelta horizon = base::TimeDelta::FromMilliseconds(kHorizonMS); |
| 583 const Movement& newest_movement = movements_[index_]; | 580 const Movement& newest_movement = movements_[index_]; |
| 584 do { | 581 do { |
| 585 const Movement& movement = movements_[index]; | 582 const Movement& movement = movements_[index]; |
| 586 if (!movement.id_bits.has_bit(id)) | 583 if (!movement.id_bits.has_bit(id)) |
| 587 break; | 584 break; |
| 588 | 585 |
| 589 TimeDelta age = newest_movement.event_time - movement.event_time; | 586 TimeDelta age = newest_movement.event_time - movement.event_time; |
| 590 if (age > horizon) | 587 if (age > horizon) |
| 591 break; | 588 break; |
| 592 | 589 |
| 593 const Position& position = movement.GetPosition(id); | 590 const Position& position = movement.GetPosition(id); |
| 594 x[m] = position.x; | 591 x[m] = position.x; |
| 595 y[m] = position.y; | 592 y[m] = position.y; |
| 596 w[m] = ChooseWeight(index); | 593 w[m] = ChooseWeight(index); |
| 597 time[m] = -age.InSecondsF(); | 594 time[m] = -age.InSecondsF(); |
| 598 index = (index == 0 ? HISTORY_SIZE : index) - 1; | 595 index = (index == 0 ? kHistorySize : index) - 1; |
| 599 } while (++m < HISTORY_SIZE); | 596 } while (++m < kHistorySize); |
| 600 | 597 |
| 601 if (m == 0) | 598 if (m == 0) |
| 602 return false; // no data | 599 return false; // no data |
| 603 | 600 |
| 604 // Calculate a least squares polynomial fit. | 601 // Calculate a least squares polynomial fit. |
| 605 uint32_t degree = degree_; | 602 uint32_t degree = degree_; |
| 606 if (degree > m - 1) | 603 if (degree > m - 1) |
| 607 degree = m - 1; | 604 degree = m - 1; |
| 608 | 605 |
| 609 if (degree >= 1) { | 606 if (degree >= 1) { |
| (...skipping 21 matching lines...) Expand all Loading... | |
| 631 float LeastSquaresVelocityTrackerStrategy::ChooseWeight(uint32_t index) const { | 628 float LeastSquaresVelocityTrackerStrategy::ChooseWeight(uint32_t index) const { |
| 632 switch (weighting_) { | 629 switch (weighting_) { |
| 633 case WEIGHTING_DELTA: { | 630 case WEIGHTING_DELTA: { |
| 634 // Weight points based on how much time elapsed between them and the next | 631 // 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. | 632 // point so that points that "cover" a shorter time span are weighed less. |
| 636 // delta 0ms: 0.5 | 633 // delta 0ms: 0.5 |
| 637 // delta 10ms: 1.0 | 634 // delta 10ms: 1.0 |
| 638 if (index == index_) { | 635 if (index == index_) { |
| 639 return 1.0f; | 636 return 1.0f; |
| 640 } | 637 } |
| 641 uint32_t next_index = (index + 1) % HISTORY_SIZE; | 638 uint32_t next_index = (index + 1) % kHistorySize; |
| 642 float delta_millis = | 639 float delta_millis = |
| 643 static_cast<float>((movements_[next_index].event_time - | 640 static_cast<float>((movements_[next_index].event_time - |
| 644 movements_[index].event_time).InMillisecondsF()); | 641 movements_[index].event_time).InMillisecondsF()); |
| 645 if (delta_millis < 0) | 642 if (delta_millis < 0) |
| 646 return 0.5f; | 643 return 0.5f; |
| 647 if (delta_millis < 10) | 644 if (delta_millis < 10) |
| 648 return 0.5f + delta_millis * 0.05; | 645 return 0.5f + delta_millis * 0.05; |
| 649 | 646 |
| 650 return 1.0f; | 647 return 1.0f; |
| 651 } | 648 } |
| (...skipping 41 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
| 693 default: | 690 default: |
| 694 return 1.0f; | 691 return 1.0f; |
| 695 } | 692 } |
| 696 } | 693 } |
| 697 | 694 |
| 698 // --- IntegratingVelocityTrackerStrategy --- | 695 // --- IntegratingVelocityTrackerStrategy --- |
| 699 | 696 |
| 700 IntegratingVelocityTrackerStrategy::IntegratingVelocityTrackerStrategy( | 697 IntegratingVelocityTrackerStrategy::IntegratingVelocityTrackerStrategy( |
| 701 uint32_t degree) | 698 uint32_t degree) |
| 702 : degree_(degree) { | 699 : degree_(degree) { |
| 703 DCHECK_LT(degree_, static_cast<uint32_t>(Estimator::MAX_DEGREE)); | 700 DCHECK_LT(degree_, static_cast<uint32_t>(Estimator::kMaxDegree)); |
| 704 } | 701 } |
| 705 | 702 |
| 706 IntegratingVelocityTrackerStrategy::~IntegratingVelocityTrackerStrategy() {} | 703 IntegratingVelocityTrackerStrategy::~IntegratingVelocityTrackerStrategy() {} |
| 707 | 704 |
| 708 void IntegratingVelocityTrackerStrategy::Clear() { pointer_id_bits_.clear(); } | 705 void IntegratingVelocityTrackerStrategy::Clear() { pointer_id_bits_.clear(); } |
| 709 | 706 |
| 710 void IntegratingVelocityTrackerStrategy::ClearPointers(BitSet32 id_bits) { | 707 void IntegratingVelocityTrackerStrategy::ClearPointers(BitSet32 id_bits) { |
| 711 pointer_id_bits_.value &= ~id_bits.value; | 708 pointer_id_bits_.value &= ~id_bits.value; |
| 712 } | 709 } |
| 713 | 710 |
| (...skipping 95 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
| 809 out_estimator->degree = state.degree; | 806 out_estimator->degree = state.degree; |
| 810 out_estimator->xcoeff[0] = state.xpos; | 807 out_estimator->xcoeff[0] = state.xpos; |
| 811 out_estimator->xcoeff[1] = state.xvel; | 808 out_estimator->xcoeff[1] = state.xvel; |
| 812 out_estimator->xcoeff[2] = state.xaccel / 2; | 809 out_estimator->xcoeff[2] = state.xaccel / 2; |
| 813 out_estimator->ycoeff[0] = state.ypos; | 810 out_estimator->ycoeff[0] = state.ypos; |
| 814 out_estimator->ycoeff[1] = state.yvel; | 811 out_estimator->ycoeff[1] = state.yvel; |
| 815 out_estimator->ycoeff[2] = state.yaccel / 2; | 812 out_estimator->ycoeff[2] = state.yaccel / 2; |
| 816 } | 813 } |
| 817 | 814 |
| 818 } // namespace ui | 815 } // namespace ui |
| OLD | NEW |