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