ui/events/gesture_detection/motion_event_buffer.cc

   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
   5 #include "ui/events/gesture_detection/motion_event_buffer.h"
   6
   7 #include "base/debug/trace_event.h"
   8 #include "ui/events/gesture_detection/motion_event.h"
   9 #include "ui/events/gesture_detection/motion_event_generic.h"
  10
  11 namespace ui {
  12 namespace {
  13
  14 // Latency added during resampling. A few milliseconds doesn't hurt much but
  15 // reduces the impact of mispredicted touch positions.
  16 const int kResampleLatencyMs = 5;
  17
  18 // Minimum time difference between consecutive samples before attempting to
  19 // resample.
  20 const int kResampleMinDeltaMs = 2;
  21
  22 // Maximum time to predict forward from the last known state, to avoid
  23 // predicting too far into the future.  This time is further bounded by 50% of
  24 // the last time delta.
  25 const int kResampleMaxPredictionMs = 8;
  26
  27 typedef ScopedVector<MotionEvent> MotionEventVector;
  28
  29 float Lerp(float a, float b, float alpha) {
  30   return a + alpha * (b - a);
  31 }
  32
  33 bool CanAddSample(const MotionEvent& event0, const MotionEvent& event1) {
  34   DCHECK_EQ(event0.GetAction(), MotionEvent::ACTION_MOVE);
  35   if (event1.GetAction() != MotionEvent::ACTION_MOVE)
  36     return false;
  37
  38   const size_t pointer_count = event0.GetPointerCount();
  39   if (pointer_count != event1.GetPointerCount())
  40     return false;
  41
  42   for (size_t event0_i = 0; event0_i < pointer_count; ++event0_i) {
  43     const int id = event0.GetPointerId(event0_i);
  44     const int event1_i = event1.FindPointerIndexOfId(id);
  45     if (event1_i == -1)
  46       return false;
  47     if (event0.GetToolType(event0_i) != event1.GetToolType(event1_i))
  48       return false;
  49   }
  50
  51   return true;
  52 }
  53
  54 bool ShouldResampleTool(MotionEvent::ToolType tool) {
  55   return tool == MotionEvent::TOOL_TYPE_UNKNOWN ||
  56          tool == MotionEvent::TOOL_TYPE_FINGER;
  57 }
  58
  59 size_t CountSamplesNoLaterThan(const MotionEventVector& batch,
  60                                base::TimeTicks time) {
  61   size_t count = 0;
  62   while (count < batch.size() && batch[count]->GetEventTime() <= time)
  63     ++count;
  64   return count;
  65 }
  66
  67 MotionEventVector ConsumeSamplesNoLaterThan(MotionEventVector* batch,
  68                                             base::TimeTicks time) {
  69   DCHECK(batch);
  70   size_t count = CountSamplesNoLaterThan(*batch, time);
  71   DCHECK_GE(batch->size(), count);
  72   if (count == 0)
  73     return MotionEventVector();
  74
  75   if (count == batch->size())
  76     return batch->Pass();
  77
  78   // TODO(jdduke): Use a ScopedDeque to work around this mess.
  79   MotionEventVector unconsumed_batch;
  80   unconsumed_batch.insert(
  81       unconsumed_batch.begin(), batch->begin() + count, batch->end());
  82   batch->weak_erase(batch->begin() + count, batch->end());
  83
  84   unconsumed_batch.swap(*batch);
  85   DCHECK_GE(unconsumed_batch.size(), 1U);
  86   return unconsumed_batch.Pass();
  87 }
  88
  89 PointerProperties PointerFromMotionEvent(const MotionEvent& event,
  90                                          size_t pointer_index) {
  91   PointerProperties result;
  92   result.id = event.GetPointerId(pointer_index);
  93   result.tool_type = event.GetToolType(pointer_index);
  94   result.x = event.GetX(pointer_index);
  95   result.y = event.GetY(pointer_index);
  96   result.raw_x = event.GetRawX(pointer_index);
  97   result.raw_y = event.GetRawY(pointer_index);
  98   result.pressure = event.GetPressure(pointer_index);
  99   result.touch_major = event.GetTouchMajor(pointer_index);
 100   return result;
 101 }
 102
 103 PointerProperties ResamplePointer(const MotionEvent& event0,
 104                                   const MotionEvent& event1,
 105                                   size_t event0_pointer_index,
 106                                   size_t event1_pointer_index,
 107                                   float alpha) {
 108   DCHECK_EQ(event0.GetPointerId(event0_pointer_index),
 109             event1.GetPointerId(event1_pointer_index));
 110   // If the tool should not be resampled, use the latest event in the valid
 111   // horizon (i.e., the event no later than the time interpolated by alpha).
 112   if (!ShouldResampleTool(event0.GetToolType(event0_pointer_index))) {
 113     if (alpha > 1)
 114       return PointerFromMotionEvent(event1, event1_pointer_index);
 115     else
 116       return PointerFromMotionEvent(event0, event0_pointer_index);
 117   }
 118
 119   PointerProperties p(PointerFromMotionEvent(event0, event0_pointer_index));
 120   p.x = Lerp(p.x, event1.GetX(event1_pointer_index), alpha);
 121   p.y = Lerp(p.y, event1.GetY(event1_pointer_index), alpha);
 122   p.raw_x = Lerp(p.raw_x, event1.GetRawX(event1_pointer_index), alpha);
 123   p.raw_y = Lerp(p.raw_y, event1.GetRawY(event1_pointer_index), alpha);
 124   return p;
 125 }
 126
 127 scoped_ptr<MotionEvent> ResampleMotionEvent(const MotionEvent& event0,
 128                                             const MotionEvent& event1,
 129                                             base::TimeTicks resample_time) {
 130   DCHECK_EQ(MotionEvent::ACTION_MOVE, event0.GetAction());
 131   DCHECK_EQ(event0.GetPointerCount(), event1.GetPointerCount());
 132
 133   const base::TimeTicks time0 = event0.GetEventTime();
 134   const base::TimeTicks time1 = event1.GetEventTime();
 135   DCHECK(time0 < time1);
 136   DCHECK(time0 <= resample_time);
 137
 138   const float alpha = (resample_time - time0).InMillisecondsF() /
 139                       (time1 - time0).InMillisecondsF();
 140
 141   scoped_ptr<MotionEventGeneric> event;
 142   const size_t pointer_count = event0.GetPointerCount();
 143   DCHECK_EQ(pointer_count, event1.GetPointerCount());
 144   for (size_t event0_i = 0; event0_i < pointer_count; ++event0_i) {
 145     int event1_i = event1.FindPointerIndexOfId(event0.GetPointerId(event0_i));
 146     DCHECK_NE(event1_i, -1);
 147     PointerProperties pointer = ResamplePointer(
 148         event0, event1, event0_i, static_cast<size_t>(event1_i), alpha);
 149
 150     if (event0_i == 0) {
 151       event.reset(new MotionEventGeneric(
 152           MotionEvent::ACTION_MOVE, resample_time, pointer));
 153     } else {
 154       event->PushPointer(pointer);
 155     }
 156   }
 157
 158   DCHECK(event);
 159   event->set_id(event0.GetId());
 160   event->set_action_index(event0.GetActionIndex());
 161   event->set_button_state(event0.GetButtonState());
 162
 163   return event.PassAs<MotionEvent>();
 164 }
 165
 166 // MotionEvent implementation for storing multiple events, with the most
 167 // recent event used as the base event, and prior events used as the history.
 168 class CompoundMotionEvent : public ui::MotionEvent {
 169  public:
 170   explicit CompoundMotionEvent(MotionEventVector events)
 171       : events_(events.Pass()) {
 172     DCHECK_GE(events_.size(), 1U);
 173   }
 174   virtual ~CompoundMotionEvent() {}
 175
 176   virtual int GetId() const OVERRIDE { return latest().GetId(); }
 177   virtual Action GetAction() const OVERRIDE { return latest().GetAction(); }
 178   virtual int GetActionIndex() const OVERRIDE {
 179     return latest().GetActionIndex();
 180   }
 181   virtual size_t GetPointerCount() const OVERRIDE {
 182     return latest().GetPointerCount();
 183   }
 184   virtual int GetPointerId(size_t pointer_index) const OVERRIDE {
 185     return latest().GetPointerId(pointer_index);
 186   }
 187   virtual float GetX(size_t pointer_index) const OVERRIDE {
 188     return latest().GetX(pointer_index);
 189   }
 190   virtual float GetY(size_t pointer_index) const OVERRIDE {
 191     return latest().GetY(pointer_index);
 192   }
 193   virtual float GetRawX(size_t pointer_index) const OVERRIDE {
 194     return latest().GetRawX(pointer_index);
 195   }
 196   virtual float GetRawY(size_t pointer_index) const OVERRIDE {
 197     return latest().GetRawY(pointer_index);
 198   }
 199   virtual float GetTouchMajor(size_t pointer_index) const OVERRIDE {
 200     return latest().GetTouchMajor(pointer_index);
 201   }
 202   virtual float GetPressure(size_t pointer_index) const OVERRIDE {
 203     return latest().GetPressure(pointer_index);
 204   }
 205   virtual ToolType GetToolType(size_t pointer_index) const OVERRIDE {
 206     return latest().GetToolType(pointer_index);
 207   }
 208   virtual int GetButtonState() const OVERRIDE {
 209     return latest().GetButtonState();
 210   }
 211   virtual base::TimeTicks GetEventTime() const OVERRIDE {
 212     return latest().GetEventTime();
 213   }
 214   virtual size_t GetHistorySize() const OVERRIDE { return events_.size() - 1; }
 215   virtual base::TimeTicks GetHistoricalEventTime(
 216       size_t historical_index) const OVERRIDE {
 217     DCHECK_LT(historical_index, GetHistorySize());
 218     return events_[historical_index]->GetEventTime();
 219   }
 220   virtual float GetHistoricalTouchMajor(
 221       size_t pointer_index,
 222       size_t historical_index) const OVERRIDE {
 223     DCHECK_LT(historical_index, GetHistorySize());
 224     return events_[historical_index]->GetTouchMajor();
 225   }
 226   virtual float GetHistoricalX(size_t pointer_index,
 227                                size_t historical_index) const OVERRIDE {
 228     DCHECK_LT(historical_index, GetHistorySize());
 229     return events_[historical_index]->GetX(pointer_index);
 230   }
 231   virtual float GetHistoricalY(size_t pointer_index,
 232                                size_t historical_index) const OVERRIDE {
 233     DCHECK_LT(historical_index, GetHistorySize());
 234     return events_[historical_index]->GetY(pointer_index);
 235   }
 236   virtual scoped_ptr<MotionEvent> Clone() const OVERRIDE {
 237     MotionEventVector cloned_events;
 238     cloned_events.reserve(events_.size());
 239     for (size_t i = 0; i < events_.size(); ++i)
 240       cloned_events.push_back(events_[i]->Clone().release());
 241     return scoped_ptr<MotionEvent>(
 242         new CompoundMotionEvent(cloned_events.Pass()));
 243   }
 244   virtual scoped_ptr<MotionEvent> Cancel() const OVERRIDE {
 245     return latest().Cancel();
 246   }
 247
 248   // Returns the new, resampled event, or NULL if none was created.
 249   // TODO(jdduke): Revisit resampling to handle cases where alternating frames
 250   // are resampled or resampling is otherwise inconsistent, e.g., a 90hz input
 251   // and 60hz frame signal could phase-align such that even frames yield an
 252   // extrapolated event and odd frames are not resampled, crbug.com/399381.
 253   const MotionEvent* TryResample(base::TimeTicks resample_time,
 254                                  const ui::MotionEvent* next) {
 255     DCHECK_EQ(GetAction(), ACTION_MOVE);
 256     const ui::MotionEvent* event0 = NULL;
 257     const ui::MotionEvent* event1 = NULL;
 258     if (next) {
 259       DCHECK(resample_time < next->GetEventTime());
 260       // Interpolate between current sample and future sample.
 261       event0 = events_.back();
 262       event1 = next;
 263     } else if (events_.size() >= 2) {
 264       // Extrapolate future sample using current sample and past sample.
 265       event0 = events_[events_.size() - 2];
 266       event1 = events_[events_.size() - 1];
 267
 268       const base::TimeTicks time1 = event1->GetEventTime();
 269       base::TimeTicks max_predict =
 270           time1 +
 271           std::min((event1->GetEventTime() - event0->GetEventTime()) / 2,
 272                    base::TimeDelta::FromMilliseconds(kResampleMaxPredictionMs));
 273       if (resample_time > max_predict) {
 274         TRACE_EVENT_INSTANT2("input",
 275                              "MotionEventBuffer::TryResample prediction adjust",
 276                              TRACE_EVENT_SCOPE_THREAD,
 277                              "original(ms)",
 278                              (resample_time - time1).InMilliseconds(),
 279                              "adjusted(ms)",
 280                              (max_predict - time1).InMilliseconds());
 281         resample_time = max_predict;
 282       }
 283     } else {
 284       TRACE_EVENT_INSTANT0("input",
 285                            "MotionEventBuffer::TryResample insufficient data",
 286                            TRACE_EVENT_SCOPE_THREAD);
 287       return NULL;
 288     }
 289
 290     DCHECK(event0);
 291     DCHECK(event1);
 292     const base::TimeTicks time0 = event0->GetEventTime();
 293     const base::TimeTicks time1 = event1->GetEventTime();
 294     base::TimeDelta delta = time1 - time0;
 295     if (delta < base::TimeDelta::FromMilliseconds(kResampleMinDeltaMs)) {
 296       TRACE_EVENT_INSTANT1("input",
 297                            "MotionEventBuffer::TryResample failure",
 298                            TRACE_EVENT_SCOPE_THREAD,
 299                            "event_delta_too_small(ms)",
 300                            delta.InMilliseconds());
 301       return NULL;
 302     }
 303
 304     events_.push_back(
 305         ResampleMotionEvent(*event0, *event1, resample_time).release());
 306     return events_.back();
 307   }
 308
 309   size_t samples() const { return events_.size(); }
 310
 311  private:
 312   const MotionEvent& latest() const { return *events_.back(); }
 313
 314   // Events are in order from oldest to newest.
 315   MotionEventVector events_;
 316
 317   DISALLOW_COPY_AND_ASSIGN(CompoundMotionEvent);
 318 };
 319
 320 }  // namespace
 321
 322 MotionEventBuffer::MotionEventBuffer(MotionEventBufferClient* client,
 323                                      bool enable_resampling)
 324     : client_(client), resample_(enable_resampling) {
 325 }
 326
 327 MotionEventBuffer::~MotionEventBuffer() {
 328 }
 329
 330 void MotionEventBuffer::OnMotionEvent(const MotionEvent& event) {
 331   if (event.GetAction() != MotionEvent::ACTION_MOVE) {
 332     last_extrapolated_event_time_ = base::TimeTicks();
 333     if (!buffered_events_.empty())
 334       FlushWithoutResampling(buffered_events_.Pass());
 335     client_->ForwardMotionEvent(event);
 336     return;
 337   }
 338
 339   // Guard against events that are *older* than the last one that may have been
 340   // artificially synthesized.
 341   if (!last_extrapolated_event_time_.is_null()) {
 342     DCHECK(buffered_events_.empty());
 343     if (event.GetEventTime() < last_extrapolated_event_time_)
 344       return;
 345     last_extrapolated_event_time_ = base::TimeTicks();
 346   }
 347
 348   scoped_ptr<MotionEvent> clone = event.Clone();
 349   if (buffered_events_.empty()) {
 350     buffered_events_.push_back(clone.release());
 351     client_->SetNeedsFlush();
 352     return;
 353   }
 354
 355   if (CanAddSample(*buffered_events_.front(), *clone)) {
 356     DCHECK(buffered_events_.back()->GetEventTime() <= clone->GetEventTime());
 357   } else {
 358     FlushWithoutResampling(buffered_events_.Pass());
 359   }
 360
 361   buffered_events_.push_back(clone.release());
 362   // No need to request another flush as the first event will have requested it.
 363 }
 364
 365 void MotionEventBuffer::Flush(base::TimeTicks frame_time) {
 366   if (buffered_events_.empty())
 367     return;
 368
 369   // Shifting the sample time back slightly minimizes the potential for
 370   // misprediction when extrapolating events.
 371   if (resample_)
 372     frame_time -= base::TimeDelta::FromMilliseconds(kResampleLatencyMs);
 373
 374   // TODO(jdduke): Use a persistent MotionEventVector vector for temporary
 375   // storage.
 376   MotionEventVector events(
 377       ConsumeSamplesNoLaterThan(&buffered_events_, frame_time));
 378   if (events.empty()) {
 379     DCHECK(!buffered_events_.empty());
 380     client_->SetNeedsFlush();
 381     return;
 382   }
 383
 384   if (!resample_ || (events.size() == 1 && buffered_events_.empty())) {
 385     FlushWithoutResampling(events.Pass());
 386     if (!buffered_events_.empty())
 387       client_->SetNeedsFlush();
 388     return;
 389   }
 390
 391   CompoundMotionEvent resampled_event(events.Pass());
 392   base::TimeTicks original_event_time = resampled_event.GetEventTime();
 393   const MotionEvent* next_event =
 394       !buffered_events_.empty() ? buffered_events_.front() : NULL;
 395
 396   // Try to interpolate/extrapolate a new event at |frame_time|. Note that
 397   // |new_event|, if non-NULL, is owned by |resampled_event_|.
 398   const MotionEvent* new_event =
 399       resampled_event.TryResample(frame_time, next_event);
 400
 401   // Log the extrapolated event time, guarding against subsequently queued
 402   // events that might have an earlier timestamp.
 403   if (!next_event && new_event &&
 404       new_event->GetEventTime() > original_event_time) {
 405     last_extrapolated_event_time_ = new_event->GetEventTime();
 406   } else {
 407     last_extrapolated_event_time_ = base::TimeTicks();
 408   }
 409
 410   client_->ForwardMotionEvent(resampled_event);
 411   if (!buffered_events_.empty())
 412     client_->SetNeedsFlush();
 413 }
 414
 415 void MotionEventBuffer::FlushWithoutResampling(MotionEventVector events) {
 416   last_extrapolated_event_time_ = base::TimeTicks();
 417   if (events.empty())
 418     return;
 419
 420   if (events.size() == 1) {
 421     // Avoid CompoundEvent creation to prevent unnecessary allocations.
 422     scoped_ptr<MotionEvent> event(events.front());
 423     events.weak_clear();
 424     client_->ForwardMotionEvent(*event);
 425     return;
 426   }
 427
 428   CompoundMotionEvent compound_event(events.Pass());
 429   client_->ForwardMotionEvent(compound_event);
 430 }
 431
 432 }  // namespace ui