Add map like pointer lookup to LegacyResampler
Added map lookup operations to find pointers by ID when resampling them
inside LegacyResampler. The CL fixes the assumption that pointers should
appear in the same order between motion events. Moreover, tests from
LegacyResampler are updated to the new behavior.
Bug: 297226446
Flag: EXEMPT refactor
Test: TEST=libinput_tests; m $TEST && $ANDROID_HOST_OUT/nativetest64/$TEST/$TEST
Change-Id: I59c83d2e55bf4ab3cb7958cab333428499f6fee8
diff --git a/include/input/Resampler.h b/include/input/Resampler.h
index 47519c2..6d95ca7 100644
--- a/include/input/Resampler.h
+++ b/include/input/Resampler.h
@@ -16,10 +16,14 @@
#pragma once
+#include <array>
#include <chrono>
+#include <iterator>
#include <optional>
#include <vector>
+#include <android-base/logging.h>
+#include <ftl/mixins.h>
#include <input/Input.h>
#include <input/InputTransport.h>
#include <input/RingBuffer.h>
@@ -79,13 +83,127 @@
PointerCoords coords;
};
+ /**
+ * Container that stores pointers as an associative array, supporting O(1) lookup by pointer id,
+ * as well as forward iteration in the order in which the pointer or pointers were inserted in
+ * the container. PointerMap has a maximum capacity equal to MAX_POINTERS.
+ */
+ class PointerMap {
+ public:
+ struct PointerId : ftl::DefaultConstructible<PointerId, int32_t>,
+ ftl::Equatable<PointerId> {
+ using DefaultConstructible::DefaultConstructible;
+ };
+
+ /**
+ * Custom iterator to enable use of range-based for loops.
+ */
+ template <typename T>
+ class iterator {
+ public:
+ using iterator_category = std::forward_iterator_tag;
+ using value_type = T;
+ using difference_type = std::ptrdiff_t;
+ using pointer = T*;
+ using reference = T&;
+
+ explicit iterator(pointer element) : mElement{element} {}
+
+ friend bool operator==(const iterator& lhs, const iterator& rhs) {
+ return lhs.mElement == rhs.mElement;
+ }
+
+ friend bool operator!=(const iterator& lhs, const iterator& rhs) {
+ return !(lhs == rhs);
+ }
+
+ iterator operator++() {
+ ++mElement;
+ return *this;
+ }
+
+ reference operator*() const { return *mElement; }
+
+ private:
+ pointer mElement;
+ };
+
+ PointerMap() {
+ idToIndex.fill(std::nullopt);
+ for (Pointer& pointer : pointers) {
+ pointer.properties.clear();
+ pointer.coords.clear();
+ }
+ }
+
+ /**
+ * Forward iterators to traverse the pointers in `pointers`. The order of the pointers is
+ * determined by the order in which they were inserted (not by id).
+ */
+ iterator<Pointer> begin() { return iterator<Pointer>{&pointers[0]}; }
+
+ iterator<const Pointer> begin() const { return iterator<const Pointer>{&pointers[0]}; }
+
+ iterator<Pointer> end() { return iterator<Pointer>{&pointers[nextPointerIndex]}; }
+
+ iterator<const Pointer> end() const {
+ return iterator<const Pointer>{&pointers[nextPointerIndex]};
+ }
+
+ /**
+ * Inserts the given pointer into the PointerMap. Precondition: The current number of
+ * contained pointers must be less than MAX_POINTERS when this function is called. It
+ * fatally logs if the user tries to insert more than MAX_POINTERS, or if pointer id is out
+ * of bounds.
+ */
+ void insert(const Pointer& pointer) {
+ LOG_IF(FATAL, nextPointerIndex >= pointers.size())
+ << "Cannot insert more than " << MAX_POINTERS << " in PointerMap.";
+ LOG_IF(FATAL, (pointer.properties.id < 0) || (pointer.properties.id > MAX_POINTER_ID))
+ << "Invalid pointer id.";
+ idToIndex[pointer.properties.id] = std::optional<size_t>{nextPointerIndex};
+ pointers[nextPointerIndex] = pointer;
+ ++nextPointerIndex;
+ }
+
+ /**
+ * Returns the pointer associated with the provided id if it exists.
+ * Otherwise, std::nullopt is returned.
+ */
+ std::optional<Pointer> find(PointerId id) const {
+ const int32_t idValue = ftl::to_underlying(id);
+ LOG_IF(FATAL, (idValue < 0) || (idValue > MAX_POINTER_ID)) << "Invalid pointer id.";
+ const std::optional<size_t> index = idToIndex[idValue];
+ return index.has_value() ? std::optional{pointers[*index]} : std::nullopt;
+ }
+
+ private:
+ /**
+ * The index at which a pointer is inserted in `pointers`. Likewise, it represents the
+ * number of pointers in PointerMap.
+ */
+ size_t nextPointerIndex{0};
+
+ /**
+ * Sequentially stores pointers. Each pointer's position is determined by the value of
+ * nextPointerIndex at insertion time.
+ */
+ std::array<Pointer, MAX_POINTERS + 1> pointers;
+
+ /**
+ * Maps each pointer id to its associated index in pointers. If no pointer with the id
+ * exists in pointers, the mapped value is std::nullopt.
+ */
+ std::array<std::optional<size_t>, MAX_POINTER_ID + 1> idToIndex;
+ };
+
struct Sample {
std::chrono::nanoseconds eventTime;
- std::vector<Pointer> pointers;
+ PointerMap pointerMap;
std::vector<PointerCoords> asPointerCoords() const {
std::vector<PointerCoords> pointersCoords;
- for (const Pointer& pointer : pointers) {
+ for (const Pointer& pointer : pointerMap) {
pointersCoords.push_back(pointer.coords);
}
return pointersCoords;
@@ -100,13 +218,12 @@
RingBuffer<Sample> mLatestSamples{/*capacity=*/2};
/**
- * Latest sample in mLatestSamples after resampling motion event. Used to compare if a pointer
- * does not move between samples.
+ * Latest sample in mLatestSamples after resampling motion event.
*/
std::optional<Sample> mLastRealSample;
/**
- * Latest prediction. Used to overwrite motion event samples if a set of conditions is met.
+ * Latest prediction. That is, the latest extrapolated sample.
*/
std::optional<Sample> mPreviousPrediction;
@@ -134,12 +251,12 @@
bool canInterpolate(const InputMessage& futureSample) const;
/**
- * Returns a sample interpolated between the latest sample of mLatestSamples and futureSample,
+ * Returns a sample interpolated between the latest sample of mLatestSamples and futureMessage,
* if the conditions from canInterpolate are satisfied. Otherwise, returns nullopt.
* mLatestSamples must have at least one sample when attemptInterpolation is called.
*/
std::optional<Sample> attemptInterpolation(std::chrono::nanoseconds resampleTime,
- const InputMessage& futureSample) const;
+ const InputMessage& futureMessage) const;
/**
* Checks if there are necessary conditions to extrapolate. That is, there are at least two
@@ -156,7 +273,8 @@
std::optional<Sample> attemptExtrapolation(std::chrono::nanoseconds resampleTime) const;
/**
- * Iterates through motion event samples, and calls overwriteStillPointers on each sample.
+ * Iterates through motion event samples, and replaces real coordinates with resampled
+ * coordinates to avoid jerkiness in certain conditions.
*/
void overwriteMotionEventSamples(MotionEvent& motionEvent) const;
@@ -174,4 +292,5 @@
inline static void addSampleToMotionEvent(const Sample& sample, MotionEvent& motionEvent);
};
+
} // namespace android
diff --git a/libs/input/Resampler.cpp b/libs/input/Resampler.cpp
index e2cc6fb..884b66e 100644
--- a/libs/input/Resampler.cpp
+++ b/libs/input/Resampler.cpp
@@ -107,46 +107,44 @@
const size_t latestIndex = numSamples - 1;
const size_t secondToLatestIndex = (latestIndex > 0) ? (latestIndex - 1) : 0;
for (size_t sampleIndex = secondToLatestIndex; sampleIndex < numSamples; ++sampleIndex) {
- std::vector<Pointer> pointers;
- const size_t numPointers = motionEvent.getPointerCount();
- for (size_t pointerIndex = 0; pointerIndex < numPointers; ++pointerIndex) {
- pointers.push_back(Pointer{*(motionEvent.getPointerProperties(pointerIndex)),
- *(motionEvent.getHistoricalRawPointerCoords(pointerIndex,
- sampleIndex))});
+ PointerMap pointerMap;
+ for (size_t pointerIndex = 0; pointerIndex < motionEvent.getPointerCount();
+ ++pointerIndex) {
+ pointerMap.insert(Pointer{*(motionEvent.getPointerProperties(pointerIndex)),
+ *(motionEvent.getHistoricalRawPointerCoords(pointerIndex,
+ sampleIndex))});
}
mLatestSamples.pushBack(
- Sample{nanoseconds{motionEvent.getHistoricalEventTime(sampleIndex)}, pointers});
+ Sample{nanoseconds{motionEvent.getHistoricalEventTime(sampleIndex)}, pointerMap});
}
}
LegacyResampler::Sample LegacyResampler::messageToSample(const InputMessage& message) {
- std::vector<Pointer> pointers;
+ PointerMap pointerMap;
for (uint32_t i = 0; i < message.body.motion.pointerCount; ++i) {
- pointers.push_back(Pointer{message.body.motion.pointers[i].properties,
- message.body.motion.pointers[i].coords});
+ pointerMap.insert(Pointer{message.body.motion.pointers[i].properties,
+ message.body.motion.pointers[i].coords});
}
- return Sample{nanoseconds{message.body.motion.eventTime}, pointers};
+ return Sample{nanoseconds{message.body.motion.eventTime}, pointerMap};
}
bool LegacyResampler::pointerPropertiesResampleable(const Sample& target, const Sample& auxiliary) {
- if (target.pointers.size() > auxiliary.pointers.size()) {
- LOG_IF(INFO, debugResampling())
- << "Not resampled. Auxiliary sample has fewer pointers than target sample.";
- return false;
- }
- for (size_t i = 0; i < target.pointers.size(); ++i) {
- if (target.pointers[i].properties.id != auxiliary.pointers[i].properties.id) {
- LOG_IF(INFO, debugResampling()) << "Not resampled. Pointer ID mismatch.";
+ for (const Pointer& pointer : target.pointerMap) {
+ const std::optional<Pointer> auxiliaryPointer =
+ auxiliary.pointerMap.find(PointerMap::PointerId{pointer.properties.id});
+ if (!auxiliaryPointer.has_value()) {
+ LOG_IF(INFO, debugResampling())
+ << "Not resampled. Auxiliary sample does not contain all pointers from target.";
return false;
}
- if (target.pointers[i].properties.toolType != auxiliary.pointers[i].properties.toolType) {
+ if (pointer.properties.toolType != auxiliaryPointer->properties.toolType) {
LOG_IF(INFO, debugResampling()) << "Not resampled. Pointer ToolType mismatch.";
return false;
}
- if (!canResampleTool(target.pointers[i].properties.toolType)) {
+ if (!canResampleTool(pointer.properties.toolType)) {
LOG_IF(INFO, debugResampling())
<< "Not resampled. Cannot resample "
- << ftl::enum_string(target.pointers[i].properties.toolType) << " ToolType.";
+ << ftl::enum_string(pointer.properties.toolType) << " ToolType.";
return false;
}
}
@@ -173,28 +171,31 @@
}
std::optional<LegacyResampler::Sample> LegacyResampler::attemptInterpolation(
- nanoseconds resampleTime, const InputMessage& futureSample) const {
- if (!canInterpolate(futureSample)) {
+ nanoseconds resampleTime, const InputMessage& futureMessage) const {
+ if (!canInterpolate(futureMessage)) {
return std::nullopt;
}
LOG_IF(FATAL, mLatestSamples.empty())
<< "Not resampled. mLatestSamples must not be empty to interpolate.";
const Sample& pastSample = *(mLatestSamples.end() - 1);
+ const Sample& futureSample = messageToSample(futureMessage);
- const nanoseconds delta =
- nanoseconds{futureSample.body.motion.eventTime} - pastSample.eventTime;
+ const nanoseconds delta = nanoseconds{futureSample.eventTime} - pastSample.eventTime;
const float alpha =
std::chrono::duration<float, std::milli>(resampleTime - pastSample.eventTime) / delta;
- std::vector<Pointer> resampledPointers;
- for (size_t i = 0; i < pastSample.pointers.size(); ++i) {
- const PointerCoords& resampledCoords =
- calculateResampledCoords(pastSample.pointers[i].coords,
- futureSample.body.motion.pointers[i].coords, alpha);
- resampledPointers.push_back(Pointer{pastSample.pointers[i].properties, resampledCoords});
+ PointerMap resampledPointerMap;
+ for (const Pointer& pointer : pastSample.pointerMap) {
+ if (std::optional<Pointer> futureSamplePointer =
+ futureSample.pointerMap.find(PointerMap::PointerId{pointer.properties.id});
+ futureSamplePointer.has_value()) {
+ const PointerCoords& resampledCoords =
+ calculateResampledCoords(pointer.coords, futureSamplePointer->coords, alpha);
+ resampledPointerMap.insert(Pointer{pointer.properties, resampledCoords});
+ }
}
- return Sample{resampleTime, resampledPointers};
+ return Sample{resampleTime, resampledPointerMap};
}
bool LegacyResampler::canExtrapolate() const {
@@ -247,14 +248,17 @@
std::chrono::duration<float, std::milli>(newResampleTime - pastSample.eventTime) /
delta;
- std::vector<Pointer> resampledPointers;
- for (size_t i = 0; i < presentSample.pointers.size(); ++i) {
- const PointerCoords& resampledCoords =
- calculateResampledCoords(pastSample.pointers[i].coords,
- presentSample.pointers[i].coords, alpha);
- resampledPointers.push_back(Pointer{presentSample.pointers[i].properties, resampledCoords});
+ PointerMap resampledPointerMap;
+ for (const Pointer& pointer : presentSample.pointerMap) {
+ if (std::optional<Pointer> pastSamplePointer =
+ pastSample.pointerMap.find(PointerMap::PointerId{pointer.properties.id});
+ pastSamplePointer.has_value()) {
+ const PointerCoords& resampledCoords =
+ calculateResampledCoords(pastSamplePointer->coords, pointer.coords, alpha);
+ resampledPointerMap.insert(Pointer{pointer.properties, resampledCoords});
+ }
}
- return Sample{newResampleTime, resampledPointers};
+ return Sample{newResampleTime, resampledPointerMap};
}
inline void LegacyResampler::addSampleToMotionEvent(const Sample& sample,
@@ -267,6 +271,12 @@
return RESAMPLE_LATENCY;
}
+/**
+ * The resampler is unaware of ACTION_DOWN. Thus, it needs to constantly check for pointer IDs
+ * occurrences. This problem could be fixed if the resampler has access to the entire stream of
+ * MotionEvent actions. That way, both ACTION_DOWN and ACTION_UP will be visible; therefore,
+ * facilitating pointer tracking between samples.
+ */
void LegacyResampler::overwriteMotionEventSamples(MotionEvent& motionEvent) const {
const size_t numSamples = motionEvent.getHistorySize() + 1;
for (size_t sampleIndex = 0; sampleIndex < numSamples; ++sampleIndex) {
@@ -276,22 +286,35 @@
}
void LegacyResampler::overwriteStillPointers(MotionEvent& motionEvent, size_t sampleIndex) const {
+ if (!mLastRealSample.has_value() || !mPreviousPrediction.has_value()) {
+ LOG_IF(INFO, debugResampling()) << "Still pointers not overwritten. Not enough data.";
+ return;
+ }
for (size_t pointerIndex = 0; pointerIndex < motionEvent.getPointerCount(); ++pointerIndex) {
+ const std::optional<Pointer> lastRealPointer = mLastRealSample->pointerMap.find(
+ PointerMap::PointerId{motionEvent.getPointerId(pointerIndex)});
+ const std::optional<Pointer> previousPointer = mPreviousPrediction->pointerMap.find(
+ PointerMap::PointerId{motionEvent.getPointerId(pointerIndex)});
+ // This could happen because resampler only receives ACTION_MOVE events.
+ if (!lastRealPointer.has_value() || !previousPointer.has_value()) {
+ continue;
+ }
const PointerCoords& pointerCoords =
*(motionEvent.getHistoricalRawPointerCoords(pointerIndex, sampleIndex));
- if (equalXY(mLastRealSample->pointers[pointerIndex].coords, pointerCoords)) {
+ if (equalXY(pointerCoords, lastRealPointer->coords)) {
LOG_IF(INFO, debugResampling())
<< "Pointer ID: " << motionEvent.getPointerId(pointerIndex)
<< " did not move. Overwriting its coordinates from " << pointerCoords << " to "
- << mLastRealSample->pointers[pointerIndex].coords;
+ << previousPointer->coords;
setMotionEventPointerCoords(motionEvent, sampleIndex, pointerIndex,
- mPreviousPrediction->pointers[pointerIndex].coords);
+ previousPointer->coords);
}
}
}
void LegacyResampler::overwriteOldPointers(MotionEvent& motionEvent, size_t sampleIndex) const {
if (!mPreviousPrediction.has_value()) {
+ LOG_IF(INFO, debugResampling()) << "Old sample not overwritten. Not enough data.";
return;
}
if (nanoseconds{motionEvent.getHistoricalEventTime(sampleIndex)} <
@@ -302,8 +325,14 @@
<< mPreviousPrediction->eventTime.count() << "ns.";
for (size_t pointerIndex = 0; pointerIndex < motionEvent.getPointerCount();
++pointerIndex) {
+ const std::optional<Pointer> previousPointer = mPreviousPrediction->pointerMap.find(
+ PointerMap::PointerId{motionEvent.getPointerId(pointerIndex)});
+ // This could happen because resampler only receives ACTION_MOVE events.
+ if (!previousPointer.has_value()) {
+ continue;
+ }
setMotionEventPointerCoords(motionEvent, sampleIndex, pointerIndex,
- mPreviousPrediction->pointers[pointerIndex].coords);
+ previousPointer->coords);
}
}
}
@@ -333,6 +362,7 @@
mPreviousPrediction = sample;
}
}
+ LOG_IF(FATAL, mLatestSamples.empty()) << "mLatestSamples must contain at least one sample.";
mLastRealSample = *(mLatestSamples.end() - 1);
}
diff --git a/libs/input/tests/Resampler_test.cpp b/libs/input/tests/Resampler_test.cpp
index fae8518..3162b77 100644
--- a/libs/input/tests/Resampler_test.cpp
+++ b/libs/input/tests/Resampler_test.cpp
@@ -648,7 +648,15 @@
mResampler->resampleMotionEvent(16ms, motionEvent, &futureSample);
- assertMotionEventIsNotResampled(originalMotionEvent, motionEvent);
+ assertMotionEventIsResampledAndCoordsNear(originalMotionEvent, motionEvent,
+ {Pointer{.id = 0,
+ .x = 1.4f,
+ .y = 1.4f,
+ .isResampled = true},
+ Pointer{.id = 1,
+ .x = 2.4f,
+ .y = 2.4f,
+ .isResampled = true}});
}
TEST_F(ResamplerTest, MultiplePointerDifferentIdOrderExtrapolation) {
@@ -670,7 +678,15 @@
mResampler->resampleMotionEvent(16ms, secondMotionEvent, /*futureSample=*/nullptr);
- assertMotionEventIsNotResampled(secondOriginalMotionEvent, secondMotionEvent);
+ assertMotionEventIsResampledAndCoordsNear(secondOriginalMotionEvent, secondMotionEvent,
+ {Pointer{.id = 1,
+ .x = 4.4f,
+ .y = 4.4f,
+ .isResampled = true},
+ Pointer{.id = 0,
+ .x = 3.4f,
+ .y = 3.4f,
+ .isResampled = true}});
}
TEST_F(ResamplerTest, MultiplePointerDifferentIdsInterpolation) {