src/cpml/cpml-segment.c

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