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