velocity_tracker.cc | Explore in Territory

// Copyright 2014 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifdef UNSAFE_BUFFERS_BUILD
// TODO(crbug.com/351564777): Remove this and convert code to safer constructs.
#pragma allow_unsafe_buffers
#endif

#include "ui/events/velocity_tracker/velocity_tracker.h"

#include <stddef.h>

#include <cmath>
#include <ostream>

#include "base/check_op.h"
#include "base/notreached.h"
#include "build/build_config.h"
#include "ui/events/velocity_tracker/motion_event.h"

TimeTicks;

namespace ui {

// Implements a particular velocity tracker algorithm.
class VelocityTrackerStrategy { … };

namespace {

static_assert …;

// 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 = …;

// 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 = …;

struct Position { … };

struct Estimator { … };

float VectorDot(const float* a, const float* b, uint32_t m) { … }

float VectorNorm(const float* a, uint32_t m) { … }

// Velocity tracker algorithm based on least-squares linear regression.
class LeastSquaresVelocityTrackerStrategy : public VelocityTrackerStrategy { … };

// Velocity tracker algorithm that uses an IIR filter.
class IntegratingVelocityTrackerStrategy : public VelocityTrackerStrategy { … };

VelocityTrackerStrategy* CreateStrategy(VelocityTracker::Strategy strategy) { … }

}  // namespace

// --- VelocityTracker ---

VelocityTracker::VelocityTracker(Strategy strategy)
    : … { … }

VelocityTracker::~VelocityTracker() { … }

void VelocityTracker::Clear() { … }

void VelocityTracker::ClearPointers(BitSet32 id_bits) { … }

void VelocityTracker::AddMovement(const TimeTicks& event_time,
                                  BitSet32 id_bits,
                                  const Position* positions) { … }

void VelocityTracker::AddMovement(const MotionEvent& event) { … }

bool VelocityTracker::GetVelocity(uint32_t id,
                                  float* out_vx,
                                  float* out_vy) const { … }

void LeastSquaresVelocityTrackerStrategy::AddMovement(
    const TimeTicks& event_time,
    BitSet32 id_bits,
    const Position* positions) { … }

bool VelocityTracker::GetEstimator(uint32_t id,
                                   Estimator* out_estimator) const { … }

// --- LeastSquaresVelocityTrackerStrategy ---

LeastSquaresVelocityTrackerStrategy::LeastSquaresVelocityTrackerStrategy(
    uint32_t degree,
    Weighting weighting,
    Restriction restriction)
    : … { … }

LeastSquaresVelocityTrackerStrategy::~LeastSquaresVelocityTrackerStrategy() { … }

void LeastSquaresVelocityTrackerStrategy::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) { … }

void LeastSquaresVelocityTrackerStrategy::ClearPointers(BitSet32 id_bits) { … }

bool LeastSquaresVelocityTrackerStrategy::GetEstimator(
    uint32_t id,
    Estimator* out_estimator) const { … }

float LeastSquaresVelocityTrackerStrategy::ChooseWeight(uint32_t index) const { … }

// --- IntegratingVelocityTrackerStrategy ---

IntegratingVelocityTrackerStrategy::IntegratingVelocityTrackerStrategy(
    uint32_t degree)
    : … { … }

IntegratingVelocityTrackerStrategy::~IntegratingVelocityTrackerStrategy() { … }

void IntegratingVelocityTrackerStrategy::Clear() { … }

void IntegratingVelocityTrackerStrategy::ClearPointers(BitSet32 id_bits) { … }

void IntegratingVelocityTrackerStrategy::AddMovement(
    const TimeTicks& event_time,
    BitSet32 id_bits,
    const Position* positions) { … }

bool IntegratingVelocityTrackerStrategy::GetEstimator(
    uint32_t id,
    Estimator* out_estimator) const { … }

void IntegratingVelocityTrackerStrategy::InitState(State& state,
                                                   const TimeTicks& event_time,
                                                   float xpos,
                                                   float ypos) const { … }

void IntegratingVelocityTrackerStrategy::UpdateState(
    State& state,
    const TimeTicks& event_time,
    float xpos,
    float ypos) const { … }

void IntegratingVelocityTrackerStrategy::PopulateEstimator(
    const State& state,
    Estimator* out_estimator) const { … }

}  // namespace ui
chromium/ui/events/velocity_tracker/velocity_tracker.cc
