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     /* segment and  path must be non-NULL and path must be valid */
 105     if (path == NULL || segment == NULL ||
 106         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     if (segment == NULL)
 192         return 0;
 193
 194     cpml_primitive_from_segment(&primitive, (CpmlSegment *) segment);
 195     length = 0;
 196
 197     do {
 198         length += cpml_primitive_get_length(&primitive);
 199     } while (cpml_primitive_next(&primitive));
 200
 201     return length;
 202 }
 203
 204 /**
 205  * cpml_segment_put_extents:
 206  * @segment: a #CpmlSegment
 207  * @extents: where to store the extents
 208  *
 209  * Gets the whole extents of @segment.
 210  *
 211  * Since: 1.0
 212  **/
 213 void
 214 cpml_segment_put_extents(const CpmlSegment *segment, CpmlExtents *extents)
 215 {
 216     CpmlPrimitive primitive;
 217     CpmlExtents primitive_extents;
 218
 219     extents->is_defined = 0;
 220
 221     cpml_primitive_from_segment(&primitive, (CpmlSegment *) segment);
 222
 223     do {
 224         cpml_primitive_put_extents(&primitive, &primitive_extents);
 225         cpml_extents_add(extents, &primitive_extents);
 226     } while (cpml_primitive_next(&primitive));
 227 }
 228
 229 /**
 230  * cpml_segment_put_pair_at:
 231  * @segment: a #CpmlSegment
 232  * @pos:     the position value
 233  * @pair:    the destination #CpmlPair
 234  *
 235  * Gets the coordinates of the point lying on @segment at position
 236  * @pos. @pos is an homogeneous factor where 0 is the start point,
 237  * 1 the end point, 0.5 the mid point and so on.
 238  * The relation <constant>0 < @pos < 1</constant> should be satisfied,
 239  * although some cases accept value outside this range.
 240  *
 241  * <important>
 242  * <title>TODO</title>
 243  * <itemizedlist>
 244  * <listitem>The actual implementation returns only the start and end points,
 245  *           that is only when @pos is 0 or 1.</listitem>
 246  * </itemizedlist>
 247  * </important>
 248  *
 249  * Since: 1.0
 250  **/
 251 void
 252 cpml_segment_put_pair_at(const CpmlSegment *segment, double pos,
 253                          CpmlPair *pair)
 254 {
 255     CpmlPrimitive primitive;
 256
 257     cpml_primitive_from_segment(&primitive, (CpmlSegment *) segment);
 258
 259     /* Handle the common cases: start and end points */
 260     if (pos == 0) {
 261         cpml_primitive_put_pair_at(&primitive, 0, pair);
 262     } if (pos == 1) {
 263         while (cpml_primitive_next(&primitive))
 264             ;
 265         cpml_primitive_put_pair_at(&primitive, 1, pair);
 266     }
 267 }
 268
 269 /**
 270  * cpml_segment_put_vector_at:
 271  * @segment: a #CpmlSegment
 272  * @pos:     the position value
 273  * @vector:  the destination #CpmlVector
 274  *
 275  * Gets the steepness 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
 285  *           steepness, 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_vector_at(const CpmlSegment *segment, double pos,
 293                            CpmlVector *vector)
 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_vector_at(&primitive, 0, vector);
 302         return;
 303     }
 304
 305     if (pos == 1) {
 306         while (cpml_primitive_next(&primitive))
 307             ;
 308         cpml_primitive_put_vector_at(&primitive, 1, vector);
 309         return;
 310     }
 311 }
 312
 313 /**
 314  * cpml_segment_put_intersections:
 315  * @segment:  the first #CpmlSegment
 316  * @segment2: the second #CpmlSegment
 317  * @n_dest:   maximum number of intersections to return
 318  * @dest:     the destination vector of #CpmlPair
 319  *
 320  * Computes the intersections between @segment and @segment2 and
 321  * returns the found points in @dest. If the intersections are more
 322  * than @n_dest, only the first @n_dest pairs are stored in @dest.
 323  *
 324  * To get the job done, the primitives of @segment are sequentially
 325  * scanned for intersections with any primitive in @segment2. This
 326  * means @segment has a higher precedence over @segment2.
 327  *
 328  * Returns: the number of intersections found
 329  *
 330  * Since: 1.0
 331  **/
 332 size_t
 333 cpml_segment_put_intersections(const CpmlSegment *segment,
 334                                const CpmlSegment *segment2,
 335                                size_t n_dest, CpmlPair *dest)
 336 {
 337     CpmlPrimitive portion;
 338     size_t partial, total;
 339
 340     cpml_primitive_from_segment(&portion, (CpmlSegment *) segment);
 341     total = 0;
 342
 343     do {
 344         partial = cpml_primitive_put_intersections_with_segment(&portion,
 345                                                                 segment2,
 346                                                                 n_dest - total,
 347                                                                 dest + total);
 348         total += partial;
 349     } while (total < n_dest && cpml_primitive_next(&portion));
 350
 351     return total;
 352 }
 353
 354 /**
 355  * cpml_segment_offset:
 356  * @segment: a #CpmlSegment
 357  * @offset: the offset distance
 358  *
 359  * Offsets a segment of the specified amount, that is builds a "parallel"
 360  * segment at the @offset distance from the original one and returns the
 361  * result by replacing the original @segment.
 362  *
 363  * <important>
 364  * <title>TODO</title>
 365  * <itemizedlist>
 366  * <listitem>Closed path are not yet managed: an elegant solution is not
 367  *           so obvious: use <function>cpml_close_offset</function> when
 368  *           will be available.</listitem>
 369  * <listitem>Degenerated primitives, such as lines of length 0, are not
 370  *           managed properly.</listitem>
 371  * </itemizedlist>
 372  * </important>
 373  *
 374  * Since: 1.0
 375  **/
 376 void
 377 cpml_segment_offset(CpmlSegment *segment, double offset)
 378 {
 379     CpmlPrimitive primitive;
 380     CpmlPrimitive last_primitive;
 381     CpmlPair old_end;
 382     cairo_path_data_t org, *old_org;
 383     int first_cycle;
 384
 385     cpml_primitive_from_segment(&primitive, segment);
 386     first_cycle = 1;
 387
 388     do {
 389         if (! first_cycle) {
 390             cpml_pair_to_cairo(&old_end, &org);
 391             old_org = primitive.org;
 392             primitive.org = &org;
 393         }
 394
 395         cpml_primitive_put_point(&primitive, -1, &old_end);
 396         cpml_primitive_offset(&primitive, offset);
 397
 398         if (! first_cycle) {
 399             cpml_primitive_join(&last_primitive, &primitive);
 400             primitive.org = old_org;
 401         }
 402
 403         cpml_primitive_copy(&last_primitive, &primitive);
 404         first_cycle = 0;
 405     } while (cpml_primitive_next(&primitive));
 406 }
 407
 408 /**
 409  * cpml_segment_transform:
 410  * @segment: a #CpmlSegment
 411  * @matrix: the matrix to be applied
 412  *
 413  * Applies @matrix on all the points of @segment.
 414  *
 415  * Since: 1.0
 416  **/
 417 void
 418 cpml_segment_transform(CpmlSegment *segment, const cairo_matrix_t *matrix)
 419 {
 420     CpmlPrimitive primitive;
 421     cairo_path_data_t *data;
 422     size_t n_points;
 423
 424     cpml_primitive_from_segment(&primitive, segment);
 425     cairo_matrix_transform_point(matrix, &(primitive.org)->point.x,
 426                                  &(primitive.org)->point.y);
 427
 428     do {
 429         data = primitive.data;
 430         if (data->header.type != CAIRO_PATH_CLOSE_PATH) {
 431             n_points = cpml_primitive_get_n_points(&primitive);
 432
 433             while (--n_points > 0) {
 434                 ++data;
 435                 cairo_matrix_transform_point(matrix,
 436                                              &data->point.x, &data->point.y);
 437             }
 438         }
 439     } while (cpml_primitive_next(&primitive));
 440 }
 441
 442 /**
 443  * cpml_segment_reverse:
 444  * @segment: a #CpmlSegment
 445  *
 446  * Reverses @segment in-place. The resulting rendering will be the same,
 447  * but with the primitives generated in reverse order.
 448  *
 449  * It is assumed that @segment has yet been sanitized, that is returned
 450  * by some CPML API function or it is a path yet conforming to the
 451  * segment rules described by the cpml_segment_from_cairo() function.
 452  *
 453  * Since: 1.0
 454  **/
 455 void
 456 cpml_segment_reverse(CpmlSegment *segment)
 457 {
 458     cairo_path_data_t *data, *dst_data;
 459     size_t data_size;
 460     double end_x, end_y;
 461     int n, length;
 462     size_t n_points, n_point;
 463     const cairo_path_data_t *src_data;
 464
 465     data_size = sizeof(cairo_path_data_t) * segment->num_data;
 466     data = malloc(data_size);
 467     end_x = segment->data[1].point.x;
 468     end_y = segment->data[1].point.y;
 469
 470     n = segment->data->header.length;
 471     data->header.type = CAIRO_PATH_CLOSE_PATH;
 472     data->header.length = n;
 473
 474     while (n < segment->num_data) {
 475         src_data = segment->data + n;
 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 = data + segment->num_data - n + data->header.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     data[1].point.x = end_x;
 498     data[1].point.y = end_y;
 499     memcpy(segment->data, data, data_size);
 500
 501     free(data);
 502 }
 503
 504 /**
 505  * cpml_segment_to_cairo:
 506  * @segment: a #CpmlSegment
 507  * @cr: the destination cairo context
 508  *
 509  * Appends the path of @segment to @cr. The segment is "flattened",
 510  * that is %CPML_ARC primitives are approximated by one or more
 511  * %CPML_CURVE using cpml_arc_to_cairo(). Check its documentation
 512  * for further details.
 513  *
 514  * Since: 1.0
 515  **/
 516 void
 517 cpml_segment_to_cairo(const CpmlSegment *segment, cairo_t *cr)
 518 {
 519     CpmlPrimitive primitive;
 520
 521     if (segment == NULL || cr == NULL)
 522         return;
 523
 524     cpml_primitive_from_segment(&primitive, (CpmlSegment *) segment);
 525
 526     do {
 527         cpml_primitive_to_cairo(&primitive, cr);
 528     } while (cpml_primitive_next(&primitive));
 529 }
 530
 531 /**
 532  * cpml_segment_dump:
 533  * @segment: a #CpmlSegment
 534  *
 535  * Dumps the specified @segment to stdout. Useful for debugging purposes.
 536  *
 537  * Since: 1.0
 538  **/
 539 void
 540 cpml_segment_dump(const CpmlSegment *segment)
 541 {
 542     CpmlPrimitive primitive;
 543     int first_call = 1;
 544
 545     cpml_primitive_from_segment(&primitive, (CpmlSegment *) segment);
 546
 547     do {
 548         cpml_primitive_dump(&primitive, first_call);
 549         first_call = 0;
 550     } while (cpml_primitive_next(&primitive));
 551 }
 552
 553
 554 /*
 555  * normalize:
 556  * @segment: a #CpmlSegment
 557  *
 558  * Sanitizes @segment by calling ensure_one_leading_move() and reshape().
 559  *
 560  * Returns: 1 on success, 0 on no leading MOVE_TOs or on errors.
 561  **/
 562 static int
 563 normalize(CpmlSegment *segment)
 564 {
 565     if (!ensure_one_leading_move(segment))
 566         return 0;
 567
 568     return reshape(segment);
 569 }
 570
 571 /*
 572  * ensure_one_leading_move:
 573  * @segment: a #CpmlSegment
 574  *
 575  * Strips the leading %CPML_MOVE primitives, updating the
 576  * <structname>CpmlSegment</structname> structure accordingly.
 577  * One, and only one, %CPML_MOVE primitive is left.
 578  *
 579  * Returns: 1 on success, 0 on no leading MOVE_TOs or on empty path
 580  **/
 581 static int
 582 ensure_one_leading_move(CpmlSegment *segment)
 583 {
 584     cairo_path_data_t *new_data;
 585     int new_num_data, move_length;
 586
 587     /* Check for at least one move to */
 588     if (segment->data->header.type != CAIRO_PATH_MOVE_TO)
 589         return 0;
 590
 591     new_data = segment->data;
 592     new_num_data = segment->num_data;
 593
 594     while (1) {
 595         move_length = new_data->header.length;
 596
 597         /* Check for the end of cairo path data, that is when
 598          * @segment is composed by only CAIRO_PATH_MOVE_TO */
 599         if (new_num_data <= move_length)
 600             return 0;
 601
 602         /* Check if this is the last CAIRO_PATH_MOVE_TO */
 603         if (new_data[move_length].header.type != CAIRO_PATH_MOVE_TO)
 604             break;
 605
 606         new_data += move_length;
 607         new_num_data -= move_length;
 608     }
 609
 610     segment->data = new_data;
 611     segment->num_data = new_num_data;
 612
 613     return 1;
 614 }
 615
 616 /*
 617  * reshape:
 618  * @segment: a #CpmlSegment
 619  *
 620  * Looks for the segment termination, that is the end of the underlying
 621  * cairo path or a %CPML_MOVE operation. <structfield>num_data</structfield>
 622  * field is modified to properly point to the end of @segment.
 623  * @segment must have only one leading %CPML_MOVE and it is supposed
 624  * to be non-empty, conditions yet imposed by the ensure_one_leading_move().
 625  *
 626  * This function also checks that all the components of @segment
 627  * are valid primitives.
 628  *
 629  * Returns: 1 on success, 0 on invalid primitive found.
 630  **/
 631 static int
 632 reshape(CpmlSegment *segment)
 633 {
 634     const cairo_path_data_t *data;
 635     int trailing_data, new_num_data, length;
 636
 637     data = segment->data;
 638     new_num_data = 0;
 639     trailing_data = segment->num_data;
 640
 641     while (1) {
 642         length = data->header.length;
 643         new_num_data += length;
 644         trailing_data -= length;
 645         data += length;
 646
 647         /* Check for invalid data size */
 648         if (trailing_data < 0)
 649             return 0;
 650
 651         if (trailing_data == 0 || data->header.type == CAIRO_PATH_MOVE_TO)
 652             break;
 653
 654         /* Ensure that all the components are valid primitives */
 655         if (cpml_primitive_type_get_n_points(data->header.type) == 0)
 656             return 0;
 657     }
 658
 659     segment->num_data = new_num_data;
 660     return 1;
 661 }