clutter/clutter-bezier.c

   1 /*
   2  * Clutter.
   3  *
   4  * An OpenGL based 'interactive canvas' library.
   5  *
   6  * Authored By Tomas Frydrych  <tf@openedhand.com>
   7  *
   8  * Copyright (C) 2007 OpenedHand
   9  *
  10  * This library is free software; you can redistribute it and/or
  11  * modify it under the terms of the GNU Lesser General Public
  12  * License as published by the Free Software Foundation; either
  13  * version 2 of the License, or (at your option) any later version.
  14  *
  15  * This library is distributed in the hope that it will be useful,
  16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18  * Lesser General Public License for more details.
  19  *
  20  * You should have received a copy of the GNU Lesser General Public
  21  * License along with this library. If not, see <http://www.gnu.org/licenses/>.
  22  */
  23
  24 #include <glib.h>
  25 #include <string.h>
  26 #include "clutter-bezier.h"
  27 #include "clutter-debug.h"
  28
  29 /*
  30  * We have some experimental code here to allow for constant velocity
  31  * movement of actors along the bezier path, this macro enables it.
  32  */
  33 #undef CBZ_L2T_INTERPOLATION
  34
  35 /****************************************************************************
  36  * ClutterBezier -- represenation of a cubic bezier curve                   *
  37  * (private; a building block for the public bspline object)                *
  38  ****************************************************************************/
  39
  40 /*
  41  * The t parameter of the bezier is from interval <0,1>, so we can use
  42  * 14.18 format and special multiplication functions that preserve
  43  * more of the least significant bits but would overflow if the value
  44  * is > 1
  45  */
  46 #define CBZ_T_Q 18
  47 #define CBZ_T_ONE (1 << CBZ_T_Q)
  48 #define CBZ_T_MUL(x,y) ((((x) >> 3) * ((y) >> 3)) >> 12)
  49 #define CBZ_T_POW2(x) CBZ_T_MUL (x, x)
  50 #define CBZ_T_POW3(x) CBZ_T_MUL (CBZ_T_POW2 (x), x)
  51 #define CBZ_T_DIV(x,y) ((((x) << 9)/(y)) << 9)
  52
  53 /*
  54  * Constants for sampling of the bezier
  55  */
  56 #define CBZ_T_SAMPLES 128
  57 #define CBZ_T_STEP (CBZ_T_ONE / CBZ_T_SAMPLES)
  58 #define CBZ_L_STEP (CBZ_T_ONE / CBZ_T_SAMPLES)
  59
  60 typedef gint32 _FixedT;
  61
  62 /*
  63  * This is a private type representing a single cubic bezier
  64  */
  65 struct _ClutterBezier
  66 {
  67   /*
  68    * bezier coefficients -- these are calculated using multiplication and
  69    * addition from integer input, so these are also integers
  70    */
  71   gint ax;
  72   gint bx;
  73   gint cx;
  74   gint dx;
  75
  76   gint ay;
  77   gint by;
  78   gint cy;
  79   gint dy;
  80
  81   /* length of the bezier */
  82   guint length;
  83
  84 #ifdef CBZ_L2T_INTERPOLATION
  85   /*
  86    * coefficients for the L -> t bezier; these are calculated from fixed
  87    * point input, and more specifically numbers that have been normalised
  88    * to fit <0,1>, so these are also fixed point, and we can used the
  89    * _FixedT type here.
  90    */
  91   _FixedT La;
  92   _FixedT Lb;
  93   _FixedT Lc;
  94   /*  _FixedT Ld; == 0 */
  95 #endif
  96 };
  97
  98 ClutterBezier *
  99 _clutter_bezier_new (void)
 100 {
 101   return g_slice_new0 (ClutterBezier);
 102 }
 103
 104 void
 105 _clutter_bezier_free (ClutterBezier * b)
 106 {
 107   if (G_LIKELY (b))
 108     {
 109       g_slice_free (ClutterBezier, b);
 110     }
 111 }
 112
 113 ClutterBezier *
 114 _clutter_bezier_clone_and_move (const ClutterBezier *b, gint x, gint y)
 115 {
 116   ClutterBezier * b2 = _clutter_bezier_new ();
 117   memcpy (b2, b, sizeof (ClutterBezier));
 118
 119   b2->dx += x;
 120   b2->dy += y;
 121
 122   return b2;
 123 }
 124
 125 #ifdef CBZ_L2T_INTERPOLATION
 126 /*
 127  * L is relative advance along the bezier curve from interval <0,1>
 128  */
 129 static _FixedT
 130 _clutter_bezier_L2t (const ClutterBezier *b, _FixedT L)
 131 {
 132   _FixedT t = CBZ_T_MUL (b->La, CBZ_T_POW3(L))
 133     +  CBZ_T_MUL (b->Lb, CBZ_T_POW2(L))
 134     +  CBZ_T_MUL (b->Lc, L);
 135
 136   if (t > CBZ_T_ONE)
 137     t = CBZ_T_ONE;
 138   else if (t < 0)
 139     t = 0;
 140
 141   return t;
 142 }
 143 #endif
 144
 145 static gint
 146 _clutter_bezier_t2x (const ClutterBezier * b, _FixedT t)
 147 {
 148   /*
 149    * NB -- the int coefficients can be at most 8192 for the multiplication
 150    * to work in this fashion due to the limits of the 14.18 fixed.
 151    */
 152   return ((b->ax*CBZ_T_POW3(t) + b->bx*CBZ_T_POW2(t) + b->cx*t) >> CBZ_T_Q)
 153     + b->dx;
 154 }
 155
 156 static gint
 157 _clutter_bezier_t2y (const ClutterBezier * b, _FixedT t)
 158 {
 159   /*
 160    * NB -- the int coefficients can be at most 8192 for the multiplication
 161    * to work in this fashion due to the limits of the 14.18 fixed.
 162    */
 163   return ((b->ay*CBZ_T_POW3(t) + b->by*CBZ_T_POW2(t) + b->cy*t) >> CBZ_T_Q)
 164     + b->dy;
 165 }
 166
 167 /*
 168  * Advances along the bezier to relative length L and returns the coordinances
 169  * in knot
 170  */
 171 void
 172 _clutter_bezier_advance (const ClutterBezier *b, gint L, ClutterKnot * knot)
 173 {
 174 #ifdef CBZ_L2T_INTERPOLATION
 175   _FixedT t = clutter_bezier_L2t (b, L);
 176 #else
 177   _FixedT t = L;
 178 #endif
 179
 180   knot->x = _clutter_bezier_t2x (b, t);
 181   knot->y = _clutter_bezier_t2y (b, t);
 182
 183   CLUTTER_NOTE (MISC, "advancing to relative pt %f: t %f, {%d,%d}",
 184                 (double) L / (double) CBZ_T_ONE,
 185                 (double) t / (double) CBZ_T_ONE,
 186                 knot->x, knot->y);
 187 }
 188
 189 void
 190 _clutter_bezier_init (ClutterBezier *b,
 191                      gint x_0, gint y_0,
 192                      gint x_1, gint y_1,
 193                      gint x_2, gint y_2,
 194                      gint x_3, gint y_3)
 195 {
 196   _FixedT t;
 197   int i;
 198   int xp = x_0;
 199   int yp = y_0;
 200   _FixedT length [CBZ_T_SAMPLES + 1];
 201
 202 #ifdef CBZ_L2T_INTERPOLATION
 203   int j, k;
 204   _FixedT L;
 205   _FixedT t_equalized [CBZ_T_SAMPLES + 1];
 206 #endif
 207
 208 #if 0
 209   g_debug ("Initializing bezier at {{%d,%d},{%d,%d},{%d,%d},{%d,%d}}",
 210            x0, y0, x1, y1, x2, y2, x3, y3);
 211 #endif
 212
 213   b->dx = x_0;
 214   b->dy = y_0;
 215
 216   b->cx = 3 * (x_1 - x_0);
 217   b->cy = 3 * (y_1 - y_0);
 218
 219   b->bx = 3 * (x_2 - x_1) - b->cx;
 220   b->by = 3 * (y_2 - y_1) - b->cy;
 221
 222   b->ax = x_3 - 3 * x_2 + 3 * x_1 - x_0;
 223   b->ay = y_3 - 3 * y_2 + 3 * y_1 - y_0;
 224
 225 #if 0
 226   g_debug ("Cooeficients {{%d,%d},{%d,%d},{%d,%d},{%d,%d}}",
 227            b->ax, b->ay, b->bx, b->by, b->cx, b->cy, b->dx, b->dy);
 228 #endif
 229
 230   /*
 231    * Because of the way we do the multiplication in bezeir_t2x,y
 232    * these coefficients need to be at most 0x1fff; this should be the case,
 233    * I think, but have added this warning to catch any problems -- if it
 234    * triggers, we need to change those two functions a bit.
 235    */
 236   if (b->ax > 0x1fff || b->bx > 0x1fff || b->cx > 0x1fff)
 237     g_warning ("Calculated coefficents will result in multiplication "
 238                "overflow in clutter_bezier_t2x and clutter_bezier_t2y.");
 239
 240   /*
 241    * Sample the bezier with CBZ_T_SAMPLES and calculate length at
 242    * each point.
 243    *
 244    * We are working with integers here, so we use the fast sqrti function.
 245    */
 246   length[0] = 0;
 247
 248   for (t = CBZ_T_STEP, i = 1; i <= CBZ_T_SAMPLES; ++i, t += CBZ_T_STEP)
 249     {
 250       int x = _clutter_bezier_t2x (b, t);
 251       int y = _clutter_bezier_t2y (b, t);
 252
 253       guint l = cogl_sqrti ((y - yp)*(y - yp) + (x - xp)*(x - xp));
 254
 255       l += length[i-1];
 256
 257       length[i] = l;
 258
 259       xp = x;
 260       yp = y;
 261     }
 262
 263   b->length = length[CBZ_T_SAMPLES];
 264
 265 #if 0
 266   g_debug ("length %d", b->length);
 267 #endif
 268
 269 #ifdef CBZ_L2T_INTERPOLATION
 270   /*
 271    * Now normalize the length values, converting them into _FixedT
 272    */
 273   for (i = 0; i <= CBZ_T_SAMPLES; ++i)
 274     {
 275       length[i] = (length[i] << CBZ_T_Q) / b->length;
 276     }
 277
 278   /*
 279    * Now generate a L -> t table such that the L will equidistant
 280    * over <0,1>
 281    */
 282   t_equalized[0] = 0;
 283
 284   for (i = 1, j = 1, L = CBZ_L_STEP; i < CBZ_T_SAMPLES; ++i, L += CBZ_L_STEP)
 285     {
 286       _FixedT l1, l2;
 287       _FixedT d1, d2, d;
 288       _FixedT t1, t2;
 289
 290       /* find the band for our L */
 291       for (k = j; k < CBZ_T_SAMPLES; ++k)
 292         {
 293           if (L < length[k])
 294             break;
 295         }
 296
 297       /*
 298        * Now we know that L is from (length[k-1],length[k]>
 299        * We remember k-1 in order not to have to iterate over the
 300        * whole length array in the next iteration of the main loop
 301        */
 302       j = k - 1;
 303
 304       /*
 305        * Now interpolate equlised t as a weighted average
 306        */
 307       l1 = length[k-1];
 308       l2 = length[k];
 309       d1 = l2 - L;
 310       d2 = L - l1;
 311       d = l2 - l1;
 312       t1 = (k - 1) * CBZ_T_STEP;
 313       t2 = k * CBZ_T_STEP;
 314
 315       t_equalized[i] = (t1*d1 + t2*d2)/d;
 316
 317       if (t_equalized[i] < t_equalized[i-1])
 318         g_debug ("wrong t: L %f, l1 %f, l2 %f, t1 %f, t2 %f",
 319                  (double) (L)/(double)CBZ_T_ONE,
 320                  (double) (l1)/(double)CBZ_T_ONE,
 321                  (double) (l2)/(double)CBZ_T_ONE,
 322                  (double) (t1)/(double)CBZ_T_ONE,
 323                  (double) (t2)/(double)CBZ_T_ONE);
 324
 325     }
 326
 327   t_equalized[CBZ_T_SAMPLES] = CBZ_T_ONE;
 328
 329   /* We now fit a bezier -- at this stage, do a single fit through our values
 330    * at 0, 1/3, 2/3 and 1
 331    *
 332    * FIXME -- do we need to  use a better fitting approach to choose the best
 333    * beziere. The actual curve we acquire this way is not too bad shapwise,
 334    * but (probably due to rounding errors) the resulting curve no longer
 335    * satisfies the necessary condition that for L2 > L1, t2 > t1, which
 336    * causes oscilation.
 337    */
 338
 339 #if 0
 340   /*
 341    * These are the control points we use to calculate the curve coefficients
 342    * for bezier t(L); these are not needed directly, but are implied in the
 343    * calculations below.
 344    *
 345    * (p0 is 0,0, and p3 is 1,1)
 346    */
 347   p1 = (18 * t_equalized[CBZ_T_SAMPLES/3] -
 348         9 * t_equalized[2*CBZ_T_SAMPLES/3] +
 349         2 << CBZ_T_Q) / 6;
 350
 351   p2 = (18 * t_equalized[2*CBZ_T_SAMPLES/3] -
 352         9 * t_equalized[CBZ_T_SAMPLES/3] -
 353         (5 << CBZ_T_Q)) / 6;
 354 #endif
 355
 356   b->Lc = (18 * t_equalized[CBZ_T_SAMPLES/3] -
 357            9 * t_equalized[2*CBZ_T_SAMPLES/3] +
 358            (2 << CBZ_T_Q)) >> 1;
 359
 360   b->Lb = (36 * t_equalized[2*CBZ_T_SAMPLES/3] -
 361            45 * t_equalized[CBZ_T_SAMPLES/3] -
 362            (9 << CBZ_T_Q)) >> 1;
 363
 364   b->La = ((27 * (t_equalized[CBZ_T_SAMPLES/3] -
 365                  t_equalized[2*CBZ_T_SAMPLES/3]) +
 366             (7 << CBZ_T_Q)) >> 1) + CBZ_T_ONE;
 367
 368   g_debug ("t(1/3) %f, t(2/3) %f",
 369            (double)t_equalized[CBZ_T_SAMPLES/3]/(double)CBZ_T_ONE,
 370            (double)t_equalized[2*CBZ_T_SAMPLES/3]/(double)CBZ_T_ONE);
 371
 372   g_debug ("L -> t coefficients: %f, %f, %f",
 373            (double)b->La/(double)CBZ_T_ONE,
 374            (double)b->Lb/(double)CBZ_T_ONE,
 375            (double)b->Lc/(double)CBZ_T_ONE);
 376
 377
 378   /*
 379    * For debugging, you can load these values into a spreadsheet and graph
 380    * them to see how well the approximation matches the data
 381    */
 382   for (i = 0; i < CBZ_T_SAMPLES; ++i)
 383     {
 384       g_print ("%f, %f, %f\n",
 385                (double)(i*CBZ_T_STEP)/(double)CBZ_T_ONE,
 386                (double)(t_equalized[i])/(double)CBZ_T_ONE,
 387                (double)(clutter_bezier_L2t(b,i*CBZ_T_STEP))/(double)CBZ_T_ONE);
 388     }
 389 #endif
 390 }
 391
 392 /*
 393  * Moves a control point at indx to location represented by knot
 394  */
 395 void
 396 _clutter_bezier_adjust (ClutterBezier * b, ClutterKnot * knot, guint indx)
 397 {
 398   guint x[4], y[4];
 399
 400   g_assert (indx < 4);
 401
 402   x[0] = b->dx;
 403   y[0] = b->dy;
 404
 405   x[1] = b->cx / 3 + x[0];
 406   y[1] = b->cy / 3 + y[0];
 407
 408   x[2] = b->bx / 3 + b->cx + x[1];
 409   y[2] = b->by / 3 + b->cy + y[1];
 410
 411   x[3] = b->ax + x[0] + b->cx + b->bx;
 412   y[3] = b->ay + y[0] + b->cy + b->by;
 413
 414   x[indx] = knot->x;
 415   y[indx] = knot->y;
 416
 417   _clutter_bezier_init (b, x[0], y[0], x[1], y[1], x[2], y[2], x[3], y[3]);
 418 }
 419
 420 guint
 421 _clutter_bezier_get_length (const ClutterBezier *b)
 422 {
 423   return b->length;
 424 }