src/cpml/cpml-segment.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-segment
  23  * @Section_Id:CpmlSegment
  24  * @title: CpmlSegment
  25  * @short_description: Contiguous segment that can be a fragment
  26  *                     or a whole cairo path
  27  *
  28  * A segment is a single contiguous line got from a cairo path. The
  29  * CPML library relies on one assumption to let the data be independent
  30  * from the current point (and thus from the cairo context): any segment
  31  * MUST be preceded by at least one %CPML_MOVE primitive.
  32  * This means a valid segment in cairo could be rejected by CPML.
  33  *
  34  * #CpmlSegment provides an unobtrusive way to access a cairo path.
  35  * This means #CpmlSegment itsself does not hold any coordinates but
  36  * instead a bunch of pointers to the original #cairo_path_t struct:
  37  * modifying data throught this struct also changes the original path.
  38  *
  39  * Every #CpmlPath struct can contain more than one segment: the CPML
  40  * library provides iteration APIs to browse the segments of a path.
  41  * Use cpml_segment_reset() to reset the iterator at the start of the
  42  * cairo path (will point the first segment) and cpml_segment_next()
  43  * to get the next segment. Getting the previous segment is not provided
  44  * as the underlying cairo struct is not accessible in reverse order.
  45  *
  46  * When initialized, #CpmlSegment yet refers to the first segment so
  47  * the initial reset is not required.
  48  *
  49  * Since: 1.0
  50  **/
  51
  52 /**
  53  * CpmlPath:
  54  *
  55  * This is another name for the #cairo_path_t type. Although phisically
  56  * they are the same struct, #CpmlPath conceptually embodies an important
  57  * difference: it is a cairo path that can embed %CPML_ARC primitives.
  58  * This is not a native cairo primitive and having two different data
  59  * types is a good way to make clear when a function expect or not
  60  * embedded arc-to primitives.
  61  *
  62  * Since: 1.0
  63  **/
  64
  65 /**
  66  * CpmlSegment:
  67  * @path:     the source #CpmlPath struct
  68  * @data:     the data points of the segment; the first primitive
  69  *            will always be a %CPML_MOVE
  70  * @num_data: size of @data
  71  *
  72  * This is an unobtrusive struct to identify a segment inside a
  73  * cairo path. Unobtrusive means that the real coordinates are
  74  * still stored in @path: CpmlSegment only provides a way to
  75  * access them.
  76  *
  77  * Since: 1.0
  78  **/
  79
  80
  81 #include "cpml-internal.h"
  82 #include "cpml-extents.h"
  83 #include "cpml-segment.h"
  84 #include "cpml-primitive.h"
  85 #include "cpml-curve.h"
  86 #include <string.h>
  87
  88 static int              normalize               (CpmlSegment       *segment);
  89 static int              ensure_one_leading_move (CpmlSegment       *segment);
  90 static int              reshape                 (CpmlSegment       *segment);
  91
  92
  93 /**
  94  * cpml_segment_from_cairo:
  95  * @segment: (out): a #CpmlSegment
  96  * @path:    (in):  the source #CpmlPath
  97  *
  98  * Builds a CpmlSegment from a #CpmlPath structure. This operation
  99  * involves stripping the duplicate %CPML_MOVE primitives at the
 100  * start of the path and setting <structfield>num_data</structfield>
 101  * field to the end of the contiguous line, that is when another
 102  * %CPML_MOVE primitive is found or at the end of the path.
 103  * A pointer to the source cairo path is kept though.
 104  *
 105  * This function will fail if @path is null, empty or if its
 106  * <structfield>status</structfield> member is not %CAIRO_STATUS_SUCCESS.
 107  * Also, the first primitive must be a %CPML_MOVE, so no
 108  * dependency on the cairo context is needed.
 109  *
 110  * Returns: (type gboolean): %1 if @segment has been succesfully computed,
 111  *                           %0 on errors
 112  *
 113  * Since: 1.0
 114  **/
 115 int
 116 cpml_segment_from_cairo(CpmlSegment *segment, CpmlPath *path)
 117 {
 118     /* The cairo path should be defined and in a perfect state */
 119     if (path == NULL || path->num_data == 0 ||
 120         path->status != CAIRO_STATUS_SUCCESS)
 121         return 0;
 122
 123     segment->path = path;
 124     segment->data = path->data;
 125     segment->num_data = path->num_data;
 126
 127     return normalize(segment);
 128 }
 129
 130 /**
 131  * cpml_segment_copy:
 132  * @segment: a #CpmlSegment
 133  * @src: the source segment to copy
 134  *
 135  * Makes a shallow copy of @src into @segment.
 136  *
 137  * Since: 1.0
 138  **/
 139 void
 140 cpml_segment_copy(CpmlSegment *segment, const CpmlSegment *src)
 141 {
 142     memcpy(segment, src, sizeof(CpmlSegment));
 143 }
 144
 145 /**
 146  * cpml_path_is_empty:
 147  * @path: a #CpmlPath (or a #cairo_path_t) pointer
 148  *
 149  * Checks if @path is empty. An invalid path is considered empty.
 150  *
 151  * Returns: (type gboolean): %1 if the path is empty or invalid,
 152  *                           %0 otherwise
 153  *
 154  * Since: 1.0
 155  **/
 156 int
 157 cpml_path_is_empty(const CpmlPath *path)
 158 {
 159     cairo_path_t *cairo_path = (cairo_path_t *) path;
 160     return path == NULL || cairo_path->data == NULL || cairo_path->num_data <= 0;
 161 }
 162
 163 /**
 164  * cpml_segment_reset:
 165  * @segment: a #CpmlSegment
 166  *
 167  * Modifies @segment to point to the first segment of the source cairo path.
 168  *
 169  * Since: 1.0
 170  **/
 171 void
 172 cpml_segment_reset(CpmlSegment *segment)
 173 {
 174     segment->data = segment->path->data;
 175     segment->num_data = segment->path->num_data;
 176     normalize(segment);
 177 }
 178
 179 /**
 180  * cpml_segment_next:
 181  * @segment: a #CpmlSegment
 182  *
 183  * Modifies @segment to point to the next segment of the source cairo path.
 184  *
 185  * Returns: (type gboolean): %1 on success,
 186  *                           %0 if no next segment found or errors
 187  *
 188  * Since: 1.0
 189  **/
 190 int
 191 cpml_segment_next(CpmlSegment *segment)
 192 {
 193     cairo_path_data_t *new_data;
 194     const cairo_path_data_t *end_data;
 195
 196     new_data = segment->data + segment->num_data;
 197     end_data = segment->path->data + segment->path->num_data;
 198
 199     if (new_data >= end_data)
 200         return 0;
 201
 202     segment->data = new_data;
 203     segment->num_data = end_data - new_data;
 204
 205     return normalize(segment);
 206 }
 207
 208 /**
 209  * cpml_segment_get_length:
 210  * @segment: a #CpmlSegment
 211  *
 212  * Gets the whole length of @segment.
 213  *
 214  * Returns: the requested length
 215  *
 216  * Since: 1.0
 217  **/
 218 double
 219 cpml_segment_get_length(const CpmlSegment *segment)
 220 {
 221     CpmlPrimitive primitive;
 222     double length;
 223
 224     cpml_primitive_from_segment(&primitive, (CpmlSegment *) segment);
 225     length = 0;
 226
 227     do {
 228         length += cpml_primitive_get_length(&primitive);
 229     } while (cpml_primitive_next(&primitive));
 230
 231     return length;
 232 }
 233
 234 /**
 235  * cpml_segment_put_extents:
 236  * @segment: a #CpmlSegment
 237  * @extents: where to store the extents
 238  *
 239  * Gets the whole extents of @segment.
 240  *
 241  * Since: 1.0
 242  **/
 243 void
 244 cpml_segment_put_extents(const CpmlSegment *segment, CpmlExtents *extents)
 245 {
 246     CpmlPrimitive primitive;
 247     CpmlExtents primitive_extents;
 248
 249     extents->is_defined = 0;
 250
 251     cpml_primitive_from_segment(&primitive, (CpmlSegment *) segment);
 252
 253     do {
 254         cpml_primitive_put_extents(&primitive, &primitive_extents);
 255         cpml_extents_add(extents, &primitive_extents);
 256     } while (cpml_primitive_next(&primitive));
 257 }
 258
 259 /**
 260  * cpml_segment_put_pair_at:
 261  * @segment: a #CpmlSegment
 262  * @pos:     the position value
 263  * @pair:    the destination #CpmlPair
 264  *
 265  * Gets the coordinates of the point lying on @segment at position
 266  * @pos. @pos is an homogeneous factor where %0 is the start point,
 267  * %1 the end point, %0.5 the mid point and so on.
 268  * The relation %0 < @pos < %1 should be satisfied, although some
 269  * cases accept value outside this range.
 270  *
 271  * <important>
 272  * <title>TODO</title>
 273  * <itemizedlist>
 274  * <listitem>The actual implementation returns only the start and end points,
 275  *           that is only when @pos is %0 or %1.</listitem>
 276  * </itemizedlist>
 277  * </important>
 278  *
 279  * Since: 1.0
 280  **/
 281 void
 282 cpml_segment_put_pair_at(const CpmlSegment *segment, double pos,
 283                          CpmlPair *pair)
 284 {
 285     CpmlPrimitive primitive;
 286
 287     cpml_primitive_from_segment(&primitive, (CpmlSegment *) segment);
 288
 289     /* Handle the common cases: start and end points */
 290     if (pos == 0) {
 291         cpml_primitive_put_pair_at(&primitive, 0, pair);
 292     } if (pos == 1) {
 293         while (cpml_primitive_next(&primitive))
 294             ;
 295         cpml_primitive_put_pair_at(&primitive, 1, pair);
 296     }
 297 }
 298
 299 /**
 300  * cpml_segment_put_vector_at:
 301  * @segment: a #CpmlSegment
 302  * @pos:     the position value
 303  * @vector:  the destination #CpmlVector
 304  *
 305  * Gets the steepness of the point lying on @segment at position
 306  * @pos. @pos is an homogeneous factor where %0 is the start point,
 307  * %1 the end point, %0.5 the mid point and so on.
 308  * The relation %0 < @pos < %1 should be satisfied, although some
 309  * cases accept value outside this range.
 310  *
 311  * <important>
 312  * <title>TODO</title>
 313  * <itemizedlist>
 314  * <listitem>The actual implementation returns only the start and end
 315  *           steepness, that is only when @pos is %0 or %1.</listitem>
 316  * </itemizedlist>
 317  * </important>
 318  *
 319  * Since: 1.0
 320  **/
 321 void
 322 cpml_segment_put_vector_at(const CpmlSegment *segment, double pos,
 323                            CpmlVector *vector)
 324 {
 325     CpmlPrimitive primitive;
 326
 327     cpml_primitive_from_segment(&primitive, (CpmlSegment *) segment);
 328
 329     /* Handle the common cases: start and end points */
 330     if (pos == 0) {
 331         cpml_primitive_put_vector_at(&primitive, 0, vector);
 332         return;
 333     }
 334
 335     if (pos == 1) {
 336         while (cpml_primitive_next(&primitive))
 337             ;
 338         cpml_primitive_put_vector_at(&primitive, 1, vector);
 339         return;
 340     }
 341 }
 342
 343 /**
 344  * cpml_segment_put_intersections:
 345  * @segment:  the first #CpmlSegment
 346  * @segment2: the second #CpmlSegment
 347  * @n_dest:   maximum number of intersections to return
 348  * @dest:     the destination vector of #CpmlPair
 349  *
 350  * Computes the intersections between @segment and @segment2 and
 351  * returns the found points in @dest. If the intersections are more
 352  * than @n_dest, only the first @n_dest pairs are stored in @dest.
 353  *
 354  * To get the job done, the primitives of @segment are sequentially
 355  * scanned for intersections with any primitive in @segment2. This
 356  * means @segment has a higher precedence over @segment2.
 357  *
 358  * Returns: the number of intersections found
 359  *
 360  * Since: 1.0
 361  **/
 362 size_t
 363 cpml_segment_put_intersections(const CpmlSegment *segment,
 364                                const CpmlSegment *segment2,
 365                                size_t n_dest, CpmlPair *dest)
 366 {
 367     CpmlPrimitive portion;
 368     size_t partial, total;
 369
 370     cpml_primitive_from_segment(&portion, (CpmlSegment *) segment);
 371     total = 0;
 372
 373     do {
 374         partial = cpml_primitive_put_intersections_with_segment(&portion,
 375                                                                 segment2,
 376                                                                 n_dest - total,
 377                                                                 dest + total);
 378         total += partial;
 379     } while (total < n_dest && cpml_primitive_next(&portion));
 380
 381     return total;
 382 }
 383
 384 /**
 385  * cpml_segment_offset:
 386  * @segment: a #CpmlSegment
 387  * @offset: the offset distance
 388  *
 389  * Offsets a segment of the specified amount, that is builds a "parallel"
 390  * segment at the @offset distance from the original one and returns the
 391  * result by replacing the original @segment.
 392  *
 393  * <important>
 394  * <title>TODO</title>
 395  * <itemizedlist>
 396  * <listitem>Closed path are not yet managed: an elegant solution is not
 397  *           so obvious: use cpml_close_offset() when available.</listitem>
 398  * <listitem>Degenerated primitives, such as lines of length 0, are not
 399  *           managed properly.</listitem>
 400  * </itemizedlist>
 401  * </important>
 402  *
 403  * Since: 1.0
 404  **/
 405 void
 406 cpml_segment_offset(CpmlSegment *segment, double offset)
 407 {
 408     CpmlPrimitive primitive;
 409     CpmlPrimitive last_primitive;
 410     CpmlPair old_end;
 411     cairo_path_data_t org, *old_org;
 412     int first_cycle;
 413
 414     cpml_primitive_from_segment(&primitive, segment);
 415     first_cycle = 1;
 416
 417     do {
 418         if (! first_cycle) {
 419             cpml_pair_to_cairo(&old_end, &org);
 420             old_org = primitive.org;
 421             primitive.org = &org;
 422         }
 423
 424         cpml_primitive_put_point(&primitive, -1, &old_end);
 425         cpml_primitive_offset(&primitive, offset);
 426
 427         if (! first_cycle) {
 428             cpml_primitive_join(&last_primitive, &primitive);
 429             primitive.org = old_org;
 430         }
 431
 432         cpml_primitive_copy(&last_primitive, &primitive);
 433         first_cycle = 0;
 434     } while (cpml_primitive_next(&primitive));
 435 }
 436
 437 /**
 438  * cpml_segment_transform:
 439  * @segment: a #CpmlSegment
 440  * @matrix: the matrix to be applied
 441  *
 442  * Applies @matrix on all the points of @segment.
 443  *
 444  * Since: 1.0
 445  **/
 446 void
 447 cpml_segment_transform(CpmlSegment *segment, const cairo_matrix_t *matrix)
 448 {
 449     CpmlPrimitive primitive;
 450     cairo_path_data_t *data;
 451     size_t n_points;
 452
 453     cpml_primitive_from_segment(&primitive, segment);
 454     cairo_matrix_transform_point(matrix, &(primitive.org)->point.x,
 455                                  &(primitive.org)->point.y);
 456
 457     do {
 458         data = primitive.data;
 459         if (data->header.type != CAIRO_PATH_CLOSE_PATH) {
 460             n_points = cpml_primitive_get_n_points(&primitive);
 461
 462             while (--n_points > 0) {
 463                 ++data;
 464                 cairo_matrix_transform_point(matrix,
 465                                              &data->point.x, &data->point.y);
 466             }
 467         }
 468     } while (cpml_primitive_next(&primitive));
 469 }
 470
 471 /**
 472  * cpml_segment_reverse:
 473  * @segment: a #CpmlSegment
 474  *
 475  * Reverses @segment in-place. The resulting rendering will be the same,
 476  * but with the primitives generated in reverse order.
 477  *
 478  * It is assumed that @segment has yet been sanitized, that is returned
 479  * by some CPML API function or it is a path yet conforming to the
 480  * segment rules described by the cpml_segment_from_cairo() function.
 481  *
 482  * Since: 1.0
 483  **/
 484 void
 485 cpml_segment_reverse(CpmlSegment *segment)
 486 {
 487     cairo_path_data_t *data, *dst_data;
 488     size_t data_size;
 489     double end_x, end_y;
 490     int n, length;
 491     size_t n_points, n_point;
 492     const cairo_path_data_t *src_data;
 493
 494     data_size = sizeof(cairo_path_data_t) * segment->num_data;
 495     data = malloc(data_size);
 496     end_x = segment->data[1].point.x;
 497     end_y = segment->data[1].point.y;
 498
 499     n = segment->data->header.length;
 500     data->header.type = CAIRO_PATH_CLOSE_PATH;
 501     data->header.length = n;
 502
 503     while (n < segment->num_data) {
 504         src_data = segment->data + n;
 505         n_points = cpml_primitive_type_get_n_points(src_data->header.type);
 506         length = src_data->header.length;
 507         n += length;
 508         dst_data = data + segment->num_data - n + data->header.length;
 509         dst_data->header.type = src_data->header.type;
 510         dst_data->header.length = length;
 511
 512         for (n_point = 1; n_point < n_points; ++n_point) {
 513             dst_data[n_points - n_point].point.x = end_x;
 514             dst_data[n_points - n_point].point.y = end_y;
 515             end_x = src_data[n_point].point.x;
 516             end_y = src_data[n_point].point.y;
 517         }
 518
 519         /* Copy also the embedded data, if any */
 520         if (n_points < length) {
 521             size_t size = (length - n_points) * sizeof(cairo_path_data_t);
 522             memcpy(dst_data + n_points, src_data + n_points, size);
 523         }
 524     }
 525
 526     data[1].point.x = end_x;
 527     data[1].point.y = end_y;
 528     memcpy(segment->data, data, data_size);
 529
 530     free(data);
 531 }
 532
 533 /**
 534  * cpml_segment_to_cairo:
 535  * @segment: a #CpmlSegment
 536  * @cr: the destination cairo context
 537  *
 538  * Appends the path of @segment to @cr. The segment is "flattened",
 539  * that is %CPML_ARC primitives are approximated by one or more
 540  * %CPML_CURVE using cpml_arc_to_cairo(). Check its documentation
 541  * for further details.
 542  *
 543  * Since: 1.0
 544  **/
 545 void
 546 cpml_segment_to_cairo(const CpmlSegment *segment, cairo_t *cr)
 547 {
 548     CpmlPrimitive primitive;
 549
 550     cpml_primitive_from_segment(&primitive, (CpmlSegment *) segment);
 551
 552     do {
 553         cpml_primitive_to_cairo(&primitive, cr);
 554     } while (cpml_primitive_next(&primitive));
 555 }
 556
 557 /**
 558  * cpml_segment_dump:
 559  * @segment: a #CpmlSegment
 560  *
 561  * Dumps the specified @segment to stdout. Useful for debugging purposes.
 562  *
 563  * Since: 1.0
 564  **/
 565 void
 566 cpml_segment_dump(const CpmlSegment *segment)
 567 {
 568     CpmlPrimitive primitive;
 569     int first_call = 1;
 570
 571     cpml_primitive_from_segment(&primitive, (CpmlSegment *) segment);
 572
 573     do {
 574         cpml_primitive_dump(&primitive, first_call);
 575         first_call = 0;
 576     } while (cpml_primitive_next(&primitive));
 577 }
 578
 579
 580 /*
 581  * normalize:
 582  * @segment: a #CpmlSegment
 583  *
 584  * Sanitizes @segment by calling ensure_one_leading_move() and reshape().
 585  *
 586  * Returns: %1 on success, %0 on no leading MOVE_TOs or on errors
 587  **/
 588 static int
 589 normalize(CpmlSegment *segment)
 590 {
 591     if (!ensure_one_leading_move(segment))
 592         return 0;
 593
 594     return reshape(segment);
 595 }
 596
 597 /*
 598  * ensure_one_leading_move:
 599  * @segment: a #CpmlSegment
 600  *
 601  * Strips the leading %CPML_MOVE primitives, updating the
 602  * <structname>CpmlSegment</structname> structure accordingly.
 603  * One, and only one, %CPML_MOVE primitive is left.
 604  *
 605  * Returns: %1 on success, %0 on no leading MOVE_TOs or on empty path
 606  **/
 607 static int
 608 ensure_one_leading_move(CpmlSegment *segment)
 609 {
 610     cairo_path_data_t *new_data;
 611     int new_num_data, move_length;
 612
 613     /* Check for at least one move to */
 614     if (segment->data->header.type != CAIRO_PATH_MOVE_TO)
 615         return 0;
 616
 617     new_data = segment->data;
 618     new_num_data = segment->num_data;
 619
 620     while (1) {
 621         move_length = new_data->header.length;
 622
 623         /* Check for the end of cairo path data, that is when
 624          * @segment is composed by only CAIRO_PATH_MOVE_TO */
 625         if (new_num_data <= move_length)
 626             return 0;
 627
 628         /* Check if this is the last CAIRO_PATH_MOVE_TO */
 629         if (new_data[move_length].header.type != CAIRO_PATH_MOVE_TO)
 630             break;
 631
 632         new_data += move_length;
 633         new_num_data -= move_length;
 634     }
 635
 636     segment->data = new_data;
 637     segment->num_data = new_num_data;
 638
 639     return 1;
 640 }
 641
 642 /*
 643  * reshape:
 644  * @segment: a #CpmlSegment
 645  *
 646  * Looks for the segment termination, that is the end of the underlying
 647  * cairo path or a %CPML_MOVE operation. <structfield>num_data</structfield>
 648  * field is modified to properly point to the end of @segment.
 649  * @segment must have only one leading %CPML_MOVE and it is supposed
 650  * to be non-empty, conditions yet imposed by the ensure_one_leading_move().
 651  *
 652  * This function also checks that all the components of @segment
 653  * are valid primitives.
 654  *
 655  * Returns: %1 on success, %0 on invalid primitive found
 656  **/
 657 static int
 658 reshape(CpmlSegment *segment)
 659 {
 660     const cairo_path_data_t *data;
 661     int trailing_data, new_num_data, length;
 662
 663     data = segment->data;
 664     new_num_data = 0;
 665     trailing_data = segment->num_data;
 666
 667     while (1) {
 668         length = data->header.length;
 669         new_num_data += length;
 670         trailing_data -= length;
 671         data += length;
 672
 673         /* Check for invalid data size */
 674         if (trailing_data < 0)
 675             return 0;
 676
 677         if (trailing_data == 0 || data->header.type == CAIRO_PATH_MOVE_TO)
 678             break;
 679
 680         /* Ensure that all the components are valid primitives */
 681         if (cpml_primitive_type_get_n_points(data->header.type) == 0)
 682             return 0;
 683     }
 684
 685     segment->num_data = new_num_data;
 686     return 1;
 687 }