include/input/VelocityTracker.h - platform/frameworks/native - Git at Google

 /*
  * Copyright (C) 2012 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 <android/os/IInputConstants.h>
 #include <input/Input.h>
 #include <input/RingBuffer.h>
 #include <utils/BitSet.h>
 #include <utils/Timers.h>
 #include <map>
 #include <set>

 namespace android {

 class VelocityTrackerStrategy;

 /*
  * Calculates the velocity of pointer movements over time.
  */
 class VelocityTracker {
 public:
     static const size_t MAX_DEGREE = 4;

     enum class Strategy : int32_t {
         DEFAULT = android::os::IInputConstants::VELOCITY_TRACKER_STRATEGY_DEFAULT,
         IMPULSE = android::os::IInputConstants::VELOCITY_TRACKER_STRATEGY_IMPULSE,
         LSQ1 = android::os::IInputConstants::VELOCITY_TRACKER_STRATEGY_LSQ1,
         LSQ2 = android::os::IInputConstants::VELOCITY_TRACKER_STRATEGY_LSQ2,
         LSQ3 = android::os::IInputConstants::VELOCITY_TRACKER_STRATEGY_LSQ3,
         WLSQ2_DELTA = android::os::IInputConstants::VELOCITY_TRACKER_STRATEGY_WLSQ2_DELTA,
         WLSQ2_CENTRAL = android::os::IInputConstants::VELOCITY_TRACKER_STRATEGY_WLSQ2_CENTRAL,
         WLSQ2_RECENT = android::os::IInputConstants::VELOCITY_TRACKER_STRATEGY_WLSQ2_RECENT,
         INT1 = android::os::IInputConstants::VELOCITY_TRACKER_STRATEGY_INT1,
         INT2 = android::os::IInputConstants::VELOCITY_TRACKER_STRATEGY_INT2,
         LEGACY = android::os::IInputConstants::VELOCITY_TRACKER_STRATEGY_LEGACY,
         MIN = IMPULSE,
         MAX = LEGACY,
         ftl_last = LEGACY,
     };

     /*
      * Contains all available velocity data from a VelocityTracker.
      */
     struct ComputedVelocity {
         inline std::optional<float> getVelocity(int32_t axis, int32_t id) const {
             const auto& axisVelocities = mVelocities.find(axis);
             if (axisVelocities == mVelocities.end()) {
                 return {};
             }

             const auto& axisIdVelocity = axisVelocities->second.find(id);
             if (axisIdVelocity == axisVelocities->second.end()) {
                 return {};
             }

             return axisIdVelocity->second;
         }

         inline void addVelocity(int32_t axis, int32_t id, float velocity) {
             mVelocities[axis][id] = velocity;
         }

     private:
         std::map<int32_t /*axis*/, std::map<int32_t /*pointerId*/, float /*velocity*/>> mVelocities;
     };

     // Creates a velocity tracker using the specified strategy for each supported axis.
     // If strategy is not provided, uses the default strategy for the platform.
     // TODO(b/32830165): support axis-specific strategies.
     VelocityTracker(const Strategy strategy = Strategy::DEFAULT);

     /** Return true if the axis is supported for velocity tracking, false otherwise. */
     static bool isAxisSupported(int32_t axis);

     // Resets the velocity tracker state.
     void clear();

     // Resets the velocity tracker state for a specific pointer.
     // Call this method when some pointers have changed and may be reusing
     // an id that was assigned to a different pointer earlier.
     void clearPointer(int32_t pointerId);

     // Adds movement information for a pointer for a specific axis
     void addMovement(nsecs_t eventTime, int32_t pointerId, int32_t axis, float position);

     // Adds movement information for all pointers in a MotionEvent, including historical samples.
     void addMovement(const MotionEvent& event);

     // Returns the velocity of the specified pointer id and axis in position units per second.
     // Returns empty optional if there is insufficient movement information for the pointer, or if
     // the given axis is not supported for velocity tracking.
     std::optional<float> getVelocity(int32_t axis, int32_t pointerId) const;

     // Returns a ComputedVelocity instance with all available velocity data, using the given units
     // (reference: units == 1 means "per millisecond"), and clamping each velocity between
     // [-maxVelocity, maxVelocity], inclusive.
     ComputedVelocity getComputedVelocity(int32_t units, float maxVelocity);

     // Gets the active pointer id, or -1 if none.
     inline int32_t getActivePointerId() const { return mActivePointerId.value_or(-1); }

 private:
     nsecs_t mLastEventTime;
     BitSet32 mCurrentPointerIdBits;
     std::optional<int32_t> mActivePointerId;

     // An override strategy passed in the constructor to be used for all axes.
     // This strategy will apply to all axes, unless the default strategy is specified here.
     // When default strategy is specified, then each axis will use a potentially different strategy
     // based on a hardcoded mapping.
     const Strategy mOverrideStrategy;
     // Maps axes to their respective VelocityTrackerStrategy instances.
     // Note that, only axes that have had MotionEvents (and not all supported axes) will be here.
     std::map<int32_t /*axis*/, std::unique_ptr<VelocityTrackerStrategy>> mConfiguredStrategies;

     void configureStrategy(int32_t axis);

     // Generates a VelocityTrackerStrategy instance for the given Strategy type.
     // The `deltaValues` parameter indicates whether or not the created strategy should treat motion
     // values as deltas (and not as absolute values). This the parameter is applicable only for
     // strategies that support differential axes.
     static std::unique_ptr<VelocityTrackerStrategy> createStrategy(const Strategy strategy,
                                                                    bool deltaValues);
 };


 /*
  * Implements a particular velocity tracker algorithm.
  */
 class VelocityTrackerStrategy {
 protected:
     VelocityTrackerStrategy() { }

 public:
     virtual ~VelocityTrackerStrategy() { }

     virtual void clearPointer(int32_t pointerId) = 0;
     virtual void addMovement(nsecs_t eventTime, int32_t pointerId, float position) = 0;
     virtual std::optional<float> getVelocity(int32_t pointerId) const = 0;
 };

 /**
  * A `VelocityTrackerStrategy` that accumulates added data points and processes the accumulated data
  * points when getting velocity.
  */
 class AccumulatingVelocityTrackerStrategy : public VelocityTrackerStrategy {
 public:
     AccumulatingVelocityTrackerStrategy(nsecs_t horizonNanos, bool maintainHorizonDuringAdd);

     void addMovement(nsecs_t eventTime, int32_t pointerId, float position) override;
     void clearPointer(int32_t pointerId) override;

 protected:
     struct Movement {
         nsecs_t eventTime;
         float position;
     };

     // Number of samples to keep.
     // If different strategies would like to maintain different history size, we can make this a
     // protected const field.
     static constexpr uint32_t HISTORY_SIZE = 20;

     /**
      * Duration, in nanoseconds, since the latest movement where a movement may be considered for
      * velocity calculation.
      */
     const nsecs_t mHorizonNanos;
     /**
      * If true, data points outside of horizon (see `mHorizonNanos`) will be cleared after each
      * addition of a new movement.
      */
     const bool mMaintainHorizonDuringAdd;
     std::map<int32_t /*pointerId*/, RingBuffer<Movement>> mMovements;
 };

 /*
  * Velocity tracker algorithm based on least-squares linear regression.
  */
 class LeastSquaresVelocityTrackerStrategy : public AccumulatingVelocityTrackerStrategy {
 public:
     enum class Weighting {
         // No weights applied.  All data points are equally reliable.
         NONE,

         // Weight by time delta.  Data points clustered together are weighted less.
         DELTA,

         // Weight such that points within a certain horizon are weighed more than those
         // outside of that horizon.
         CENTRAL,

         // Weight such that points older than a certain amount are weighed less.
         RECENT,
     };

     // Degree must be no greater than VelocityTracker::MAX_DEGREE.
     LeastSquaresVelocityTrackerStrategy(uint32_t degree, Weighting weighting = Weighting::NONE);
     ~LeastSquaresVelocityTrackerStrategy() override;

     std::optional<float> getVelocity(int32_t pointerId) const override;

 private:
     // Sample horizon.
     // We don't use too much history by default since we want to react to quick
     // changes in direction.
     static const nsecs_t HORIZON = 100 * 1000000; // 100 ms

     float chooseWeight(int32_t pointerId, uint32_t index) const;
     /**
      * An optimized least-squares solver for degree 2 and no weight (i.e. `Weighting.NONE`).
      * The provided container of movements shall NOT be empty, and shall have the movements in
      * chronological order.
      */
     std::optional<float> solveUnweightedLeastSquaresDeg2(
             const RingBuffer<Movement>& movements) const;

     const uint32_t mDegree;
     const Weighting mWeighting;
 };

 /*
  * Velocity tracker algorithm that uses an IIR filter.
  */
 class IntegratingVelocityTrackerStrategy : public VelocityTrackerStrategy {
 public:
     // Degree must be 1 or 2.
     IntegratingVelocityTrackerStrategy(uint32_t degree);
     ~IntegratingVelocityTrackerStrategy() override;

     void clearPointer(int32_t pointerId) override;
     void addMovement(nsecs_t eventTime, int32_t pointerId, float positions) override;
     std::optional<float> getVelocity(int32_t pointerId) const override;

 private:
     // Current state estimate for a particular pointer.
     struct State {
         nsecs_t updateTime;
         uint32_t degree;

         float pos, vel, accel;
     };

     const uint32_t mDegree;
     BitSet32 mPointerIdBits;
     State mPointerState[MAX_POINTER_ID + 1];

     void initState(State& state, nsecs_t eventTime, float pos) const;
     void updateState(State& state, nsecs_t eventTime, float pos) const;
 };


 /*
  * Velocity tracker strategy used prior to ICS.
  */
 class LegacyVelocityTrackerStrategy : public AccumulatingVelocityTrackerStrategy {
 public:
     LegacyVelocityTrackerStrategy();
     ~LegacyVelocityTrackerStrategy() override;

     std::optional<float> getVelocity(int32_t pointerId) const override;

 private:
     // Oldest sample to consider when calculating the velocity.
     static const nsecs_t HORIZON = 200 * 1000000; // 100 ms

     // The minimum duration between samples when estimating velocity.
     static const nsecs_t MIN_DURATION = 10 * 1000000; // 10 ms
 };

 class ImpulseVelocityTrackerStrategy : public AccumulatingVelocityTrackerStrategy {
 public:
     ImpulseVelocityTrackerStrategy(bool deltaValues);
     ~ImpulseVelocityTrackerStrategy() override;

     std::optional<float> getVelocity(int32_t pointerId) const override;

 private:
     // Sample horizon.
     // We don't use too much history by default since we want to react to quick
     // changes in direction.
     static constexpr nsecs_t HORIZON = 100 * 1000000; // 100 ms

     // Whether or not the input movement values for the strategy come in the form of delta values.
     // If the input values are not deltas, the strategy needs to calculate deltas as part of its
     // velocity calculation.
     const bool mDeltaValues;
 };

 } // namespace android
	/*
	* Copyright (C) 2012 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 <android/os/IInputConstants.h>
	#include <input/Input.h>
	#include <input/RingBuffer.h>
	#include <utils/BitSet.h>
	#include <utils/Timers.h>
	#include <map>
	#include <set>

	namespace android {

	class VelocityTrackerStrategy;

	/*
	* Calculates the velocity of pointer movements over time.
	*/
	class VelocityTracker {
	public:
	static const size_t MAX_DEGREE = 4;

	enum class Strategy : int32_t {
	DEFAULT = android::os::IInputConstants::VELOCITY_TRACKER_STRATEGY_DEFAULT,
	IMPULSE = android::os::IInputConstants::VELOCITY_TRACKER_STRATEGY_IMPULSE,
	LSQ1 = android::os::IInputConstants::VELOCITY_TRACKER_STRATEGY_LSQ1,
	LSQ2 = android::os::IInputConstants::VELOCITY_TRACKER_STRATEGY_LSQ2,
	LSQ3 = android::os::IInputConstants::VELOCITY_TRACKER_STRATEGY_LSQ3,
	WLSQ2_DELTA = android::os::IInputConstants::VELOCITY_TRACKER_STRATEGY_WLSQ2_DELTA,
	WLSQ2_CENTRAL = android::os::IInputConstants::VELOCITY_TRACKER_STRATEGY_WLSQ2_CENTRAL,
	WLSQ2_RECENT = android::os::IInputConstants::VELOCITY_TRACKER_STRATEGY_WLSQ2_RECENT,
	INT1 = android::os::IInputConstants::VELOCITY_TRACKER_STRATEGY_INT1,
	INT2 = android::os::IInputConstants::VELOCITY_TRACKER_STRATEGY_INT2,
	LEGACY = android::os::IInputConstants::VELOCITY_TRACKER_STRATEGY_LEGACY,
	MIN = IMPULSE,
	MAX = LEGACY,
	ftl_last = LEGACY,
	};

	/*
	* Contains all available velocity data from a VelocityTracker.
	*/
	struct ComputedVelocity {
	inline std::optional<float> getVelocity(int32_t axis, int32_t id) const {
	const auto& axisVelocities = mVelocities.find(axis);
	if (axisVelocities == mVelocities.end()) {
	return {};
	}

	const auto& axisIdVelocity = axisVelocities->second.find(id);
	if (axisIdVelocity == axisVelocities->second.end()) {
	return {};
	}

	return axisIdVelocity->second;
	}

	inline void addVelocity(int32_t axis, int32_t id, float velocity) {
	mVelocities[axis][id] = velocity;
	}

	private:
	std::map<int32_t /axis/, std::map<int32_t /pointerId/, float /velocity/>> mVelocities;
	};

	// Creates a velocity tracker using the specified strategy for each supported axis.
	// If strategy is not provided, uses the default strategy for the platform.
	// TODO(b/32830165): support axis-specific strategies.
	VelocityTracker(const Strategy strategy = Strategy::DEFAULT);

	/** Return true if the axis is supported for velocity tracking, false otherwise. */
	static bool isAxisSupported(int32_t axis);

	// Resets the velocity tracker state.
	void clear();

	// Resets the velocity tracker state for a specific pointer.
	// Call this method when some pointers have changed and may be reusing
	// an id that was assigned to a different pointer earlier.
	void clearPointer(int32_t pointerId);

	// Adds movement information for a pointer for a specific axis
	void addMovement(nsecs_t eventTime, int32_t pointerId, int32_t axis, float position);

	// Adds movement information for all pointers in a MotionEvent, including historical samples.
	void addMovement(const MotionEvent& event);

	// Returns the velocity of the specified pointer id and axis in position units per second.
	// Returns empty optional if there is insufficient movement information for the pointer, or if
	// the given axis is not supported for velocity tracking.
	std::optional<float> getVelocity(int32_t axis, int32_t pointerId) const;

	// Returns a ComputedVelocity instance with all available velocity data, using the given units
	// (reference: units == 1 means "per millisecond"), and clamping each velocity between
	// [-maxVelocity, maxVelocity], inclusive.
	ComputedVelocity getComputedVelocity(int32_t units, float maxVelocity);

	// Gets the active pointer id, or -1 if none.
	inline int32_t getActivePointerId() const { return mActivePointerId.value_or(-1); }

	private:
	nsecs_t mLastEventTime;
	BitSet32 mCurrentPointerIdBits;
	std::optional<int32_t> mActivePointerId;

	// An override strategy passed in the constructor to be used for all axes.
	// This strategy will apply to all axes, unless the default strategy is specified here.
	// When default strategy is specified, then each axis will use a potentially different strategy
	// based on a hardcoded mapping.
	const Strategy mOverrideStrategy;
	// Maps axes to their respective VelocityTrackerStrategy instances.
	// Note that, only axes that have had MotionEvents (and not all supported axes) will be here.
	std::map<int32_t /axis/, std::unique_ptr<VelocityTrackerStrategy>> mConfiguredStrategies;

	void configureStrategy(int32_t axis);

	// Generates a VelocityTrackerStrategy instance for the given Strategy type.
	// The `deltaValues` parameter indicates whether or not the created strategy should treat motion
	// values as deltas (and not as absolute values). This the parameter is applicable only for
	// strategies that support differential axes.
	static std::unique_ptr<VelocityTrackerStrategy> createStrategy(const Strategy strategy,
	bool deltaValues);
	};


	/*
	* Implements a particular velocity tracker algorithm.
	*/
	class VelocityTrackerStrategy {
	protected:
	VelocityTrackerStrategy() { }

	public:
	virtual ~VelocityTrackerStrategy() { }

	virtual void clearPointer(int32_t pointerId) = 0;
	virtual void addMovement(nsecs_t eventTime, int32_t pointerId, float position) = 0;
	virtual std::optional<float> getVelocity(int32_t pointerId) const = 0;
	};

	/**
	* A `VelocityTrackerStrategy` that accumulates added data points and processes the accumulated data
	* points when getting velocity.
	*/
	class AccumulatingVelocityTrackerStrategy : public VelocityTrackerStrategy {
	public:
	AccumulatingVelocityTrackerStrategy(nsecs_t horizonNanos, bool maintainHorizonDuringAdd);

	void addMovement(nsecs_t eventTime, int32_t pointerId, float position) override;
	void clearPointer(int32_t pointerId) override;

	protected:
	struct Movement {
	nsecs_t eventTime;
	float position;
	};

	// Number of samples to keep.
	// If different strategies would like to maintain different history size, we can make this a
	// protected const field.
	static constexpr uint32_t HISTORY_SIZE = 20;

	/**
	* Duration, in nanoseconds, since the latest movement where a movement may be considered for
	* velocity calculation.
	*/
	const nsecs_t mHorizonNanos;
	/**
	* If true, data points outside of horizon (see `mHorizonNanos`) will be cleared after each
	* addition of a new movement.
	*/
	const bool mMaintainHorizonDuringAdd;
	std::map<int32_t /pointerId/, RingBuffer<Movement>> mMovements;
	};

	/*
	* Velocity tracker algorithm based on least-squares linear regression.
	*/
	class LeastSquaresVelocityTrackerStrategy : public AccumulatingVelocityTrackerStrategy {
	public:
	enum class Weighting {
	// No weights applied. All data points are equally reliable.
	NONE,

	// Weight by time delta. Data points clustered together are weighted less.
	DELTA,

	// Weight such that points within a certain horizon are weighed more than those
	// outside of that horizon.
	CENTRAL,

	// Weight such that points older than a certain amount are weighed less.
	RECENT,
	};

	// Degree must be no greater than VelocityTracker::MAX_DEGREE.
	LeastSquaresVelocityTrackerStrategy(uint32_t degree, Weighting weighting = Weighting::NONE);
	~LeastSquaresVelocityTrackerStrategy() override;

	std::optional<float> getVelocity(int32_t pointerId) const override;

	private:
	// Sample horizon.
	// We don't use too much history by default since we want to react to quick
	// changes in direction.
	static const nsecs_t HORIZON = 100 * 1000000; // 100 ms

	float chooseWeight(int32_t pointerId, uint32_t index) const;
	/**
	* An optimized least-squares solver for degree 2 and no weight (i.e. `Weighting.NONE`).
	* The provided container of movements shall NOT be empty, and shall have the movements in
	* chronological order.
	*/
	std::optional<float> solveUnweightedLeastSquaresDeg2(
	const RingBuffer<Movement>& movements) const;

	const uint32_t mDegree;
	const Weighting mWeighting;
	};

	/*
	* Velocity tracker algorithm that uses an IIR filter.
	*/
	class IntegratingVelocityTrackerStrategy : public VelocityTrackerStrategy {
	public:
	// Degree must be 1 or 2.
	IntegratingVelocityTrackerStrategy(uint32_t degree);
	~IntegratingVelocityTrackerStrategy() override;

	void clearPointer(int32_t pointerId) override;
	void addMovement(nsecs_t eventTime, int32_t pointerId, float positions) override;
	std::optional<float> getVelocity(int32_t pointerId) const override;

	private:
	// Current state estimate for a particular pointer.
	struct State {
	nsecs_t updateTime;
	uint32_t degree;

	float pos, vel, accel;
	};

	const uint32_t mDegree;
	BitSet32 mPointerIdBits;
	State mPointerState[MAX_POINTER_ID + 1];

	void initState(State& state, nsecs_t eventTime, float pos) const;
	void updateState(State& state, nsecs_t eventTime, float pos) const;
	};


	/*
	* Velocity tracker strategy used prior to ICS.
	*/
	class LegacyVelocityTrackerStrategy : public AccumulatingVelocityTrackerStrategy {
	public:
	LegacyVelocityTrackerStrategy();
	~LegacyVelocityTrackerStrategy() override;

	std::optional<float> getVelocity(int32_t pointerId) const override;

	private:
	// Oldest sample to consider when calculating the velocity.
	static const nsecs_t HORIZON = 200 * 1000000; // 100 ms

	// The minimum duration between samples when estimating velocity.
	static const nsecs_t MIN_DURATION = 10 * 1000000; // 10 ms
	};

	class ImpulseVelocityTrackerStrategy : public AccumulatingVelocityTrackerStrategy {
	public:
	ImpulseVelocityTrackerStrategy(bool deltaValues);
	~ImpulseVelocityTrackerStrategy() override;

	std::optional<float> getVelocity(int32_t pointerId) const override;

	private:
	// Sample horizon.
	// We don't use too much history by default since we want to react to quick
	// changes in direction.
	static constexpr nsecs_t HORIZON = 100 * 1000000; // 100 ms

	// Whether or not the input movement values for the strategy come in the form of delta values.
	// If the input values are not deltas, the strategy needs to calculate deltas as part of its
	// velocity calculation.
	const bool mDeltaValues;
	};

	} // namespace android