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_move_to      (CpmlSegment       *segment);
  88 static void             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 leading #CPML_MOVE primitives and setting
  98  * the internal segment structure accordling. A pointer to the
  99  * source cairo path is kept.
 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     int rest = segment->path->num_data - segment->num_data +
 171         segment->path->data - segment->data;
 172
 173     if (rest <= 0)
 174         return 0;
 175
 176     segment->data += segment->num_data;
 177     segment->num_data = rest;
 178
 179     return normalize(segment);
 180 }
 181
 182 /**
 183  * cpml_segment_get_length:
 184  * @segment: a #CpmlSegment
 185  *
 186  * Gets the whole length of @segment.
 187  *
 188  * Returns: the requested length
 189  **/
 190 double
 191 cpml_segment_get_length(const CpmlSegment *segment)
 192 {
 193     CpmlPrimitive primitive;
 194     double length;
 195
 196     cpml_primitive_from_segment(&primitive, (CpmlSegment *) segment);
 197     length = 0;
 198
 199     do {
 200         length += cpml_primitive_get_length(&primitive);
 201     } while (cpml_primitive_next(&primitive));
 202
 203     return length;
 204 }
 205
 206 /**
 207  * cpml_segment_put_extents:
 208  * @segment: a #CpmlSegment
 209  * @extents: where to store the extents
 210  *
 211  * Gets the whole extents of @segment.
 212  **/
 213 void
 214 cpml_segment_put_extents(const CpmlSegment *segment, CpmlExtents *extents)
 215 {
 216     CpmlPrimitive primitive;
 217     CpmlExtents primitive_extents;
 218
 219     extents->is_defined = 0;
 220
 221     cpml_primitive_from_segment(&primitive, (CpmlSegment *) segment);
 222
 223     do {
 224         cpml_primitive_put_extents(&primitive, &primitive_extents);
 225         cpml_extents_add(extents, &primitive_extents);
 226     } while (cpml_primitive_next(&primitive));
 227 }
 228
 229 /**
 230  * cpml_segment_put_pair_at:
 231  * @segment: a #CpmlSegment
 232  * @pos:     the position value
 233  * @pair:    the destination #CpmlPair
 234  *
 235  * Gets the coordinates of the point lying on @segment at position
 236  * @pos. @pos is an homogeneous factor where %0 is the start point,
 237  * %1 the end point, %0.5 the mid point and so on.
 238  * The relation %0 < @pos < %1 should be satisfied, although some
 239  * cases accept value outside this range.
 240  *
 241  * <important>
 242  * <title>TODO</title>
 243  * <itemizedlist>
 244  * <listitem>The actual implementation returns only the start and end points,
 245  *           that is only when @pos is %0 or %1.</listitem>
 246  * </itemizedlist>
 247  * </important>
 248  **/
 249 void
 250 cpml_segment_put_pair_at(const CpmlSegment *segment, double pos,
 251                          CpmlPair *pair)
 252 {
 253     CpmlPrimitive primitive;
 254
 255     cpml_primitive_from_segment(&primitive, (CpmlSegment *) segment);
 256
 257     /* Handle the common cases: start and end points */
 258     if (pos == 0)
 259         return cpml_primitive_put_pair_at(&primitive, 0, pair);
 260
 261     if (pos == 1) {
 262         while (cpml_primitive_next(&primitive))
 263             ;
 264         return 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 void
 289 cpml_segment_put_vector_at(const CpmlSegment *segment, double pos,
 290                            CpmlVector *vector)
 291 {
 292     CpmlPrimitive primitive;
 293
 294     cpml_primitive_from_segment(&primitive, (CpmlSegment *) segment);
 295
 296     /* Handle the common cases: start and end points */
 297     if (pos == 0) {
 298         cpml_primitive_put_vector_at(&primitive, 0, vector);
 299         return;
 300     }
 301
 302     if (pos == 1) {
 303         while (cpml_primitive_next(&primitive))
 304             ;
 305         cpml_primitive_put_vector_at(&primitive, 1, vector);
 306         return;
 307     }
 308 }
 309
 310 /**
 311  * cpml_segment_put_intersections:
 312  * @segment:  the first #CpmlSegment
 313  * @segment2: the second #CpmlSegment
 314  * @n_dest:   maximum number of intersections to return
 315  * @dest:     the destination vector of #CpmlPair
 316  *
 317  * Computes the intersections between @segment and @segment2 and
 318  * returns the found points in @dest. If the intersections are more
 319  * than @n_dest, only the first @n_dest pairs are stored in @dest.
 320  *
 321  * To get the job done, the primitives of @segment are sequentially
 322  * scanned for intersections with any primitive in @segment2. This
 323  * means @segment has a higher precedence over @segment2.
 324  *
 325  * Returns: the number of intersections found
 326  **/
 327 size_t
 328 cpml_segment_put_intersections(const CpmlSegment *segment,
 329                                const CpmlSegment *segment2,
 330                                size_t n_dest, CpmlPair *dest)
 331 {
 332     CpmlPrimitive portion;
 333     size_t partial, total;
 334
 335     cpml_primitive_from_segment(&portion, (CpmlSegment *) segment);
 336     total = 0;
 337
 338     do {
 339         partial = cpml_primitive_put_intersections_with_segment(&portion,
 340                                                                 segment2,
 341                                                                 n_dest - total,
 342                                                                 dest + total);
 343         total += partial;
 344     } while (total < n_dest && cpml_primitive_next(&portion));
 345
 346     return total;
 347 }
 348
 349 /**
 350  * cpml_segment_offset:
 351  * @segment: a #CpmlSegment
 352  * @offset: the offset distance
 353  *
 354  * Offsets a segment of the specified amount, that is builds a "parallel"
 355  * segment at the @offset distance from the original one and returns the
 356  * result by replacing the original @segment.
 357  *
 358  * <important>
 359  * <title>TODO</title>
 360  * <itemizedlist>
 361  * <listitem>Closed path are not yet managed: an elegant solution is not
 362  *           so obvious: use cpml_close_offset() when available.</listitem>
 363  * <listitem>Degenerated primitives, such as lines of length 0, are not
 364  *           managed properly.</listitem>
 365  * </itemizedlist>
 366  * </important>
 367  **/
 368 void
 369 cpml_segment_offset(CpmlSegment *segment, double offset)
 370 {
 371     CpmlPrimitive primitive;
 372     CpmlPrimitive last_primitive;
 373     cairo_path_data_t org, old_end;
 374     cairo_bool_t first_cycle;
 375
 376     cpml_primitive_from_segment(&primitive, segment);
 377     first_cycle = 1;
 378
 379     do {
 380         if (!first_cycle) {
 381             org = old_end;
 382             primitive.org = &org;
 383         }
 384
 385         old_end = *cpml_primitive_get_point(&primitive, -1);
 386         cpml_primitive_offset(&primitive, offset);
 387
 388         if (!first_cycle) {
 389             cpml_primitive_join(&last_primitive, &primitive);
 390             primitive.org = cpml_primitive_get_point(&last_primitive, -1);
 391         }
 392
 393         cpml_primitive_copy(&last_primitive, &primitive);
 394         first_cycle = 0;
 395     } while (cpml_primitive_next(&primitive));
 396 }
 397
 398 /**
 399  * cpml_segment_transform:
 400  * @segment: a #CpmlSegment
 401  * @matrix: the matrix to be applied
 402  *
 403  * Applies @matrix on all the points of @segment.
 404  **/
 405 void
 406 cpml_segment_transform(CpmlSegment *segment, const cairo_matrix_t *matrix)
 407 {
 408     cairo_path_data_t *data;
 409     int n, n_point, num_points;
 410
 411     data = segment->data;
 412
 413     for (n = 0; n < segment->num_data; n += num_points) {
 414         num_points = data->header.length;
 415         ++data;
 416         for (n_point = 1; n_point < num_points; ++n_point) {
 417             cairo_matrix_transform_point(matrix, &data->point.x, &data->point.y);
 418             ++data;
 419         }
 420     }
 421 }
 422
 423 /**
 424  * cpml_segment_reverse:
 425  * @segment: a #CpmlSegment
 426  *
 427  * Reverses @segment in-place. The resulting rendering will be the same,
 428  * but with the primitives generated in reverse order.
 429  **/
 430 void
 431 cpml_segment_reverse(CpmlSegment *segment)
 432 {
 433     cairo_path_data_t *data, *dst_data;
 434     size_t data_size;
 435     double end_x, end_y;
 436     int n, num_points, n_point;
 437     const cairo_path_data_t *src_data;
 438
 439     data_size = sizeof(cairo_path_data_t) * segment->num_data;
 440     data = cpml_alloca(data_size);
 441     end_x = segment->data[1].point.x;
 442     end_y = segment->data[1].point.y;
 443
 444     for (n = 2; n < segment->num_data; ++n) {
 445         src_data = segment->data + n;
 446         num_points = src_data->header.length;
 447
 448         dst_data = data + segment->num_data - n - num_points + 2;
 449         dst_data->header.type = src_data->header.type;
 450         dst_data->header.length = num_points;
 451
 452         for (n_point = 1; n_point < num_points; ++n_point) {
 453             dst_data[num_points - n_point].point.x = end_x;
 454             dst_data[num_points - n_point].point.y = end_y;
 455             end_x = src_data[n_point].point.x;
 456             end_y = src_data[n_point].point.y;
 457         }
 458
 459         n += n_point - 1;
 460     }
 461
 462     data[0].header.type = CPML_MOVE;
 463     data[0].header.length = 2;
 464     data[1].point.x = end_x;
 465     data[1].point.y = end_y;
 466     memcpy(segment->data, data, data_size);
 467 }
 468
 469 /**
 470  * cpml_segment_to_cairo:
 471  * @segment: a #CpmlSegment
 472  * @cr: the destination cairo context
 473  *
 474  * Appends the path of @segment to @cr. The segment is "flattened",
 475  * that is #CPML_ARC primitives are approximated by one or more
 476  * #CPML_CURVE using cpml_arc_to_cairo(). Check its documentation
 477  * for further details.
 478  **/
 479 void
 480 cpml_segment_to_cairo(const CpmlSegment *segment, cairo_t *cr)
 481 {
 482     CpmlPrimitive primitive;
 483
 484     cpml_primitive_from_segment(&primitive, (CpmlSegment *) segment);
 485
 486     do {
 487         cpml_primitive_to_cairo(&primitive, cr);
 488     } while (cpml_primitive_next(&primitive));
 489 }
 490
 491 /**
 492  * cpml_segment_dump:
 493  * @segment: a #CpmlSegment
 494  *
 495  * Dumps the specified @segment to stdout. Useful for debugging purposes.
 496  **/
 497 void
 498 cpml_segment_dump(const CpmlSegment *segment)
 499 {
 500     CpmlPrimitive primitive;
 501     cairo_bool_t first_call = 1;
 502
 503     cpml_primitive_from_segment(&primitive, (CpmlSegment *) segment);
 504
 505     do {
 506         cpml_primitive_dump(&primitive, first_call);
 507         first_call = 0;
 508     } while (cpml_primitive_next(&primitive));
 509 }
 510
 511
 512 /**
 513  * normalize:
 514  * @segment: a #CpmlSegment
 515  *
 516  * Strips the leading #CPML_MOVE primitives, updating the #CpmlSegment
 517  * structure accordingly. One, and only one, #CPML_MOVE primitive is left.
 518  *
 519  * Returns: 1 on success, 0 on no leading MOVE_TOs or on errors
 520  **/
 521 static cairo_bool_t
 522 normalize(CpmlSegment *segment)
 523 {
 524     if (!ensure_one_move_to(segment))
 525         return 0;
 526
 527     reshape(segment);
 528     return 1;
 529 }
 530
 531 /**
 532  * ensure_one_move_to:
 533  * @segment: a #CpmlSegment
 534  *
 535  * Strips the leading #CPML_MOVE primitives, updating the
 536  * <structname>CpmlSegment</structname> structure accordingly.
 537  * One, and only one, #CPML_MOVE primitive is left.
 538  *
 539  * Returns: 1 on success, 0 on no leading MOVE_TOs or on empty path
 540  **/
 541 static cairo_bool_t
 542 ensure_one_move_to(CpmlSegment *segment)
 543 {
 544     cairo_path_data_t *new_data;
 545     int new_num_data, length;
 546
 547     new_data = segment->data;
 548
 549     /* Check for at least one move to */
 550     if (new_data->header.type != CPML_MOVE)
 551         return 0;
 552
 553     new_num_data = segment->num_data;
 554     length = 0;
 555
 556     /* Strip the leading CPML_MOVE, leaving only the last one */
 557     do {
 558         new_data += length;
 559         new_num_data -= length;
 560         length = new_data->header.length;
 561
 562         /* Check for end of cairo path data */
 563         if (length >= new_num_data)
 564             return 0;
 565     } while (new_data[length].header.type == CPML_MOVE);
 566
 567     segment->data = new_data;
 568     segment->num_data = new_num_data;
 569
 570     return 1;
 571 }
 572
 573 /**
 574  * reshape:
 575  * @segment: a #CpmlSegment
 576  *
 577  * Looks for the segment termination and modify the
 578  * <structfield>num_data</structfield> field of @segment accordling.
 579  * @segment must have only one leading #CPML_MOVE and it is supposed
 580  * to be non-empty, conditions yet imposed by the
 581  * ensure_one_move_to() function.
 582  **/
 583 static void
 584 reshape(CpmlSegment *segment)
 585 {
 586     cairo_path_data_t *data;
 587     int num_data, new_num_data, length;
 588
 589     /* Skip the leading move to */
 590     new_num_data = 2;
 591     data = segment->data + new_num_data;
 592
 593     /* Calculate the remaining data in the cairo path */
 594     num_data = segment->path->num_data -
 595                (segment->data - segment->path->data);
 596
 597     while (new_num_data < num_data) {
 598         /* A primitive is considered valid if it has at least one point */
 599         if (cpml_primitive_type_get_n_points(data->header.type) == 0)
 600             break;
 601
 602         length = data->header.length;
 603         data += length;
 604         new_num_data += length;
 605     }
 606
 607     segment->num_data = new_num_data;
 608 }