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 void
  37 filter_dispatch(struct motion_filter *filter,
  38                 struct motion_params *motion,
  39                 void *data, uint64_t time)
  40 {
  41         filter->interface->filter(filter, motion, 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         double dx;      /* delta to most recent event, in device units */
  84         double dy;      /* delta to most recent event, in device units */
  85         uint64_t time;  /* ms */
  86         int dir;
  87 };
  88
  89 struct pointer_accelerator;
  90 struct pointer_accelerator {
  91         struct motion_filter base;
  92
  93         accel_profile_func_t profile;
  94
  95         double velocity;        /* units/ms */
  96         double last_velocity;   /* units/ms */
  97         int last_dx;            /* device units */
  98         int last_dy;            /* device units */
  99
 100         struct pointer_tracker *trackers;
 101         int cur_tracker;
 102
 103         double threshold;       /* units/ms */
 104         double accel;           /* unitless factor */
 105         double incline;         /* incline of the function */
 106 };
 107
 108 static void
 109 feed_trackers(struct pointer_accelerator *accel,
 110               double dx, double dy,
 111               uint64_t time)
 112 {
 113         int i, current;
 114         struct pointer_tracker *trackers = accel->trackers;
 115
 116         for (i = 0; i < NUM_POINTER_TRACKERS; i++) {
 117                 trackers[i].dx += dx;
 118                 trackers[i].dy += dy;
 119         }
 120
 121         current = (accel->cur_tracker + 1) % NUM_POINTER_TRACKERS;
 122         accel->cur_tracker = current;
 123
 124         trackers[current].dx = 0.0;
 125         trackers[current].dy = 0.0;
 126         trackers[current].time = time;
 127         trackers[current].dir = vector_get_direction(dx, dy);
 128 }
 129
 130 static struct pointer_tracker *
 131 tracker_by_offset(struct pointer_accelerator *accel, unsigned int offset)
 132 {
 133         unsigned int index =
 134                 (accel->cur_tracker + NUM_POINTER_TRACKERS - offset)
 135                 % NUM_POINTER_TRACKERS;
 136         return &accel->trackers[index];
 137 }
 138
 139 static double
 140 calculate_tracker_velocity(struct pointer_tracker *tracker, uint64_t time)
 141 {
 142         double dx;
 143         double dy;
 144         double distance;
 145
 146         dx = tracker->dx;
 147         dy = tracker->dy;
 148         distance = sqrt(dx*dx + dy*dy);
 149         return distance / (double)(time - tracker->time); /* units/ms */
 150 }
 151
 152 static double
 153 calculate_velocity(struct pointer_accelerator *accel, uint64_t time)
 154 {
 155         struct pointer_tracker *tracker;
 156         double velocity;
 157         double result = 0.0;
 158         double initial_velocity = 0.0;
 159         double velocity_diff;
 160         unsigned int offset;
 161
 162         unsigned int dir = tracker_by_offset(accel, 0)->dir;
 163
 164         /* Find least recent vector within a timelimit, maximum velocity diff
 165          * and direction threshold. */
 166         for (offset = 1; offset < NUM_POINTER_TRACKERS; offset++) {
 167                 tracker = tracker_by_offset(accel, offset);
 168
 169                 /* Stop if too far away in time */
 170                 if (time - tracker->time > MOTION_TIMEOUT ||
 171                     tracker->time > time)
 172                         break;
 173
 174                 /* Stop if direction changed */
 175                 dir &= tracker->dir;
 176                 if (dir == 0)
 177                         break;
 178
 179                 velocity = calculate_tracker_velocity(tracker, time);
 180
 181                 if (initial_velocity == 0.0) {
 182                         result = initial_velocity = velocity;
 183                 } else {
 184                         /* Stop if velocity differs too much from initial */
 185                         velocity_diff = fabs(initial_velocity - velocity);
 186                         if (velocity_diff > MAX_VELOCITY_DIFF)
 187                                 break;
 188
 189                         result = velocity;
 190                 }
 191         }
 192
 193         return result; /* units/ms */
 194 }
 195
 196 static double
 197 acceleration_profile(struct pointer_accelerator *accel,
 198                      void *data, double velocity, uint64_t time)
 199 {
 200         return accel->profile(&accel->base, data, velocity, time);
 201 }
 202
 203 static double
 204 calculate_acceleration(struct pointer_accelerator *accel,
 205                        void *data, double velocity, uint64_t time)
 206 {
 207         double factor;
 208
 209         /* Use Simpson's rule to calculate the avarage acceleration between
 210          * the previous motion and the most recent. */
 211         factor = acceleration_profile(accel, data, velocity, time);
 212         factor += acceleration_profile(accel, data, accel->last_velocity, time);
 213         factor += 4.0 *
 214                 acceleration_profile(accel, data,
 215                                      (accel->last_velocity + velocity) / 2,
 216                                      time);
 217
 218         factor = factor / 6.0;
 219
 220         return factor; /* unitless factor */
 221 }
 222
 223 static void
 224 accelerator_filter(struct motion_filter *filter,
 225                    struct motion_params *motion,
 226                    void *data, uint64_t time)
 227 {
 228         struct pointer_accelerator *accel =
 229                 (struct pointer_accelerator *) filter;
 230         double velocity; /* units/ms */
 231         double accel_value; /* unitless factor */
 232
 233         feed_trackers(accel, motion->dx, motion->dy, time);
 234         velocity = calculate_velocity(accel, time);
 235         accel_value = calculate_acceleration(accel, data, velocity, time);
 236
 237         motion->dx = accel_value * motion->dx;
 238         motion->dy = accel_value * motion->dy;
 239
 240         accel->last_dx = motion->dx;
 241         accel->last_dy = motion->dy;
 242
 243         accel->last_velocity = velocity;
 244 }
 245
 246 static void
 247 accelerator_destroy(struct motion_filter *filter)
 248 {
 249         struct pointer_accelerator *accel =
 250                 (struct pointer_accelerator *) filter;
 251
 252         free(accel->trackers);
 253         free(accel);
 254 }
 255
 256 static bool
 257 accelerator_set_speed(struct motion_filter *filter,
 258                       double speed)
 259 {
 260         struct pointer_accelerator *accel_filter =
 261                 (struct pointer_accelerator *)filter;
 262
 263         assert(speed >= -1.0 && speed <= 1.0);
 264
 265         /* delay when accel kicks in */
 266         accel_filter->threshold = DEFAULT_THRESHOLD - speed/6.0;
 267
 268         /* adjust max accel factor */
 269         accel_filter->accel = DEFAULT_ACCELERATION + speed;
 270
 271         /* higher speed -> faster to reach max */
 272         accel_filter->incline = DEFAULT_INCLINE + speed/2.0;
 273
 274         filter->speed = speed;
 275         return true;
 276 }
 277
 278 struct motion_filter_interface accelerator_interface = {
 279         accelerator_filter,
 280         accelerator_destroy,
 281         accelerator_set_speed,
 282 };
 283
 284 struct motion_filter *
 285 create_pointer_accelerator_filter(accel_profile_func_t profile)
 286 {
 287         struct pointer_accelerator *filter;
 288
 289         filter = malloc(sizeof *filter);
 290         if (filter == NULL)
 291                 return NULL;
 292
 293         filter->base.interface = &accelerator_interface;
 294
 295         filter->profile = profile;
 296         filter->last_velocity = 0.0;
 297         filter->last_dx = 0;
 298         filter->last_dy = 0;
 299
 300         filter->trackers =
 301                 calloc(NUM_POINTER_TRACKERS, sizeof *filter->trackers);
 302         filter->cur_tracker = 0;
 303
 304         filter->threshold = DEFAULT_THRESHOLD;
 305         filter->accel = DEFAULT_ACCELERATION;
 306         filter->incline = DEFAULT_INCLINE;
 307
 308         return &filter->base;
 309 }
 310
 311 static inline double
 312 calc_penumbral_gradient(double x)
 313 {
 314         x *= 2.0;
 315         x -= 1.0;
 316         return 0.5 + (x * sqrt(1.0 - x * x) + asin(x)) / M_PI;
 317 }
 318
 319 double
 320 pointer_accel_profile_linear(struct motion_filter *filter,
 321                              void *data,
 322                              double speed_in,
 323                              uint64_t time)
 324 {
 325         struct pointer_accelerator *accel_filter =
 326                 (struct pointer_accelerator *)filter;
 327
 328         double s1, s2;
 329         const double max_accel = accel_filter->accel; /* unitless factor */
 330         const double threshold = accel_filter->threshold; /* units/ms */
 331         const double incline = accel_filter->incline;
 332
 333         s1 = min(1, speed_in * 5);
 334         s2 = 1 + (speed_in - threshold) * incline;
 335
 336         return min(max_accel, s2 > 1 ? s2 : s1);
 337 }