gimpbezierstroke.c 19.9 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
/* The GIMP -- an image manipulation program
 * Copyright (C) 1995 Spencer Kimball and Peter Mattis
 *
 * gimpstroke.c
 * Copyright (C) 2002 Simon Budig  <simon@gimp.org>
 * 
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */


#include "config.h"

#include "glib-object.h"

#include "vectors-types.h"

#include "gimpanchor.h"
#include "gimpbezierstroke.h"

32
#define INPUT_RESOLUTION 256
33 34 35 36


/*  private variables  */

37
static GimpStrokeClass *parent_class = NULL;
38 39


40 41
/* local prototypes */

42 43
static void gimp_bezier_stroke_class_init (GimpBezierStrokeClass *klass);
static void gimp_bezier_stroke_init       (GimpBezierStroke      *bezier_stroke);
44

45
static void gimp_bezier_stroke_finalize   (GObject               *object);
46

47 48 49 50 51 52
static void gimp_bezier_coords_average    (GimpCoords            *a,
                                           GimpCoords            *b,
                                           GimpCoords            *ret_average);

static void gimp_bezier_coords_subdivide  (GimpCoords            *beziercoords,
                                           const gdouble          precision,
53
                                           GArray               **ret_coords);
54

55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92
static void gimp_bezier_coords_mix        (gdouble                amul,
                                           GimpCoords            *a,
                                           gdouble                bmul,
                                           GimpCoords            *b,
                                           GimpCoords            *ret_val);

static void gimp_bezier_coords_average    (GimpCoords            *a,
                                           GimpCoords            *b,
                                           GimpCoords            *ret_average);

static void gimp_bezier_coords_difference (GimpCoords          *a,
                                           GimpCoords          *b,
                                           GimpCoords          *ret_difference);

static void gimp_bezier_coords_scale      (gdouble                f,
                                           GimpCoords            *a,
                                           GimpCoords            *ret_multiply);

static void gimp_bezier_coords_subdivide  (GimpCoords            *beziercoords,
                                           const gdouble          precision,
                                           GArray               **ret_coords);

static void gimp_bezier_coords_subdivide2 (GimpCoords            *beziercoords,
                                           const gdouble          precision,
                                           GArray               **ret_coords,
                                           gint                   depth);

static gdouble  gimp_bezier_coords_scalarprod  (GimpCoords       *a,
                                                GimpCoords       *b);
                                              
static gdouble  gimp_bezier_coords_length      (GimpCoords       *a);
                                                                
static gdouble  gimp_bezier_coords_length2     (GimpCoords       *a);

static gboolean gimp_bezier_coords_is_straight (GimpCoords       *beziercoords,
                                                gdouble           precision);


93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120
GType
gimp_bezier_stroke_get_type (void)
{
  static GType bezier_stroke_type = 0;

  if (! bezier_stroke_type)
    {
      static const GTypeInfo bezier_stroke_info =
      {
        sizeof (GimpBezierStrokeClass),
        (GBaseInitFunc) NULL,
        (GBaseFinalizeFunc) NULL,
        (GClassInitFunc) gimp_bezier_stroke_class_init,
        NULL,           /* class_finalize */
        NULL,           /* class_data     */
        sizeof (GimpBezierStroke),
        0,              /* n_preallocs    */
        (GInstanceInitFunc) gimp_bezier_stroke_init,
      };

      bezier_stroke_type = g_type_register_static (GIMP_TYPE_STROKE,
                                                   "GimpBezierStroke", 
                                                   &bezier_stroke_info, 0);
    }

  return bezier_stroke_type;
}

121
static void
122
gimp_bezier_stroke_class_init (GimpBezierStrokeClass *klass)
123 124
{
  GObjectClass      *object_class;
125
  GimpStrokeClass   *stroke_class;
126

127
  object_class = G_OBJECT_CLASS (klass);
128
  stroke_class = GIMP_STROKE_CLASS (klass);
129 130 131 132

  parent_class = g_type_class_peek_parent (klass);

  object_class->finalize             = gimp_bezier_stroke_finalize;
133 134 135

  stroke_class->interpolate          = gimp_bezier_stroke_interpolate;

136
}
137 138 139 140 141 142 143

static void
gimp_bezier_stroke_init (GimpBezierStroke *bezier_stroke)
{
  /* pass */
};

144 145 146 147 148 149
static void
gimp_bezier_stroke_finalize (GObject *object)
{
  G_OBJECT_CLASS (parent_class)->finalize (object);
}

150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167

/* Bezier specific functions */

GimpStroke *
gimp_bezier_stroke_new (const GimpCoords *start)
{
  GimpBezierStroke *bezier_stroke;
  GimpStroke       *stroke;
  GimpAnchor       *anchor;

  bezier_stroke = g_object_new (GIMP_TYPE_BEZIER_STROKE, NULL);

  stroke = GIMP_STROKE (bezier_stroke);

  anchor = g_new0 (GimpAnchor, 1);
  anchor->position.x = start->x;
  anchor->position.y = start->y;
  anchor->position.pressure = 1;
168 169 170
  anchor->position.xtilt = 0.5;
  anchor->position.ytilt = 0.5;
  anchor->position.wheel = 0.5;
171 172 173

  g_printerr ("Adding at %f, %f\n", start->x, start->y);
  
174
  anchor->type = GIMP_HANDLE_ANCHOR;
175
  anchor->selected = TRUE;
176 177 178 179 180 181

  stroke->anchors = g_list_append (stroke->anchors, anchor);
  return stroke;
}


182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202
GimpStroke *
gimp_bezier_stroke_new_from_coords (const GimpCoords *coords,
                                    const gint        ncoords)
{
  GimpBezierStroke *bezier_stroke;
  GimpStroke       *stroke = NULL;
  GimpAnchor       *last_anchor;

  gint              count;

  if (ncoords >= 1)
    {
      stroke = gimp_bezier_stroke_new (coords);
      bezier_stroke = GIMP_BEZIER_STROKE (stroke);
      last_anchor = (GimpAnchor *) (stroke->anchors->data);

      count = 1;
      while (count < ncoords)
        {
          last_anchor = gimp_bezier_stroke_extend (bezier_stroke,
                                                   &(coords[count]),
203 204
                                                   last_anchor,
                                                   EXTEND_SIMPLE);
205 206 207 208 209 210
        }
    }
  return stroke;
}


211
GimpAnchor *
212 213 214 215
gimp_bezier_stroke_extend (GimpBezierStroke     *bezier_stroke,
                           const GimpCoords     *coords,
                           GimpAnchor           *neighbor,
                           GimpVectorExtendMode  extend_mode)
216
{
217
  GimpAnchor       *anchor=NULL;
218 219
  GimpStroke       *stroke;
  GList            *listneighbor;
220
  gint              loose_end, control_count;
221 222 223 224 225 226 227

  g_return_val_if_fail (GIMP_IS_BEZIER_STROKE (bezier_stroke), NULL);
  g_return_val_if_fail ((neighbor != NULL), NULL);

  stroke = GIMP_STROKE (bezier_stroke);

  loose_end = 0;
228 229 230 231 232 233
  listneighbor = g_list_last (stroke->anchors);
  if (listneighbor->data == neighbor)
    {
      loose_end = 1;
    }
  else
234 235
    {
      listneighbor = g_list_first (stroke->anchors);
236
      if (listneighbor->data == neighbor)
237
        {
238
          loose_end = -1;
239 240 241
        }
      else
        {
242 243
          listneighbor = NULL;
          loose_end = 0;
244 245 246 247 248
        }
    }

  if (loose_end)
    {
249
      /* We have to detect the type of the point to add... */
250

251
      control_count = 0;
252

253
      if (loose_end == 1)
254
        {
255
          while (listneighbor &&
256
                 ((GimpAnchor *) listneighbor->data)->type == GIMP_HANDLE_CONTROL)
257 258 259 260
            {
              control_count++;
              listneighbor = listneighbor->prev;
            }
261 262 263
        }
      else
        {
264
          while (listneighbor &&
265
                 ((GimpAnchor *) listneighbor->data)->type == GIMP_HANDLE_CONTROL)
266 267 268 269
            {
              control_count++;
              listneighbor = listneighbor->next;
            }
270 271
        }

272
      switch (extend_mode)
273
        {
274 275 276 277 278 279 280 281 282 283 284 285
        case EXTEND_SIMPLE:
          anchor = g_new0 (GimpAnchor, 1);
          anchor->position.x = coords->x;
          anchor->position.y = coords->y;
          anchor->position.pressure = 1.0;
          anchor->position.xtilt = 0.5;
          anchor->position.ytilt = 0.5;
          anchor->position.wheel = 0.5;

          anchor->selected = FALSE;

          switch (control_count)
286
            {
287 288
            case 0:
            case 1:
289
              anchor->type = GIMP_HANDLE_CONTROL;
290 291
              break;
            case 2:
292
              anchor->type = GIMP_HANDLE_ANCHOR;
293 294 295 296
              break;
            default:
              g_printerr ("inconsistent bezier curve: "
                          "%d successive control handles", control_count);
297
            }
298

299 300
          g_printerr ("Extending at %f, %f, type %d\n",
                      coords->x, coords->y, anchor->type);
301

302 303
          if (loose_end == 1)
            stroke->anchors = g_list_append (stroke->anchors, anchor);
304

305 306 307
          if (loose_end == -1)
            stroke->anchors = g_list_prepend (stroke->anchors, anchor);
          break;
308

309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339
        case EXTEND_EDITABLE:
          switch (control_count)
            {
            case 0:
              neighbor = gimp_bezier_stroke_extend (bezier_stroke,
                                                    &(neighbor->position),
                                                    neighbor,
                                                    EXTEND_SIMPLE);
            case 1:
              neighbor = gimp_bezier_stroke_extend (bezier_stroke,
                                                    coords,
                                                    neighbor,
                                                    EXTEND_SIMPLE);
            case 2:
              neighbor = gimp_bezier_stroke_extend (bezier_stroke,
                                                    coords,
                                                    neighbor,
                                                    EXTEND_SIMPLE);

              gimp_stroke_anchor_select (stroke, neighbor, TRUE);

              anchor = gimp_bezier_stroke_extend (bezier_stroke,
                                                  coords,
                                                  neighbor,
                                                  EXTEND_SIMPLE);
              break;
            default:
              g_printerr ("inconsistent bezier curve: "
                          "%d successive control handles", control_count);
            }
        }
340 341 342 343
      return anchor;
    }
  else
    return NULL;   /* No loose end to add an anchor to... */
344 345 346

}

347

348
GArray *
349 350 351 352
gimp_bezier_stroke_interpolate (const GimpStroke  *stroke,
                                gdouble            precision,
                                gboolean          *ret_closed)
{
353
  GArray           *ret_coords;
354 355
  GimpAnchor       *anchor;
  GList            *anchorlist;
356 357
  GimpCoords        segmentcoords[4];
  gint              count;
358 359 360 361

  g_return_val_if_fail (GIMP_IS_BEZIER_STROKE (stroke), NULL);
  g_return_val_if_fail (ret_closed != NULL, NULL);
  
362 363
  ret_coords = g_array_new (FALSE, FALSE, sizeof (GimpCoords));

364 365
  count = 0;

366
  for (anchorlist = stroke->anchors;
367
       anchorlist && ((GimpAnchor *) anchorlist->data)->type != GIMP_HANDLE_ANCHOR;
368 369 370
       anchorlist = g_list_next (anchorlist));

  for ( ; anchorlist; anchorlist = g_list_next (anchorlist))
371 372 373
    {
      anchor = anchorlist->data;

374
      segmentcoords[count] = anchor->position;
375
      count++;
376 377 378 379 380 381 382

      if (count == 4)
        {
          gimp_bezier_coords_subdivide (segmentcoords, precision, &ret_coords);
          segmentcoords[0] = segmentcoords[3];
          count = 1;
        }
383 384
    }

385 386
  /* ret_coords = g_array_append_val (ret_coords, anchor->position); */

387 388 389 390 391 392
  *ret_closed    = FALSE;

  return ret_coords;
}


393 394
/* local helper functions for bezier subdivision */

395 396 397 398 399 400 401 402 403 404 405 406
/*   amul * a + bmul * b   */

static void
gimp_bezier_coords_mix (gdouble amul,
                        GimpCoords *a,
                        gdouble bmul,
                        GimpCoords *b,
                        GimpCoords *ret_val)
{
  if (b)
    {
      ret_val->x        = amul * a->x        + bmul * b->x ;
407 408 409 410 411
      ret_val->y        = amul * a->y        + bmul * b->y ;
      ret_val->pressure = amul * a->pressure + bmul * b->pressure ;
      ret_val->xtilt    = amul * a->xtilt    + bmul * b->xtilt ;
      ret_val->ytilt    = amul * a->ytilt    + bmul * b->ytilt ;
      ret_val->wheel    = amul * a->wheel    + bmul * b->wheel ;
412 413 414 415 416 417 418 419 420 421 422 423 424 425 426
    }
  else
    {
      ret_val->x        = amul * a->x;
      ret_val->y        = amul * a->y;
      ret_val->pressure = amul * a->pressure;
      ret_val->xtilt    = amul * a->xtilt;
      ret_val->ytilt    = amul * a->ytilt;
      ret_val->wheel    = amul * a->wheel;
    }
}

                        
/*    (a+b)/2   */

427 428 429 430 431
static void
gimp_bezier_coords_average (GimpCoords *a,
                            GimpCoords *b,
                            GimpCoords *ret_average)
{
432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508
  gimp_bezier_coords_mix (0.5, a, 0.5, b, ret_average);
}


/* a - b */

static void
gimp_bezier_coords_difference (GimpCoords *a,
                               GimpCoords *b,
                               GimpCoords *ret_difference)
{
  gimp_bezier_coords_mix (1.0, a, -1.0, b, ret_difference);
}


/* a * f = ret_product */

static void
gimp_bezier_coords_scale (gdouble     f,
                          GimpCoords *a,
                          GimpCoords *ret_multiply)
{
  gimp_bezier_coords_mix (f, a, 0.0, NULL, ret_multiply);
}


/* local helper for measuring the scalarproduct of two gimpcoords. */

static gdouble
gimp_bezier_coords_scalarprod (GimpCoords *a,
                               GimpCoords *b)
{
  return (a->x        * b->x        +
          a->y        * b->y        +
          a->pressure * b->pressure +
          a->xtilt    * b->xtilt    +
          a->ytilt    * b->ytilt    +
          a->wheel    * b->wheel   );
}


/*
 * The "lenght" of the gimpcoord.
 * Applies a metric that increases the weight on the
 * pressure/xtilt/ytilt/wheel to ensure proper interpolation
 */

static gdouble
gimp_bezier_coords_length2 (GimpCoords *a)
{
  GimpCoords upscaled_a;

  upscaled_a.x        = a->x;
  upscaled_a.y        = a->y;
  upscaled_a.pressure = a->pressure * INPUT_RESOLUTION;
  upscaled_a.xtilt    = a->xtilt    * INPUT_RESOLUTION;
  upscaled_a.ytilt    = a->ytilt    * INPUT_RESOLUTION;
  upscaled_a.wheel    = a->wheel    * INPUT_RESOLUTION;
  return (gimp_bezier_coords_scalarprod (&upscaled_a, &upscaled_a));
}


static gdouble
gimp_bezier_coords_length (GimpCoords *a)
{
  return (sqrt (gimp_bezier_coords_length2 (a)));
}


/*
 * a helper function that determines if a bezier segment is "straight
 * enough" to be approximated by a line.
 * 
 * Needs four GimpCoords in an array.
 */

static gboolean
509 510
gimp_bezier_coords_is_straight (GimpCoords *beziercoords,
                                gdouble precision)
511 512 513 514 515 516 517 518
{
  GimpCoords line, tan1, tan2, d1, d2;
  gdouble l2, s1, s2;

  gimp_bezier_coords_difference (&(beziercoords[3]),
                                 &(beziercoords[0]),
                                 &line);

519
  if (gimp_bezier_coords_length2 (&line) < precision * precision)
520 521 522 523 524 525 526
    {
      gimp_bezier_coords_difference (&(beziercoords[1]),
                                     &(beziercoords[0]),
                                     &tan1);
      gimp_bezier_coords_difference (&(beziercoords[2]),
                                     &(beziercoords[3]),
                                     &tan2);
527 528
      if ((gimp_bezier_coords_length2 (&tan1) < precision * precision) &&
          (gimp_bezier_coords_length2 (&tan2) < precision * precision))
529 530 531 532 533
        {
          return 1;
        }
      else
        {
534 535
          /* Tangents are too big for the small baseline */
          /* g_printerr ("Zu grosse Tangenten bei zu kleiner Basislinie\n"); */
536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552
          return 0;
        }
    }
  else
    {
      gimp_bezier_coords_difference (&(beziercoords[1]),
                                     &(beziercoords[0]),
                                     &tan1);
      gimp_bezier_coords_difference (&(beziercoords[2]),
                                     &(beziercoords[0]),
                                     &tan2);

      l2 = gimp_bezier_coords_scalarprod (&line, &line);
      s1 = gimp_bezier_coords_scalarprod (&line, &tan1) / l2;
      s2 = gimp_bezier_coords_scalarprod (&line, &tan2) / l2;

      if (s1 < 0 || s1 > 1 || s2 < 0 || s2 > 1 || s2 < s1)
553 554 555 556 557
        {
          /* The tangents get projected outside the baseline */
          /* g_printerr ("Tangenten projezieren sich ausserhalb der Basisline\n"); */
          return 0;
        }
558 559 560 561

      gimp_bezier_coords_mix (1.0, &tan1, - s1, &line, &d1);
      gimp_bezier_coords_mix (1.0, &tan2, - s2, &line, &d2);

562 563
      if ((gimp_bezier_coords_length2 (&d1) > precision * precision) ||
          (gimp_bezier_coords_length2 (&d2) > precision * precision))
564 565 566 567 568
        {
          /* The control points are too far away from the baseline */
          /* g_printerr ("Zu grosser Abstand zur Basislinie\n"); */
          return 0;
        }
569 570 571

      return 1;
    }
572 573 574 575
}


static void
576 577 578 579
gimp_bezier_coords_subdivide2 (GimpCoords     *beziercoords,
                               const gdouble   precision,
                               GArray        **ret_coords,
                               gint            depth)
580 581 582 583 584 585 586 587 588 589 590
{
  /*
   * beziercoords has to contain four GimpCoords with the four control points
   * of the bezier segment. We subdivide it at the parameter 0.5.
   */

  GimpCoords subdivided[8];

  subdivided[0] = beziercoords[0];
  subdivided[6] = beziercoords[3];

591 592
  if (!depth) g_printerr ("Hit rekursion depth limit!\n");

593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620
  gimp_bezier_coords_average (&(beziercoords[0]), &(beziercoords[1]),
                              &(subdivided[1]));

  gimp_bezier_coords_average (&(beziercoords[1]), &(beziercoords[2]),
                              &(subdivided[7]));

  gimp_bezier_coords_average (&(beziercoords[2]), &(beziercoords[3]),
                              &(subdivided[5]));

  gimp_bezier_coords_average (&(subdivided[1]), &(subdivided[7]),
                              &(subdivided[2]));

  gimp_bezier_coords_average (&(subdivided[7]), &(subdivided[5]),
                              &(subdivided[4]));

  gimp_bezier_coords_average (&(subdivided[2]), &(subdivided[4]),
                              &(subdivided[3]));

  /*
   * We now have the coordinates of the two bezier segments in
   * subdivided [0-3] and subdivided [3-6]
   */

  /*
   * Here we need to check, if we have sufficiently subdivided, i.e.
   * if the stroke is sufficiently close to a straight line.
   */

621 622
  if (!depth || gimp_bezier_coords_is_straight (&(subdivided[0]),
                                                precision)) /* 1st half */
623
    {
624
      *ret_coords = g_array_append_vals (*ret_coords, &(subdivided[0]), 3);
625 626 627
    }
  else
    {
628 629
      gimp_bezier_coords_subdivide2 (&(subdivided[0]), precision,
                                     ret_coords, depth-1);
630 631
    }

632 633
  if (!depth || gimp_bezier_coords_is_straight (&(subdivided[3]),
                                                precision)) /* 2nd half */
634
    {
635
      *ret_coords = g_array_append_vals (*ret_coords, &(subdivided[3]), 3);
636 637 638
    }
  else
    {
639 640
      gimp_bezier_coords_subdivide2 (&(subdivided[3]), precision,
                                     ret_coords, depth-1);
641 642
    }
  
643
  /* g_printerr ("gimp_bezier_coords_subdivide end: %d entries\n", (*ret_coords)->len); */
644
}
645 646 647 648 649 650 651 652 653 654


static void
gimp_bezier_coords_subdivide (GimpCoords     *beziercoords,
                              const gdouble   precision,
                              GArray        **ret_coords)
{
  gimp_bezier_coords_subdivide2 (beziercoords, precision, ret_coords, 10);
}