blob: 0f2cffc14554823d06700f4d5054930ddef0da21 [file] [log] [blame]
// Copyright 2014 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "ui/events/gesture_detection/velocity_tracker.h"
#include <stddef.h>
#include <cmath>
#include "base/logging.h"
#include "ui/events/gesture_detection/motion_event.h"
using base::TimeDelta;
using base::TimeTicks;
namespace ui {
// Implements a particular velocity tracker algorithm.
class VelocityTrackerStrategy {
public:
virtual ~VelocityTrackerStrategy() {}
virtual void Clear() = 0;
virtual void ClearPointers(BitSet32 id_bits) = 0;
virtual void AddMovement(const base::TimeTicks& event_time,
BitSet32 id_bits,
const Position* positions) = 0;
virtual bool GetEstimator(uint32_t id, Estimator* out_estimator) const = 0;
protected:
VelocityTrackerStrategy() {}
};
namespace {
static_assert(MotionEvent::MAX_POINTER_ID < 32, "max pointer id too large");
// Threshold between Action::MOVE events for determining that a pointer has
// stopped moving. Some input devices do not send Action::MOVE events in the
// case where a pointer has stopped. We need to detect this case so that we can
// accurately predict the velocity after the pointer starts moving again.
const int kAssumePointerMoveStoppedTimeMs = 40;
// Threshold between Action::MOVE and Action::{UP|POINTER_UP} events for
// determining that a pointer has stopped moving. This is a larger threshold
// than |kAssumePointerMoveStoppedTimeMs|, as some devices may delay synthesis
// of Action::{UP|POINTER_UP} to reduce risk of noisy release.
const int kAssumePointerUpStoppedTimeMs = 80;
struct Position {
float x, y;
};
struct Estimator {
static const uint8_t kMaxDegree = 4;
// Estimator time base.
TimeTicks time;
// Polynomial coefficients describing motion in X and Y.
float xcoeff[kMaxDegree + 1], ycoeff[kMaxDegree + 1];
// Polynomial degree (number of coefficients), or zero if no information is
// available.
uint32_t degree;
// Confidence (coefficient of determination), between 0 (no fit)
// and 1 (perfect fit).
float confidence;
inline void Clear() {
time = TimeTicks();
degree = 0;
confidence = 0;
for (size_t i = 0; i <= kMaxDegree; i++) {
xcoeff[i] = 0;
ycoeff[i] = 0;
}
}
};
float VectorDot(const float* a, const float* b, uint32_t m) {
float r = 0;
while (m--) {
r += *(a++) * *(b++);
}
return r;
}
float VectorNorm(const float* a, uint32_t m) {
float r = 0;
while (m--) {
float t = *(a++);
r += t * t;
}
return sqrtf(r);
}
// Velocity tracker algorithm based on least-squares linear regression.
class LeastSquaresVelocityTrackerStrategy : public VelocityTrackerStrategy {
public:
enum Weighting {
// No weights applied. All data points are equally reliable.
WEIGHTING_NONE,
// Weight by time delta. Data points clustered together are weighted less.
WEIGHTING_DELTA,
// Weight such that points within a certain horizon are weighed more than
// those outside of that horizon.
WEIGHTING_CENTRAL,
// Weight such that points older than a certain amount are weighed less.
WEIGHTING_RECENT,
};
enum Restriction {
// There's no restriction on the output of the velocity tracker.
RESTRICTION_NONE,
// If the velocity determined by the tracker is in a sufficiently different
// direction from the primary motion of the finger for the events being
// considered for velocity calculation, return a velocity of 0.
RESTRICTION_ALIGNED_DIRECTIONS
};
// Number of samples to keep.
static const uint8_t kHistorySize = 20;
// Degree must be no greater than Estimator::kMaxDegree.
LeastSquaresVelocityTrackerStrategy(
uint32_t degree,
Weighting weighting,
Restriction restriction);
~LeastSquaresVelocityTrackerStrategy() override;
void Clear() override;
void ClearPointers(BitSet32 id_bits) override;
void AddMovement(const TimeTicks& event_time,
BitSet32 id_bits,
const Position* positions) override;
bool GetEstimator(uint32_t id, Estimator* out_estimator) const override;
private:
// Sample horizon.
// We don't use too much history by default since we want to react to quick
// changes in direction.
static const uint8_t kHorizonMS = 100;
struct Movement {
TimeTicks event_time;
BitSet32 id_bits;
Position positions[VelocityTracker::MAX_POINTERS];
inline const Position& GetPosition(uint32_t id) const {
return positions[id_bits.get_index_of_bit(id)];
}
};
float ChooseWeight(uint32_t index) const;
const uint32_t degree_;
const Weighting weighting_;
const Restriction restriction_;
uint32_t index_;
Movement movements_[kHistorySize];
};
// Velocity tracker algorithm that uses an IIR filter.
class IntegratingVelocityTrackerStrategy : public VelocityTrackerStrategy {
public:
// Degree must be 1 or 2.
explicit IntegratingVelocityTrackerStrategy(uint32_t degree);
~IntegratingVelocityTrackerStrategy() override;
void Clear() override;
void ClearPointers(BitSet32 id_bits) override;
void AddMovement(const TimeTicks& event_time,
BitSet32 id_bits,
const Position* positions) override;
bool GetEstimator(uint32_t id, Estimator* out_estimator) const override;
private:
// Current state estimate for a particular pointer.
struct State {
TimeTicks update_time;
uint32_t degree;
float xpos, xvel, xaccel;
float ypos, yvel, yaccel;
};
const uint32_t degree_;
BitSet32 pointer_id_bits_;
State mPointerState[MotionEvent::MAX_POINTER_ID + 1];
void InitState(State& state,
const TimeTicks& event_time,
float xpos,
float ypos) const;
void UpdateState(State& state,
const TimeTicks& event_time,
float xpos,
float ypos) const;
void PopulateEstimator(const State& state, Estimator* out_estimator) const;
};
VelocityTrackerStrategy* CreateStrategy(VelocityTracker::Strategy strategy) {
LeastSquaresVelocityTrackerStrategy::Weighting none =
LeastSquaresVelocityTrackerStrategy::WEIGHTING_NONE;
LeastSquaresVelocityTrackerStrategy::Restriction no_restriction =
LeastSquaresVelocityTrackerStrategy::RESTRICTION_NONE;
switch (strategy) {
case VelocityTracker::LSQ1:
return new LeastSquaresVelocityTrackerStrategy(1, none, no_restriction);
case VelocityTracker::LSQ2:
return new LeastSquaresVelocityTrackerStrategy(2, none, no_restriction);
case VelocityTracker::LSQ2_RESTRICTED:
return new LeastSquaresVelocityTrackerStrategy(
2, LeastSquaresVelocityTrackerStrategy::WEIGHTING_NONE,
LeastSquaresVelocityTrackerStrategy::RESTRICTION_ALIGNED_DIRECTIONS);
case VelocityTracker::LSQ3:
return new LeastSquaresVelocityTrackerStrategy(3, none, no_restriction);
case VelocityTracker::WLSQ2_DELTA:
return new LeastSquaresVelocityTrackerStrategy(
2, LeastSquaresVelocityTrackerStrategy::WEIGHTING_DELTA,
no_restriction);
case VelocityTracker::WLSQ2_CENTRAL:
return new LeastSquaresVelocityTrackerStrategy(
2, LeastSquaresVelocityTrackerStrategy::WEIGHTING_CENTRAL,
no_restriction);
case VelocityTracker::WLSQ2_RECENT:
return new LeastSquaresVelocityTrackerStrategy(
2, LeastSquaresVelocityTrackerStrategy::WEIGHTING_RECENT,
no_restriction);
case VelocityTracker::INT1:
return new IntegratingVelocityTrackerStrategy(1);
case VelocityTracker::INT2:
return new IntegratingVelocityTrackerStrategy(2);
}
NOTREACHED() << "Unrecognized velocity tracker strategy: " << strategy;
// Quadratic regression is a safe default.
return CreateStrategy(VelocityTracker::STRATEGY_DEFAULT);
}
} // namespace
// --- VelocityTracker ---
VelocityTracker::VelocityTracker(Strategy strategy)
: current_pointer_id_bits_(0),
active_pointer_id_(-1),
strategy_(CreateStrategy(strategy)) {}
VelocityTracker::~VelocityTracker() {}
void VelocityTracker::Clear() {
current_pointer_id_bits_.clear();
active_pointer_id_ = -1;
strategy_->Clear();
}
void VelocityTracker::ClearPointers(BitSet32 id_bits) {
BitSet32 remaining_id_bits(current_pointer_id_bits_.value & ~id_bits.value);
current_pointer_id_bits_ = remaining_id_bits;
if (active_pointer_id_ >= 0 && id_bits.has_bit(active_pointer_id_)) {
active_pointer_id_ = !remaining_id_bits.is_empty()
? remaining_id_bits.first_marked_bit()
: -1;
}
strategy_->ClearPointers(id_bits);
}
void VelocityTracker::AddMovement(const TimeTicks& event_time,
BitSet32 id_bits,
const Position* positions) {
while (id_bits.count() > MAX_POINTERS)
id_bits.clear_last_marked_bit();
if ((current_pointer_id_bits_.value & id_bits.value) &&
(event_time - last_event_time_) >=
base::TimeDelta::FromMilliseconds(kAssumePointerMoveStoppedTimeMs)) {
// We have not received any movements for too long. Assume that all pointers
// have stopped.
strategy_->Clear();
}
last_event_time_ = event_time;
current_pointer_id_bits_ = id_bits;
if (active_pointer_id_ < 0 || !id_bits.has_bit(active_pointer_id_))
active_pointer_id_ = id_bits.is_empty() ? -1 : id_bits.first_marked_bit();
strategy_->AddMovement(event_time, id_bits, positions);
}
void VelocityTracker::AddMovement(const MotionEvent& event) {
switch (event.GetAction()) {
case MotionEvent::Action::DOWN:
// case MotionEvent::HOVER_ENTER:
// Clear all pointers on down before adding the new movement.
Clear();
break;
case MotionEvent::Action::POINTER_DOWN: {
// Start a new movement trace for a pointer that just went down.
// We do this on down instead of on up because the client may want to
// query the final velocity for a pointer that just went up.
BitSet32 downIdBits;
downIdBits.mark_bit(event.GetPointerId(event.GetActionIndex()));
ClearPointers(downIdBits);
break;
}
case MotionEvent::Action::MOVE:
// case MotionEvent::Action::HOVER_MOVE:
break;
case MotionEvent::Action::UP:
case MotionEvent::Action::POINTER_UP:
// Note that Action::UP and Action::POINTER_UP always report the last
// known position of the pointers that went up. Action::POINTER_UP does
// include the new position of pointers that remained down but we will
// also receive an Action::MOVE with this information if any of them
// actually moved. Since we don't know how many pointers will be going up
// at once it makes sense to just wait for the following Action::MOVE
// before adding the movement. However, if the up event itself is delayed
// because of (difficult albeit possible) prolonged stationary screen
// contact, assume that motion has stopped.
if ((event.GetEventTime() - last_event_time_) >=
base::TimeDelta::FromMilliseconds(kAssumePointerUpStoppedTimeMs))
strategy_->Clear();
return;
default:
// Ignore all other actions because they do not convey any new information
// about pointer movement. We also want to preserve the last known
// velocity of the pointers.
return;
}
size_t pointer_count = event.GetPointerCount();
if (pointer_count > MAX_POINTERS) {
pointer_count = MAX_POINTERS;
}
BitSet32 id_bits;
for (size_t i = 0; i < pointer_count; i++) {
id_bits.mark_bit(event.GetPointerId(i));
}
uint32_t pointer_index[MAX_POINTERS];
for (size_t i = 0; i < pointer_count; i++) {
pointer_index[i] = id_bits.get_index_of_bit(event.GetPointerId(i));
}
Position positions[MAX_POINTERS];
size_t historySize = event.GetHistorySize();
for (size_t h = 0; h < historySize; h++) {
for (size_t i = 0; i < pointer_count; i++) {
uint32_t index = pointer_index[i];
positions[index].x = event.GetHistoricalX(i, h);
positions[index].y = event.GetHistoricalY(i, h);
}
AddMovement(event.GetHistoricalEventTime(h), id_bits, positions);
}
for (size_t i = 0; i < pointer_count; i++) {
uint32_t index = pointer_index[i];
positions[index].x = event.GetX(i);
positions[index].y = event.GetY(i);
}
AddMovement(event.GetEventTime(), id_bits, positions);
}
bool VelocityTracker::GetVelocity(uint32_t id,
float* out_vx,
float* out_vy) const {
Estimator estimator;
if (GetEstimator(id, &estimator) && estimator.degree >= 1) {
*out_vx = estimator.xcoeff[1];
*out_vy = estimator.ycoeff[1];
return true;
}
*out_vx = 0;
*out_vy = 0;
return false;
}
void LeastSquaresVelocityTrackerStrategy::AddMovement(
const TimeTicks& event_time,
BitSet32 id_bits,
const Position* positions) {
if (++index_ == kHistorySize) {
index_ = 0;
}
Movement& movement = movements_[index_];
movement.event_time = event_time;
movement.id_bits = id_bits;
uint32_t count = id_bits.count();
for (uint32_t i = 0; i < count; i++) {
movement.positions[i] = positions[i];
}
}
bool VelocityTracker::GetEstimator(uint32_t id,
Estimator* out_estimator) const {
return strategy_->GetEstimator(id, out_estimator);
}
// --- LeastSquaresVelocityTrackerStrategy ---
LeastSquaresVelocityTrackerStrategy::LeastSquaresVelocityTrackerStrategy(
uint32_t degree,
Weighting weighting,
Restriction restriction)
: degree_(degree),
weighting_(weighting),
restriction_(restriction) {
DCHECK_LT(degree_, static_cast<uint32_t>(Estimator::kMaxDegree));
Clear();
}
LeastSquaresVelocityTrackerStrategy::~LeastSquaresVelocityTrackerStrategy() {}
void LeastSquaresVelocityTrackerStrategy::Clear() {
index_ = 0;
movements_[0].id_bits.clear();
}
/**
* Solves a linear least squares problem to obtain a N degree polynomial that
* fits the specified input data as nearly as possible.
*
* Returns true if a solution is found, false otherwise.
*
* The input consists of two vectors of data points X and Y with indices 0..m-1
* along with a weight vector W of the same size.
*
* The output is a vector B with indices 0..n that describes a polynomial
* that fits the data, such the sum of W[i] * W[i] * abs(Y[i] - (B[0] + B[1]
* X[i] * + B[2] X[i]^2 ... B[n] X[i]^n)) for all i between 0 and m-1 is
* minimized.
*
* Accordingly, the weight vector W should be initialized by the caller with the
* reciprocal square root of the variance of the error in each input data point.
* In other words, an ideal choice for W would be W[i] = 1 / var(Y[i]) = 1 /
* stddev(Y[i]).
* The weights express the relative importance of each data point. If the
* weights are* all 1, then the data points are considered to be of equal
* importance when fitting the polynomial. It is a good idea to choose weights
* that diminish the importance of data points that may have higher than usual
* error margins.
*
* Errors among data points are assumed to be independent. W is represented
* here as a vector although in the literature it is typically taken to be a
* diagonal matrix.
*
* That is to say, the function that generated the input data can be
* approximated by y(x) ~= B[0] + B[1] x + B[2] x^2 + ... + B[n] x^n.
*
* The coefficient of determination (R^2) is also returned to describe the
* goodness of fit of the model for the given data. It is a value between 0
* and 1, where 1 indicates perfect correspondence.
*
* This function first expands the X vector to a m by n matrix A such that
* A[i][0] = 1, A[i][1] = X[i], A[i][2] = X[i]^2, ..., A[i][n] = X[i]^n, then
* multiplies it by w[i]./
*
* Then it calculates the QR decomposition of A yielding an m by m orthonormal
* matrix Q and an m by n upper triangular matrix R. Because R is upper
* triangular (lower part is all zeroes), we can simplify the decomposition into
* an m by n matrix Q1 and a n by n matrix R1 such that A = Q1 R1.
*
* Finally we solve the system of linear equations given by
* R1 B = (Qtranspose W Y) to find B.
*
* For efficiency, we lay out A and Q column-wise in memory because we
* frequently operate on the column vectors. Conversely, we lay out R row-wise.
*
* http://en.wikipedia.org/wiki/Numerical_methods_for_linear_least_squares
* http://en.wikipedia.org/wiki/Gram-Schmidt
*/
static bool SolveLeastSquares(const float* x,
const float* y,
const float* w,
uint32_t m,
uint32_t n,
float* out_b,
float* out_det) {
// MSVC does not support variable-length arrays (used by the original Android
// implementation of this function).
#if defined(COMPILER_MSVC)
const uint32_t M_ARRAY_LENGTH =
LeastSquaresVelocityTrackerStrategy::kHistorySize;
const uint32_t N_ARRAY_LENGTH = Estimator::kMaxDegree;
DCHECK_LE(m, M_ARRAY_LENGTH);
DCHECK_LE(n, N_ARRAY_LENGTH);
#else
const uint32_t M_ARRAY_LENGTH = m;
const uint32_t N_ARRAY_LENGTH = n;
#endif
// Expand the X vector to a matrix A, pre-multiplied by the weights.
float a[N_ARRAY_LENGTH][M_ARRAY_LENGTH]; // column-major order
for (uint32_t h = 0; h < m; h++) {
a[0][h] = w[h];
for (uint32_t i = 1; i < n; i++) {
a[i][h] = a[i - 1][h] * x[h];
}
}
// Apply the Gram-Schmidt process to A to obtain its QR decomposition.
// Orthonormal basis, column-major order.
float q[N_ARRAY_LENGTH][M_ARRAY_LENGTH];
// Upper triangular matrix, row-major order.
float r[N_ARRAY_LENGTH][N_ARRAY_LENGTH];
for (uint32_t j = 0; j < n; j++) {
for (uint32_t h = 0; h < m; h++) {
q[j][h] = a[j][h];
}
for (uint32_t i = 0; i < j; i++) {
float dot = VectorDot(&q[j][0], &q[i][0], m);
for (uint32_t h = 0; h < m; h++) {
q[j][h] -= dot * q[i][h];
}
}
float norm = VectorNorm(&q[j][0], m);
if (norm < 0.000001f) {
// vectors are linearly dependent or zero so no solution
return false;
}
float invNorm = 1.0f / norm;
for (uint32_t h = 0; h < m; h++) {
q[j][h] *= invNorm;
}
for (uint32_t i = 0; i < n; i++) {
r[j][i] = i < j ? 0 : VectorDot(&q[j][0], &a[i][0], m);
}
}
// Solve R B = Qt W Y to find B. This is easy because R is upper triangular.
// We just work from bottom-right to top-left calculating B's coefficients.
float wy[M_ARRAY_LENGTH];
for (uint32_t h = 0; h < m; h++) {
wy[h] = y[h] * w[h];
}
for (uint32_t i = n; i-- != 0;) {
out_b[i] = VectorDot(&q[i][0], wy, m);
for (uint32_t j = n - 1; j > i; j--) {
out_b[i] -= r[i][j] * out_b[j];
}
out_b[i] /= r[i][i];
}
// Calculate the coefficient of determination as 1 - (SSerr / SStot) where
// SSerr is the residual sum of squares (variance of the error),
// and SStot is the total sum of squares (variance of the data) where each
// has been weighted.
float ymean = 0;
for (uint32_t h = 0; h < m; h++) {
ymean += y[h];
}
ymean /= m;
float sserr = 0;
float sstot = 0;
for (uint32_t h = 0; h < m; h++) {
float err = y[h] - out_b[0];
float term = 1;
for (uint32_t i = 1; i < n; i++) {
term *= x[h];
err -= term * out_b[i];
}
sserr += w[h] * w[h] * err * err;
float var = y[h] - ymean;
sstot += w[h] * w[h] * var * var;
}
*out_det = sstot > 0.000001f ? 1.0f - (sserr / sstot) : 1;
return true;
}
void LeastSquaresVelocityTrackerStrategy::ClearPointers(BitSet32 id_bits) {
BitSet32 remaining_id_bits(movements_[index_].id_bits.value & ~id_bits.value);
movements_[index_].id_bits = remaining_id_bits;
}
bool LeastSquaresVelocityTrackerStrategy::GetEstimator(
uint32_t id,
Estimator* out_estimator) const {
out_estimator->Clear();
// Iterate over movement samples in reverse time order and collect samples.
float x[kHistorySize];
float y[kHistorySize];
float w[kHistorySize];
float time[kHistorySize];
uint32_t m = 0;
uint32_t index = index_;
const base::TimeDelta horizon = base::TimeDelta::FromMilliseconds(kHorizonMS);
const Movement& newest_movement = movements_[index_];
const Movement* first_movement = nullptr;
do {
const Movement& movement = movements_[index];
if (!movement.id_bits.has_bit(id))
break;
first_movement = &movement;
TimeDelta age = newest_movement.event_time - movement.event_time;
if (age > horizon)
break;
const Position& position = movement.GetPosition(id);
x[m] = position.x;
y[m] = position.y;
w[m] = ChooseWeight(index);
time[m] = -static_cast<float>(age.InSecondsF());
index = (index == 0 ? kHistorySize : index) - 1;
} while (++m < kHistorySize);
if (m == 0)
return false; // no data
// Calculate a least squares polynomial fit.
uint32_t degree = degree_;
if (degree > m - 1)
degree = m - 1;
if (degree >= 1) {
float xdet = 0, ydet = 0;
uint32_t n = degree + 1;
if (SolveLeastSquares(time, x, w, m, n, out_estimator->xcoeff, &xdet) &&
SolveLeastSquares(time, y, w, m, n, out_estimator->ycoeff, &ydet)) {
if (restriction_ == RESTRICTION_ALIGNED_DIRECTIONS) {
DCHECK(first_movement);
float dx = newest_movement.GetPosition(id).x -
first_movement->GetPosition(id).x;
float dy = newest_movement.GetPosition(id).y -
first_movement->GetPosition(id).y;
// If the velocity is in a sufficiently different direction from the
// primary movement, ignore it.
if (out_estimator->xcoeff[1] * dx + out_estimator->ycoeff[1] * dy < 0)
return false;
}
out_estimator->time = newest_movement.event_time;
out_estimator->degree = degree;
out_estimator->confidence = xdet * ydet;
return true;
}
}
// No velocity data available for this pointer, but we do have its current
// position.
out_estimator->xcoeff[0] = x[0];
out_estimator->ycoeff[0] = y[0];
out_estimator->time = newest_movement.event_time;
out_estimator->degree = 0;
out_estimator->confidence = 1;
return true;
}
float LeastSquaresVelocityTrackerStrategy::ChooseWeight(uint32_t index) const {
switch (weighting_) {
case WEIGHTING_DELTA: {
// Weight points based on how much time elapsed between them and the next
// point so that points that "cover" a shorter time span are weighed less.
// delta 0ms: 0.5
// delta 10ms: 1.0
if (index == index_) {
return 1.0f;
}
uint32_t next_index = (index + 1) % kHistorySize;
float delta_millis =
static_cast<float>((movements_[next_index].event_time -
movements_[index].event_time).InMillisecondsF());
if (delta_millis < 0)
return 0.5f;
if (delta_millis < 10)
return 0.5f + delta_millis * 0.05f;
return 1.0f;
}
case WEIGHTING_CENTRAL: {
// Weight points based on their age, weighing very recent and very old
// points less.
// age 0ms: 0.5
// age 10ms: 1.0
// age 50ms: 1.0
// age 60ms: 0.5
float age_millis =
static_cast<float>((movements_[index_].event_time -
movements_[index].event_time).InMillisecondsF());
if (age_millis < 0)
return 0.5f;
if (age_millis < 10)
return 0.5f + age_millis * 0.05f;
if (age_millis < 50)
return 1.0f;
if (age_millis < 60)
return 0.5f + (60 - age_millis) * 0.05f;
return 0.5f;
}
case WEIGHTING_RECENT: {
// Weight points based on their age, weighing older points less.
// age 0ms: 1.0
// age 50ms: 1.0
// age 100ms: 0.5
float age_millis =
static_cast<float>((movements_[index_].event_time -
movements_[index].event_time).InMillisecondsF());
if (age_millis < 50) {
return 1.0f;
}
if (age_millis < 100) {
return 0.5f + (100 - age_millis) * 0.01f;
}
return 0.5f;
}
case WEIGHTING_NONE:
default:
return 1.0f;
}
}
// --- IntegratingVelocityTrackerStrategy ---
IntegratingVelocityTrackerStrategy::IntegratingVelocityTrackerStrategy(
uint32_t degree)
: degree_(degree) {
DCHECK_LT(degree_, static_cast<uint32_t>(Estimator::kMaxDegree));
}
IntegratingVelocityTrackerStrategy::~IntegratingVelocityTrackerStrategy() {}
void IntegratingVelocityTrackerStrategy::Clear() { pointer_id_bits_.clear(); }
void IntegratingVelocityTrackerStrategy::ClearPointers(BitSet32 id_bits) {
pointer_id_bits_.value &= ~id_bits.value;
}
void IntegratingVelocityTrackerStrategy::AddMovement(
const TimeTicks& event_time,
BitSet32 id_bits,
const Position* positions) {
uint32_t index = 0;
for (BitSet32 iter_id_bits(id_bits); !iter_id_bits.is_empty();) {
uint32_t id = iter_id_bits.clear_first_marked_bit();
State& state = mPointerState[id];
const Position& position = positions[index++];
if (pointer_id_bits_.has_bit(id))
UpdateState(state, event_time, position.x, position.y);
else
InitState(state, event_time, position.x, position.y);
}
pointer_id_bits_ = id_bits;
}
bool IntegratingVelocityTrackerStrategy::GetEstimator(
uint32_t id,
Estimator* out_estimator) const {
out_estimator->Clear();
if (pointer_id_bits_.has_bit(id)) {
const State& state = mPointerState[id];
PopulateEstimator(state, out_estimator);
return true;
}
return false;
}
void IntegratingVelocityTrackerStrategy::InitState(State& state,
const TimeTicks& event_time,
float xpos,
float ypos) const {
state.update_time = event_time;
state.degree = 0;
state.xpos = xpos;
state.xvel = 0;
state.xaccel = 0;
state.ypos = ypos;
state.yvel = 0;
state.yaccel = 0;
}
void IntegratingVelocityTrackerStrategy::UpdateState(
State& state,
const TimeTicks& event_time,
float xpos,
float ypos) const {
const base::TimeDelta MIN_TIME_DELTA = TimeDelta::FromMicroseconds(2);
const float FILTER_TIME_CONSTANT = 0.010f; // 10 milliseconds
if (event_time <= state.update_time + MIN_TIME_DELTA)
return;
float dt = static_cast<float>((event_time - state.update_time).InSecondsF());
state.update_time = event_time;
float xvel = (xpos - state.xpos) / dt;
float yvel = (ypos - state.ypos) / dt;
if (state.degree == 0) {
state.xvel = xvel;
state.yvel = yvel;
state.degree = 1;
} else {
float alpha = dt / (FILTER_TIME_CONSTANT + dt);
if (degree_ == 1) {
state.xvel += (xvel - state.xvel) * alpha;
state.yvel += (yvel - state.yvel) * alpha;
} else {
float xaccel = (xvel - state.xvel) / dt;
float yaccel = (yvel - state.yvel) / dt;
if (state.degree == 1) {
state.xaccel = xaccel;
state.yaccel = yaccel;
state.degree = 2;
} else {
state.xaccel += (xaccel - state.xaccel) * alpha;
state.yaccel += (yaccel - state.yaccel) * alpha;
}
state.xvel += (state.xaccel * dt) * alpha;
state.yvel += (state.yaccel * dt) * alpha;
}
}
state.xpos = xpos;
state.ypos = ypos;
}
void IntegratingVelocityTrackerStrategy::PopulateEstimator(
const State& state,
Estimator* out_estimator) const {
out_estimator->time = state.update_time;
out_estimator->confidence = 1.0f;
out_estimator->degree = state.degree;
out_estimator->xcoeff[0] = state.xpos;
out_estimator->xcoeff[1] = state.xvel;
out_estimator->xcoeff[2] = state.xaccel / 2;
out_estimator->ycoeff[0] = state.ypos;
out_estimator->ycoeff[1] = state.yvel;
out_estimator->ycoeff[2] = state.yaccel / 2;
}
} // namespace ui