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