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