src/cpml/cpml-segment.c

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