src/cpml/cpml-segment.c

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