src/filter.c

   1 /*
   2  * Copyright © 2012 Jonas Ådahl
   3  *
   4  * Permission to use, copy, modify, distribute, and sell this software and
   5  * its documentation for any purpose is hereby granted without fee, provided
   6  * that the above copyright notice appear in all copies and that both that
   7  * copyright notice and this permission notice appear in supporting
   8  * documentation, and that the name of the copyright holders not be used in
   9  * advertising or publicity pertaining to distribution of the software
  10  * without specific, written prior permission.  The copyright holders make
  11  * no representations about the suitability of this software for any
  12  * purpose.  It is provided "as is" without express or implied warranty.
  13  *
  14  * THE COPYRIGHT HOLDERS DISCLAIM ALL WARRANTIES WITH REGARD TO THIS
  15  * SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
  16  * FITNESS, IN NO EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY
  17  * SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER
  18  * RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF
  19  * CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
  20  * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  21  */
  22
  23 #include "config.h"
  24
  25 #include <stdio.h>
  26 #include <stdlib.h>
  27 #include <stdint.h>
  28 #include <limits.h>
  29 #include <math.h>
  30
  31 #include "filter.h"
  32 #include "libinput-util.h"
  33
  34 void
  35 filter_dispatch(struct motion_filter *filter,
  36                 struct motion_params *motion,
  37                 void *data, uint64_t time)
  38 {
  39         filter->interface->filter(filter, motion, data, time);
  40 }
  41
  42 void
  43 filter_destroy(struct motion_filter *filter)
  44 {
  45         if (!filter)
  46                 return;
  47
  48         filter->interface->destroy(filter);
  49 }
  50
  51 /*
  52  * Default parameters for pointer acceleration profiles.
  53  */
  54
  55 #define DEFAULT_THRESHOLD 0.4                   /* in units/ms */
  56 #define DEFAULT_ACCELERATION 2.0                /* unitless factor */
  57
  58 /*
  59  * Pointer acceleration filter constants
  60  */
  61
  62 #define MAX_VELOCITY_DIFF       1.0 /* units/ms */
  63 #define MOTION_TIMEOUT          300 /* (ms) */
  64 #define NUM_POINTER_TRACKERS    16
  65
  66 struct pointer_tracker {
  67         double dx;      /* delta to most recent event, in device units */
  68         double dy;      /* delta to most recent event, in device units */
  69         uint64_t time;  /* ms */
  70         int dir;
  71 };
  72
  73 struct pointer_accelerator;
  74 struct pointer_accelerator {
  75         struct motion_filter base;
  76
  77         accel_profile_func_t profile;
  78
  79         double velocity;        /* units/ms */
  80         double last_velocity;   /* units/ms */
  81         int last_dx;            /* device units */
  82         int last_dy;            /* device units */
  83
  84         struct pointer_tracker *trackers;
  85         int cur_tracker;
  86 };
  87
  88 static void
  89 feed_trackers(struct pointer_accelerator *accel,
  90               double dx, double dy,
  91               uint64_t time)
  92 {
  93         int i, current;
  94         struct pointer_tracker *trackers = accel->trackers;
  95
  96         for (i = 0; i < NUM_POINTER_TRACKERS; i++) {
  97                 trackers[i].dx += dx;
  98                 trackers[i].dy += dy;
  99         }
 100
 101         current = (accel->cur_tracker + 1) % NUM_POINTER_TRACKERS;
 102         accel->cur_tracker = current;
 103
 104         trackers[current].dx = 0.0;
 105         trackers[current].dy = 0.0;
 106         trackers[current].time = time;
 107         trackers[current].dir = vector_get_direction(dx, dy);
 108 }
 109
 110 static struct pointer_tracker *
 111 tracker_by_offset(struct pointer_accelerator *accel, unsigned int offset)
 112 {
 113         unsigned int index =
 114                 (accel->cur_tracker + NUM_POINTER_TRACKERS - offset)
 115                 % NUM_POINTER_TRACKERS;
 116         return &accel->trackers[index];
 117 }
 118
 119 static double
 120 calculate_tracker_velocity(struct pointer_tracker *tracker, uint64_t time)
 121 {
 122         int dx;
 123         int dy;
 124         double distance;
 125
 126         dx = tracker->dx;
 127         dy = tracker->dy;
 128         distance = sqrt(dx*dx + dy*dy);
 129         return distance / (double)(time - tracker->time); /* units/ms */
 130 }
 131
 132 static double
 133 calculate_velocity(struct pointer_accelerator *accel, uint64_t time)
 134 {
 135         struct pointer_tracker *tracker;
 136         double velocity;
 137         double result = 0.0;
 138         double initial_velocity = 0.0;
 139         double velocity_diff;
 140         unsigned int offset;
 141
 142         unsigned int dir = tracker_by_offset(accel, 0)->dir;
 143
 144         /* Find least recent vector within a timelimit, maximum velocity diff
 145          * and direction threshold. */
 146         for (offset = 1; offset < NUM_POINTER_TRACKERS; offset++) {
 147                 tracker = tracker_by_offset(accel, offset);
 148
 149                 /* Stop if too far away in time */
 150                 if (time - tracker->time > MOTION_TIMEOUT ||
 151                     tracker->time > time)
 152                         break;
 153
 154                 /* Stop if direction changed */
 155                 dir &= tracker->dir;
 156                 if (dir == 0)
 157                         break;
 158
 159                 velocity = calculate_tracker_velocity(tracker, time);
 160
 161                 if (initial_velocity == 0.0) {
 162                         result = initial_velocity = velocity;
 163                 } else {
 164                         /* Stop if velocity differs too much from initial */
 165                         velocity_diff = fabs(initial_velocity - velocity);
 166                         if (velocity_diff > MAX_VELOCITY_DIFF)
 167                                 break;
 168
 169                         result = velocity;
 170                 }
 171         }
 172
 173         return result; /* units/ms */
 174 }
 175
 176 static double
 177 acceleration_profile(struct pointer_accelerator *accel,
 178                      void *data, double velocity, uint64_t time)
 179 {
 180         return accel->profile(&accel->base, data, velocity, time);
 181 }
 182
 183 static double
 184 calculate_acceleration(struct pointer_accelerator *accel,
 185                        void *data, double velocity, uint64_t time)
 186 {
 187         double factor;
 188
 189         /* Use Simpson's rule to calculate the avarage acceleration between
 190          * the previous motion and the most recent. */
 191         factor = acceleration_profile(accel, data, velocity, time);
 192         factor += acceleration_profile(accel, data, accel->last_velocity, time);
 193         factor += 4.0 *
 194                 acceleration_profile(accel, data,
 195                                      (accel->last_velocity + velocity) / 2,
 196                                      time);
 197
 198         factor = factor / 6.0;
 199
 200         return factor; /* unitless factor */
 201 }
 202
 203 static void
 204 accelerator_filter(struct motion_filter *filter,
 205                    struct motion_params *motion,
 206                    void *data, uint64_t time)
 207 {
 208         struct pointer_accelerator *accel =
 209                 (struct pointer_accelerator *) filter;
 210         double velocity; /* units/ms */
 211         double accel_value; /* unitless factor */
 212
 213         feed_trackers(accel, motion->dx, motion->dy, time);
 214         velocity = calculate_velocity(accel, time);
 215         accel_value = calculate_acceleration(accel, data, velocity, time);
 216
 217         motion->dx = accel_value * motion->dx;
 218         motion->dy = accel_value * motion->dy;
 219
 220         accel->last_dx = motion->dx;
 221         accel->last_dy = motion->dy;
 222
 223         accel->last_velocity = velocity;
 224 }
 225
 226 static void
 227 accelerator_destroy(struct motion_filter *filter)
 228 {
 229         struct pointer_accelerator *accel =
 230                 (struct pointer_accelerator *) filter;
 231
 232         free(accel->trackers);
 233         free(accel);
 234 }
 235
 236 struct motion_filter_interface accelerator_interface = {
 237         accelerator_filter,
 238         accelerator_destroy
 239 };
 240
 241 struct motion_filter *
 242 create_pointer_accelator_filter(accel_profile_func_t profile)
 243 {
 244         struct pointer_accelerator *filter;
 245
 246         filter = malloc(sizeof *filter);
 247         if (filter == NULL)
 248                 return NULL;
 249
 250         filter->base.interface = &accelerator_interface;
 251
 252         filter->profile = profile;
 253         filter->last_velocity = 0.0;
 254         filter->last_dx = 0;
 255         filter->last_dy = 0;
 256
 257         filter->trackers =
 258                 calloc(NUM_POINTER_TRACKERS, sizeof *filter->trackers);
 259         filter->cur_tracker = 0;
 260
 261         return &filter->base;
 262 }
 263
 264 static inline double
 265 calc_penumbral_gradient(double x)
 266 {
 267         x *= 2.0;
 268         x -= 1.0;
 269         return 0.5 + (x * sqrt(1.0 - x * x) + asin(x)) / M_PI;
 270 }
 271
 272 double
 273 pointer_accel_profile_smooth_simple(struct motion_filter *filter,
 274                                     void *data,
 275                                     double velocity, /* units/ms */
 276                                     uint64_t time)
 277 {
 278         double threshold = DEFAULT_THRESHOLD; /* units/ms */
 279         double accel = DEFAULT_ACCELERATION; /* unitless factor */
 280         double smooth_accel_coefficient; /* unitless factor */
 281         double factor; /* unitless factor */
 282
 283         if (threshold < 0.1)
 284                 threshold = 0.1;
 285         if (accel < 1.0)
 286                 accel = 1.0;
 287
 288         /* We use units/ms as velocity but it has no real meaning unless all
 289            devices have the same resolution. For touchpads, we normalize to
 290            400dpi (15.75 units/mm), but the resolution on USB mice is all
 291            over the place. Though most mice these days have either 400
 292            dpi (15.75 units/mm), 800 dpi or 1000dpi, excluding gaming mice
 293            that can usually adjust it on the fly anyway and currently go up
 294            to 8200dpi.
 295           */
 296         if (velocity < (threshold / 2.0))
 297                 return calc_penumbral_gradient(0.5 + velocity / threshold) * 2.0 - 1.0;
 298
 299         if (velocity <= threshold)
 300                 return 1.0;
 301
 302         factor = velocity/threshold;
 303         if (factor >= accel)
 304                 return accel;
 305
 306         /* factor is between 1.0 and accel, scale this to 0.0 - 1.0 */
 307         factor = (factor - 1.0) / (accel - 1.0);
 308         smooth_accel_coefficient = calc_penumbral_gradient(factor);
 309         return 1.0 + (smooth_accel_coefficient * (accel - 1.0));
 310 }