cpml/cpml-primitive.c

   1 /* CPML - Cairo Path Manipulation Library
   2  * Copyright (C) 2008,2009,2010  Nicola Fontana <ntd at entidi.it>
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Lesser General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Lesser General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser General Public
  15  * License along with this library; if not, write to the
  16  * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  17  * Boston, MA  02110-1301, USA.
  18  */
  19
  20
  21 /**
  22  * SECTION:cpml-primitive
  23  * @Section_Id:CpmlPrimitive
  24  * @title: CpmlPrimitive
  25  * @short_description: Basic component of segments
  26  *
  27  * A primitive is an atomic geometric element found inside #CpmlSegment.
  28  * The available primitives are the same defined by #cairo_path_data_type_t
  29  * with the additional #CPML_ARC type (check #CpmlPrimitiveType
  30  * for further information) and without #CPML_MOVE as it is not
  31  * considered a primitive and it is managed in different way: the move-to
  32  * primitives are only used to define the origin of a segment.
  33  **/
  34
  35 /**
  36  * CpmlPrimitiveType:
  37  *
  38  * This is another name for #cairo_path_data_type_t type. Although
  39  * phisically they are the same struct, #CpmlPrimitiveType conceptually
  40  * embodies an important difference: it can be used to specify the
  41  * special #CPML_ARC primitive. This is not a native cairo
  42  * primitive and having two different types is a good way to make clear
  43  * when a function expect or not embedded arc-to primitives.
  44  **/
  45
  46 /**
  47  * CpmlPrimitive:
  48  * @segment: the source #CpmlSegment
  49  * @org: a pointer to the first point of the primitive
  50  * @data: the array of the path data, prepended by the header
  51  *
  52  * As for #CpmlSegment, also the primitive is unobtrusive. This
  53  * means CpmlPrimitive does not include any coordinates but instead
  54  * keeps pointers to the original segment (and, by transition, to
  55  * the underlying #CpmlPath struct).
  56  **/
  57
  58 /**
  59  * CPML_MOVE:
  60  *
  61  * An operation that denotes a current point movement internally used to
  62  * keep track of the starting point of a primitive.
  63  * It is equivalent to the %CAIRO_PATH_MOVE_TO cairo constant.
  64  **/
  65
  66
  67 #include "cpml-internal.h"
  68 #include "cpml-extents.h"
  69 #include "cpml-segment.h"
  70 #include "cpml-primitive.h"
  71 #include "cpml-primitive-private.h"
  72 #include "cpml-line.h"
  73 #include "cpml-arc.h"
  74 #include "cpml-curve.h"
  75 #include "cpml-close.h"
  76 #include <string.h>
  77 #include <stdio.h>
  78
  79
  80 static const _CpmlPrimitiveClass *
  81                 get_class_from_type     (CpmlPrimitiveType        type);
  82 static const _CpmlPrimitiveClass *
  83                 get_class               (const CpmlPrimitive     *primitive);
  84 static void     dump_cairo_point        (const cairo_path_data_t *path_data);
  85
  86
  87 /**
  88  * cpml_primitive_type_get_n_points:
  89  * @type: a primitive type
  90  *
  91  * Gets the number of points required to identify the @type primitive.
  92  *
  93  * Returns: the number of points or %0 on errors
  94  **/
  95 size_t
  96 cpml_primitive_type_get_n_points(CpmlPrimitiveType type)
  97 {
  98     const _CpmlPrimitiveClass *class_data = get_class_from_type(type);
  99
 100     if (class_data == NULL)
 101         return 0;
 102
 103     return class_data->n_points;
 104 }
 105
 106 /**
 107  * cpml_primitive_from_segment:
 108  * @primitive: the destination #CpmlPrimitive struct
 109  * @segment: the source segment
 110  *
 111  * Initializes @primitive to the first primitive of @segment.
 112  *
 113  * Returns: @primitive
 114  **/
 115 CpmlPrimitive *
 116 cpml_primitive_from_segment(CpmlPrimitive *primitive, CpmlSegment *segment)
 117 {
 118     primitive->segment = segment;
 119
 120     /* The first element of a CpmlSegment is always a CPML_MOVE,
 121      * as ensured by cpml_segment_from_cairo() and by the browsing APIs,
 122      * so the origin is in the second data item */
 123     primitive->org = &segment->data[1];
 124
 125     /* Also, the segment APIs ensure that @segment is prepended by
 126      * only one CPML_MOVE */
 127     primitive->data = segment->data + segment->data[0].header.length;
 128
 129     return primitive;
 130 }
 131
 132 /**
 133  * cpml_primitive_copy:
 134  * @primitive: the destination #CpmlPrimitive
 135  * @src: the source #CpmlPrimitive
 136  *
 137  * Copies @src in @primitive. This is a shallow copy: the internal fields
 138  * of @primitive refer to the same memory as the original @src primitive.
 139  **/
 140 void
 141 cpml_primitive_copy(CpmlPrimitive *primitive, const CpmlPrimitive *src)
 142 {
 143     memcpy(primitive, src, sizeof(CpmlPrimitive));
 144 }
 145
 146 /**
 147  * cpml_primitive_reset:
 148  * @primitive: a #CpmlPrimitive
 149  *
 150  * Resets @primitive so it refers to the first primitive of the
 151  * source segment.
 152  **/
 153 void
 154 cpml_primitive_reset(CpmlPrimitive *primitive)
 155 {
 156     cpml_primitive_from_segment(primitive, primitive->segment);
 157 }
 158
 159 /**
 160  * cpml_primitive_next:
 161  * @primitive: a #CpmlPrimitive
 162  *
 163  *
 164  * Changes @primitive so it refers to the next primitive on the
 165  * source segment. If there are no more primitives, @primitive is
 166  * not changed and 0 is returned.
 167  *
 168  * Returns: 1 on success, 0 if no next primitive found or errors
 169  **/
 170 cairo_bool_t
 171 cpml_primitive_next(CpmlPrimitive *primitive)
 172 {
 173     cairo_path_data_t *new_data;
 174
 175     new_data = primitive->data + primitive->data->header.length;
 176     if (new_data - primitive->segment->data >= primitive->segment->num_data)
 177         return 0;
 178
 179     /* TODO: this is a temporary workaround to be removed as soon as
 180      * the issue #21 will be resolved */
 181     if (new_data->header.type == CPML_MOVE)
 182         return 0;
 183
 184     primitive->org = cpml_primitive_get_point(primitive, -1);
 185     primitive->data = new_data;
 186
 187     return 1;
 188 }
 189
 190 /**
 191  * cpml_primitive_get_n_points:
 192  * @primitive: a #CpmlPrimitive
 193  *
 194  * Gets the number of points required to identify @primitive.
 195  * It is similar to cpml_primitive_type_get_n_points() but using
 196  * a @primitive instance instead of a type.
 197  *
 198  * Returns: the number of points or %0 on errors
 199  **/
 200 size_t
 201 cpml_primitive_get_n_points(const CpmlPrimitive *primitive)
 202 {
 203     return cpml_primitive_type_get_n_points(primitive->data->header.type);
 204 }
 205
 206 /**
 207  * cpml_primitive_get_point:
 208  * @primitive: a #CpmlPrimitive
 209  * @n_point: the index of the point to retrieve
 210  *
 211  * Gets the specified @n_point from @primitive. The index starts
 212  * at 0: if @n_point is 0, the start point (the origin) is
 213  * returned, 1 for the second point and so on. If @n_point is
 214  * negative, it is considered as a negative index from the end,
 215  * so that -1 is the end point, -2 the point before the end point
 216  * and so on.
 217  *
 218  * #CPML_CLOSE is managed in a special way: if @n_point
 219  * is -1 or 1 and @primitive is a close-path, this function cycles
 220  * the source #CpmlSegment and returns the first point. This is
 221  * needed because requesting the end point (or the second point)
 222  * of a close path is a valid operation and must returns the start
 223  * of the segment.
 224  *
 225  * Returns: a pointer to the requested point (in cairo format)
 226  *          or %NULL if the point is outside the valid range
 227  **/
 228 cairo_path_data_t *
 229 cpml_primitive_get_point(const CpmlPrimitive *primitive, int n_point)
 230 {
 231     size_t n_points;
 232
 233     /* For a start point request, simply return the origin
 234      * without further checking */
 235     if (n_point == 0)
 236         return primitive->org;
 237
 238     /* The CPML_CLOSE special case */
 239     if (primitive->data->header.type == CPML_CLOSE &&
 240         (n_point == 1 || n_point == -1))
 241         return &primitive->segment->data[1];
 242
 243     n_points = cpml_primitive_get_n_points(primitive);
 244     if (n_points == 0)
 245         return NULL;
 246
 247     /* If n_point is negative, consider it as a negative index from the end */
 248     if (n_point < 0)
 249         n_point = n_points + n_point;
 250
 251     /* Out of range condition */
 252     if (n_point < 0 || n_point >= n_points)
 253         return NULL;
 254
 255     return n_point == 0 ? primitive->org : &primitive->data[n_point];
 256 }
 257
 258 /**
 259  * cpml_primitive_get_length:
 260  * @primitive: a #CpmlPrimitive
 261  *
 262  * Abstracts the length() family functions by providing a common
 263  * way to access the underlying primitive-specific implementation.
 264  * The function returns the length of @primitive.
 265  *
 266  * Returns: the requested length or 0 on errors
 267  **/
 268 double
 269 cpml_primitive_get_length(const CpmlPrimitive *primitive)
 270 {
 271     const _CpmlPrimitiveClass *class_data = get_class(primitive);
 272
 273     if (class_data == NULL || class_data->get_length == NULL)
 274         return 0;
 275
 276     return class_data->get_length(primitive);
 277 }
 278
 279 /**
 280  * cpml_primitive_put_extents:
 281  * @primitive: a #CpmlPrimitive
 282  * @extents: where to store the extents
 283  *
 284  * Abstracts the extents() family functions by providing a common
 285  * way to access the underlying primitive-specific implementation.
 286  *
 287  * This function stores in @extents the bounding box of @primitive.
 288  *
 289  * On errors, that is if the extents cannot be calculated for some
 290  * reason, this function does nothing.
 291  **/
 292 void
 293 cpml_primitive_put_extents(const CpmlPrimitive *primitive,
 294                            CpmlExtents *extents)
 295 {
 296     const _CpmlPrimitiveClass *class_data = get_class(primitive);
 297
 298     if (class_data == NULL || class_data->put_extents == NULL)
 299         return;
 300
 301     class_data->put_extents(primitive, extents);
 302 }
 303
 304 /**
 305  * cpml_primitive_put_pair_at:
 306  * @primitive: a #CpmlPrimitive
 307  * @pos:       the position value
 308  * @pair:      the destination #CpmlPair
 309  *
 310  * Abstracts the put_pair_at() family functions by providing a common
 311  * way to access the underlying primitive-specific implementation.
 312  *
 313  * It gets the coordinates of the point lying on @primitive
 314  * at position @pos. @pos is an homogeneous factor where 0 is the
 315  * start point, 1 the end point, 0.5 the mid point and so on.
 316  * @pos can be less than 0 or greater than %1, in which case the
 317  * coordinates of @pair are interpolated.
 318  *
 319  * On errors, that is if the coordinates cannot be calculated for
 320  * some reason, this function does nothing.
 321  **/
 322 void
 323 cpml_primitive_put_pair_at(const CpmlPrimitive *primitive, double pos,
 324                            CpmlPair *pair)
 325 {
 326     const _CpmlPrimitiveClass *class_data = get_class(primitive);
 327
 328     if (class_data == NULL || class_data->put_pair_at == NULL)
 329         return;
 330
 331     class_data->put_pair_at(primitive, pos, pair);
 332 }
 333
 334 /**
 335  * cpml_primitive_put_vector_at:
 336  * @primitive: a #CpmlPrimitive
 337  * @pos:       the position value
 338  * @vector:    the destination #CpmlVector
 339  *
 340  * Abstracts the put_vector_at() family functions by providing a common
 341  * way to access the underlying primitive-specific implementation.
 342  *
 343  * It gets the steepness of the point at position @pos on @primitive.
 344  * @pos is an homogeneous factor where 0 is the start point, 1 the
 345  * end point, 0.5 the mid point and so on.
 346  * @pos can be less than 0 or greater than %1, in which case the
 347  * coordinates of @pair are interpolated.
 348  *
 349  * On errors, that is if the steepness cannot be calculated for
 350  * some reason, this function does nothing.
 351  **/
 352 void
 353 cpml_primitive_put_vector_at(const CpmlPrimitive *primitive, double pos,
 354                              CpmlVector *vector)
 355 {
 356     const _CpmlPrimitiveClass *class_data = get_class(primitive);
 357
 358     if (class_data == NULL || class_data->put_vector_at == NULL)
 359         return;
 360
 361     class_data->put_vector_at(primitive, pos, vector);
 362 }
 363
 364 /**
 365  * cpml_primitive_get_closest_pos:
 366  * @primitive: a #CpmlPrimitive
 367  * @pair:      the coordinates of the subject point
 368  *
 369  * Returns the pos value of the point on @primitive nearest to @pair.
 370  * The returned value is always clamped between %0 and %1.
 371  *
 372  * Returns: the requested pos value between %0 and %1, or %-1 on errors
 373  **/
 374 double
 375 cpml_primitive_get_closest_pos(const CpmlPrimitive *primitive,
 376                                const CpmlPair *pair)
 377 {
 378     const _CpmlPrimitiveClass *class_data = get_class(primitive);
 379
 380     if (class_data == NULL || class_data->get_closest_pos == NULL)
 381         return -1;
 382
 383     return class_data->get_closest_pos(primitive, pair);
 384 }
 385
 386 /**
 387  * cpml_primitive_put_intersections:
 388  * @primitive:  the first #CpmlPrimitive
 389  * @primitive2: the second #CpmlPrimitive
 390  * @n_dest:     maximum number of intersections to return
 391  * @dest:       the destination buffer that can contain @n_dest #CpmlPair
 392  *
 393  * Finds the intersection points between the given primitives and
 394  * returns the result in @dest. The size of @dest should be enough
 395  * to store @n_dest #CpmlPair. The maximum number of intersections
 396  * is dependent on the type of the primitive involved in the
 397  * operation. If there are at least one Bézier curve involved, up to
 398  * %4 intersections could be returned. Otherwise, if there is an arc
 399  * the intersections will be %2 at maximum. For line primitives, there
 400  * is only %1 point (or %0 if the lines are parallel).
 401  *
 402  * <note>
 403  * <para>
 404  * The convention used by the CPML library is that a primitive should
 405  * implement only the intersection algorithms with lower degree
 406  * primitives. This is required to avoid code duplication: intersection
 407  * between arc and Bézier curves must be implemented by #CPML_CURVE and
 408  * intersection between lines and arcs must be implemented by #CPML_ARC.
 409  * cpml_primitive_put_intersections() will take care of swapping the
 410  * arguments if they are not properly ordered.
 411  * </para>
 412  * </note>
 413  *
 414  * Returns: the number of intersection points found or 0 if the
 415  *          primitives do not intersect or on errors
 416  **/
 417 size_t
 418 cpml_primitive_put_intersections(const CpmlPrimitive *primitive,
 419                                  const CpmlPrimitive *primitive2,
 420                                  size_t n_dest, CpmlPair *dest)
 421 {
 422     const _CpmlPrimitiveClass *class_data;
 423     size_t n_points, n_points2;
 424
 425     class_data = get_class(primitive);
 426
 427     if (class_data == NULL || class_data->put_intersections == NULL)
 428         return 0;
 429
 430     n_points = cpml_primitive_get_n_points(primitive);
 431     n_points2 = cpml_primitive_get_n_points(primitive2);
 432
 433     if (n_points == -1 || n_points2 == -1)
 434         return 0;
 435
 436     /* Primitives reordering: the first must be the more complex one */
 437     if (n_points < n_points2) {
 438         const CpmlPrimitive *old_primitive2 = primitive2;
 439         primitive2 = primitive;
 440         primitive = old_primitive2;
 441     }
 442
 443     return class_data->put_intersections(primitive, primitive2, n_dest, dest);
 444 }
 445
 446 /**
 447  * cpml_primitive_put_intersections_with_segment:
 448  * @primitive: a #CpmlPrimitive
 449  * @segment:   a #CpmlSegment
 450  * @n_dest:    maximum number of intersection pairs to return
 451  * @dest:      the destination buffer of #CpmlPair
 452  *
 453  * Computes the intersections between @segment and @primitive by
 454  * sequentially scanning the primitives in @segment and looking
 455  * for their intersections with @primitive.
 456  *
 457  * If the intersections are more than @n_dest, only the first
 458  * @n_dest pairs are stored.
 459  *
 460  * Returns: the number of intersections found
 461  **/
 462 size_t
 463 cpml_primitive_put_intersections_with_segment(const CpmlPrimitive *primitive,
 464                                               const CpmlSegment *segment,
 465                                               size_t n_dest, CpmlPair *dest)
 466 {
 467     CpmlPrimitive portion;
 468     size_t found;
 469
 470     cpml_primitive_from_segment(&portion, (CpmlSegment *) segment);
 471     found = 0;
 472
 473     while (found < n_dest) {
 474         found += cpml_primitive_put_intersections(&portion, primitive,
 475                                                   n_dest-found, dest+found);
 476         if (!cpml_primitive_next(&portion))
 477             break;
 478     }
 479
 480     return found;
 481 }
 482
 483 /**
 484  * cpml_primitive_offset:
 485  * @primitive: a #CpmlPrimitive
 486  * @offset: distance for the computed offset primitive
 487  *
 488  * Given a primitive, computes the same (or approximated) parallel
 489  * primitive distant @offset from the original one and returns
 490  * the result by changing @primitive.
 491  *
 492  * On errors, that is if the offset primitive cannot be calculated
 493  * for some reason, this function does nothing.
 494  **/
 495 void
 496 cpml_primitive_offset(CpmlPrimitive *primitive, double offset)
 497 {
 498     const _CpmlPrimitiveClass *class_data = get_class(primitive);
 499
 500     if (class_data == NULL || class_data->offset == NULL)
 501         return;
 502
 503     return class_data->offset(primitive, offset);
 504 }
 505
 506 /**
 507  * cpml_primitive_join:
 508  * @primitive: the first #CpmlPrimitive
 509  * @primitive2: the second #CpmlPrimitive
 510  *
 511  * Joins two primitive modifying the end point of @primitive and the
 512  * start point of @primitive2 so that the resulting points will overlap.
 513  *
 514  * <important>
 515  * <title>TODO</title>
 516  * <itemizedlist>
 517  * <listitem>Actually, the join is done by extending the end vector
 518  *           of @primitive and the start vector of @primitive2 and
 519  *           interpolating the intersection: this means no primitive
 520  *           dependent code is needed. Anyway, it is likely to change
 521  *           in the future because this approach is quite naive when
 522  *           curves are involved.</listitem>
 523  * </itemizedlist>
 524  * </important>
 525  *
 526  * Returns: 1 on success, 0 if the end vector of @primitive
 527  *          and the start vector of @primitive2 are parallel
 528  **/
 529 cairo_bool_t
 530 cpml_primitive_join(CpmlPrimitive *primitive, CpmlPrimitive *primitive2)
 531 {
 532     cairo_path_data_t *end1, *start2;
 533     CpmlPrimitive line1, line2;
 534     cairo_path_data_t data1[2], data2[2];
 535     CpmlPair joint;
 536
 537     end1 = cpml_primitive_get_point(primitive, -1);
 538     start2 = cpml_primitive_get_point(primitive2, 0);
 539
 540     /* Check if the primitives are yet connected */
 541     if (end1->point.x == start2->point.x && end1->point.y == start2->point.y)
 542         return 1;
 543
 544     line1.org = cpml_primitive_get_point(primitive, -2);
 545     line1.data = data1;
 546     data1[0].header.type = CPML_LINE;
 547     data1[1] = *end1;
 548
 549     line2.org = start2;
 550     line2.data = data2;
 551     data2[0].header.type = CPML_LINE;
 552     data2[1] = *cpml_primitive_get_point(primitive2, 1);
 553
 554     if (!cpml_primitive_put_intersections(&line1, &line2, 1, &joint))
 555         return 0;
 556
 557     cpml_pair_to_cairo(&joint, end1);
 558     cpml_pair_to_cairo(&joint, start2);
 559
 560     return 1;
 561 }
 562
 563 /**
 564  * cpml_primitive_to_cairo:
 565  * @primitive: a #CpmlPrimitive
 566  * @cr: the destination cairo context
 567  *
 568  * Renders a single @primitive to the @cr cairo context.
 569  * As a special case, if the primitive is a #CPML_CLOSE, an
 570  * equivalent line is rendered, because a close path left alone
 571  * is not renderable.
 572  *
 573  * Also a #CPML_ARC primitive is treated specially, as it is not
 574  * natively supported by cairo and has its own rendering API.
 575  **/
 576 void
 577 cpml_primitive_to_cairo(const CpmlPrimitive *primitive, cairo_t *cr)
 578 {
 579     cairo_path_t path;
 580     cairo_path_data_t *path_data;
 581
 582     cairo_move_to(cr, primitive->org->point.x, primitive->org->point.y);
 583
 584     switch (primitive->data->header.type) {
 585
 586     case CPML_CLOSE:
 587         path_data = cpml_primitive_get_point(primitive, -1);
 588         cairo_line_to(cr, path_data->point.x, path_data->point.y);
 589         break;
 590
 591     case CPML_ARC:
 592         cpml_arc_to_cairo(primitive, cr);
 593         break;
 594
 595     default:
 596         path.status = CAIRO_STATUS_SUCCESS;
 597         path.data = primitive->data;
 598         path.num_data = primitive->data->header.length;
 599         cairo_append_path(cr, &path);
 600         break;
 601     }
 602 }
 603
 604 /**
 605  * cpml_primitive_dump:
 606  * @primitive: a #CpmlPrimitive
 607  * @org_also:  whether to output also the origin coordinates
 608  *
 609  * Dumps info on the specified @primitive to stdout: useful for
 610  * debugging purposes. If @org_also is 1, a #CPML_MOVE to the
 611  * origin is prepended to the data otherwise the
 612  * <structfield>org</structfield> field is not used.
 613  **/
 614 void
 615 cpml_primitive_dump(const CpmlPrimitive *primitive, cairo_bool_t org_also)
 616 {
 617     const cairo_path_data_t *data;
 618     int type;
 619     const _CpmlPrimitiveClass *class_data;
 620     size_t n, n_points;
 621
 622     data = primitive->data;
 623     type = data->header.type;
 624     class_data = get_class_from_type(type);
 625
 626     if (class_data == NULL) {
 627         printf("Unknown primitive type (%d)\n", type);
 628         return;
 629     }
 630
 631     /* Dump the origin, if requested */
 632     if (org_also) {
 633         printf("move to ");
 634         dump_cairo_point(primitive->org);
 635         printf("\n");
 636     }
 637
 638     printf("%s ", class_data->name);
 639
 640     n_points = cpml_primitive_get_n_points(primitive);
 641     for (n = 1; n < n_points; ++n)
 642         dump_cairo_point(cpml_primitive_get_point(primitive, n));
 643
 644     printf("\n");
 645 }
 646
 647
 648 static const _CpmlPrimitiveClass *
 649 get_class_from_type(CpmlPrimitiveType type)
 650 {
 651     switch (type) {
 652     case CPML_LINE:
 653         return _cpml_line_get_class();
 654     case CPML_ARC:
 655         return _cpml_arc_get_class();
 656     case CPML_CURVE:
 657         return _cpml_curve_get_class();
 658     case CPML_CLOSE:
 659         return _cpml_close_get_class();
 660     default:
 661         break;
 662     }
 663
 664     return NULL;
 665 }
 666
 667 static const _CpmlPrimitiveClass *
 668 get_class(const CpmlPrimitive *primitive)
 669 {
 670     return get_class_from_type(primitive->data->header.type);
 671 }
 672
 673 static void
 674 dump_cairo_point(const cairo_path_data_t *path_data)
 675 {
 676     printf("(%g %g) ", path_data->point.x, path_data->point.y);
 677 }