Home | History | Annotate | Download | only in gesture_detection 
      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   result.touch_minor = event.GetTouchMinor(pointer_index);
    101   result.orientation = event.GetOrientation(pointer_index);
    102   return result;
    103 }
    104 
    105 PointerProperties ResamplePointer(const MotionEvent& event0,
    106                                   const MotionEvent& event1,
    107                                   size_t event0_pointer_index,
    108                                   size_t event1_pointer_index,
    109                                   float alpha) {
    110   DCHECK_EQ(event0.GetPointerId(event0_pointer_index),
    111             event1.GetPointerId(event1_pointer_index));
    112   // If the tool should not be resampled, use the latest event in the valid
    113   // horizon (i.e., the event no later than the time interpolated by alpha).
    114   if (!ShouldResampleTool(event0.GetToolType(event0_pointer_index))) {
    115     if (alpha > 1)
    116       return PointerFromMotionEvent(event1, event1_pointer_index);
    117     else
    118       return PointerFromMotionEvent(event0, event0_pointer_index);
    119   }
    120 
    121   PointerProperties p(PointerFromMotionEvent(event0, event0_pointer_index));
    122   p.x = Lerp(p.x, event1.GetX(event1_pointer_index), alpha);
    123   p.y = Lerp(p.y, event1.GetY(event1_pointer_index), alpha);
    124   p.raw_x = Lerp(p.raw_x, event1.GetRawX(event1_pointer_index), alpha);
    125   p.raw_y = Lerp(p.raw_y, event1.GetRawY(event1_pointer_index), alpha);
    126   return p;
    127 }
    128 
    129 scoped_ptr<MotionEvent> ResampleMotionEvent(const MotionEvent& event0,
    130                                             const MotionEvent& event1,
    131                                             base::TimeTicks resample_time) {
    132   DCHECK_EQ(MotionEvent::ACTION_MOVE, event0.GetAction());
    133   DCHECK_EQ(event0.GetPointerCount(), event1.GetPointerCount());
    134 
    135   const base::TimeTicks time0 = event0.GetEventTime();
    136   const base::TimeTicks time1 = event1.GetEventTime();
    137   DCHECK(time0 < time1);
    138   DCHECK(time0 <= resample_time);
    139 
    140   const float alpha = (resample_time - time0).InMillisecondsF() /
    141                       (time1 - time0).InMillisecondsF();
    142 
    143   scoped_ptr<MotionEventGeneric> event;
    144   const size_t pointer_count = event0.GetPointerCount();
    145   DCHECK_EQ(pointer_count, event1.GetPointerCount());
    146   for (size_t event0_i = 0; event0_i < pointer_count; ++event0_i) {
    147     int event1_i = event1.FindPointerIndexOfId(event0.GetPointerId(event0_i));
    148     DCHECK_NE(event1_i, -1);
    149     PointerProperties pointer = ResamplePointer(
    150         event0, event1, event0_i, static_cast<size_t>(event1_i), alpha);
    151 
    152     if (event0_i == 0) {
    153       event.reset(new MotionEventGeneric(
    154           MotionEvent::ACTION_MOVE, resample_time, pointer));
    155     } else {
    156       event->PushPointer(pointer);
    157     }
    158   }
    159 
    160   DCHECK(event);
    161   event->set_id(event0.GetId());
    162   event->set_action_index(event0.GetActionIndex());
    163   event->set_button_state(event0.GetButtonState());
    164 
    165   return event.PassAs<MotionEvent>();
    166 }
    167 
    168 // MotionEvent implementation for storing multiple events, with the most
    169 // recent event used as the base event, and prior events used as the history.
    170 class CompoundMotionEvent : public ui::MotionEvent {
    171  public:
    172   explicit CompoundMotionEvent(MotionEventVector events)
    173       : events_(events.Pass()) {
    174     DCHECK_GE(events_.size(), 1U);
    175   }
    176   virtual ~CompoundMotionEvent() {}
    177 
    178   virtual int GetId() const OVERRIDE { return latest().GetId(); }
    179 
    180   virtual Action GetAction() const OVERRIDE { return latest().GetAction(); }
    181 
    182   virtual int GetActionIndex() const OVERRIDE {
    183     return latest().GetActionIndex();
    184   }
    185 
    186   virtual size_t GetPointerCount() const OVERRIDE {
    187     return latest().GetPointerCount();
    188   }
    189 
    190   virtual int GetPointerId(size_t pointer_index) const OVERRIDE {
    191     return latest().GetPointerId(pointer_index);
    192   }
    193 
    194   virtual float GetX(size_t pointer_index) const OVERRIDE {
    195     return latest().GetX(pointer_index);
    196   }
    197 
    198   virtual float GetY(size_t pointer_index) const OVERRIDE {
    199     return latest().GetY(pointer_index);
    200   }
    201 
    202   virtual float GetRawX(size_t pointer_index) const OVERRIDE {
    203     return latest().GetRawX(pointer_index);
    204   }
    205 
    206   virtual float GetRawY(size_t pointer_index) const OVERRIDE {
    207     return latest().GetRawY(pointer_index);
    208   }
    209 
    210   virtual float GetTouchMajor(size_t pointer_index) const OVERRIDE {
    211     return latest().GetTouchMajor(pointer_index);
    212   }
    213 
    214   virtual float GetTouchMinor(size_t pointer_index) const OVERRIDE {
    215     return latest().GetTouchMinor(pointer_index);
    216   }
    217 
    218   virtual float GetOrientation(size_t pointer_index) const OVERRIDE {
    219     return latest().GetOrientation(pointer_index);
    220   }
    221 
    222   virtual float GetPressure(size_t pointer_index) const OVERRIDE {
    223     return latest().GetPressure(pointer_index);
    224   }
    225 
    226   virtual ToolType GetToolType(size_t pointer_index) const OVERRIDE {
    227     return latest().GetToolType(pointer_index);
    228   }
    229 
    230   virtual int GetButtonState() const OVERRIDE {
    231     return latest().GetButtonState();
    232   }
    233 
    234   virtual int GetFlags() const OVERRIDE { return latest().GetFlags(); }
    235 
    236   virtual base::TimeTicks GetEventTime() const OVERRIDE {
    237     return latest().GetEventTime();
    238   }
    239 
    240   virtual size_t GetHistorySize() const OVERRIDE { return events_.size() - 1; }
    241 
    242   virtual base::TimeTicks GetHistoricalEventTime(
    243       size_t historical_index) const OVERRIDE {
    244     DCHECK_LT(historical_index, GetHistorySize());
    245     return events_[historical_index]->GetEventTime();
    246   }
    247 
    248   virtual float GetHistoricalTouchMajor(
    249       size_t pointer_index,
    250       size_t historical_index) const OVERRIDE {
    251     DCHECK_LT(historical_index, GetHistorySize());
    252     return events_[historical_index]->GetTouchMajor();
    253   }
    254 
    255   virtual float GetHistoricalX(size_t pointer_index,
    256                                size_t historical_index) const OVERRIDE {
    257     DCHECK_LT(historical_index, GetHistorySize());
    258     return events_[historical_index]->GetX(pointer_index);
    259   }
    260 
    261   virtual float GetHistoricalY(size_t pointer_index,
    262                                size_t historical_index) const OVERRIDE {
    263     DCHECK_LT(historical_index, GetHistorySize());
    264     return events_[historical_index]->GetY(pointer_index);
    265   }
    266 
    267   virtual scoped_ptr<MotionEvent> Clone() const OVERRIDE {
    268     MotionEventVector cloned_events;
    269     cloned_events.reserve(events_.size());
    270     for (size_t i = 0; i < events_.size(); ++i)
    271       cloned_events.push_back(events_[i]->Clone().release());
    272     return scoped_ptr<MotionEvent>(
    273         new CompoundMotionEvent(cloned_events.Pass()));
    274   }
    275 
    276   virtual scoped_ptr<MotionEvent> Cancel() const OVERRIDE {
    277     return latest().Cancel();
    278   }
    279 
    280   // Returns the new, resampled event, or NULL if none was created.
    281   // TODO(jdduke): Revisit resampling to handle cases where alternating frames
    282   // are resampled or resampling is otherwise inconsistent, e.g., a 90hz input
    283   // and 60hz frame signal could phase-align such that even frames yield an
    284   // extrapolated event and odd frames are not resampled, crbug.com/399381.
    285   const MotionEvent* TryResample(base::TimeTicks resample_time,
    286                                  const ui::MotionEvent* next) {
    287     DCHECK_EQ(GetAction(), ACTION_MOVE);
    288     const ui::MotionEvent* event0 = NULL;
    289     const ui::MotionEvent* event1 = NULL;
    290     if (next) {
    291       DCHECK(resample_time < next->GetEventTime());
    292       // Interpolate between current sample and future sample.
    293       event0 = events_.back();
    294       event1 = next;
    295     } else if (events_.size() >= 2) {
    296       // Extrapolate future sample using current sample and past sample.
    297       event0 = events_[events_.size() - 2];
    298       event1 = events_[events_.size() - 1];
    299 
    300       const base::TimeTicks time1 = event1->GetEventTime();
    301       base::TimeTicks max_predict =
    302           time1 +
    303           std::min((event1->GetEventTime() - event0->GetEventTime()) / 2,
    304                    base::TimeDelta::FromMilliseconds(kResampleMaxPredictionMs));
    305       if (resample_time > max_predict) {
    306         TRACE_EVENT_INSTANT2("input",
    307                              "MotionEventBuffer::TryResample prediction adjust",
    308                              TRACE_EVENT_SCOPE_THREAD,
    309                              "original(ms)",
    310                              (resample_time - time1).InMilliseconds(),
    311                              "adjusted(ms)",
    312                              (max_predict - time1).InMilliseconds());
    313         resample_time = max_predict;
    314       }
    315     } else {
    316       TRACE_EVENT_INSTANT0("input",
    317                            "MotionEventBuffer::TryResample insufficient data",
    318                            TRACE_EVENT_SCOPE_THREAD);
    319       return NULL;
    320     }
    321 
    322     DCHECK(event0);
    323     DCHECK(event1);
    324     const base::TimeTicks time0 = event0->GetEventTime();
    325     const base::TimeTicks time1 = event1->GetEventTime();
    326     base::TimeDelta delta = time1 - time0;
    327     if (delta < base::TimeDelta::FromMilliseconds(kResampleMinDeltaMs)) {
    328       TRACE_EVENT_INSTANT1("input",
    329                            "MotionEventBuffer::TryResample failure",
    330                            TRACE_EVENT_SCOPE_THREAD,
    331                            "event_delta_too_small(ms)",
    332                            delta.InMilliseconds());
    333       return NULL;
    334     }
    335 
    336     events_.push_back(
    337         ResampleMotionEvent(*event0, *event1, resample_time).release());
    338     return events_.back();
    339   }
    340 
    341   size_t samples() const { return events_.size(); }
    342 
    343  private:
    344   const MotionEvent& latest() const { return *events_.back(); }
    345 
    346   // Events are in order from oldest to newest.
    347   MotionEventVector events_;
    348 
    349   DISALLOW_COPY_AND_ASSIGN(CompoundMotionEvent);
    350 };
    351 
    352 }  // namespace
    353 
    354 MotionEventBuffer::MotionEventBuffer(MotionEventBufferClient* client,
    355                                      bool enable_resampling)
    356     : client_(client), resample_(enable_resampling) {
    357 }
    358 
    359 MotionEventBuffer::~MotionEventBuffer() {
    360 }
    361 
    362 void MotionEventBuffer::OnMotionEvent(const MotionEvent& event) {
    363   if (event.GetAction() != MotionEvent::ACTION_MOVE) {
    364     last_extrapolated_event_time_ = base::TimeTicks();
    365     if (!buffered_events_.empty())
    366       FlushWithoutResampling(buffered_events_.Pass());
    367     client_->ForwardMotionEvent(event);
    368     return;
    369   }
    370 
    371   // Guard against events that are *older* than the last one that may have been
    372   // artificially synthesized.
    373   if (!last_extrapolated_event_time_.is_null()) {
    374     DCHECK(buffered_events_.empty());
    375     if (event.GetEventTime() < last_extrapolated_event_time_)
    376       return;
    377     last_extrapolated_event_time_ = base::TimeTicks();
    378   }
    379 
    380   scoped_ptr<MotionEvent> clone = event.Clone();
    381   if (buffered_events_.empty()) {
    382     buffered_events_.push_back(clone.release());
    383     client_->SetNeedsFlush();
    384     return;
    385   }
    386 
    387   if (CanAddSample(*buffered_events_.front(), *clone)) {
    388     DCHECK(buffered_events_.back()->GetEventTime() <= clone->GetEventTime());
    389   } else {
    390     FlushWithoutResampling(buffered_events_.Pass());
    391   }
    392 
    393   buffered_events_.push_back(clone.release());
    394   // No need to request another flush as the first event will have requested it.
    395 }
    396 
    397 void MotionEventBuffer::Flush(base::TimeTicks frame_time) {
    398   if (buffered_events_.empty())
    399     return;
    400 
    401   // Shifting the sample time back slightly minimizes the potential for
    402   // misprediction when extrapolating events.
    403   if (resample_)
    404     frame_time -= base::TimeDelta::FromMilliseconds(kResampleLatencyMs);
    405 
    406   // TODO(jdduke): Use a persistent MotionEventVector vector for temporary
    407   // storage.
    408   MotionEventVector events(
    409       ConsumeSamplesNoLaterThan(&buffered_events_, frame_time));
    410   if (events.empty()) {
    411     DCHECK(!buffered_events_.empty());
    412     client_->SetNeedsFlush();
    413     return;
    414   }
    415 
    416   if (!resample_ || (events.size() == 1 && buffered_events_.empty())) {
    417     FlushWithoutResampling(events.Pass());
    418     if (!buffered_events_.empty())
    419       client_->SetNeedsFlush();
    420     return;
    421   }
    422 
    423   CompoundMotionEvent resampled_event(events.Pass());
    424   base::TimeTicks original_event_time = resampled_event.GetEventTime();
    425   const MotionEvent* next_event =
    426       !buffered_events_.empty() ? buffered_events_.front() : NULL;
    427 
    428   // Try to interpolate/extrapolate a new event at |frame_time|. Note that
    429   // |new_event|, if non-NULL, is owned by |resampled_event_|.
    430   const MotionEvent* new_event =
    431       resampled_event.TryResample(frame_time, next_event);
    432 
    433   // Log the extrapolated event time, guarding against subsequently queued
    434   // events that might have an earlier timestamp.
    435   if (!next_event && new_event &&
    436       new_event->GetEventTime() > original_event_time) {
    437     last_extrapolated_event_time_ = new_event->GetEventTime();
    438   } else {
    439     last_extrapolated_event_time_ = base::TimeTicks();
    440   }
    441 
    442   client_->ForwardMotionEvent(resampled_event);
    443   if (!buffered_events_.empty())
    444     client_->SetNeedsFlush();
    445 }
    446 
    447 void MotionEventBuffer::FlushWithoutResampling(MotionEventVector events) {
    448   last_extrapolated_event_time_ = base::TimeTicks();
    449   if (events.empty())
    450     return;
    451 
    452   if (events.size() == 1) {
    453     // Avoid CompoundEvent creation to prevent unnecessary allocations.
    454     scoped_ptr<MotionEvent> event(events.front());
    455     events.weak_clear();
    456     client_->ForwardMotionEvent(*event);
    457     return;
    458   }
    459 
    460   CompoundMotionEvent compound_event(events.Pass());
    461   client_->ForwardMotionEvent(compound_event);
    462 }
    463 
    464 }  // namespace ui
    465