motion_event_buffer.cc 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332
  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/motion_event_buffer.h"
  5. #include <stddef.h>
  6. #include <algorithm>
  7. #include <iterator>
  8. #include <utility>
  9. #include "base/trace_event/trace_event.h"
  10. #include "ui/events/gesture_detection/motion_event_generic.h"
  11. namespace ui {
  12. namespace {
  13. // Latency added during resampling. A few milliseconds doesn't hurt much but
  14. // reduces the impact of mispredicted touch positions.
  15. const int kResampleLatencyMs = 5;
  16. // Minimum time difference between consecutive samples before attempting to
  17. // resample.
  18. const int kResampleMinDeltaMs = 2;
  19. // Maximum time to predict forward from the last known state, to avoid
  20. // predicting too far into the future. This time is further bounded by 50% of
  21. // the last time delta.
  22. const int kResampleMaxPredictionMs = 8;
  23. using MotionEventVector = std::vector<std::unique_ptr<MotionEventGeneric>>;
  24. float Lerp(float a, float b, float alpha) {
  25. return a + alpha * (b - a);
  26. }
  27. bool CanAddSample(const MotionEvent& event0, const MotionEvent& event1) {
  28. DCHECK_EQ(event0.GetAction(), MotionEvent::Action::MOVE);
  29. if (event1.GetAction() != MotionEvent::Action::MOVE)
  30. return false;
  31. const size_t pointer_count = event0.GetPointerCount();
  32. if (pointer_count != event1.GetPointerCount())
  33. return false;
  34. for (size_t event0_i = 0; event0_i < pointer_count; ++event0_i) {
  35. const int id = event0.GetPointerId(event0_i);
  36. const int event1_i = event1.FindPointerIndexOfId(id);
  37. if (event1_i == -1)
  38. return false;
  39. if (event0.GetToolType(event0_i) != event1.GetToolType(event1_i))
  40. return false;
  41. }
  42. return true;
  43. }
  44. bool ShouldResampleTool(MotionEvent::ToolType tool) {
  45. return tool == MotionEvent::ToolType::UNKNOWN ||
  46. tool == MotionEvent::ToolType::FINGER;
  47. }
  48. // Splits a chunk of events from the front of the provided |batch| and returns
  49. // it. Requires that |batch| is sorted.
  50. MotionEventVector ConsumeSamplesNoLaterThan(MotionEventVector* batch,
  51. base::TimeTicks time) {
  52. DCHECK(batch);
  53. auto first_kept_event = std::partition_point(
  54. batch->begin(), batch->end(),
  55. [time](const std::unique_ptr<MotionEventGeneric>& event) {
  56. return event->GetEventTime() <= time;
  57. });
  58. MotionEventVector result(std::make_move_iterator(batch->begin()),
  59. std::make_move_iterator(first_kept_event));
  60. batch->erase(batch->begin(), first_kept_event);
  61. return result;
  62. }
  63. // Linearly interpolate the pointer position between two MotionEvent samples.
  64. // Only pointers of finger or unknown type will be resampled.
  65. PointerProperties ResamplePointer(const MotionEvent& event0,
  66. const MotionEvent& event1,
  67. size_t event0_pointer_index,
  68. size_t event1_pointer_index,
  69. float alpha) {
  70. DCHECK_EQ(event0.GetPointerId(event0_pointer_index),
  71. event1.GetPointerId(event1_pointer_index));
  72. // If the tool should not be resampled, use the latest event in the valid
  73. // horizon (i.e., the event no later than the time interpolated by alpha).
  74. if (!ShouldResampleTool(event0.GetToolType(event0_pointer_index))) {
  75. if (alpha > 1)
  76. return PointerProperties(event1, event1_pointer_index);
  77. else
  78. return PointerProperties(event0, event0_pointer_index);
  79. }
  80. PointerProperties p(event0, event0_pointer_index);
  81. p.x = Lerp(p.x, event1.GetX(event1_pointer_index), alpha);
  82. p.y = Lerp(p.y, event1.GetY(event1_pointer_index), alpha);
  83. p.raw_x = Lerp(p.raw_x, event1.GetRawX(event1_pointer_index), alpha);
  84. p.raw_y = Lerp(p.raw_y, event1.GetRawY(event1_pointer_index), alpha);
  85. return p;
  86. }
  87. // Linearly interpolate the pointers between two event samples using the
  88. // provided |resample_time|.
  89. std::unique_ptr<MotionEventGeneric> ResampleMotionEvent(
  90. const MotionEvent& event0,
  91. const MotionEvent& event1,
  92. base::TimeTicks resample_time) {
  93. DCHECK_EQ(MotionEvent::Action::MOVE, event0.GetAction());
  94. DCHECK_EQ(event0.GetPointerCount(), event1.GetPointerCount());
  95. const base::TimeTicks time0 = event0.GetEventTime();
  96. const base::TimeTicks time1 = event1.GetEventTime();
  97. DCHECK(time0 < time1);
  98. DCHECK(time0 <= resample_time);
  99. const float alpha = (resample_time - time0) / (time1 - time0);
  100. std::unique_ptr<MotionEventGeneric> event;
  101. const size_t pointer_count = event0.GetPointerCount();
  102. DCHECK_EQ(pointer_count, event1.GetPointerCount());
  103. for (size_t event0_i = 0; event0_i < pointer_count; ++event0_i) {
  104. int event1_i = event1.FindPointerIndexOfId(event0.GetPointerId(event0_i));
  105. DCHECK_NE(event1_i, -1);
  106. PointerProperties pointer = ResamplePointer(
  107. event0, event1, event0_i, static_cast<size_t>(event1_i), alpha);
  108. if (event0_i == 0) {
  109. event = std::make_unique<MotionEventGeneric>(MotionEvent::Action::MOVE,
  110. resample_time, pointer);
  111. } else {
  112. event->PushPointer(pointer);
  113. }
  114. }
  115. DCHECK(event);
  116. event->set_button_state(event0.GetButtonState());
  117. return event;
  118. }
  119. // Synthesize a compound MotionEventGeneric event from a sequence of events.
  120. // Events must be in non-decreasing (time) order.
  121. std::unique_ptr<MotionEventGeneric> ConsumeSamples(MotionEventVector events) {
  122. DCHECK(!events.empty());
  123. std::unique_ptr<MotionEventGeneric> event = std::move(events.back());
  124. events.pop_back();
  125. for (auto& historic_event : events)
  126. event->PushHistoricalEvent(std::move(historic_event));
  127. return event;
  128. }
  129. // Consume a series of event samples, attempting to synthesize a new, synthetic
  130. // event if the samples and sample time meet certain interpolation/extrapolation
  131. // conditions. If such conditions are met, the provided samples will be added
  132. // to the synthetic event's history, otherwise, the samples will be used to
  133. // generate a basic, compound event.
  134. // TODO(jdduke): Revisit resampling to handle cases where alternating frames
  135. // are resampled or resampling is otherwise inconsistent, e.g., a 90hz input
  136. // and 60hz frame signal could phase-align such that even frames yield an
  137. // extrapolated event and odd frames are not resampled, crbug.com/399381.
  138. std::unique_ptr<MotionEventGeneric> ConsumeSamplesAndTryResampling(
  139. base::TimeTicks resample_time,
  140. MotionEventVector events,
  141. const MotionEvent* next) {
  142. const ui::MotionEvent* event0 = nullptr;
  143. const ui::MotionEvent* event1 = nullptr;
  144. if (next) {
  145. DCHECK(resample_time < next->GetEventTime());
  146. // Interpolate between current sample and future sample.
  147. event0 = events.back().get();
  148. event1 = next;
  149. } else if (events.size() >= 2) {
  150. // Extrapolate future sample using current sample and past sample.
  151. event0 = events[events.size() - 2].get();
  152. event1 = events[events.size() - 1].get();
  153. const base::TimeTicks time1 = event1->GetEventTime();
  154. base::TimeTicks max_predict =
  155. time1 + std::min((event1->GetEventTime() - event0->GetEventTime()) / 2,
  156. base::Milliseconds(kResampleMaxPredictionMs));
  157. if (resample_time > max_predict) {
  158. TRACE_EVENT_INSTANT2("input",
  159. "MotionEventBuffer::TryResample prediction adjust",
  160. TRACE_EVENT_SCOPE_THREAD,
  161. "original(ms)",
  162. (resample_time - time1).InMilliseconds(),
  163. "adjusted(ms)",
  164. (max_predict - time1).InMilliseconds());
  165. resample_time = max_predict;
  166. }
  167. } else {
  168. TRACE_EVENT_INSTANT0("input",
  169. "MotionEventBuffer::TryResample insufficient data",
  170. TRACE_EVENT_SCOPE_THREAD);
  171. return ConsumeSamples(std::move(events));
  172. }
  173. DCHECK(event0);
  174. DCHECK(event1);
  175. const base::TimeTicks time0 = event0->GetEventTime();
  176. const base::TimeTicks time1 = event1->GetEventTime();
  177. base::TimeDelta delta = time1 - time0;
  178. if (delta < base::Milliseconds(kResampleMinDeltaMs)) {
  179. TRACE_EVENT_INSTANT1("input",
  180. "MotionEventBuffer::TryResample failure",
  181. TRACE_EVENT_SCOPE_THREAD,
  182. "event_delta_too_small(ms)",
  183. delta.InMilliseconds());
  184. return ConsumeSamples(std::move(events));
  185. }
  186. std::unique_ptr<MotionEventGeneric> resampled_event =
  187. ResampleMotionEvent(*event0, *event1, resample_time);
  188. for (auto& historic_event : events)
  189. resampled_event->PushHistoricalEvent(std::move(historic_event));
  190. return resampled_event;
  191. }
  192. } // namespace
  193. MotionEventBuffer::MotionEventBuffer(MotionEventBufferClient* client,
  194. bool enable_resampling)
  195. : client_(client), resample_(enable_resampling) {
  196. }
  197. MotionEventBuffer::~MotionEventBuffer() {
  198. }
  199. void MotionEventBuffer::OnMotionEvent(const MotionEvent& event) {
  200. DCHECK_EQ(0U, event.GetHistorySize());
  201. if (event.GetAction() != MotionEvent::Action::MOVE) {
  202. last_extrapolated_event_time_ = base::TimeTicks();
  203. if (!buffered_events_.empty())
  204. FlushWithoutResampling(std::move(buffered_events_));
  205. client_->ForwardMotionEvent(event);
  206. return;
  207. }
  208. // Guard against events that are *older* than the last one that may have been
  209. // artificially synthesized.
  210. if (!last_extrapolated_event_time_.is_null()) {
  211. DCHECK(buffered_events_.empty());
  212. if (event.GetEventTime() < last_extrapolated_event_time_)
  213. return;
  214. last_extrapolated_event_time_ = base::TimeTicks();
  215. }
  216. std::unique_ptr<MotionEventGeneric> clone =
  217. MotionEventGeneric::CloneEvent(event);
  218. if (buffered_events_.empty()) {
  219. buffered_events_.push_back(std::move(clone));
  220. client_->SetNeedsFlush();
  221. return;
  222. }
  223. if (CanAddSample(*buffered_events_.front(), *clone)) {
  224. // Ensure that buffered_events_ is ordered.
  225. DCHECK(buffered_events_.back()->GetEventTime() <= clone->GetEventTime());
  226. } else {
  227. FlushWithoutResampling(std::move(buffered_events_));
  228. }
  229. buffered_events_.push_back(std::move(clone));
  230. // No need to request another flush as the first event will have requested it.
  231. }
  232. void MotionEventBuffer::Flush(base::TimeTicks frame_time) {
  233. if (buffered_events_.empty())
  234. return;
  235. // Shifting the sample time back slightly minimizes the potential for
  236. // misprediction when extrapolating events.
  237. if (resample_)
  238. frame_time -= base::Milliseconds(kResampleLatencyMs);
  239. // TODO(jdduke): Use a persistent MotionEventVector vector for temporary
  240. // storage.
  241. MotionEventVector events =
  242. ConsumeSamplesNoLaterThan(&buffered_events_, frame_time);
  243. if (events.empty()) {
  244. DCHECK(!buffered_events_.empty());
  245. client_->SetNeedsFlush();
  246. return;
  247. }
  248. if (!resample_ || (events.size() == 1 && buffered_events_.empty())) {
  249. FlushWithoutResampling(std::move(events));
  250. if (!buffered_events_.empty())
  251. client_->SetNeedsFlush();
  252. return;
  253. }
  254. FlushWithResampling(std::move(events), frame_time);
  255. }
  256. void MotionEventBuffer::FlushWithResampling(MotionEventVector events,
  257. base::TimeTicks resample_time) {
  258. DCHECK(!events.empty());
  259. base::TimeTicks original_event_time = events.back()->GetEventTime();
  260. const MotionEvent* next_event =
  261. !buffered_events_.empty() ? buffered_events_.front().get() : nullptr;
  262. std::unique_ptr<MotionEventGeneric> resampled_event =
  263. ConsumeSamplesAndTryResampling(resample_time, std::move(events),
  264. next_event);
  265. DCHECK(resampled_event);
  266. // Log the extrapolated event time, guarding against subsequently queued
  267. // events that might have an earlier timestamp.
  268. if (!next_event && resampled_event->GetEventTime() > original_event_time) {
  269. last_extrapolated_event_time_ = resampled_event->GetEventTime();
  270. } else {
  271. last_extrapolated_event_time_ = base::TimeTicks();
  272. }
  273. client_->ForwardMotionEvent(*resampled_event);
  274. if (!buffered_events_.empty())
  275. client_->SetNeedsFlush();
  276. }
  277. void MotionEventBuffer::FlushWithoutResampling(MotionEventVector events) {
  278. last_extrapolated_event_time_ = base::TimeTicks();
  279. if (events.empty())
  280. return;
  281. client_->ForwardMotionEvent(*ConsumeSamples(std::move(events)));
  282. }
  283. } // namespace ui