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 <assert.h>
  26 #include <stdio.h>
  27 #include <stdlib.h>
  28 #include <stdint.h>
  29 #include <limits.h>
  30 #include <math.h>
  31
  32 #include "filter.h"
  33 #include "libinput-util.h"
  34 #include "filter-private.h"
  35
  36 struct normalized_coords
  37 filter_dispatch(struct motion_filter *filter,
  38                 const struct normalized_coords *unaccelerated,
  39                 void *data, uint64_t time)
  40 {
  41         return filter->interface->filter(filter, unaccelerated, data, time);
  42 }
  43
  44 void
  45 filter_destroy(struct motion_filter *filter)
  46 {
  47         if (!filter)
  48                 return;
  49
  50         filter->interface->destroy(filter);
  51 }
  52
  53 bool
  54 filter_set_speed(struct motion_filter *filter,
  55                  double speed)
  56 {
  57         return filter->interface->set_speed(filter, speed);
  58 }
  59
  60 double
  61 filter_get_speed(struct motion_filter *filter)
  62 {
  63         return filter->speed;
  64 }
  65
  66 /*
  67  * Default parameters for pointer acceleration profiles.
  68  */
  69
  70 #define DEFAULT_THRESHOLD 0.4                   /* in units/ms */
  71 #define DEFAULT_ACCELERATION 2.0                /* unitless factor */
  72 #define DEFAULT_INCLINE 1.1                     /* unitless factor */
  73
  74 /*
  75  * Pointer acceleration filter constants
  76  */
  77
  78 #define MAX_VELOCITY_DIFF       1.0 /* units/ms */
  79 #define MOTION_TIMEOUT          300 /* (ms) */
  80 #define NUM_POINTER_TRACKERS    16
  81
  82 struct pointer_tracker {
  83         struct normalized_coords delta; /* delta to most recent event */
  84         uint64_t time;  /* ms */
  85         int dir;
  86 };
  87
  88 struct pointer_accelerator;
  89 struct pointer_accelerator {
  90         struct motion_filter base;
  91
  92         accel_profile_func_t profile;
  93
  94         double velocity;        /* units/ms */
  95         double last_velocity;   /* units/ms */
  96         struct normalized_coords last;
  97
  98         struct pointer_tracker *trackers;
  99         int cur_tracker;
 100
 101         double threshold;       /* units/ms */
 102         double accel;           /* unitless factor */
 103         double incline;         /* incline of the function */
 104 };
 105
 106 static void
 107 feed_trackers(struct pointer_accelerator *accel,
 108               const struct normalized_coords *delta,
 109               uint64_t time)
 110 {
 111         int i, current;
 112         struct pointer_tracker *trackers = accel->trackers;
 113
 114         for (i = 0; i < NUM_POINTER_TRACKERS; i++) {
 115                 trackers[i].delta.x += delta->x;
 116                 trackers[i].delta.y += delta->y;
 117         }
 118
 119         current = (accel->cur_tracker + 1) % NUM_POINTER_TRACKERS;
 120         accel->cur_tracker = current;
 121
 122         trackers[current].delta.x = 0.0;
 123         trackers[current].delta.y = 0.0;
 124         trackers[current].time = time;
 125         trackers[current].dir = normalized_get_direction(*delta);
 126 }
 127
 128 static struct pointer_tracker *
 129 tracker_by_offset(struct pointer_accelerator *accel, unsigned int offset)
 130 {
 131         unsigned int index =
 132                 (accel->cur_tracker + NUM_POINTER_TRACKERS - offset)
 133                 % NUM_POINTER_TRACKERS;
 134         return &accel->trackers[index];
 135 }
 136
 137 static double
 138 calculate_tracker_velocity(struct pointer_tracker *tracker, uint64_t time)
 139 {
 140         double tdelta = time - tracker->time + 1;
 141
 142         return normalized_length(tracker->delta) / tdelta; /* units/ms */
 143 }
 144
 145 static double
 146 calculate_velocity(struct pointer_accelerator *accel, uint64_t time)
 147 {
 148         struct pointer_tracker *tracker;
 149         double velocity;
 150         double result = 0.0;
 151         double initial_velocity = 0.0;
 152         double velocity_diff;
 153         unsigned int offset;
 154
 155         unsigned int dir = tracker_by_offset(accel, 0)->dir;
 156
 157         /* Find least recent vector within a timelimit, maximum velocity diff
 158          * and direction threshold. */
 159         for (offset = 1; offset < NUM_POINTER_TRACKERS; offset++) {
 160                 tracker = tracker_by_offset(accel, offset);
 161
 162                 /* Stop if too far away in time */
 163                 if (time - tracker->time > MOTION_TIMEOUT ||
 164                     tracker->time > time)
 165                         break;
 166
 167                 /* Stop if direction changed */
 168                 dir &= tracker->dir;
 169                 if (dir == 0)
 170                         break;
 171
 172                 velocity = calculate_tracker_velocity(tracker, time);
 173
 174                 if (initial_velocity == 0.0) {
 175                         result = initial_velocity = velocity;
 176                 } else {
 177                         /* Stop if velocity differs too much from initial */
 178                         velocity_diff = fabs(initial_velocity - velocity);
 179                         if (velocity_diff > MAX_VELOCITY_DIFF)
 180                                 break;
 181
 182                         result = velocity;
 183                 }
 184         }
 185
 186         return result; /* units/ms */
 187 }
 188
 189 static double
 190 acceleration_profile(struct pointer_accelerator *accel,
 191                      void *data, double velocity, uint64_t time)
 192 {
 193         return accel->profile(&accel->base, data, velocity, time);
 194 }
 195
 196 static double
 197 calculate_acceleration(struct pointer_accelerator *accel,
 198                        void *data, double velocity, uint64_t time)
 199 {
 200         double factor;
 201
 202         /* Use Simpson's rule to calculate the avarage acceleration between
 203          * the previous motion and the most recent. */
 204         factor = acceleration_profile(accel, data, velocity, time);
 205         factor += acceleration_profile(accel, data, accel->last_velocity, time);
 206         factor += 4.0 *
 207                 acceleration_profile(accel, data,
 208                                      (accel->last_velocity + velocity) / 2,
 209                                      time);
 210
 211         factor = factor / 6.0;
 212
 213         return factor; /* unitless factor */
 214 }
 215
 216 static struct normalized_coords
 217 accelerator_filter(struct motion_filter *filter,
 218                    const struct normalized_coords *unaccelerated,
 219                    void *data, uint64_t time)
 220 {
 221         struct pointer_accelerator *accel =
 222                 (struct pointer_accelerator *) filter;
 223         double velocity; /* units/ms */
 224         double accel_value; /* unitless factor */
 225         struct normalized_coords accelerated;
 226
 227         feed_trackers(accel, unaccelerated, time);
 228         velocity = calculate_velocity(accel, time);
 229         accel_value = calculate_acceleration(accel, data, velocity, time);
 230
 231         accelerated.x = accel_value * unaccelerated->x;
 232         accelerated.y = accel_value * unaccelerated->y;
 233
 234         accel->last = *unaccelerated;
 235
 236         accel->last_velocity = velocity;
 237
 238         return accelerated;
 239 }
 240
 241 static void
 242 accelerator_destroy(struct motion_filter *filter)
 243 {
 244         struct pointer_accelerator *accel =
 245                 (struct pointer_accelerator *) filter;
 246
 247         free(accel->trackers);
 248         free(accel);
 249 }
 250
 251 static bool
 252 accelerator_set_speed(struct motion_filter *filter,
 253                       double speed)
 254 {
 255         struct pointer_accelerator *accel_filter =
 256                 (struct pointer_accelerator *)filter;
 257
 258         assert(speed >= -1.0 && speed <= 1.0);
 259
 260         /* delay when accel kicks in */
 261         accel_filter->threshold = DEFAULT_THRESHOLD - speed / 4.0;
 262         if (accel_filter->threshold < 0.2)
 263                 accel_filter->threshold = 0.2;
 264
 265         /* adjust max accel factor */
 266         accel_filter->accel = DEFAULT_ACCELERATION + speed * 1.5;
 267
 268         /* higher speed -> faster to reach max */
 269         accel_filter->incline = DEFAULT_INCLINE + speed * 0.75;
 270
 271         filter->speed = speed;
 272         return true;
 273 }
 274
 275 struct motion_filter_interface accelerator_interface = {
 276         accelerator_filter,
 277         accelerator_destroy,
 278         accelerator_set_speed,
 279 };
 280
 281 struct motion_filter *
 282 create_pointer_accelerator_filter(accel_profile_func_t profile)
 283 {
 284         struct pointer_accelerator *filter;
 285
 286         filter = zalloc(sizeof *filter);
 287         if (filter == NULL)
 288                 return NULL;
 289
 290         filter->base.interface = &accelerator_interface;
 291
 292         filter->profile = profile;
 293         filter->last_velocity = 0.0;
 294         filter->last.x = 0;
 295         filter->last.y = 0;
 296
 297         filter->trackers =
 298                 calloc(NUM_POINTER_TRACKERS, sizeof *filter->trackers);
 299         filter->cur_tracker = 0;
 300
 301         filter->threshold = DEFAULT_THRESHOLD;
 302         filter->accel = DEFAULT_ACCELERATION;
 303         filter->incline = DEFAULT_INCLINE;
 304
 305         return &filter->base;
 306 }
 307
 308 double
 309 pointer_accel_profile_linear(struct motion_filter *filter,
 310                              void *data,
 311                              double speed_in,
 312                              uint64_t time)
 313 {
 314         struct pointer_accelerator *accel_filter =
 315                 (struct pointer_accelerator *)filter;
 316
 317         double s1, s2;
 318         const double max_accel = accel_filter->accel; /* unitless factor */
 319         const double threshold = accel_filter->threshold; /* units/ms */
 320         const double incline = accel_filter->incline;
 321
 322         s1 = min(1, speed_in * 5);
 323         s2 = 1 + (speed_in - threshold) * incline;
 324
 325         return min(max_accel, s2 > 1 ? s2 : s1);
 326 }
 327
 328 double
 329 touchpad_accel_profile_linear(struct motion_filter *filter,
 330                               void *data,
 331                               double speed_in,
 332                               uint64_t time)
 333 {
 334         /* Once normalized, touchpads see the same
 335            acceleration as mice. that is technically correct but
 336            subjectively wrong, we expect a touchpad to be a lot
 337            slower than a mouse. Apply a magic factor here and proceed
 338            as normal.  */
 339         const double TP_MAGIC_SLOWDOWN = 0.4;
 340         double speed_out;
 341
 342         speed_in *= TP_MAGIC_SLOWDOWN;
 343
 344         speed_out = pointer_accel_profile_linear(filter, data, speed_in, time);
 345
 346         return speed_out * TP_MAGIC_SLOWDOWN;
 347 }
 348
 349 double
 350 touchpad_lenovo_x230_accel_profile(struct motion_filter *filter,
 351                                       void *data,
 352                                       double speed_in,
 353                                       uint64_t time)
 354 {
 355         /* Keep the magic factor from touchpad_accel_profile_linear.  */
 356         const double TP_MAGIC_SLOWDOWN = 0.4;
 357
 358         /* Those touchpads presents an actual lower resolution that what is
 359          * advertised. We see some jumps from the cursor due to the big steps
 360          * in X and Y when we are receiving data.
 361          * Apply a factor to minimize those jumps at low speed, and try
 362          * keeping the same feeling as regular touchpads at high speed.
 363          * It still feels slower but it is usable at least */
 364         const double TP_MAGIC_LOW_RES_FACTOR = 4.0;
 365         double speed_out;
 366         struct pointer_accelerator *accel_filter =
 367                 (struct pointer_accelerator *)filter;
 368
 369         double s1, s2;
 370         const double max_accel = accel_filter->accel *
 371                                   TP_MAGIC_LOW_RES_FACTOR; /* unitless factor */
 372         const double threshold = accel_filter->threshold /
 373                                   TP_MAGIC_LOW_RES_FACTOR; /* units/ms */
 374         const double incline = accel_filter->incline * TP_MAGIC_LOW_RES_FACTOR;
 375
 376         speed_in *= TP_MAGIC_SLOWDOWN / TP_MAGIC_LOW_RES_FACTOR;
 377
 378         s1 = min(1, speed_in * 5);
 379         s2 = 1 + (speed_in - threshold) * incline;
 380
 381         speed_out = min(max_accel, s2 > 1 ? s2 : s1);
 382
 383         return speed_out * TP_MAGIC_SLOWDOWN / TP_MAGIC_LOW_RES_FACTOR;
 384 }