Merge "Reimplement Chromium's OneEuroFilter to InputConsumer" into main
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