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