michael@0: /*
michael@0:  * Copyright (C) 2012 The Android Open Source Project
michael@0:  *
michael@0:  * Licensed under the Apache License, Version 2.0 (the "License");
michael@0:  * you may not use this file except in compliance with the License.
michael@0:  * You may obtain a copy of the License at
michael@0:  *
michael@0:  *      http://www.apache.org/licenses/LICENSE-2.0
michael@0:  *
michael@0:  * Unless required by applicable law or agreed to in writing, software
michael@0:  * distributed under the License is distributed on an "AS IS" BASIS,
michael@0:  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
michael@0:  * See the License for the specific language governing permissions and
michael@0:  * limitations under the License.
michael@0:  */
michael@0: 
michael@0: #ifndef _ANDROIDFW_VELOCITY_TRACKER_H
michael@0: #define _ANDROIDFW_VELOCITY_TRACKER_H
michael@0: 
michael@0: #include "Input.h"
michael@0: #include <utils/Timers.h>
michael@0: #include <utils/BitSet.h>
michael@0: 
michael@0: namespace android {
michael@0: 
michael@0: class VelocityTrackerStrategy;
michael@0: 
michael@0: /*
michael@0:  * Calculates the velocity of pointer movements over time.
michael@0:  */
michael@0: class VelocityTracker {
michael@0: public:
michael@0:     struct Position {
michael@0:         float x, y;
michael@0:     };
michael@0: 
michael@0:     struct Estimator {
michael@0:         static const size_t MAX_DEGREE = 4;
michael@0: 
michael@0:         // Estimator time base.
michael@0:         nsecs_t time;
michael@0: 
michael@0:         // Polynomial coefficients describing motion in X and Y.
michael@0:         float xCoeff[MAX_DEGREE + 1], yCoeff[MAX_DEGREE + 1];
michael@0: 
michael@0:         // Polynomial degree (number of coefficients), or zero if no information is
michael@0:         // available.
michael@0:         uint32_t degree;
michael@0: 
michael@0:         // Confidence (coefficient of determination), between 0 (no fit) and 1 (perfect fit).
michael@0:         float confidence;
michael@0: 
michael@0:         inline void clear() {
michael@0:             time = 0;
michael@0:             degree = 0;
michael@0:             confidence = 0;
michael@0:             for (size_t i = 0; i <= MAX_DEGREE; i++) {
michael@0:                 xCoeff[i] = 0;
michael@0:                 yCoeff[i] = 0;
michael@0:             }
michael@0:         }
michael@0:     };
michael@0: 
michael@0:     // Creates a velocity tracker using the specified strategy.
michael@0:     // If strategy is NULL, uses the default strategy for the platform.
michael@0:     VelocityTracker(const char* strategy = NULL);
michael@0: 
michael@0:     ~VelocityTracker();
michael@0: 
michael@0:     // Resets the velocity tracker state.
michael@0:     void clear();
michael@0: 
michael@0:     // Resets the velocity tracker state for specific pointers.
michael@0:     // Call this method when some pointers have changed and may be reusing
michael@0:     // an id that was assigned to a different pointer earlier.
michael@0:     void clearPointers(BitSet32 idBits);
michael@0: 
michael@0:     // Adds movement information for a set of pointers.
michael@0:     // The idBits bitfield specifies the pointer ids of the pointers whose positions
michael@0:     // are included in the movement.
michael@0:     // The positions array contains position information for each pointer in order by
michael@0:     // increasing id.  Its size should be equal to the number of one bits in idBits.
michael@0:     void addMovement(nsecs_t eventTime, BitSet32 idBits, const Position* positions);
michael@0: 
michael@0:     // Adds movement information for all pointers in a MotionEvent, including historical samples.
michael@0:     void addMovement(const MotionEvent* event);
michael@0: 
michael@0:     // Gets the velocity of the specified pointer id in position units per second.
michael@0:     // Returns false and sets the velocity components to zero if there is
michael@0:     // insufficient movement information for the pointer.
michael@0:     bool getVelocity(uint32_t id, float* outVx, float* outVy) const;
michael@0: 
michael@0:     // Gets an estimator for the recent movements of the specified pointer id.
michael@0:     // Returns false and clears the estimator if there is no information available
michael@0:     // about the pointer.
michael@0:     bool getEstimator(uint32_t id, Estimator* outEstimator) const;
michael@0: 
michael@0:     // Gets the active pointer id, or -1 if none.
michael@0:     inline int32_t getActivePointerId() const { return mActivePointerId; }
michael@0: 
michael@0:     // Gets a bitset containing all pointer ids from the most recent movement.
michael@0:     inline BitSet32 getCurrentPointerIdBits() const { return mCurrentPointerIdBits; }
michael@0: 
michael@0: private:
michael@0:     static const char* DEFAULT_STRATEGY;
michael@0: 
michael@0:     nsecs_t mLastEventTime;
michael@0:     BitSet32 mCurrentPointerIdBits;
michael@0:     int32_t mActivePointerId;
michael@0:     VelocityTrackerStrategy* mStrategy;
michael@0: 
michael@0:     bool configureStrategy(const char* strategy);
michael@0: 
michael@0:     static VelocityTrackerStrategy* createStrategy(const char* strategy);
michael@0: };
michael@0: 
michael@0: 
michael@0: /*
michael@0:  * Implements a particular velocity tracker algorithm.
michael@0:  */
michael@0: class VelocityTrackerStrategy {
michael@0: protected:
michael@0:     VelocityTrackerStrategy() { }
michael@0: 
michael@0: public:
michael@0:     virtual ~VelocityTrackerStrategy() { }
michael@0: 
michael@0:     virtual void clear() = 0;
michael@0:     virtual void clearPointers(BitSet32 idBits) = 0;
michael@0:     virtual void addMovement(nsecs_t eventTime, BitSet32 idBits,
michael@0:             const VelocityTracker::Position* positions) = 0;
michael@0:     virtual bool getEstimator(uint32_t id, VelocityTracker::Estimator* outEstimator) const = 0;
michael@0: };
michael@0: 
michael@0: 
michael@0: /*
michael@0:  * Velocity tracker algorithm based on least-squares linear regression.
michael@0:  */
michael@0: class LeastSquaresVelocityTrackerStrategy : public VelocityTrackerStrategy {
michael@0: public:
michael@0:     enum Weighting {
michael@0:         // No weights applied.  All data points are equally reliable.
michael@0:         WEIGHTING_NONE,
michael@0: 
michael@0:         // Weight by time delta.  Data points clustered together are weighted less.
michael@0:         WEIGHTING_DELTA,
michael@0: 
michael@0:         // Weight such that points within a certain horizon are weighed more than those
michael@0:         // outside of that horizon.
michael@0:         WEIGHTING_CENTRAL,
michael@0: 
michael@0:         // Weight such that points older than a certain amount are weighed less.
michael@0:         WEIGHTING_RECENT,
michael@0:     };
michael@0: 
michael@0:     // Degree must be no greater than Estimator::MAX_DEGREE.
michael@0:     LeastSquaresVelocityTrackerStrategy(uint32_t degree, Weighting weighting = WEIGHTING_NONE);
michael@0:     virtual ~LeastSquaresVelocityTrackerStrategy();
michael@0: 
michael@0:     virtual void clear();
michael@0:     virtual void clearPointers(BitSet32 idBits);
michael@0:     virtual void addMovement(nsecs_t eventTime, BitSet32 idBits,
michael@0:             const VelocityTracker::Position* positions);
michael@0:     virtual bool getEstimator(uint32_t id, VelocityTracker::Estimator* outEstimator) const;
michael@0: 
michael@0: private:
michael@0:     // Sample horizon.
michael@0:     // We don't use too much history by default since we want to react to quick
michael@0:     // changes in direction.
michael@0:     static const nsecs_t HORIZON = 100 * 1000000; // 100 ms
michael@0: 
michael@0:     // Number of samples to keep.
michael@0:     static const uint32_t HISTORY_SIZE = 20;
michael@0: 
michael@0:     struct Movement {
michael@0:         nsecs_t eventTime;
michael@0:         BitSet32 idBits;
michael@0:         VelocityTracker::Position positions[MAX_POINTERS];
michael@0: 
michael@0:         inline const VelocityTracker::Position& getPosition(uint32_t id) const {
michael@0:             return positions[idBits.getIndexOfBit(id)];
michael@0:         }
michael@0:     };
michael@0: 
michael@0:     float chooseWeight(uint32_t index) const;
michael@0: 
michael@0:     const uint32_t mDegree;
michael@0:     const Weighting mWeighting;
michael@0:     uint32_t mIndex;
michael@0:     Movement mMovements[HISTORY_SIZE];
michael@0: };
michael@0: 
michael@0: 
michael@0: /*
michael@0:  * Velocity tracker algorithm that uses an IIR filter.
michael@0:  */
michael@0: class IntegratingVelocityTrackerStrategy : public VelocityTrackerStrategy {
michael@0: public:
michael@0:     // Degree must be 1 or 2.
michael@0:     IntegratingVelocityTrackerStrategy(uint32_t degree);
michael@0:     ~IntegratingVelocityTrackerStrategy();
michael@0: 
michael@0:     virtual void clear();
michael@0:     virtual void clearPointers(BitSet32 idBits);
michael@0:     virtual void addMovement(nsecs_t eventTime, BitSet32 idBits,
michael@0:             const VelocityTracker::Position* positions);
michael@0:     virtual bool getEstimator(uint32_t id, VelocityTracker::Estimator* outEstimator) const;
michael@0: 
michael@0: private:
michael@0:     // Current state estimate for a particular pointer.
michael@0:     struct State {
michael@0:         nsecs_t updateTime;
michael@0:         uint32_t degree;
michael@0: 
michael@0:         float xpos, xvel, xaccel;
michael@0:         float ypos, yvel, yaccel;
michael@0:     };
michael@0: 
michael@0:     const uint32_t mDegree;
michael@0:     BitSet32 mPointerIdBits;
michael@0:     State mPointerState[MAX_POINTER_ID + 1];
michael@0: 
michael@0:     void initState(State& state, nsecs_t eventTime, float xpos, float ypos) const;
michael@0:     void updateState(State& state, nsecs_t eventTime, float xpos, float ypos) const;
michael@0:     void populateEstimator(const State& state, VelocityTracker::Estimator* outEstimator) const;
michael@0: };
michael@0: 
michael@0: 
michael@0: /*
michael@0:  * Velocity tracker strategy used prior to ICS.
michael@0:  */
michael@0: class LegacyVelocityTrackerStrategy : public VelocityTrackerStrategy {
michael@0: public:
michael@0:     LegacyVelocityTrackerStrategy();
michael@0:     virtual ~LegacyVelocityTrackerStrategy();
michael@0: 
michael@0:     virtual void clear();
michael@0:     virtual void clearPointers(BitSet32 idBits);
michael@0:     virtual void addMovement(nsecs_t eventTime, BitSet32 idBits,
michael@0:             const VelocityTracker::Position* positions);
michael@0:     virtual bool getEstimator(uint32_t id, VelocityTracker::Estimator* outEstimator) const;
michael@0: 
michael@0: private:
michael@0:     // Oldest sample to consider when calculating the velocity.
michael@0:     static const nsecs_t HORIZON = 200 * 1000000; // 100 ms
michael@0: 
michael@0:     // Number of samples to keep.
michael@0:     static const uint32_t HISTORY_SIZE = 20;
michael@0: 
michael@0:     // The minimum duration between samples when estimating velocity.
michael@0:     static const nsecs_t MIN_DURATION = 10 * 1000000; // 10 ms
michael@0: 
michael@0:     struct Movement {
michael@0:         nsecs_t eventTime;
michael@0:         BitSet32 idBits;
michael@0:         VelocityTracker::Position positions[MAX_POINTERS];
michael@0: 
michael@0:         inline const VelocityTracker::Position& getPosition(uint32_t id) const {
michael@0:             return positions[idBits.getIndexOfBit(id)];
michael@0:         }
michael@0:     };
michael@0: 
michael@0:     uint32_t mIndex;
michael@0:     Movement mMovements[HISTORY_SIZE];
michael@0: };
michael@0: 
michael@0: } // namespace android
michael@0: 
michael@0: #endif // _ANDROIDFW_VELOCITY_TRACKER_H