fast_ink_points.cc 8.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244
  1. // Copyright 2016 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 "ash/fast_ink/fast_ink_points.h"
  5. #include <algorithm>
  6. #include <array>
  7. #include <limits>
  8. #include "base/containers/adapters.h"
  9. #include "base/containers/circular_deque.h"
  10. #include "ui/gfx/geometry/point_f.h"
  11. #include "ui/gfx/geometry/rect_conversions.h"
  12. namespace {
  13. constexpr SkColor kDefaultPointColor = SkColorSetRGB(0x42, 0x85, 0xF4);
  14. constexpr int kDefaultOpacity = 0xCC;
  15. } // namespace
  16. namespace fast_ink {
  17. const SkColor FastInkPoints::kDefaultColor =
  18. SkColorSetA(kDefaultPointColor, kDefaultOpacity);
  19. FastInkPoints::FastInkPoints(base::TimeDelta life_duration)
  20. : life_duration_(life_duration) {}
  21. FastInkPoints::~FastInkPoints() = default;
  22. void FastInkPoints::AddPoint(const gfx::PointF& point,
  23. const base::TimeTicks& time) {
  24. FastInkPoint new_point;
  25. new_point.location = point;
  26. new_point.time = time;
  27. points_.push_back(new_point);
  28. }
  29. void FastInkPoints::AddPoint(const gfx::PointF& point,
  30. const base::TimeTicks& time,
  31. SkColor color) {
  32. FastInkPoint new_point;
  33. new_point.location = point;
  34. new_point.time = time;
  35. new_point.color = color;
  36. points_.push_back(new_point);
  37. }
  38. void FastInkPoints::AddGap() {
  39. // Not doing anything special regarding prediction, as in real usage there
  40. // will be a gap in timestamps, and the prediction algorithm will reject the
  41. // points that are too old.
  42. points_.back().gap_after = true;
  43. }
  44. void FastInkPoints::MoveForwardToTime(const base::TimeTicks& latest_time) {
  45. DCHECK_GE(latest_time, collection_latest_time_);
  46. collection_latest_time_ = latest_time;
  47. if (!points_.empty() && !life_duration_.is_zero()) {
  48. // Remove obsolete points.
  49. const base::TimeTicks expiration = latest_time - life_duration_;
  50. auto first_alive_point = std::find_if(
  51. points_.begin(), points_.end(),
  52. [expiration](const FastInkPoint& p) { return p.time > expiration; });
  53. points_.erase(points_.begin(), first_alive_point);
  54. }
  55. }
  56. gfx::Rect FastInkPoints::UndoLastStroke() {
  57. if (points_.empty())
  58. return gfx::Rect();
  59. gfx::PointF min_point = GetNewest().location;
  60. gfx::PointF max_point = min_point;
  61. // Skip the last gap to delete until the penultimate gap.
  62. if (points_.back().gap_after)
  63. points_.pop_back();
  64. while (!points_.empty() && !points_.back().gap_after) {
  65. const gfx::PointF& location = points_.back().location;
  66. min_point.SetToMin(location);
  67. max_point.SetToMax(location);
  68. points_.pop_back();
  69. }
  70. return gfx::ToEnclosingRect(gfx::BoundingRect(min_point, max_point));
  71. }
  72. void FastInkPoints::Clear() {
  73. points_.clear();
  74. }
  75. gfx::Rect FastInkPoints::GetBoundingBox() const {
  76. return gfx::ToEnclosingRect(GetBoundingBoxF());
  77. }
  78. gfx::RectF FastInkPoints::GetBoundingBoxF() const {
  79. if (IsEmpty())
  80. return gfx::RectF();
  81. gfx::PointF min_point = GetOldest().location;
  82. gfx::PointF max_point = min_point;
  83. for (const FastInkPoint& point : points_) {
  84. min_point.SetToMin(point.location);
  85. max_point.SetToMax(point.location);
  86. }
  87. return gfx::BoundingRect(min_point, max_point);
  88. }
  89. FastInkPoints::FastInkPoint FastInkPoints::GetOldest() const {
  90. DCHECK(!IsEmpty());
  91. return points_.front();
  92. }
  93. FastInkPoints::FastInkPoint FastInkPoints::GetNewest() const {
  94. DCHECK(!IsEmpty());
  95. return points_.back();
  96. }
  97. bool FastInkPoints::IsEmpty() const {
  98. return points_.empty();
  99. }
  100. int FastInkPoints::GetNumberOfPoints() const {
  101. return points_.size();
  102. }
  103. const base::circular_deque<FastInkPoints::FastInkPoint>& FastInkPoints::points()
  104. const {
  105. return points_;
  106. }
  107. float FastInkPoints::GetFadeoutFactor(int index) const {
  108. DCHECK(!life_duration_.is_zero());
  109. DCHECK_GE(index, 0);
  110. DCHECK_LT(index, GetNumberOfPoints());
  111. const base::TimeDelta age = collection_latest_time_ - points_[index].time;
  112. return std::min(age / life_duration_, 1.0);
  113. }
  114. void FastInkPoints::Predict(const FastInkPoints& real_points,
  115. const base::TimeTicks& current_time,
  116. base::TimeDelta prediction_duration,
  117. const gfx::Size& screen_size) {
  118. Clear();
  119. if (real_points.IsEmpty() || prediction_duration.is_zero())
  120. return;
  121. gfx::Vector2dF scale(1.0f / screen_size.width(), 1.0f / screen_size.height());
  122. // Create a new set of predicted points based on the last four points added.
  123. // We add enough predicted points to fill the time between the new point and
  124. // the expected presentation time. Note that estimated presentation time is
  125. // based on current time and inefficient rendering of points can result in an
  126. // actual presentation time that is later.
  127. // TODO(reveman): Determine interval based on history when event time stamps
  128. // are accurate. b/36137953
  129. const float kPredictionIntervalMs = 5.0f;
  130. const float kMaxPointIntervalMs = 10.0f;
  131. base::TimeDelta prediction_interval =
  132. base::Milliseconds(kPredictionIntervalMs);
  133. base::TimeDelta max_point_interval = base::Milliseconds(kMaxPointIntervalMs);
  134. const FastInkPoint newest_real_point = real_points.GetNewest();
  135. base::TimeTicks last_point_time = newest_real_point.time;
  136. gfx::PointF last_point_location =
  137. gfx::ScalePoint(newest_real_point.location, scale.x(), scale.y());
  138. // Use the last four points for prediction.
  139. using PositionArray = std::array<gfx::PointF, 4>;
  140. PositionArray position;
  141. PositionArray::iterator it = position.begin();
  142. for (const auto& point : base::Reversed(real_points.points())) {
  143. // Stop adding positions if interval between points is too large to provide
  144. // an accurate history for prediction.
  145. if ((last_point_time - point.time) > max_point_interval)
  146. break;
  147. last_point_time = point.time;
  148. last_point_location = gfx::ScalePoint(point.location, scale.x(), scale.y());
  149. *it++ = last_point_location;
  150. // Stop when no more positions are needed.
  151. if (it == position.end())
  152. break;
  153. }
  154. const size_t valid_positions = it - position.begin();
  155. if (valid_positions < 2) // Not enough reliable data, bail out.
  156. return;
  157. // Note: Currently there's no need to divide by the time delta between
  158. // points as we assume a constant delta between points that matches the
  159. // prediction point interval.
  160. gfx::Vector2dF velocity[3];
  161. for (size_t i = 0; i < valid_positions - 1; ++i)
  162. velocity[i] = position[i] - position[i + 1];
  163. // velocity[0] is always valid, since |valid_positions| >=2
  164. gfx::Vector2dF acceleration[2];
  165. for (size_t i = 0; i < valid_positions - 2; ++i)
  166. acceleration[i] = velocity[i] - velocity[i + 1];
  167. // acceleration[0] is always valid (zero if |valid_positions| < 3).
  168. gfx::Vector2dF jerk;
  169. if (valid_positions > 3)
  170. jerk = acceleration[0] - acceleration[1];
  171. // |jerk| is aways valid (zero if |valid_positions| < 4).
  172. // Adjust max prediction time based on speed as prediction data is not great
  173. // at lower speeds.
  174. const float kMaxPredictionScaleSpeed = 1e-5;
  175. double speed = velocity[0].LengthSquared();
  176. base::TimeTicks max_prediction_time =
  177. current_time +
  178. std::min(prediction_duration * (speed / kMaxPredictionScaleSpeed),
  179. prediction_duration);
  180. // Add predicted points until we reach the max prediction time.
  181. gfx::PointF location = position[0];
  182. for (base::TimeTicks time = newest_real_point.time + prediction_interval;
  183. time < max_prediction_time; time += prediction_interval) {
  184. // Note: Currently there's no need to multiply by the prediction interval
  185. // as the velocity is calculated based on a time delta between points that
  186. // is the same as the prediction interval.
  187. velocity[0] += acceleration[0];
  188. acceleration[0] += jerk;
  189. location += velocity[0];
  190. AddPoint(gfx::ScalePoint(location, 1 / scale.x(), 1 / scale.y()), time,
  191. newest_real_point.color);
  192. // Always stop at three predicted points as a four point history doesn't
  193. // provide accurate prediction of more points.
  194. if (GetNumberOfPoints() == 3)
  195. break;
  196. }
  197. }
  198. } // namespace fast_ink