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