Reimplement Chromium's OneEuroFilter to InputConsumer
Reimplemented Chromium's OneEuroFilter usage to InputConsumerNoResampling.
There are a few differences between Chromium's work and this CL. We
reimplemented One Euro filter an adaptive cutoff frequency low pass
made in this implementation as in the Chromium's implementation. The
class FilteredResampler filters the output of LegacyResampler using the
One Euro filter approach.
Here's the link to Chromium's to One Euro filter:
https://source.chromium.org/chromium/chromium/src/+/main:ui/base/prediction/one_euro_filter.h
Bug: 297226446
Flag: EXEMPT bugfix
Test: TEST=libinput_tests; m $TEST && $ANDROID_HOST_OUT/nativetest64/$TEST/$TEST
Change-Id: I0316cb1e81c73b1dc28dc809f55dee3a1cc0ebd2
diff --git a/include/input/CoordinateFilter.h b/include/input/CoordinateFilter.h
new file mode 100644
index 0000000..f36472d
--- /dev/null
+++ b/include/input/CoordinateFilter.h
@@ -0,0 +1,54 @@
+/**
+ * Copyright 2024 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#pragma once
+
+#include <chrono>
+
+#include <input/Input.h>
+#include <input/OneEuroFilter.h>
+
+namespace android {
+
+/**
+ * Pair of OneEuroFilters that independently filter X and Y coordinates. Both filters share the same
+ * constructor's parameters. The minimum cutoff frequency is the base cutoff frequency, that is, the
+ * resulting cutoff frequency in the absence of signal's speed. Likewise, beta is a scaling factor
+ * of the signal's speed that sets how much the signal's speed contributes to the resulting cutoff
+ * frequency. The adaptive cutoff frequency criterion is f_c = f_c_min + β|̇x_filtered|
+ */
+class CoordinateFilter {
+public:
+ explicit CoordinateFilter(float minCutoffFreq, float beta);
+
+ /**
+ * Filters in place only the AXIS_X and AXIS_Y fields from coords. Each call to filter must
+ * provide a timestamp strictly greater than the timestamp of the previous call. The first time
+ * this method is invoked no filtering takes place. Subsequent calls do overwrite `coords` with
+ * filtered data.
+ *
+ * @param timestamp The timestamps at which to filter. It must be greater than the one passed in
+ * the previous call.
+ * @param coords Coordinates to be overwritten by the corresponding filtered coordinates.
+ */
+ void filter(std::chrono::duration<float> timestamp, PointerCoords& coords);
+
+private:
+ OneEuroFilter mXFilter;
+ OneEuroFilter mYFilter;
+};
+
+} // namespace android
\ No newline at end of file
diff --git a/include/input/OneEuroFilter.h b/include/input/OneEuroFilter.h
new file mode 100644
index 0000000..a0168e4
--- /dev/null
+++ b/include/input/OneEuroFilter.h
@@ -0,0 +1,101 @@
+/**
+ * Copyright 2024 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#pragma once
+
+#include <chrono>
+#include <optional>
+
+#include <input/Input.h>
+
+namespace android {
+
+/**
+ * Low pass filter with adaptive low pass frequency based on the signal's speed. The signal's cutoff
+ * frequency is determined by f_c = f_c_min + β|̇x_filtered|. Refer to
+ * https://dl.acm.org/doi/10.1145/2207676.2208639 for details on how the filter works and how to
+ * tune it.
+ */
+class OneEuroFilter {
+public:
+ /**
+ * Default cutoff frequency of the filtered signal's speed. 1.0 Hz is the value in the filter's
+ * paper.
+ */
+ static constexpr float kDefaultSpeedCutoffFreq = 1.0;
+
+ OneEuroFilter() = delete;
+
+ explicit OneEuroFilter(float minCutoffFreq, float beta,
+ float speedCutoffFreq = kDefaultSpeedCutoffFreq);
+
+ OneEuroFilter(const OneEuroFilter&) = delete;
+ OneEuroFilter& operator=(const OneEuroFilter&) = delete;
+ OneEuroFilter(OneEuroFilter&&) = delete;
+ OneEuroFilter& operator=(OneEuroFilter&&) = delete;
+
+ /**
+ * Returns the filtered value of rawPosition. Each call to filter must provide a timestamp
+ * strictly greater than the timestamp of the previous call. The first time the method is
+ * called, it returns the value of rawPosition. Any subsequent calls provide a filtered value.
+ *
+ * @param timestamp The timestamp at which to filter. It must be strictly greater than the one
+ * provided in the previous call.
+ * @param rawPosition Position to be filtered.
+ */
+ float filter(std::chrono::duration<float> timestamp, float rawPosition);
+
+private:
+ /**
+ * Minimum cutoff frequency. This is the constant term in the adaptive cutoff frequency
+ * criterion. Units are Hertz.
+ */
+ const float mMinCutoffFreq;
+
+ /**
+ * Slope of the cutoff frequency criterion. This is the term scaling the absolute value of the
+ * filtered signal's speed. The data member is dimensionless, that is, it does not have units.
+ */
+ const float mBeta;
+
+ /**
+ * Cutoff frequency of the signal's speed. This is the cutoff frequency applied to the filtering
+ * of the signal's speed. Units are Hertz.
+ */
+ const float mSpeedCutoffFreq;
+
+ /**
+ * The timestamp from the previous call. Units are seconds.
+ */
+ std::optional<std::chrono::duration<float>> mPrevTimestamp;
+
+ /**
+ * The raw position from the previous call.
+ */
+ std::optional<float> mPrevRawPosition;
+
+ /**
+ * The filtered velocity from the previous call. Units are position per second.
+ */
+ std::optional<float> mPrevFilteredVelocity;
+
+ /**
+ * The filtered position from the previous call.
+ */
+ std::optional<float> mPrevFilteredPosition;
+};
+
+} // namespace android
diff --git a/include/input/Resampler.h b/include/input/Resampler.h
index 6d95ca7..1550977 100644
--- a/include/input/Resampler.h
+++ b/include/input/Resampler.h
@@ -19,11 +19,13 @@
#include <array>
#include <chrono>
#include <iterator>
+#include <map>
#include <optional>
#include <vector>
#include <android-base/logging.h>
#include <ftl/mixins.h>
+#include <input/CoordinateFilter.h>
#include <input/Input.h>
#include <input/InputTransport.h>
#include <input/RingBuffer.h>
@@ -293,4 +295,43 @@
inline static void addSampleToMotionEvent(const Sample& sample, MotionEvent& motionEvent);
};
+/**
+ * Resampler that first applies the LegacyResampler resampling algorithm, then independently filters
+ * the X and Y coordinates with a pair of One Euro filters.
+ */
+class FilteredLegacyResampler final : public Resampler {
+public:
+ /**
+ * Creates a resampler, using the given minCutoffFreq and beta to instantiate its One Euro
+ * filters.
+ */
+ explicit FilteredLegacyResampler(float minCutoffFreq, float beta);
+
+ void resampleMotionEvent(std::chrono::nanoseconds requestedFrameTime, MotionEvent& motionEvent,
+ const InputMessage* futureMessage) override;
+
+ std::chrono::nanoseconds getResampleLatency() const override;
+
+private:
+ LegacyResampler mResampler;
+
+ /**
+ * Minimum cutoff frequency of the value's low pass filter. Refer to OneEuroFilter class for a
+ * more detailed explanation.
+ */
+ const float mMinCutoffFreq;
+
+ /**
+ * Scaling factor of the adaptive cutoff frequency criterion. Refer to OneEuroFilter class for a
+ * more detailed explanation.
+ */
+ const float mBeta;
+
+ /*
+ * Note: an associative array with constant insertion and lookup times would be more efficient.
+ * When this was implemented, there was no container with these properties.
+ */
+ std::map<int32_t /*pointerId*/, CoordinateFilter> mFilteredPointers;
+};
+
} // namespace android
diff --git a/libs/input/Android.bp b/libs/input/Android.bp
index e4e81ad..a4ae54b 100644
--- a/libs/input/Android.bp
+++ b/libs/input/Android.bp
@@ -217,6 +217,7 @@
],
srcs: [
"AccelerationCurve.cpp",
+ "CoordinateFilter.cpp",
"Input.cpp",
"InputConsumer.cpp",
"InputConsumerNoResampling.cpp",
@@ -230,6 +231,7 @@
"KeyLayoutMap.cpp",
"MotionPredictor.cpp",
"MotionPredictorMetricsManager.cpp",
+ "OneEuroFilter.cpp",
"PrintTools.cpp",
"PropertyMap.cpp",
"Resampler.cpp",
diff --git a/libs/input/CoordinateFilter.cpp b/libs/input/CoordinateFilter.cpp
new file mode 100644
index 0000000..d231474
--- /dev/null
+++ b/libs/input/CoordinateFilter.cpp
@@ -0,0 +1,31 @@
+/**
+ * Copyright 2024 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#define LOG_TAG "CoordinateFilter"
+
+#include <input/CoordinateFilter.h>
+
+namespace android {
+
+CoordinateFilter::CoordinateFilter(float minCutoffFreq, float beta)
+ : mXFilter{minCutoffFreq, beta}, mYFilter{minCutoffFreq, beta} {}
+
+void CoordinateFilter::filter(std::chrono::duration<float> timestamp, PointerCoords& coords) {
+ coords.setAxisValue(AMOTION_EVENT_AXIS_X, mXFilter.filter(timestamp, coords.getX()));
+ coords.setAxisValue(AMOTION_EVENT_AXIS_Y, mYFilter.filter(timestamp, coords.getY()));
+}
+
+} // namespace android
diff --git a/libs/input/OneEuroFilter.cpp b/libs/input/OneEuroFilter.cpp
new file mode 100644
index 0000000..400d7c9
--- /dev/null
+++ b/libs/input/OneEuroFilter.cpp
@@ -0,0 +1,79 @@
+/**
+ * Copyright 2024 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#define LOG_TAG "OneEuroFilter"
+
+#include <chrono>
+#include <cmath>
+
+#include <android-base/logging.h>
+#include <input/CoordinateFilter.h>
+
+namespace android {
+namespace {
+
+inline float cutoffFreq(float minCutoffFreq, float beta, float filteredSpeed) {
+ return minCutoffFreq + beta * std::abs(filteredSpeed);
+}
+
+inline float smoothingFactor(std::chrono::duration<float> samplingPeriod, float cutoffFreq) {
+ return samplingPeriod.count() / (samplingPeriod.count() + (1.0 / (2.0 * M_PI * cutoffFreq)));
+}
+
+inline float lowPassFilter(float rawPosition, float prevFilteredPosition, float smoothingFactor) {
+ return smoothingFactor * rawPosition + (1 - smoothingFactor) * prevFilteredPosition;
+}
+
+} // namespace
+
+OneEuroFilter::OneEuroFilter(float minCutoffFreq, float beta, float speedCutoffFreq)
+ : mMinCutoffFreq{minCutoffFreq}, mBeta{beta}, mSpeedCutoffFreq{speedCutoffFreq} {}
+
+float OneEuroFilter::filter(std::chrono::duration<float> timestamp, float rawPosition) {
+ LOG_IF(FATAL, mPrevFilteredPosition.has_value() && (timestamp <= *mPrevTimestamp))
+ << "Timestamp must be greater than mPrevTimestamp";
+
+ const std::chrono::duration<float> samplingPeriod = (mPrevTimestamp.has_value())
+ ? (timestamp - *mPrevTimestamp)
+ : std::chrono::duration<float>{1.0};
+
+ const float rawVelocity = (mPrevFilteredPosition.has_value())
+ ? ((rawPosition - *mPrevFilteredPosition) / samplingPeriod.count())
+ : 0.0;
+
+ const float speedSmoothingFactor = smoothingFactor(samplingPeriod, mSpeedCutoffFreq);
+
+ const float filteredVelocity = (mPrevFilteredVelocity.has_value())
+ ? lowPassFilter(rawVelocity, *mPrevFilteredVelocity, speedSmoothingFactor)
+ : rawVelocity;
+
+ const float positionCutoffFreq = cutoffFreq(mMinCutoffFreq, mBeta, filteredVelocity);
+
+ const float positionSmoothingFactor = smoothingFactor(samplingPeriod, positionCutoffFreq);
+
+ const float filteredPosition = (mPrevFilteredPosition.has_value())
+ ? lowPassFilter(rawPosition, *mPrevFilteredPosition, positionSmoothingFactor)
+ : rawPosition;
+
+ mPrevTimestamp = timestamp;
+ mPrevRawPosition = rawPosition;
+ mPrevFilteredVelocity = filteredVelocity;
+ mPrevFilteredPosition = filteredPosition;
+
+ return filteredPosition;
+}
+
+} // namespace android
diff --git a/libs/input/Resampler.cpp b/libs/input/Resampler.cpp
index 056db09..3ab132d 100644
--- a/libs/input/Resampler.cpp
+++ b/libs/input/Resampler.cpp
@@ -389,4 +389,34 @@
mLastRealSample = *(mLatestSamples.end() - 1);
}
+// --- FilteredLegacyResampler ---
+
+FilteredLegacyResampler::FilteredLegacyResampler(float minCutoffFreq, float beta)
+ : mResampler{}, mMinCutoffFreq{minCutoffFreq}, mBeta{beta} {}
+
+void FilteredLegacyResampler::resampleMotionEvent(std::chrono::nanoseconds requestedFrameTime,
+ MotionEvent& motionEvent,
+ const InputMessage* futureSample) {
+ mResampler.resampleMotionEvent(requestedFrameTime, motionEvent, futureSample);
+ const size_t numSamples = motionEvent.getHistorySize() + 1;
+ for (size_t sampleIndex = 0; sampleIndex < numSamples; ++sampleIndex) {
+ for (size_t pointerIndex = 0; pointerIndex < motionEvent.getPointerCount();
+ ++pointerIndex) {
+ const int32_t pointerId = motionEvent.getPointerProperties(pointerIndex)->id;
+ const nanoseconds eventTime =
+ nanoseconds{motionEvent.getHistoricalEventTime(sampleIndex)};
+ // Refer to the static function `setMotionEventPointerCoords` for a justification of
+ // casting away const.
+ PointerCoords& pointerCoords = const_cast<PointerCoords&>(
+ *(motionEvent.getHistoricalRawPointerCoords(pointerIndex, sampleIndex)));
+ const auto& [iter, _] = mFilteredPointers.try_emplace(pointerId, mMinCutoffFreq, mBeta);
+ iter->second.filter(eventTime, pointerCoords);
+ }
+ }
+}
+
+std::chrono::nanoseconds FilteredLegacyResampler::getResampleLatency() const {
+ return mResampler.getResampleLatency();
+}
+
} // namespace android
diff --git a/libs/input/tests/Android.bp b/libs/input/tests/Android.bp
index 661c9f7..46e8190 100644
--- a/libs/input/tests/Android.bp
+++ b/libs/input/tests/Android.bp
@@ -25,6 +25,7 @@
"InputVerifier_test.cpp",
"MotionPredictor_test.cpp",
"MotionPredictorMetricsManager_test.cpp",
+ "OneEuroFilter_test.cpp",
"Resampler_test.cpp",
"RingBuffer_test.cpp",
"TestInputChannel.cpp",
diff --git a/libs/input/tests/OneEuroFilter_test.cpp b/libs/input/tests/OneEuroFilter_test.cpp
new file mode 100644
index 0000000..270e789
--- /dev/null
+++ b/libs/input/tests/OneEuroFilter_test.cpp
@@ -0,0 +1,134 @@
+/**
+ * Copyright 2024 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <input/OneEuroFilter.h>
+
+#include <algorithm>
+#include <chrono>
+#include <cmath>
+#include <numeric>
+#include <vector>
+
+#include <gtest/gtest.h>
+
+#include <input/Input.h>
+
+namespace android {
+namespace {
+
+using namespace std::literals::chrono_literals;
+using std::chrono::duration;
+
+struct Sample {
+ duration<double> timestamp{};
+ double value{};
+
+ friend bool operator<(const Sample& lhs, const Sample& rhs) { return lhs.value < rhs.value; }
+};
+
+/**
+ * Generates a sinusoidal signal with the passed frequency and amplitude.
+ */
+std::vector<Sample> generateSinusoidalSignal(duration<double> signalDuration,
+ double samplingFrequency, double signalFrequency,
+ double amplitude) {
+ std::vector<Sample> signal;
+ const duration<double> samplingPeriod{1.0 / samplingFrequency};
+ for (duration<double> timestamp{0.0}; timestamp < signalDuration; timestamp += samplingPeriod) {
+ signal.push_back(
+ Sample{timestamp,
+ amplitude * std::sin(2.0 * M_PI * signalFrequency * timestamp.count())});
+ }
+ return signal;
+}
+
+double meanAbsoluteError(const std::vector<Sample>& filteredSignal,
+ const std::vector<Sample>& signal) {
+ if (filteredSignal.size() != signal.size()) {
+ ADD_FAILURE() << "filteredSignal and signal do not have equal number of samples";
+ return std::numeric_limits<double>::max();
+ }
+ std::vector<double> absoluteError;
+ for (size_t sampleIndex = 0; sampleIndex < signal.size(); ++sampleIndex) {
+ absoluteError.push_back(
+ std::abs(filteredSignal[sampleIndex].value - signal[sampleIndex].value));
+ }
+ if (absoluteError.empty()) {
+ ADD_FAILURE() << "Zero division. absoluteError is empty";
+ return std::numeric_limits<double>::max();
+ }
+ return std::accumulate(absoluteError.begin(), absoluteError.end(), 0.0) / absoluteError.size();
+}
+
+double maxAbsoluteAmplitude(const std::vector<Sample>& signal) {
+ if (signal.empty()) {
+ ADD_FAILURE() << "Max absolute value amplitude does not exist. Signal is empty";
+ return std::numeric_limits<double>::max();
+ }
+ std::vector<Sample> absoluteSignal;
+ for (const Sample& sample : signal) {
+ absoluteSignal.push_back(Sample{sample.timestamp, std::abs(sample.value)});
+ }
+ return std::max_element(absoluteSignal.begin(), absoluteSignal.end())->value;
+}
+
+} // namespace
+
+class OneEuroFilterTest : public ::testing::Test {
+protected:
+ // The constructor's parameters are the ones that Chromium's using. The tuning was based on a 60
+ // Hz sampling frequency. Refer to their one_euro_filter.h header for additional information
+ // about these parameters.
+ OneEuroFilterTest() : mFilter{/*minCutoffFreq=*/4.7, /*beta=*/0.01} {}
+
+ std::vector<Sample> filterSignal(const std::vector<Sample>& signal) {
+ std::vector<Sample> filteredSignal;
+ for (const Sample& sample : signal) {
+ filteredSignal.push_back(
+ Sample{sample.timestamp, mFilter.filter(sample.timestamp, sample.value)});
+ }
+ return filteredSignal;
+ }
+
+ OneEuroFilter mFilter;
+};
+
+TEST_F(OneEuroFilterTest, PassLowFrequencySignal) {
+ const std::vector<Sample> signal =
+ generateSinusoidalSignal(1s, /*samplingFrequency=*/60, /*signalFrequency=*/1,
+ /*amplitude=*/1);
+
+ const std::vector<Sample> filteredSignal = filterSignal(signal);
+
+ // The reason behind using the mean absolute error as a metric is that, ideally, a low frequency
+ // filtered signal is expected to be almost identical to the raw one. Therefore, the error
+ // between them should be minimal. The constant is heuristically chosen.
+ EXPECT_LT(meanAbsoluteError(filteredSignal, signal), 0.25);
+}
+
+TEST_F(OneEuroFilterTest, RejectHighFrequencySignal) {
+ const std::vector<Sample> signal =
+ generateSinusoidalSignal(1s, /*samplingFrequency=*/60, /*signalFrequency=*/22.5,
+ /*amplitude=*/1);
+
+ const std::vector<Sample> filteredSignal = filterSignal(signal);
+
+ // The filtered signal should consist of values that are much closer to zero. The comparison
+ // constant is heuristically chosen.
+ EXPECT_LT(maxAbsoluteAmplitude(filteredSignal), 0.25);
+}
+
+} // namespace android