summaryrefslogtreecommitdiffstats
path: root/widget/TouchResampler.cpp
blob: 51974a440596025290f18a24e96f0c2937cd74b3 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#include "TouchResampler.h"

#include "nsAlgorithm.h"

/**
 * TouchResampler implementation
 */

namespace mozilla {
namespace widget {

// The values below have been tested and found to be acceptable on a device
// with a display refresh rate of 60Hz and touch sampling rate of 100Hz.
// While their "ideal" values are dependent on the exact rates of each device,
// the values we've picked below should be somewhat robust across a variation of
// different rates. They mostly aim to avoid making predictions that are too far
// away (in terms of distance) from the finger, and to detect pauses in the
// finger motion without too much delay.

// Maximum time between two consecutive data points to consider resampling
// between them.
// Values between 1x and 5x of the touch sampling interval are reasonable.
static const double kTouchResampleWindowSize = 40.0;

// These next two values constrain the sampling timestamp.
// Our caller will usually adjust frame timestamps to be slightly in the past,
// for example by 5ms. This means that, during normal operation, we will
// maximally need to predict by [touch sampling rate] minus 5ms.
// So we would like kTouchResampleMaxPredictMs to satisfy the following:
// kTouchResampleMaxPredictMs + [frame time adjust] > [touch sampling rate]
static const double kTouchResampleMaxPredictMs = 8.0;
// This one is a protection against very outdated frame timestamps.
// Values larger than the touch sampling interval and less than 3x of the vsync
// interval are reasonable.
static const double kTouchResampleMaxBacksampleMs = 20.0;

// The maximum age of the most recent data point to consider resampling.
// Should be between 1x and 3x of the touch sampling interval.
static const double kTouchResampleOldTouchThresholdMs = 17.0;

uint64_t TouchResampler::ProcessEvent(MultiTouchInput&& aInput) {
  mCurrentTouches.UpdateFromEvent(aInput);

  uint64_t eventId = mNextEventId;
  mNextEventId++;

  if (aInput.mType == MultiTouchInput::MULTITOUCH_MOVE) {
    // Touch move events are deferred until NotifyFrame.
    mDeferredTouchMoveEvents.push({std::move(aInput), eventId});
  } else {
    // Non-move events are transferred to the outgoing queue unmodified.
    // If there are pending touch move events, flush those out first, so that
    // events are emitted in the right order.
    FlushDeferredTouchMoveEventsUnresampled();
    if (mInResampledState) {
      // Return to a non-resampled state before emitting a non-move event.
      ReturnToNonResampledState();
    }
    EmitEvent(std::move(aInput), eventId);
  }

  return eventId;
}

void TouchResampler::NotifyFrame(const TimeStamp& aTimeStamp) {
  TimeStamp lastTouchTime = mCurrentTouches.LatestDataPointTime();
  if (mDeferredTouchMoveEvents.empty() ||
      (lastTouchTime &&
       lastTouchTime < aTimeStamp - TimeDuration::FromMilliseconds(
                                        kTouchResampleOldTouchThresholdMs))) {
    // We haven't received a touch move event in a while, so the fingers must
    // have stopped moving. Flush any old touch move events.
    FlushDeferredTouchMoveEventsUnresampled();

    if (mInResampledState) {
      // Make sure we pause at the resting position that we actually observed,
      // and not at a resampled position.
      ReturnToNonResampledState();
    }

    // Clear touch location history so that we don't resample across a pause.
    mCurrentTouches.ClearDataPoints();
    return;
  }

  MOZ_RELEASE_ASSERT(lastTouchTime);
  TimeStamp lowerBound = lastTouchTime - TimeDuration::FromMilliseconds(
                                             kTouchResampleMaxBacksampleMs);
  TimeStamp upperBound = lastTouchTime + TimeDuration::FromMilliseconds(
                                             kTouchResampleMaxPredictMs);
  TimeStamp sampleTime = clamped(aTimeStamp, lowerBound, upperBound);

  if (mLastEmittedEventTime && sampleTime < mLastEmittedEventTime) {
    // Keep emitted timestamps in order.
    sampleTime = mLastEmittedEventTime;
  }

  // We have at least one pending touch move event. Pick one of the events from
  // mDeferredTouchMoveEvents as the base event for the resampling adjustment.
  // We want to produce an event stream whose timestamps are in the right order.
  // As the base event, use the first event that's at or after sampleTime,
  // unless there is no such event, in that case use the last one we have. We
  // will set the timestamp on the resampled event to sampleTime later.
  // Flush out any older events so that everything remains in the right order.
  MultiTouchInput input;
  uint64_t eventId;
  while (true) {
    MOZ_RELEASE_ASSERT(!mDeferredTouchMoveEvents.empty());

    std::tie(input, eventId) = std::move(mDeferredTouchMoveEvents.front());
    mDeferredTouchMoveEvents.pop();
    if (mDeferredTouchMoveEvents.empty() || input.mTimeStamp >= sampleTime) {
      break;
    }

    // Flush this event to the outgoing queue without resampling. What ends up
    // on the screen will still be smooth because we will proceed to emit a
    // resampled event before the paint for this frame starts.
    PrependLeftoverHistoricalData(&input);
    MOZ_RELEASE_ASSERT(input.mTimeStamp < sampleTime);
    EmitEvent(std::move(input), eventId);
  }

  mOriginalOfResampledTouchMove = Nothing();

  // Compute the resampled touch positions.
  nsTArray<ScreenIntPoint> resampledPositions;
  bool anyPositionDifferentFromOriginal = false;
  for (const auto& touch : input.mTouches) {
    ScreenIntPoint resampledPosition =
        mCurrentTouches.ResampleTouchPositionAtTime(
            touch.mIdentifier, touch.mScreenPoint, sampleTime);
    if (resampledPosition != touch.mScreenPoint) {
      anyPositionDifferentFromOriginal = true;
    }
    resampledPositions.AppendElement(resampledPosition);
  }

  if (anyPositionDifferentFromOriginal) {
    // Store a copy of the original event, so that we can return to an
    // non-resampled position later, if necessary.
    mOriginalOfResampledTouchMove = Some(input);

    // Add the original observed position to the historical data, as well as any
    // leftover historical positions from the previous touch move event, and
    // store the resampled values in the "final" position of the event.
    PrependLeftoverHistoricalData(&input);
    for (size_t i = 0; i < input.mTouches.Length(); i++) {
      auto& touch = input.mTouches[i];
      touch.mHistoricalData.AppendElement(SingleTouchData::HistoricalTouchData{
          input.mTimeStamp,
          touch.mScreenPoint,
          touch.mLocalScreenPoint,
          touch.mRadius,
          touch.mRotationAngle,
          touch.mForce,
      });

      // Remove any historical touch data that's in the future, compared to
      // sampleTime. This data will be included by upcoming touch move
      // events. This only happens if the frame timestamp can be older than the
      // event timestamp, i.e. if interpolation occurs (rather than
      // extrapolation).
      auto futureDataStart = std::find_if(
          touch.mHistoricalData.begin(), touch.mHistoricalData.end(),
          [sampleTime](
              const SingleTouchData::HistoricalTouchData& aHistoricalData) {
            return aHistoricalData.mTimeStamp > sampleTime;
          });
      if (futureDataStart != touch.mHistoricalData.end()) {
        nsTArray<SingleTouchData::HistoricalTouchData> futureData(
            Span<SingleTouchData::HistoricalTouchData>(touch.mHistoricalData)
                .From(futureDataStart.GetIndex()));
        touch.mHistoricalData.TruncateLength(futureDataStart.GetIndex());
        mRemainingTouchData.insert({touch.mIdentifier, std::move(futureData)});
      }

      touch.mScreenPoint = resampledPositions[i];
    }
    input.mTimeStamp = sampleTime;
  }

  EmitEvent(std::move(input), eventId);
  mInResampledState = anyPositionDifferentFromOriginal;
}

void TouchResampler::PrependLeftoverHistoricalData(MultiTouchInput* aInput) {
  for (auto& touch : aInput->mTouches) {
    auto leftoverData = mRemainingTouchData.find(touch.mIdentifier);
    if (leftoverData != mRemainingTouchData.end()) {
      nsTArray<SingleTouchData::HistoricalTouchData> data =
          std::move(leftoverData->second);
      mRemainingTouchData.erase(leftoverData);
      touch.mHistoricalData.InsertElementsAt(0, data);
    }

    if (TimeStamp cutoffTime = mLastEmittedEventTime) {
      // If we received historical touch data that was further in the past than
      // the last resampled event, discard that data so that the touch data
      // points are emitted in order.
      touch.mHistoricalData.RemoveElementsBy(
          [cutoffTime](const SingleTouchData::HistoricalTouchData& aTouchData) {
            return aTouchData.mTimeStamp < cutoffTime;
          });
    }
  }
  mRemainingTouchData.clear();
}

void TouchResampler::FlushDeferredTouchMoveEventsUnresampled() {
  while (!mDeferredTouchMoveEvents.empty()) {
    MultiTouchInput input;
    uint64_t eventId;
    std::tie(input, eventId) = std::move(mDeferredTouchMoveEvents.front());
    mDeferredTouchMoveEvents.pop();
    PrependLeftoverHistoricalData(&input);
    EmitEvent(std::move(input), eventId);
    mInResampledState = false;
    mOriginalOfResampledTouchMove = Nothing();
  }
}

void TouchResampler::ReturnToNonResampledState() {
  MOZ_RELEASE_ASSERT(mInResampledState);
  MOZ_RELEASE_ASSERT(mDeferredTouchMoveEvents.empty(),
                     "Don't call this if there is a deferred touch move event. "
                     "We can return to the non-resampled state by sending that "
                     "event, rather than a copy of a previous event.");

  // The last outgoing event was a resampled touch move event.
  // Return to the non-resampled state, by sending a touch move event to
  // "overwrite" any resampled positions with the original observed positions.
  MultiTouchInput input = std::move(*mOriginalOfResampledTouchMove);
  mOriginalOfResampledTouchMove = Nothing();

  // For the event's timestamp, we want to backdate the correction as far as we
  // can, while still preserving timestamp ordering. But we also don't want to
  // backdate it to be older than it was originally.
  if (mLastEmittedEventTime > input.mTimeStamp) {
    input.mTimeStamp = mLastEmittedEventTime;
  }

  // Assemble the correct historical touch data for this event.
  // We don't want to include data points that we've already sent out with the
  // resampled event. And from the leftover data points, we only want those that
  // don't duplicate the final time + position of this event.
  for (auto& touch : input.mTouches) {
    touch.mHistoricalData.Clear();
  }
  PrependLeftoverHistoricalData(&input);
  for (auto& touch : input.mTouches) {
    touch.mHistoricalData.RemoveElementsBy([&](const auto& histData) {
      return histData.mTimeStamp >= input.mTimeStamp;
    });
  }

  EmitExtraEvent(std::move(input));
  mInResampledState = false;
}

void TouchResampler::TouchInfo::Update(const SingleTouchData& aTouch,
                                       const TimeStamp& aEventTime) {
  for (const auto& historicalData : aTouch.mHistoricalData) {
    mBaseDataPoint = mLatestDataPoint;
    mLatestDataPoint =
        Some(DataPoint{historicalData.mTimeStamp, historicalData.mScreenPoint});
  }
  mBaseDataPoint = mLatestDataPoint;
  mLatestDataPoint = Some(DataPoint{aEventTime, aTouch.mScreenPoint});
}

ScreenIntPoint TouchResampler::TouchInfo::ResampleAtTime(
    const ScreenIntPoint& aLastObservedPosition, const TimeStamp& aTimeStamp) {
  TimeStamp cutoff =
      aTimeStamp - TimeDuration::FromMilliseconds(kTouchResampleWindowSize);
  if (!mBaseDataPoint || !mLatestDataPoint ||
      !(mBaseDataPoint->mTimeStamp < mLatestDataPoint->mTimeStamp) ||
      mBaseDataPoint->mTimeStamp < cutoff) {
    return aLastObservedPosition;
  }

  // For the actual resampling, connect the last two data points with a line and
  // sample along that line.
  TimeStamp t1 = mBaseDataPoint->mTimeStamp;
  TimeStamp t2 = mLatestDataPoint->mTimeStamp;
  double t = (aTimeStamp - t1) / (t2 - t1);

  double x1 = mBaseDataPoint->mPosition.x;
  double x2 = mLatestDataPoint->mPosition.x;
  double y1 = mBaseDataPoint->mPosition.y;
  double y2 = mLatestDataPoint->mPosition.y;

  int32_t resampledX = round(x1 + t * (x2 - x1));
  int32_t resampledY = round(y1 + t * (y2 - y1));
  return ScreenIntPoint(resampledX, resampledY);
}

void TouchResampler::CurrentTouches::UpdateFromEvent(
    const MultiTouchInput& aInput) {
  switch (aInput.mType) {
    case MultiTouchInput::MULTITOUCH_START: {
      // A new touch has been added; make sure mTouches reflects the current
      // touches in the event.
      nsTArray<TouchInfo> newTouches;
      for (const auto& touch : aInput.mTouches) {
        const auto touchInfo = TouchByIdentifier(touch.mIdentifier);
        if (touchInfo != mTouches.end()) {
          // This is one of the existing touches.
          newTouches.AppendElement(std::move(*touchInfo));
          mTouches.RemoveElementAt(touchInfo);
        } else {
          // This is the new touch.
          newTouches.AppendElement(TouchInfo{
              touch.mIdentifier, Nothing(),
              Some(DataPoint{aInput.mTimeStamp, touch.mScreenPoint})});
        }
      }
      MOZ_ASSERT(mTouches.IsEmpty(), "Missing touch end before touch start?");
      mTouches = std::move(newTouches);
      break;
    }

    case MultiTouchInput::MULTITOUCH_MOVE: {
      // The touches have moved.
      // Add position information to the history data points.
      for (const auto& touch : aInput.mTouches) {
        const auto touchInfo = TouchByIdentifier(touch.mIdentifier);
        MOZ_ASSERT(touchInfo != mTouches.end());
        if (touchInfo != mTouches.end()) {
          touchInfo->Update(touch, aInput.mTimeStamp);
        }
      }
      mLatestDataPointTime = aInput.mTimeStamp;
      break;
    }

    case MultiTouchInput::MULTITOUCH_END: {
      // A touch has been removed.
      MOZ_RELEASE_ASSERT(aInput.mTouches.Length() == 1);
      const auto touchInfo = TouchByIdentifier(aInput.mTouches[0].mIdentifier);
      MOZ_ASSERT(touchInfo != mTouches.end());
      if (touchInfo != mTouches.end()) {
        mTouches.RemoveElementAt(touchInfo);
      }
      break;
    }

    case MultiTouchInput::MULTITOUCH_CANCEL:
      // All touches are canceled.
      mTouches.Clear();
      break;
  }
}

nsTArray<TouchResampler::TouchInfo>::iterator
TouchResampler::CurrentTouches::TouchByIdentifier(int32_t aIdentifier) {
  return std::find_if(mTouches.begin(), mTouches.end(),
                      [aIdentifier](const TouchInfo& info) {
                        return info.mIdentifier == aIdentifier;
                      });
}

ScreenIntPoint TouchResampler::CurrentTouches::ResampleTouchPositionAtTime(
    int32_t aIdentifier, const ScreenIntPoint& aLastObservedPosition,
    const TimeStamp& aTimeStamp) {
  const auto touchInfo = TouchByIdentifier(aIdentifier);
  MOZ_ASSERT(touchInfo != mTouches.end());
  if (touchInfo != mTouches.end()) {
    return touchInfo->ResampleAtTime(aLastObservedPosition, aTimeStamp);
  }
  return aLastObservedPosition;
}

}  // namespace widget
}  // namespace mozilla