include/input/VelocityTracker.h

/*
 * 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.
 */

#ifndef _LIBINPUT_VELOCITY_TRACKER_H
#define _LIBINPUT_VELOCITY_TRACKER_H

#include <input/Input.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:
    enum class Strategy : int32_t {
        DEFAULT = -1,
        MIN = 0,
        IMPULSE = 0,
        LSQ1 = 1,
        LSQ2 = 2,
        LSQ3 = 3,
        WLSQ2_DELTA = 4,
        WLSQ2_CENTRAL = 5,
        WLSQ2_RECENT = 6,
        INT1 = 7,
        INT2 = 8,
        LEGACY = 9,
        MAX = LEGACY,
    };

    struct Estimator {
        static const size_t MAX_DEGREE = 4;

        // Estimator time base.
        nsecs_t time;

        // Polynomial coefficients describing motion.
        float coeff[MAX_DEGREE + 1];

        // Polynomial degree (number of coefficients), or zero if no information is
        // available.
        uint32_t degree;

        // Confidence (coefficient of determination), between 0 (no fit) and 1 (perfect fit).
        float confidence;

        inline void clear() {
            time = 0;
            degree = 0;
            confidence = 0;
            for (size_t i = 0; i <= MAX_DEGREE; i++) {
                coeff[i] = 0;
            }
        }
    };

    /*
     * Contains all available velocity data from a VelocityTracker.
     */
    struct ComputedVelocity {
        inline std::optional<float> getVelocity(int32_t axis, uint32_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, uint32_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);

    ~VelocityTracker();

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

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

    // Adds movement information for a set of pointers.
    // The idBits bitfield specifies the pointer ids of the pointers whose data points
    // are included in the movement.
    // The positions map contains a mapping of an axis to positions array.
    // The positions arrays contain information for each pointer in order by increasing id.
    // Each array's size should be equal to the number of one bits in idBits.
    void addMovement(nsecs_t eventTime, BitSet32 idBits,
                     const std::map<int32_t, std::vector<float>>& positions);

    // 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, uint32_t id) 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 an estimator for the recent movements of the specified pointer id for the given axis.
    // Returns false and clears the estimator if there is no information available
    // about the pointer.
    bool getEstimator(int32_t axis, uint32_t id, Estimator* outEstimator) const;

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

private:
    // All axes supported for velocity tracking, mapped to their default strategies.
    // Although other strategies are available for testing and comparison purposes,
    // the default strategy is the one that applications will actually use.  Be very careful
    // when adjusting the default strategy because it can dramatically affect
    // (often in a bad way) the user experience.
    static const std::map<int32_t, Strategy> DEFAULT_STRATEGY_BY_AXIS;

    // Axes specifying location on a 2D plane (i.e. X and Y).
    static const std::set<int32_t> PLANAR_AXES;

    nsecs_t mLastEventTime;
    BitSet32 mCurrentPointerIdBits;
    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);

    static std::unique_ptr<VelocityTrackerStrategy> createStrategy(const Strategy strategy);
};


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

public:
    virtual ~VelocityTrackerStrategy() { }

    virtual void clearPointers(BitSet32 idBits) = 0;
    virtual void addMovement(nsecs_t eventTime, BitSet32 idBits,
                             const std::vector<float>& positions) = 0;
    virtual bool getEstimator(uint32_t id, VelocityTracker::Estimator* outEstimator) const = 0;
};


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

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

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

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

    // Degree must be no greater than Estimator::MAX_DEGREE.
    LeastSquaresVelocityTrackerStrategy(uint32_t degree, Weighting weighting = WEIGHTING_NONE);
    virtual ~LeastSquaresVelocityTrackerStrategy();

    virtual void clearPointers(BitSet32 idBits);
    void addMovement(nsecs_t eventTime, BitSet32 idBits,
                     const std::vector<float>& positions) override;
    virtual bool getEstimator(uint32_t id, VelocityTracker::Estimator* outEstimator) const;

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

    // Number of samples to keep.
    static const uint32_t HISTORY_SIZE = 20;

    struct Movement {
        nsecs_t eventTime;
        BitSet32 idBits;
        float positions[MAX_POINTERS];

        inline float getPosition(uint32_t id) const { return positions[idBits.getIndexOfBit(id)]; }
    };

    float chooseWeight(uint32_t index) const;

    const uint32_t mDegree;
    const Weighting mWeighting;
    uint32_t mIndex;
    Movement mMovements[HISTORY_SIZE];
};


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

    virtual void clearPointers(BitSet32 idBits);
    void addMovement(nsecs_t eventTime, BitSet32 idBits,
                     const std::vector<float>& positions) override;
    virtual bool getEstimator(uint32_t id, VelocityTracker::Estimator* outEstimator) const;

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;
    void populateEstimator(const State& state, VelocityTracker::Estimator* outEstimator) const;
};


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

    virtual void clearPointers(BitSet32 idBits);
    void addMovement(nsecs_t eventTime, BitSet32 idBits,
                     const std::vector<float>& positions) override;
    virtual bool getEstimator(uint32_t id, VelocityTracker::Estimator* outEstimator) const;

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

    // Number of samples to keep.
    static const uint32_t HISTORY_SIZE = 20;

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

    struct Movement {
        nsecs_t eventTime;
        BitSet32 idBits;
        float positions[MAX_POINTERS];

        inline float getPosition(uint32_t id) const { return positions[idBits.getIndexOfBit(id)]; }
    };

    uint32_t mIndex;
    Movement mMovements[HISTORY_SIZE];
};

class ImpulseVelocityTrackerStrategy : public VelocityTrackerStrategy {
public:
    ImpulseVelocityTrackerStrategy();
    virtual ~ImpulseVelocityTrackerStrategy();

    virtual void clearPointers(BitSet32 idBits);
    void addMovement(nsecs_t eventTime, BitSet32 idBits,
                     const std::vector<float>& positions) override;
    virtual bool getEstimator(uint32_t id, VelocityTracker::Estimator* outEstimator) const;

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

    // Number of samples to keep.
    static constexpr size_t HISTORY_SIZE = 20;

    struct Movement {
        nsecs_t eventTime;
        BitSet32 idBits;
        float positions[MAX_POINTERS];

        inline float getPosition(uint32_t id) const { return positions[idBits.getIndexOfBit(id)]; }
    };

    size_t mIndex;
    Movement mMovements[HISTORY_SIZE];
};

} // namespace android

#endif // _LIBINPUT_VELOCITY_TRACKER_H