src/cpml/cpml-primitive.c

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