src/cpml/cpml-segment.c

   1 /* CPML - Cairo Path Manipulation Library
   2  * Copyright (C) 2007,2008,2009,2010,2011,2012,2013  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 #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,
  98  *                           %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 defined and in a perfect state */
 106     if (path == NULL || path->num_data == 0 ||
 107         path->status != CAIRO_STATUS_SUCCESS)
 108         return 0;
 109
 110     segment->path = path;
 111     segment->data = path->data;
 112     segment->num_data = path->num_data;
 113
 114     return normalize(segment);
 115 }
 116
 117 /**
 118  * cpml_segment_copy:
 119  * @segment: a #CpmlSegment
 120  * @src: the source segment to copy
 121  *
 122  * Makes a shallow copy of @src into @segment.
 123  *
 124  * Since: 1.0
 125  **/
 126 void
 127 cpml_segment_copy(CpmlSegment *segment, const CpmlSegment *src)
 128 {
 129     memcpy(segment, src, sizeof(CpmlSegment));
 130 }
 131
 132 /**
 133  * cpml_segment_reset:
 134  * @segment: a #CpmlSegment
 135  *
 136  * Modifies @segment to point to the first segment of the source cairo path.
 137  *
 138  * Since: 1.0
 139  **/
 140 void
 141 cpml_segment_reset(CpmlSegment *segment)
 142 {
 143     segment->data = segment->path->data;
 144     segment->num_data = segment->path->num_data;
 145     normalize(segment);
 146 }
 147
 148 /**
 149  * cpml_segment_next:
 150  * @segment: a #CpmlSegment
 151  *
 152  * Modifies @segment to point to the next segment of the source cairo path.
 153  *
 154  * Returns: (type gboolean): %1 on success,
 155  *                           %0 if no next segment found or errors
 156  *
 157  * Since: 1.0
 158  **/
 159 int
 160 cpml_segment_next(CpmlSegment *segment)
 161 {
 162     cairo_path_data_t *new_data;
 163     const cairo_path_data_t *end_data;
 164
 165     new_data = segment->data + segment->num_data;
 166     end_data = segment->path->data + segment->path->num_data;
 167
 168     if (new_data >= end_data)
 169         return 0;
 170
 171     segment->data = new_data;
 172     segment->num_data = end_data - new_data;
 173
 174     return normalize(segment);
 175 }
 176
 177 /**
 178  * cpml_segment_get_length:
 179  * @segment: a #CpmlSegment
 180  *
 181  * Gets the whole length of @segment.
 182  *
 183  * Returns: the requested length
 184  *
 185  * Since: 1.0
 186  **/
 187 double
 188 cpml_segment_get_length(const CpmlSegment *segment)
 189 {
 190     CpmlPrimitive primitive;
 191     double length;
 192
 193     cpml_primitive_from_segment(&primitive, (CpmlSegment *) segment);
 194     length = 0;
 195
 196     do {
 197         length += cpml_primitive_get_length(&primitive);
 198     } while (cpml_primitive_next(&primitive));
 199
 200     return length;
 201 }
 202
 203 /**
 204  * cpml_segment_put_extents:
 205  * @segment: a #CpmlSegment
 206  * @extents: where to store the extents
 207  *
 208  * Gets the whole extents of @segment.
 209  *
 210  * Since: 1.0
 211  **/
 212 void
 213 cpml_segment_put_extents(const CpmlSegment *segment, CpmlExtents *extents)
 214 {
 215     CpmlPrimitive primitive;
 216     CpmlExtents primitive_extents;
 217
 218     extents->is_defined = 0;
 219
 220     cpml_primitive_from_segment(&primitive, (CpmlSegment *) segment);
 221
 222     do {
 223         cpml_primitive_put_extents(&primitive, &primitive_extents);
 224         cpml_extents_add(extents, &primitive_extents);
 225     } while (cpml_primitive_next(&primitive));
 226 }
 227
 228 /**
 229  * cpml_segment_put_pair_at:
 230  * @segment: a #CpmlSegment
 231  * @pos:     the position value
 232  * @pair:    the destination #CpmlPair
 233  *
 234  * Gets the coordinates of the point lying on @segment at position
 235  * @pos. @pos is an homogeneous factor where %0 is the start point,
 236  * %1 the end point, %0.5 the mid point and so on.
 237  * The relation %0 < @pos < %1 should be satisfied, although some
 238  * cases accept value outside this range.
 239  *
 240  * <important>
 241  * <title>TODO</title>
 242  * <itemizedlist>
 243  * <listitem>The actual implementation returns only the start and end points,
 244  *           that is only when @pos is %0 or %1.</listitem>
 245  * </itemizedlist>
 246  * </important>
 247  *
 248  * Since: 1.0
 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         cpml_primitive_put_pair_at(&primitive, 0, pair);
 261     } if (pos == 1) {
 262         while (cpml_primitive_next(&primitive))
 263             ;
 264         cpml_primitive_put_pair_at(&primitive, 1, pair);
 265     }
 266 }
 267
 268 /**
 269  * cpml_segment_put_vector_at:
 270  * @segment: a #CpmlSegment
 271  * @pos:     the position value
 272  * @vector:  the destination #CpmlVector
 273  *
 274  * Gets the steepness of the point lying on @segment at position
 275  * @pos. @pos is an homogeneous factor where %0 is the start point,
 276  * %1 the end point, %0.5 the mid point and so on.
 277  * The relation %0 < @pos < %1 should be satisfied, although some
 278  * cases accept value outside this range.
 279  *
 280  * <important>
 281  * <title>TODO</title>
 282  * <itemizedlist>
 283  * <listitem>The actual implementation returns only the start and end
 284  *           steepness, that is only when @pos is %0 or %1.</listitem>
 285  * </itemizedlist>
 286  * </important>
 287  *
 288  * Since: 1.0
 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  * Since: 1.0
 330  **/
 331 size_t
 332 cpml_segment_put_intersections(const CpmlSegment *segment,
 333                                const CpmlSegment *segment2,
 334                                size_t n_dest, CpmlPair *dest)
 335 {
 336     CpmlPrimitive portion;
 337     size_t partial, total;
 338
 339     cpml_primitive_from_segment(&portion, (CpmlSegment *) segment);
 340     total = 0;
 341
 342     do {
 343         partial = cpml_primitive_put_intersections_with_segment(&portion,
 344                                                                 segment2,
 345                                                                 n_dest - total,
 346                                                                 dest + total);
 347         total += partial;
 348     } while (total < n_dest && cpml_primitive_next(&portion));
 349
 350     return total;
 351 }
 352
 353 /**
 354  * cpml_segment_offset:
 355  * @segment: a #CpmlSegment
 356  * @offset: the offset distance
 357  *
 358  * Offsets a segment of the specified amount, that is builds a "parallel"
 359  * segment at the @offset distance from the original one and returns the
 360  * result by replacing the original @segment.
 361  *
 362  * <important>
 363  * <title>TODO</title>
 364  * <itemizedlist>
 365  * <listitem>Closed path are not yet managed: an elegant solution is not
 366  *           so obvious: use cpml_close_offset() when available.</listitem>
 367  * <listitem>Degenerated primitives, such as lines of length 0, are not
 368  *           managed properly.</listitem>
 369  * </itemizedlist>
 370  * </important>
 371  *
 372  * Since: 1.0
 373  **/
 374 void
 375 cpml_segment_offset(CpmlSegment *segment, double offset)
 376 {
 377     CpmlPrimitive primitive;
 378     CpmlPrimitive last_primitive;
 379     CpmlPair old_end;
 380     cairo_path_data_t org, *old_org;
 381     int first_cycle;
 382
 383     cpml_primitive_from_segment(&primitive, segment);
 384     first_cycle = 1;
 385
 386     do {
 387         if (! first_cycle) {
 388             cpml_pair_to_cairo(&old_end, &org);
 389             old_org = primitive.org;
 390             primitive.org = &org;
 391         }
 392
 393         cpml_primitive_put_point(&primitive, -1, &old_end);
 394         cpml_primitive_offset(&primitive, offset);
 395
 396         if (! first_cycle) {
 397             cpml_primitive_join(&last_primitive, &primitive);
 398             primitive.org = old_org;
 399         }
 400
 401         cpml_primitive_copy(&last_primitive, &primitive);
 402         first_cycle = 0;
 403     } while (cpml_primitive_next(&primitive));
 404 }
 405
 406 /**
 407  * cpml_segment_transform:
 408  * @segment: a #CpmlSegment
 409  * @matrix: the matrix to be applied
 410  *
 411  * Applies @matrix on all the points of @segment.
 412  *
 413  * Since: 1.0
 414  **/
 415 void
 416 cpml_segment_transform(CpmlSegment *segment, const cairo_matrix_t *matrix)
 417 {
 418     CpmlPrimitive primitive;
 419     cairo_path_data_t *data;
 420     size_t n_points;
 421
 422     cpml_primitive_from_segment(&primitive, segment);
 423     cairo_matrix_transform_point(matrix, &(primitive.org)->point.x,
 424                                  &(primitive.org)->point.y);
 425
 426     do {
 427         data = primitive.data;
 428         if (data->header.type != CAIRO_PATH_CLOSE_PATH) {
 429             n_points = cpml_primitive_get_n_points(&primitive);
 430
 431             while (--n_points > 0) {
 432                 ++data;
 433                 cairo_matrix_transform_point(matrix,
 434                                              &data->point.x, &data->point.y);
 435             }
 436         }
 437     } while (cpml_primitive_next(&primitive));
 438 }
 439
 440 /**
 441  * cpml_segment_reverse:
 442  * @segment: a #CpmlSegment
 443  *
 444  * Reverses @segment in-place. The resulting rendering will be the same,
 445  * but with the primitives generated in reverse order.
 446  *
 447  * It is assumed that @segment has yet been sanitized, that is returned
 448  * by some CPML API function or it is a path yet conforming to the
 449  * segment rules described by the cpml_segment_from_cairo() function.
 450  *
 451  * Since: 1.0
 452  **/
 453 void
 454 cpml_segment_reverse(CpmlSegment *segment)
 455 {
 456     cairo_path_data_t *data, *dst_data;
 457     size_t data_size;
 458     double end_x, end_y;
 459     int n, length;
 460     size_t n_points, n_point;
 461     const cairo_path_data_t *src_data;
 462
 463     data_size = sizeof(cairo_path_data_t) * segment->num_data;
 464     data = malloc(data_size);
 465     end_x = segment->data[1].point.x;
 466     end_y = segment->data[1].point.y;
 467
 468     n = segment->data->header.length;
 469     data->header.type = CAIRO_PATH_CLOSE_PATH;
 470     data->header.length = n;
 471
 472     while (n < segment->num_data) {
 473         src_data = segment->data + n;
 474         n_points = cpml_primitive_type_get_n_points(src_data->header.type);
 475         length = src_data->header.length;
 476         n += length;
 477         dst_data = data + segment->num_data - n + data->header.length;
 478         dst_data->header.type = src_data->header.type;
 479         dst_data->header.length = length;
 480
 481         for (n_point = 1; n_point < n_points; ++n_point) {
 482             dst_data[n_points - n_point].point.x = end_x;
 483             dst_data[n_points - n_point].point.y = end_y;
 484             end_x = src_data[n_point].point.x;
 485             end_y = src_data[n_point].point.y;
 486         }
 487
 488         /* Copy also the embedded data, if any */
 489         if (n_points < length) {
 490             size_t size = (length - n_points) * sizeof(cairo_path_data_t);
 491             memcpy(dst_data + n_points, src_data + n_points, size);
 492         }
 493     }
 494
 495     data[1].point.x = end_x;
 496     data[1].point.y = end_y;
 497     memcpy(segment->data, data, data_size);
 498
 499     free(data);
 500 }
 501
 502 /**
 503  * cpml_segment_to_cairo:
 504  * @segment: a #CpmlSegment
 505  * @cr: the destination cairo context
 506  *
 507  * Appends the path of @segment to @cr. The segment is "flattened",
 508  * that is %CPML_ARC primitives are approximated by one or more
 509  * %CPML_CURVE using cpml_arc_to_cairo(). Check its documentation
 510  * for further details.
 511  *
 512  * Since: 1.0
 513  **/
 514 void
 515 cpml_segment_to_cairo(const CpmlSegment *segment, cairo_t *cr)
 516 {
 517     CpmlPrimitive primitive;
 518
 519     cpml_primitive_from_segment(&primitive, (CpmlSegment *) segment);
 520
 521     do {
 522         cpml_primitive_to_cairo(&primitive, cr);
 523     } while (cpml_primitive_next(&primitive));
 524 }
 525
 526 /**
 527  * cpml_segment_dump:
 528  * @segment: a #CpmlSegment
 529  *
 530  * Dumps the specified @segment to stdout. Useful for debugging purposes.
 531  *
 532  * Since: 1.0
 533  **/
 534 void
 535 cpml_segment_dump(const CpmlSegment *segment)
 536 {
 537     CpmlPrimitive primitive;
 538     int first_call = 1;
 539
 540     cpml_primitive_from_segment(&primitive, (CpmlSegment *) segment);
 541
 542     do {
 543         cpml_primitive_dump(&primitive, first_call);
 544         first_call = 0;
 545     } while (cpml_primitive_next(&primitive));
 546 }
 547
 548
 549 /*
 550  * normalize:
 551  * @segment: a #CpmlSegment
 552  *
 553  * Sanitizes @segment by calling ensure_one_leading_move() and reshape().
 554  *
 555  * Returns: %1 on success, %0 on no leading MOVE_TOs or on errors
 556  **/
 557 static int
 558 normalize(CpmlSegment *segment)
 559 {
 560     if (!ensure_one_leading_move(segment))
 561         return 0;
 562
 563     return reshape(segment);
 564 }
 565
 566 /*
 567  * ensure_one_leading_move:
 568  * @segment: a #CpmlSegment
 569  *
 570  * Strips the leading %CPML_MOVE primitives, updating the
 571  * <structname>CpmlSegment</structname> structure accordingly.
 572  * One, and only one, %CPML_MOVE primitive is left.
 573  *
 574  * Returns: %1 on success, %0 on no leading MOVE_TOs or on empty path
 575  **/
 576 static int
 577 ensure_one_leading_move(CpmlSegment *segment)
 578 {
 579     cairo_path_data_t *new_data;
 580     int new_num_data, move_length;
 581
 582     /* Check for at least one move to */
 583     if (segment->data->header.type != CAIRO_PATH_MOVE_TO)
 584         return 0;
 585
 586     new_data = segment->data;
 587     new_num_data = segment->num_data;
 588
 589     while (1) {
 590         move_length = new_data->header.length;
 591
 592         /* Check for the end of cairo path data, that is when
 593          * @segment is composed by only CAIRO_PATH_MOVE_TO */
 594         if (new_num_data <= move_length)
 595             return 0;
 596
 597         /* Check if this is the last CAIRO_PATH_MOVE_TO */
 598         if (new_data[move_length].header.type != CAIRO_PATH_MOVE_TO)
 599             break;
 600
 601         new_data += move_length;
 602         new_num_data -= move_length;
 603     }
 604
 605     segment->data = new_data;
 606     segment->num_data = new_num_data;
 607
 608     return 1;
 609 }
 610
 611 /*
 612  * reshape:
 613  * @segment: a #CpmlSegment
 614  *
 615  * Looks for the segment termination, that is the end of the underlying
 616  * cairo path or a %CPML_MOVE operation. <structfield>num_data</structfield>
 617  * field is modified to properly point to the end of @segment.
 618  * @segment must have only one leading %CPML_MOVE and it is supposed
 619  * to be non-empty, conditions yet imposed by the ensure_one_leading_move().
 620  *
 621  * This function also checks that all the components of @segment
 622  * are valid primitives.
 623  *
 624  * Returns: %1 on success, %0 on invalid primitive found
 625  **/
 626 static int
 627 reshape(CpmlSegment *segment)
 628 {
 629     const cairo_path_data_t *data;
 630     int trailing_data, new_num_data, length;
 631
 632     data = segment->data;
 633     new_num_data = 0;
 634     trailing_data = segment->num_data;
 635
 636     while (1) {
 637         length = data->header.length;
 638         new_num_data += length;
 639         trailing_data -= length;
 640         data += length;
 641
 642         /* Check for invalid data size */
 643         if (trailing_data < 0)
 644             return 0;
 645
 646         if (trailing_data == 0 || data->header.type == CAIRO_PATH_MOVE_TO)
 647             break;
 648
 649         /* Ensure that all the components are valid primitives */
 650         if (cpml_primitive_type_get_n_points(data->header.type) == 0)
 651             return 0;
 652     }
 653
 654     segment->num_data = new_num_data;
 655     return 1;
 656 }