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