velocity_tracker.cc 28 KB

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