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