File: least_squares_predictor.cc

package info (click to toggle)
chromium 138.0.7204.183-1
  • links: PTS, VCS
  • area: main
  • in suites: trixie
  • size: 6,071,908 kB
  • sloc: cpp: 34,937,088; ansic: 7,176,967; javascript: 4,110,704; python: 1,419,953; asm: 946,768; xml: 739,971; pascal: 187,324; sh: 89,623; perl: 88,663; objc: 79,944; sql: 50,304; cs: 41,786; fortran: 24,137; makefile: 21,806; php: 13,980; tcl: 13,166; yacc: 8,925; ruby: 7,485; awk: 3,720; lisp: 3,096; lex: 1,327; ada: 727; jsp: 228; sed: 36
file content (114 lines) | stat: -rw-r--r-- 3,264 bytes parent folder | download | duplicates (5)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
// Copyright 2018 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "ui/base/prediction/least_squares_predictor.h"

#include <algorithm>

#include "ui/base/ui_base_features.h"

namespace ui {

namespace {

// Solve XB = y.
static bool SolveLeastSquares(const gfx::Matrix3F& x,
                              const std::deque<double>& y,
                              gfx::Vector3dF& result) {
  constexpr double kEpsilon = std::numeric_limits<double>::epsilon();

  // return last point if y didn't change.
  if (std::abs(y[0] - y[1]) < kEpsilon && std::abs(y[1] - y[2]) < kEpsilon) {
    result = gfx::Vector3dF(y[2], 0, 0);
    return true;
  }

  gfx::Matrix3F x_transpose = x.Transpose();
  gfx::Matrix3F temp = gfx::MatrixProduct(x_transpose, x).Inverse();

  // Return false if x is singular.
  if (temp == gfx::Matrix3F::Zeros())
    return false;

  result = gfx::MatrixProduct(gfx::MatrixProduct(temp, x_transpose),
                              gfx::Vector3dF(y[0], y[1], y[2]));
  return true;
}

}  // namespace

LeastSquaresPredictor::LeastSquaresPredictor() = default;

LeastSquaresPredictor::~LeastSquaresPredictor() = default;

const char* LeastSquaresPredictor::GetName() const {
  return features::kPredictorNameLsq;
}

void LeastSquaresPredictor::Reset() {
  x_queue_.clear();
  y_queue_.clear();
  time_.clear();
}

void LeastSquaresPredictor::Update(const InputData& cur_input) {
  if (!time_.empty()) {
    // When last point is kMaxTimeDelta away, consider it is incontinuous.
    if (cur_input.time_stamp - time_.back() > kMaxTimeDelta)
      Reset();
  }

  x_queue_.push_back(cur_input.pos.x());
  y_queue_.push_back(cur_input.pos.y());
  time_.push_back(cur_input.time_stamp);
  if (time_.size() > kSize) {
    x_queue_.pop_front();
    y_queue_.pop_front();
    time_.pop_front();
  }
}

bool LeastSquaresPredictor::HasPrediction() const {
  return time_.size() >= kSize;
}

gfx::Matrix3F LeastSquaresPredictor::GetXMatrix() const {
  gfx::Matrix3F x = gfx::Matrix3F::Zeros();
  double t1 = (time_[1] - time_[0]).InMillisecondsF();
  double t2 = (time_[2] - time_[0]).InMillisecondsF();
  x.set(1, 0, 0, 1, t1, t1 * t1, 1, t2, t2 * t2);
  return x;
}

std::unique_ptr<InputPredictor::InputData>
LeastSquaresPredictor::GeneratePrediction(base::TimeTicks predict_time,
                                          base::TimeDelta frame_interval) {
  if (!HasPrediction())
    return nullptr;

  float pred_dt = (predict_time - time_[0]).InMillisecondsF();

  gfx::Vector3dF b1, b2;
  gfx::Matrix3F time_matrix = GetXMatrix();
  if (SolveLeastSquares(time_matrix, x_queue_, b1) &&
      SolveLeastSquares(time_matrix, y_queue_, b2)) {
    gfx::Vector3dF prediction_time(1, pred_dt, pred_dt * pred_dt);

    return std::make_unique<InputData>(
        gfx::PointF(gfx::DotProduct(prediction_time, b1),
                    gfx::DotProduct(prediction_time, b2)),
        predict_time);
  }
  return nullptr;
}

base::TimeDelta LeastSquaresPredictor::TimeInterval() const {
  if (time_.size() > 1) {
    return std::max(kMinTimeInterval,
                    (time_.back() - time_.front()) / (time_.size() - 1));
  }
  return kTimeInterval;
}

}  // namespace ui