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 <stdlib.h>
  26 #include <stdint.h>
  27 #include <limits.h>
  28 #include <math.h>
  29
  30 #include <wayland-util.h>
  31
  32 #include "compositor.h"
  33 #include "filter.h"
  34
  35 void
  36 weston_filter_dispatch(struct weston_motion_filter *filter,
  37                        struct weston_motion_params *motion,
  38                        void *data, uint32_t time)
  39 {
  40         filter->interface->filter(filter, motion, data, time);
  41 }
  42
  43 /*
  44  * Pointer acceleration filter
  45  */
  46
  47 #define MAX_VELOCITY_DIFF       1.0
  48 #define MOTION_TIMEOUT          300 /* (ms) */
  49 #define NUM_POINTER_TRACKERS    16
  50
  51 struct pointer_tracker {
  52         double dx;
  53         double dy;
  54         uint32_t time;
  55         int dir;
  56 };
  57
  58 struct pointer_accelerator;
  59 struct pointer_accelerator {
  60         struct weston_motion_filter base;
  61
  62         accel_profile_func_t profile;
  63
  64         double velocity;
  65         double last_velocity;
  66         int last_dx;
  67         int last_dy;
  68
  69         struct pointer_tracker *trackers;
  70         int cur_tracker;
  71 };
  72
  73 enum directions {
  74         N  = 1 << 0,
  75         NE = 1 << 1,
  76         E  = 1 << 2,
  77         SE = 1 << 3,
  78         S  = 1 << 4,
  79         SW = 1 << 5,
  80         W  = 1 << 6,
  81         NW = 1 << 7,
  82         UNDEFINED_DIRECTION = 0xff
  83 };
  84
  85 static int
  86 get_direction(int dx, int dy)
  87 {
  88         int dir = UNDEFINED_DIRECTION;
  89         int d1, d2;
  90         double r;
  91
  92         if (abs(dx) < 2 && abs(dy) < 2) {
  93                 if (dx > 0 && dy > 0)
  94                         dir = S | SE | E;
  95                 else if (dx > 0 && dy < 0)
  96                         dir = N | NE | E;
  97                 else if (dx < 0 && dy > 0)
  98                         dir = S | SW | W;
  99                 else if (dx < 0 && dy < 0)
 100                         dir = N | NW | W;
 101                 else if (dx > 0)
 102                         dir = NW | W | SW;
 103                 else if (dx < 0)
 104                         dir = NE | E | SE;
 105                 else if (dy > 0)
 106                         dir = SE | S | SW;
 107                 else if (dy < 0)
 108                         dir = NE | N | NW;
 109         }
 110         else {
 111                 /* Calculate r within the interval  [0 to 8)
 112                  *
 113                  * r = [0 .. 2π] where 0 is North
 114                  * d_f = r / 2π  ([0 .. 1))
 115                  * d_8 = 8 * d_f
 116                  */
 117                 r = atan2(dy, dx);
 118                 r = fmod(r + 2.5*M_PI, 2*M_PI);
 119                 r *= 4*M_1_PI;
 120
 121                 /* Mark one or two close enough octants */
 122                 d1 = (int)(r + 0.9) % 8;
 123                 d2 = (int)(r + 0.1) % 8;
 124
 125                 dir = (1 << d1) | (1 << d2);
 126         }
 127
 128         return dir;
 129 }
 130
 131 static void
 132 feed_trackers(struct pointer_accelerator *accel,
 133               double dx, double dy,
 134               uint32_t time)
 135 {
 136         int i, current;
 137         struct pointer_tracker *trackers = accel->trackers;
 138
 139         for (i = 0; i < NUM_POINTER_TRACKERS; i++) {
 140                 trackers[i].dx += dx;
 141                 trackers[i].dy += dy;
 142         }
 143
 144         current = (accel->cur_tracker + 1) % NUM_POINTER_TRACKERS;
 145         accel->cur_tracker = current;
 146
 147         trackers[current].dx = 0.0;
 148         trackers[current].dy = 0.0;
 149         trackers[current].time = time;
 150         trackers[current].dir = get_direction(dx, dy);
 151 }
 152
 153 static struct pointer_tracker *
 154 tracker_by_offset(struct pointer_accelerator *accel, unsigned int offset)
 155 {
 156         unsigned int index =
 157                 (accel->cur_tracker + NUM_POINTER_TRACKERS - offset)
 158                 % NUM_POINTER_TRACKERS;
 159         return &accel->trackers[index];
 160 }
 161
 162 static double
 163 calculate_tracker_velocity(struct pointer_tracker *tracker, uint32_t time)
 164 {
 165         int dx;
 166         int dy;
 167         double distance;
 168
 169         dx = tracker->dx;
 170         dy = tracker->dy;
 171         distance = sqrt(dx*dx + dy*dy);
 172         return distance / (double)(time - tracker->time);
 173 }
 174
 175 static double
 176 calculate_velocity(struct pointer_accelerator *accel, uint32_t time)
 177 {
 178         struct pointer_tracker *tracker;
 179         double velocity;
 180         double result = 0.0;
 181         double initial_velocity;
 182         double velocity_diff;
 183         unsigned int offset;
 184
 185         unsigned int dir = tracker_by_offset(accel, 0)->dir;
 186
 187         /* Find first velocity */
 188         for (offset = 1; offset < NUM_POINTER_TRACKERS; offset++) {
 189                 tracker = tracker_by_offset(accel, offset);
 190
 191                 if (time <= tracker->time)
 192                         continue;
 193
 194                 result = initial_velocity =
 195                         calculate_tracker_velocity(tracker, time);
 196                 if (initial_velocity > 0.0)
 197                         break;
 198         }
 199
 200         /* Find least recent vector within a timelimit, maximum velocity diff
 201          * and direction threshold. */
 202         for (; offset < NUM_POINTER_TRACKERS; offset++) {
 203                 tracker = tracker_by_offset(accel, offset);
 204
 205                 /* Stop if too far away in time */
 206                 if (time - tracker->time > MOTION_TIMEOUT ||
 207                     tracker->time > time)
 208                         break;
 209
 210                 /* Stop if direction changed */
 211                 dir &= tracker->dir;
 212                 if (dir == 0)
 213                         break;
 214
 215                 velocity = calculate_tracker_velocity(tracker, time);
 216
 217                 /* Stop if velocity differs too much from initial */
 218                 velocity_diff = fabs(initial_velocity - velocity);
 219                 if (velocity_diff > MAX_VELOCITY_DIFF)
 220                         break;
 221
 222                 result = velocity;
 223         }
 224
 225         return result;
 226 }
 227
 228 static double
 229 acceleration_profile(struct pointer_accelerator *accel,
 230                      void *data, double velocity, uint32_t time)
 231 {
 232         return accel->profile(&accel->base, data, velocity, time);
 233 }
 234
 235 static double
 236 calculate_acceleration(struct pointer_accelerator *accel,
 237                        void *data, double velocity, uint32_t time)
 238 {
 239         double factor;
 240
 241         /* Use Simpson's rule to calculate the avarage acceleration between
 242          * the previous motion and the most recent. */
 243         factor = acceleration_profile(accel, data, velocity, time);
 244         factor += acceleration_profile(accel, data, accel->last_velocity, time);
 245         factor += 4.0 *
 246                 acceleration_profile(accel, data,
 247                                      (accel->last_velocity + velocity) / 2,
 248                                      time);
 249
 250         factor = factor / 6.0;
 251
 252         return factor;
 253 }
 254
 255 static double
 256 soften_delta(double last_delta, double delta)
 257 {
 258         if (delta < -1.0 || delta > 1.0) {
 259                 if (delta > last_delta)
 260                         return delta - 0.5;
 261                 else if (delta < last_delta)
 262                         return delta + 0.5;
 263         }
 264
 265         return delta;
 266 }
 267
 268 static void
 269 apply_softening(struct pointer_accelerator *accel,
 270                 struct weston_motion_params *motion)
 271 {
 272         motion->dx = soften_delta(accel->last_dx, motion->dx);
 273         motion->dy = soften_delta(accel->last_dy, motion->dy);
 274 }
 275
 276 static void
 277 accelerator_filter(struct weston_motion_filter *filter,
 278                    struct weston_motion_params *motion,
 279                    void *data, uint32_t time)
 280 {
 281         struct pointer_accelerator *accel =
 282                 (struct pointer_accelerator *) filter;
 283         double velocity;
 284         double accel_value;
 285
 286         feed_trackers(accel, motion->dx, motion->dy, time);
 287         velocity = calculate_velocity(accel, time);
 288         accel_value = calculate_acceleration(accel, data, velocity, time);
 289
 290         motion->dx = accel_value * motion->dx;
 291         motion->dy = accel_value * motion->dy;
 292
 293         apply_softening(accel, motion);
 294
 295         accel->last_dx = motion->dx;
 296         accel->last_dy = motion->dy;
 297
 298         accel->last_velocity = velocity;
 299 }
 300
 301 static void
 302 accelerator_destroy(struct weston_motion_filter *filter)
 303 {
 304         struct pointer_accelerator *accel =
 305                 (struct pointer_accelerator *) filter;
 306
 307         free(accel->trackers);
 308         free(accel);
 309 }
 310
 311 struct weston_motion_filter_interface accelerator_interface = {
 312         accelerator_filter,
 313         accelerator_destroy
 314 };
 315
 316 struct weston_motion_filter *
 317 create_pointer_accelator_filter(accel_profile_func_t profile)
 318 {
 319         struct pointer_accelerator *filter;
 320
 321         filter = malloc(sizeof *filter);
 322         if (filter == NULL)
 323                 return NULL;
 324
 325         filter->base.interface = &accelerator_interface;
 326         wl_list_init(&filter->base.link);
 327
 328         filter->profile = profile;
 329         filter->last_velocity = 0.0;
 330         filter->last_dx = 0;
 331         filter->last_dy = 0;
 332
 333         filter->trackers =
 334                 calloc(NUM_POINTER_TRACKERS, sizeof *filter->trackers);
 335         filter->cur_tracker = 0;
 336
 337         return &filter->base;
 338 }