cpml/cpml-primitive.c

   1 /* CPML - Cairo Path Manipulation Library
   2  * Copyright (C) 2008, 2009  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  * SECTION:primitive
  22  * @title: CpmlPrimitive
  23  * @short_description: Basic component of segments
  24  *
  25  * A primitive is an atomic geometric element found inside #CpmlSegment.
  26  * The available primitives are defined in the #cairo_path_data_type_t
  27  * enum, excluding %CAIRO_PATH_MOVE_TO, as it is not considered a valid
  28  * primitive and it is managed in different way (the moveto primitives
  29  * are used to set the origin of the first primitive in a segment).
  30  **/
  31
  32 /**
  33  * CpmlPrimitive:
  34  * @segment: the source #CpmlSegment
  35  * @org: a pointer to the first point of the primitive
  36  * @data: the array of the path data, prepended by the header
  37  *
  38  * As for #CpmlSegment, also the primitive is unobtrusive. This
  39  * means CpmlPrimitive does not include any coordinates but instead
  40  * keeps pointers to the original segment (and, by transition, to
  41  * the underlying #cairo_path_t struct).
  42  **/
  43
  44 #include "cpml-primitive.h"
  45 #include "cpml-line.h"
  46 #include "cpml-arc.h"
  47 #include "cpml-curve.h"
  48 #include "cpml-close.h"
  49
  50 #include <stdlib.h>
  51 #include <string.h>
  52 #include <stdio.h>
  53
  54 static void     dump_cairo_point        (const cairo_path_data_t *path_data);
  55
  56
  57 /**
  58  * cpml_primitive_copy:
  59  * @primitive: the destination #CpmlPrimitive
  60  * @src: the source #CpmlPrimitive
  61  *
  62  * Copies @src in @primitive.
  63  *
  64  * Return value: @primitive
  65  **/
  66 CpmlPrimitive *
  67 cpml_primitive_copy(CpmlPrimitive *primitive, const CpmlPrimitive *src)
  68 {
  69     return memcpy(primitive, src, sizeof(CpmlPrimitive));
  70 }
  71
  72 /**
  73  * cpml_primitive_from_segment:
  74  * @primitive: the destination #CpmlPrimitive struct
  75  * @segment: the source segment
  76  *
  77  * Initializes @primitive to the first primitive of @segment.
  78  *
  79  * Return value: @primitive
  80  **/
  81 CpmlPrimitive *
  82 cpml_primitive_from_segment(CpmlPrimitive *primitive, CpmlSegment *segment)
  83 {
  84     primitive->segment = segment;
  85
  86     /* The first element of a CpmlSegment is always a CAIRO_PATH_MOVE_TO,
  87      * as ensured by cpml_segment_from_cairo() and by the browsing APIs,
  88      * so the origin is in the second data item */
  89     primitive->org = &segment->data[1];
  90
  91     /* Also, the segment APIs ensure that @segment is prepended by
  92      * only one CAIRO_PATH_MOVE_TO */
  93     primitive->data = segment->data + 2;
  94
  95     return primitive;
  96 }
  97
  98 /**
  99  * cpml_primitive_reset:
 100  * @primitive: a #CpmlPrimitive
 101  *
 102  * Resets @primitive so it refers to the first primitive of the
 103  * source segment.
 104  **/
 105 void
 106 cpml_primitive_reset(CpmlPrimitive *primitive)
 107 {
 108     primitive->org = &primitive->segment->data[1];
 109     primitive->data = primitive->segment->data + 2;
 110 }
 111
 112 /**
 113  * cpml_primitive_next:
 114  * @primitive: a #CpmlPrimitive
 115  *
 116  *
 117  * Changes @primitive so it refers to the next primitive on the
 118  * source segment. If there are no more primitives, @primitive is
 119  * not changed and 0 is returned.
 120  *
 121  * Return value: 1 on success, 0 if no next primitive found or errors
 122  **/
 123 cairo_bool_t
 124 cpml_primitive_next(CpmlPrimitive *primitive)
 125 {
 126     cairo_path_data_t *new_data;
 127
 128     new_data = primitive->data + primitive->data->header.length;
 129     if (new_data - primitive->segment->data >= primitive->segment->num_data)
 130         return 0;
 131
 132     primitive->org = cpml_primitive_get_point(primitive, -1);
 133     primitive->data = new_data;
 134
 135     return 1;
 136 }
 137
 138 /**
 139  * cpml_primitive_get_npoints:
 140  * @primitive: a #CpmlPrimitive
 141  *
 142  * Gets the number of points required to identify @primitive.
 143  * It is similar to cpml_primitive_type_get_npoints() but using
 144  * a @primitive instance instead of a type.
 145  *
 146  * Return value: the number of points or -1 on errors
 147  **/
 148 int
 149 cpml_primitive_get_npoints(const CpmlPrimitive *primitive)
 150 {
 151     return cpml_primitive_type_get_npoints(primitive->data->header.type);
 152 }
 153
 154 /**
 155  * cpml_primitive_get_point:
 156  * @primitive: a #CpmlPrimitive
 157  * @npoint: the index of the point to retrieve
 158  *
 159  * Gets the specified @npoint from @primitive. The index starts
 160  * at 0: if @npoint is 0, the start point (the origin) is
 161  * returned, 1 for the second point and so on. If @npoint is
 162  * negative, it is considered as a negative index from the end,
 163  * so that -1 is the end point, -2 the point before the end point
 164  * and so on.
 165  *
 166  * %CAIRO_PATH_CLOSE_PATH is managed in a special way: if @npoint
 167  * is -1 or 1 and @primitive is a close-path, this function cycles
 168  * the source #CpmlSegment and returns the first point. This is
 169  * needed because requesting the end point (or the second point)
 170  * of a close path is a valid operation and must returns the start
 171  * of the segment.
 172  *
 173  * Return value: a pointer to the requested point (in cairo format)
 174  *               or %NULL if the point is outside the valid range
 175  **/
 176 cairo_path_data_t *
 177 cpml_primitive_get_point(const CpmlPrimitive *primitive, int npoint)
 178 {
 179     int npoints;
 180
 181     /* For a start point request, simply return the origin
 182      * without further checking */
 183     if (npoint == 0)
 184         return primitive->org;
 185
 186     /* The CAIRO_PATH_CLOSE_PATH special case */
 187     if (primitive->data->header.type == CAIRO_PATH_CLOSE_PATH &&
 188         (npoint == 1 || npoint == -1))
 189         return &primitive->segment->data[1];
 190
 191     npoints = cpml_primitive_get_npoints(primitive);
 192     if (npoints < 0)
 193         return NULL;
 194
 195     /* If npoint is negative, consider it as a negative index from the end */
 196     if (npoint < 0)
 197         npoint = npoints + npoint;
 198
 199     /* Out of range condition */
 200     if (npoint < 0 || npoint >= npoints)
 201         return NULL;
 202
 203     return npoint == 0 ? primitive->org : &primitive->data[npoint];
 204 }
 205
 206 /**
 207  * cpml_primitive_to_cairo:
 208  * @primitive: a #CpmlPrimitive
 209  * @cr: the destination cairo context
 210  *
 211  * Renders a single @primitive to the @cr cairo context.
 212  * As a special case, if the primitive is a #CAIRO_PATH_CLOSE_PATH,
 213  * an equivalent line is rendered, because a close path left alone
 214  * is not renderable.
 215  *
 216  * Also a #CAIRO_PATH_ARC_TO primitive is treated specially, as it
 217  * is not natively supported by cairo and has its own rendering API.
 218  **/
 219 void
 220 cpml_primitive_to_cairo(const CpmlPrimitive *primitive, cairo_t *cr)
 221 {
 222     cairo_path_t path;
 223     cairo_path_data_t *path_data;
 224
 225     cairo_move_to(cr, primitive->org->point.x, primitive->org->point.y);
 226
 227     if (primitive->data->header.type == CAIRO_PATH_CLOSE_PATH) {
 228         path_data = cpml_primitive_get_point(primitive, -1);
 229         cairo_line_to(cr, path_data->point.x, path_data->point.y);
 230     } else if (primitive->data->header.type == CAIRO_PATH_ARC_TO) {
 231         cairo_move_to(cr, &path->org.x, &path->org.y);
 232         cpml_arc_to_cairo(primitive, cr);
 233     } else {
 234         path.status = CAIRO_STATUS_SUCCESS;
 235         path.data = primitive->data;
 236         path.num_data = primitive->data->header.length;
 237         cairo_append_path(cr, &path);
 238     }
 239 }
 240
 241 /**
 242  * cpml_primitive_dump:
 243  * @primitive: a #CpmlPrimitive
 244  * @org_also:  whether to output also the origin coordinates
 245  *
 246  * Dumps info on the specified @primitive to stdout: useful for
 247  * debugging purposes. If @org_also is 1, a %CAIRO_PATH_MOVE_TO
 248  * to the origin is prepended to the data otherwise the
 249  * <structfield>org</structfield> field is not used.
 250  **/
 251 void
 252 cpml_primitive_dump(const CpmlPrimitive *primitive, cairo_bool_t org_also)
 253 {
 254     const cairo_path_data_t *data;
 255     int type, n, npoints;
 256
 257     data = primitive->data;
 258     type = data->header.type;
 259     npoints = cpml_primitive_get_npoints(primitive);
 260     if (npoints < 0) {
 261         printf("Unhandled primitive type (%d)\n", type);
 262         return;
 263     }
 264
 265     /* Dump the origin movement, if requested */
 266     if (org_also) {
 267         printf("Move to ");
 268         dump_cairo_point(primitive->org);
 269         printf("\n");
 270     }
 271
 272     switch (type) {
 273
 274     case CAIRO_PATH_LINE_TO:
 275         printf("Line to ");
 276         break;
 277
 278     case CAIRO_PATH_ARC_TO:
 279         printf("Arc to ");
 280         break;
 281
 282     case CAIRO_PATH_CURVE_TO:
 283         printf("Curve to ");
 284         break;
 285
 286     case CAIRO_PATH_CLOSE_PATH:
 287         printf("Path close");
 288         break;
 289
 290     default:
 291         printf("Unknown primitive (type = %d)", type);
 292         break;
 293     }
 294
 295     for (n = 1; n < npoints; ++n)
 296         dump_cairo_point(cpml_primitive_get_point(primitive, n));
 297
 298     printf("\n");
 299 }
 300
 301 /**
 302  * cpml_primitive_intersection_with_segment:
 303  * @primitive: a #CpmlPrimitive
 304  * @segment:   a #CpmlSegment
 305  * @dest:      the destination vector of #CpmlPair
 306  * @max:       maximum number of intersections to return
 307  *
 308  * Computes the intersections between @segment and @primitive by
 309  * sequentially scanning the primitives in @segment and looking
 310  * for intersections with @primitive.
 311  * If the intersections are more than @max, only the first @max pairs
 312  * are stored in @dest.
 313  *
 314  * Return value: the number of intersections found
 315  **/
 316 int
 317 cpml_primitive_intersection_with_segment(const CpmlPrimitive *primitive,
 318                                          const CpmlSegment *segment,
 319                                          CpmlPair *dest, int max)
 320 {
 321     CpmlPrimitive portion;
 322     int partial, total;
 323     CpmlPair tmp_pairs[4];
 324
 325     cpml_primitive_from_segment(&portion, (CpmlSegment *) segment);
 326     total = 0;
 327
 328     do {
 329         partial = cpml_primitive_intersection(&portion, primitive, tmp_pairs);
 330         if (total + partial > max)
 331             partial = max - total;
 332
 333         if (partial > 0) {
 334             memcpy(dest + total, tmp_pairs, partial * sizeof(CpmlPair));
 335             total += partial;
 336         }
 337     } while (total < max && cpml_primitive_next(&portion));
 338
 339     return total;
 340 }
 341
 342
 343 /**
 344  * cpml_primitive_type_get_npoints:
 345  * @type: a primitive type
 346  *
 347  * Gets the number of points required to identify the @type primitive.
 348  *
 349  * <note><para>
 350  * This function is primitive dependent, that is every primitive has
 351  * its own implementation.
 352  * </para></note>
 353  *
 354  * Return value: the number of points or -1 on errors
 355  **/
 356 int
 357 cpml_primitive_type_get_npoints(cairo_path_data_type_t type)
 358 {
 359     switch (type) {
 360
 361     case CAIRO_PATH_LINE_TO:
 362         return cpml_line_type_get_npoints();
 363
 364     case CAIRO_PATH_ARC_TO:
 365         return cpml_arc_type_get_npoints();
 366
 367     case CAIRO_PATH_CURVE_TO:
 368         return cpml_curve_type_get_npoints();
 369
 370     case CAIRO_PATH_CLOSE_PATH:
 371         return cpml_close_type_get_npoints();
 372
 373     default:
 374         break;
 375     }
 376
 377     return -1;
 378 }
 379
 380 /**
 381  * cpml_primitive_pair_at:
 382  * @primitive: a #CpmlPrimitive
 383  * @pair:      the destination #CpmlPair
 384  * @pos:       the position value
 385  *
 386  * Abstracts the pair_at() family functions by providing a common
 387  * way to access the underlying primitive-specific implementation.
 388  *
 389  * It gets the coordinates of the point lying on @primitive
 390  * at position @pos. @pos is an homogeneous factor where 0 is the
 391  * start point, 1 the end point, 0.5 the mid point and so on.
 392  * The relation 0 < @pos < 1 should be satisfied, although some
 393  * primitives accept value outside this range.
 394  *
 395  * <note><para>
 396  * This function is primitive dependent, that is every primitive has
 397  * its own implementation.
 398  * </para></note>
 399  **/
 400 void
 401 cpml_primitive_pair_at(const CpmlPrimitive *primitive,
 402                        CpmlPair *pair, double pos)
 403 {
 404     switch (primitive->data->header.type) {
 405
 406     case CAIRO_PATH_LINE_TO:
 407         cpml_line_pair_at(primitive, pair, pos);
 408         break;
 409
 410     case CAIRO_PATH_ARC_TO:
 411         cpml_arc_pair_at(primitive, pair, pos);
 412         break;
 413
 414     case CAIRO_PATH_CURVE_TO:
 415         cpml_curve_pair_at(primitive, pair, pos);
 416         break;
 417
 418     case CAIRO_PATH_CLOSE_PATH:
 419         cpml_close_pair_at(primitive, pair, pos);
 420         break;
 421
 422     default:
 423         break;
 424     }
 425 }
 426
 427 /**
 428  * cpml_primitive_vector_at:
 429  * @primitive: a #CpmlPrimitive
 430  * @vector:    the destination #CpmlVector
 431  * @pos:       the position value
 432  *
 433  * Abstracts the vector_at() family functions by providing a common
 434  * way to access the underlying primitive-specific implementation.
 435  *
 436  * It gets the steepness of the point at position @pos on @primitive.
 437  * @pos is an homogeneous factor where 0 is the start point, 1 the
 438  * end point, 0.5 the mid point and so on.
 439  * The relation 0 < @pos < 1 should be satisfied, although some
 440  * primitives accept value outside this range.
 441  *
 442  * <note><para>
 443  * This function is primitive dependent, that is every primitive has
 444  * its own implementation.
 445  * </para></note>
 446  **/
 447 void
 448 cpml_primitive_vector_at(const CpmlPrimitive *primitive,
 449                          CpmlVector *vector, double pos)
 450 {
 451     switch (primitive->data->header.type) {
 452
 453     case CAIRO_PATH_LINE_TO:
 454         cpml_line_vector_at(primitive, vector, pos);
 455         break;
 456
 457     case CAIRO_PATH_ARC_TO:
 458         cpml_arc_vector_at(primitive, vector, pos);
 459         break;
 460
 461     case CAIRO_PATH_CURVE_TO:
 462         cpml_curve_vector_at(primitive, vector, pos);
 463         break;
 464
 465     case CAIRO_PATH_CLOSE_PATH:
 466         cpml_close_vector_at(primitive, vector, pos);
 467         break;
 468
 469     default:
 470         break;
 471     }
 472 }
 473
 474 /**
 475  * cpml_primitive_join:
 476  * @primitive: the first #CpmlPrimitive
 477  * @primitive2: the second #CpmlPrimitive
 478  *
 479  * Joins two primitive modifying the end point of @primitive and the
 480  * start point of @primitive2 so that the resulting points will overlap.
 481  *
 482  * <important>
 483  * <title>TODO</title>
 484  * <itemizedlist>
 485  * <listitem>Actually, the join is done by extending the end vector
 486  *           of @primitive and the start vector of @primitive2 and
 487  *           interpolating the intersection: this means no primitive
 488  *           dependent code is needed. Anyway, it is likely to change
 489  *           in the future because this approach is quite naive when
 490  *           curves are involved.</listitem>
 491  * </itemizedlist>
 492  * </important>
 493  *
 494  * Return value: 1 on success, 0 if the end vector of @primitive
 495  *               and the start vector of @primitive2 are parallel
 496  **/
 497 cairo_bool_t
 498 cpml_primitive_join(CpmlPrimitive *primitive, CpmlPrimitive *primitive2)
 499 {
 500     cairo_path_data_t *end1, *start2;
 501     CpmlPrimitive line1, line2;
 502     cairo_path_data_t data1[2], data2[2];
 503     CpmlPair joint;
 504
 505     end1 = cpml_primitive_get_point(primitive, -1);
 506     start2 = cpml_primitive_get_point(primitive2, 0);
 507
 508     /* Check if the primitives are yet connected */
 509     if (end1->point.x == start2->point.x && end1->point.y == start2->point.y)
 510         return 1;
 511
 512     line1.org = cpml_primitive_get_point(primitive, -2);
 513     line1.data = data1;
 514     data1[0].header.type = CAIRO_PATH_LINE_TO;
 515     data1[1] = *end1;
 516
 517     line2.org = start2;
 518     line2.data = data2;
 519     data2[0].header.type = CAIRO_PATH_LINE_TO;
 520     data2[1] = *cpml_primitive_get_point(primitive2, 1);
 521
 522     if (!cpml_line_intersection(&line1, &line2, &joint))
 523         return 0;
 524
 525     cpml_pair_to_cairo(&joint, end1);
 526     cpml_pair_to_cairo(&joint, start2);
 527
 528     return 1;
 529 }
 530
 531 /**
 532  * cpml_primitive_intersection:
 533  * @primitive:  the first #CpmlPrimitive
 534  * @primitive2: the second #CpmlPrimitive
 535  * @dest:       the destination #CpmlPair (or a vector of #CpmlPair)
 536  *
 537  * Finds the intersection points between the given primitives and
 538  * returns the result in @dest. The size of @dest is dependent
 539  * from the type of the most complex primitive involved in the
 540  * operation. If there are curves involved, @dest MUST be an array
 541  * of at least 4 #CpmlPair. If an arc is the most complex primitive
 542  * involved, @dest MUST be sized to 2 #CpmlPair. In the simplest
 543  * case, that is intersection between two lines, only 1 #CpmlPair
 544  * is required.
 545  *
 546  * If the primitive types are not known in advance, simply suppose
 547  * the worst case and leave room for 4 #CpmlPair in @dest.
 548  *
 549  * <note><para>
 550  * This function is primitive dependent: every new primitive must
 551  * expose API to get intersections with any other primitive type
 552  * (excluding %CAIRO_PATH_CLOSE_PATH, as it is converted to a line
 553  * primitive).</para>
 554  * <para>The convention used by CPML is that a primitive should
 555  * expose only APIs dealing with lower complexity primitives.
 556  * This is required to avoid double functions: you will have
 557  * only a cpml_curve_intersection_with_line() function not a
 558  * cpml_line_intersection_with_curve(), as the latter is
 559  * easily reproduced by calling the former with @primitive2
 560  * and @primitive switched.
 561  * </para></note>
 562  *
 563  * Return value: the number of intersection points found
 564  **/
 565 int
 566 cpml_primitive_intersection(const CpmlPrimitive *primitive,
 567                             const CpmlPrimitive *primitive2,
 568                             CpmlPair *dest)
 569 {
 570     cairo_path_data_type_t type1, type2;
 571
 572     type1 = primitive->data->header.type;
 573     type2 = primitive->data->header.type;
 574
 575     /* Close path primitives are treated as line-to */
 576     if (type1 == CAIRO_PATH_CLOSE_PATH)
 577         type1 = CAIRO_PATH_LINE_TO;
 578     if (type2 == CAIRO_PATH_CLOSE_PATH)
 579         type2 = CAIRO_PATH_LINE_TO;
 580
 581     /* Order the two primitives in ascending complexity, to facilitate
 582      * the dispatcher logic */
 583     if (cpml_primitive_type_get_npoints(type1) > cpml_primitive_type_get_npoints(type2)) {
 584         const CpmlPrimitive *tmp_primitive;
 585         cairo_path_data_type_t tmp_type;
 586
 587         tmp_type = type1;
 588         tmp_primitive = primitive;
 589
 590         type1 = type2;
 591         primitive = primitive2;
 592
 593         type2 = tmp_type;
 594         primitive2 = tmp_primitive;
 595     }
 596
 597     /* Dispatcher: probably there's a smarter way to do this */
 598     switch (type1) {
 599
 600     case CAIRO_PATH_LINE_TO:
 601         if (type2 == CAIRO_PATH_LINE_TO)
 602             return cpml_line_intersection(primitive2, primitive, dest);
 603         else if (type2 == CAIRO_PATH_ARC_TO)
 604             return cpml_arc_intersection_with_line(primitive2, primitive, dest);
 605         else if (type2 == CAIRO_PATH_CURVE_TO)
 606             return cpml_curve_intersection_with_line(primitive2, primitive, dest);
 607         break;
 608
 609     case CAIRO_PATH_ARC_TO:
 610         if (type2 == CAIRO_PATH_ARC_TO)
 611             return cpml_arc_intersection(primitive2, primitive, dest);
 612         else if (type2 == CAIRO_PATH_CURVE_TO)
 613             return cpml_curve_intersection_with_arc(primitive2, primitive, dest);
 614         break;
 615
 616     case CAIRO_PATH_CURVE_TO:
 617         if (type2 == CAIRO_PATH_CURVE_TO)
 618             return cpml_curve_intersection(primitive2, primitive, dest);
 619         break;
 620
 621     default:
 622         break;
 623     }
 624
 625     /* Primitive combination not found */
 626     return 0;
 627 }
 628
 629 /**
 630  * cpml_primitive_offset:
 631  * @primitive: a #CpmlPrimitive
 632  * @offset: distance for the computed offset primitive
 633  *
 634  * Given a primitive, computes the same (or approximated) parallel
 635  * primitive distant @offset from the original one and returns
 636  * the result by changing @primitive.
 637  *
 638  * <note><para>
 639  * This function is primitive dependent, that is every primitive has
 640  * its own implementation.
 641  * </para></note>
 642  **/
 643 void
 644 cpml_primitive_offset(CpmlPrimitive *primitive, double offset)
 645 {
 646     switch (primitive->data->header.type) {
 647
 648     case CAIRO_PATH_LINE_TO:
 649         cpml_line_offset(primitive, offset);
 650         break;
 651
 652     case CAIRO_PATH_ARC_TO:
 653         cpml_arc_offset(primitive, offset);
 654         break;
 655
 656     case CAIRO_PATH_CURVE_TO:
 657         cpml_curve_offset(primitive, offset);
 658         break;
 659
 660     case CAIRO_PATH_CLOSE_PATH:
 661         cpml_close_offset(primitive, offset);
 662         break;
 663
 664     default:
 665         break;
 666     }
 667 }
 668
 669 static void
 670 dump_cairo_point(const cairo_path_data_t *path_data)
 671 {
 672     printf("(%g %g) ", path_data->point.x, path_data->point.y);
 673 }