cpml/cpml-segment.c

   1 /* CPML - Cairo Path Manipulation Library
   2  * Copyright (C) 2008, 2009  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 %CAIRO_PATH_MOVE_TO 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 %CAIRO_PATH_ARC_TO
  56  * primitives. This is not a native cairo primitive and having two
  57  * different data types is a good way to make clear when a function
  58  * expect or not 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 %CAIRO_PATH_MOVE_TO
  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-segment.h"
  76 #include "cpml-primitive.h"
  77 #include "cpml-line.h"
  78 #include "cpml-curve.h"
  79 #include "cpml-pair.h"
  80 #include "cpml-alloca.h"
  81
  82 #include <stdio.h>
  83 #include <string.h>
  84
  85 static cairo_bool_t     normalize               (CpmlSegment       *segment);
  86 static cairo_bool_t     ensure_one_move_to      (CpmlSegment       *segment);
  87 static void             reshape                 (CpmlSegment       *segment);
  88
  89
  90 /**
  91  * cpml_segment_from_cairo:
  92  * @segment: a #CpmlSegment
  93  * @path: the source #CpmlPath
  94  *
  95  * Builds a CpmlSegment from a #CpmlPath structure. This operation
  96  * involves stripping the leading %CAIRO_PATH_MOVE_TO primitives and
  97  * setting the internal segment structure accordling. A pointer to the
  98  * source cairo path is kept.
  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 %CAIRO_PATH_MOVE_TO, so no
 103  * dependency on the cairo context is needed.
 104  *
 105  * Return value: 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  * Return value: @segment or %NULL on errors
 130  **/
 131 CpmlSegment *
 132 cpml_segment_copy(CpmlSegment *segment, const CpmlSegment *src)
 133 {
 134     if (segment == NULL || src == NULL)
 135         return NULL;
 136
 137     return memcpy(segment, src, sizeof(CpmlSegment));
 138 }
 139
 140
 141 /**
 142  * cpml_segment_reset:
 143  * @segment: a #CpmlSegment
 144  *
 145  * Modifies @segment to point to the first segment of the source cairo path.
 146  **/
 147 void
 148 cpml_segment_reset(CpmlSegment *segment)
 149 {
 150     segment->data = segment->path->data;
 151     segment->num_data = segment->path->num_data;
 152     normalize(segment);
 153 }
 154
 155 /**
 156  * cpml_segment_next:
 157  * @segment: a #CpmlSegment
 158  *
 159  * Modifies @segment to point to the next segment of the source cairo path.
 160  *
 161  * Return value: 1 on success, 0 if no next segment found or errors
 162  **/
 163 cairo_bool_t
 164 cpml_segment_next(CpmlSegment *segment)
 165 {
 166     int rest = segment->path->num_data - segment->num_data +
 167         segment->path->data - segment->data;
 168
 169     if (rest <= 0)
 170         return 0;
 171
 172     segment->data += segment->num_data;
 173     segment->num_data = rest;
 174
 175     return normalize(segment);
 176 }
 177
 178
 179 /**
 180  * cpml_segment_length:
 181  * @segment: a #CpmlSegment
 182  *
 183  * Gets the whole length of @segment.
 184  *
 185  * Returns: the requested length
 186  **/
 187 double
 188 cpml_segment_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_length(&primitive);
 198     } while (cpml_primitive_next(&primitive));
 199
 200     return length;
 201 }
 202
 203 /**
 204  * cpml_segment_extents:
 205  * @segment: a #CpmlSegment
 206  * @extents: where to store the extents
 207  *
 208  * Gets the whole extents of @segment.
 209  **/
 210 void
 211 cpml_segment_extents(const CpmlSegment *segment, CpmlExtents *extents)
 212 {
 213     CpmlPrimitive primitive;
 214     CpmlExtents primitive_extents;
 215
 216     extents->is_defined = 0;
 217
 218     cpml_primitive_from_segment(&primitive, (CpmlSegment *) segment);
 219
 220     do {
 221         cpml_primitive_extents(&primitive, &primitive_extents);
 222         cpml_extents_add(extents, &primitive_extents);
 223     } while (cpml_primitive_next(&primitive));
 224 }
 225
 226 /**
 227  * cpml_segment_pair_at:
 228  * @segment: a #CpmlSegment
 229  * @pair:    the destination #CpmlPair
 230  * @pos:     the position value
 231  *
 232  * Gets the coordinates of the point lying on @segment at position
 233  * @pos. @pos is an homogeneous factor where %0 is the start point,
 234  * %1 the end point, %0.5 the mid point and so on.
 235  * The relation %0 < @pos < %1 should be satisfied, although some
 236  * cases accept value outside this range.
 237  *
 238  * <important>
 239  * <title>TODO</title>
 240  * <itemizedlist>
 241  * <listitem>The actual implementation returns only the start and end points,
 242  *           that is only when @pos is %0 or %1.</listitem>
 243  * </itemizedlist>
 244  * </important>
 245  **/
 246 void
 247 cpml_segment_pair_at(const CpmlSegment *segment, CpmlPair *pair, double pos)
 248 {
 249     CpmlPrimitive primitive;
 250
 251     cpml_primitive_from_segment(&primitive, (CpmlSegment *) segment);
 252
 253     /* Handle the common cases: start and end points */
 254     if (pos == 0)
 255         return cpml_primitive_pair_at(&primitive, pair, 0);
 256
 257     if (pos == 1) {
 258         while (cpml_primitive_next(&primitive))
 259             ;
 260         return cpml_primitive_pair_at(&primitive, pair, 1);
 261     }
 262 }
 263
 264 /**
 265  * cpml_segment_vector_at:
 266  * @segment: a #CpmlSegment
 267  * @vector:  the destination #CpmlVector
 268  * @pos:     the position value
 269  *
 270  * Gets the steepness of the point lying on @segment at position
 271  * @pos. @pos is an homogeneous factor where %0 is the start point,
 272  * %1 the end point, %0.5 the mid point and so on.
 273  * The relation %0 < @pos < %1 should be satisfied, although some
 274  * cases accept value outside this range.
 275  *
 276  * <important>
 277  * <title>TODO</title>
 278  * <itemizedlist>
 279  * <listitem>The actual implementation returns only the start and end
 280  *           steepness, that is only when @pos is %0 or %1.</listitem>
 281  * </itemizedlist>
 282  * </important>
 283  **/
 284 void
 285 cpml_segment_vector_at(const CpmlSegment *segment,
 286                        CpmlVector *vector, double pos)
 287 {
 288     CpmlPrimitive primitive;
 289
 290     cpml_primitive_from_segment(&primitive, (CpmlSegment *) segment);
 291
 292     /* Handle the common cases: start and end points */
 293     if (pos == 0) {
 294         cpml_primitive_vector_at(&primitive, vector, 0);
 295         return;
 296     }
 297
 298     if (pos == 1) {
 299         while (cpml_primitive_next(&primitive))
 300             ;
 301         cpml_primitive_vector_at(&primitive, vector, 1);
 302         return;
 303     }
 304 }
 305
 306
 307 /**
 308  * cpml_segment_to_cairo:
 309  * @segment: a #CpmlSegment
 310  * @cr: the destination cairo context
 311  *
 312  * Appends the path of @segment to @cr. The segment is "flattened",
 313  * that is %CAIRO_PATH_ARC_TO primitives are approximated by one
 314  * or more %CAIRO_PATH_CURVE_TO using cpml_arc_to_cairo(). Check
 315  * its documentation for further details.
 316  **/
 317 void
 318 cpml_segment_to_cairo(const CpmlSegment *segment, cairo_t *cr)
 319 {
 320     CpmlPrimitive primitive;
 321
 322     cpml_primitive_from_segment(&primitive, (CpmlSegment *) segment);
 323
 324     do {
 325         cpml_primitive_to_cairo(&primitive, cr);
 326     } while (cpml_primitive_next(&primitive));
 327 }
 328
 329 /**
 330  * cpml_segment_dump:
 331  * @segment: a #CpmlSegment
 332  *
 333  * Dumps the specified @segment to stdout. Useful for debugging purposes.
 334  **/
 335 void
 336 cpml_segment_dump(const CpmlSegment *segment)
 337 {
 338     CpmlPrimitive primitive;
 339     cairo_bool_t first_call = 1;
 340
 341     cpml_primitive_from_segment(&primitive, (CpmlSegment *) segment);
 342
 343     do {
 344         cpml_primitive_dump(&primitive, first_call);
 345         first_call = 0;
 346     } while (cpml_primitive_next(&primitive));
 347 }
 348
 349
 350 /**
 351  * cpml_segment_reverse:
 352  * @segment: a #CpmlSegment
 353  *
 354  * Reverses @segment in-place. The resulting rendering will be the same,
 355  * but with the primitives generated in reverse order.
 356  **/
 357 void
 358 cpml_segment_reverse(CpmlSegment *segment)
 359 {
 360     cairo_path_data_t *data, *dst_data;
 361     size_t data_size;
 362     double end_x, end_y;
 363     int n, num_points, n_point;
 364     const cairo_path_data_t *src_data;
 365
 366     data_size = sizeof(cairo_path_data_t) * segment->num_data;
 367     data = cpml_alloca(data_size);
 368     end_x = segment->data[1].point.x;
 369     end_y = segment->data[1].point.y;
 370
 371     for (n = 2; n < segment->num_data; ++n) {
 372         src_data = segment->data + n;
 373         num_points = src_data->header.length;
 374
 375         dst_data = data + segment->num_data - n - num_points + 2;
 376         dst_data->header.type = src_data->header.type;
 377         dst_data->header.length = num_points;
 378
 379         for (n_point = 1; n_point < num_points; ++n_point) {
 380             dst_data[num_points - n_point].point.x = end_x;
 381             dst_data[num_points - n_point].point.y = end_y;
 382             end_x = src_data[n_point].point.x;
 383             end_y = src_data[n_point].point.y;
 384         }
 385
 386         n += n_point - 1;
 387     }
 388
 389     data[0].header.type = CAIRO_PATH_MOVE_TO;
 390     data[0].header.length = 2;
 391     data[1].point.x = end_x;
 392     data[1].point.y = end_y;
 393     memcpy(segment->data, data, data_size);
 394 }
 395
 396 /**
 397  * cpml_segment_transform:
 398  * @segment: a #CpmlSegment
 399  * @matrix: the matrix to be applied
 400  *
 401  * Applies @matrix on all the points of @segment.
 402  **/
 403 void
 404 cpml_segment_transform(CpmlSegment *segment, const cairo_matrix_t *matrix)
 405 {
 406     cairo_path_data_t *data;
 407     int n, n_point, num_points;
 408
 409     data = segment->data;
 410
 411     for (n = 0; n < segment->num_data; n += num_points) {
 412         num_points = data->header.length;
 413         ++data;
 414         for (n_point = 1; n_point < num_points; ++n_point) {
 415             cairo_matrix_transform_point(matrix, &data->point.x, &data->point.y);
 416             ++data;
 417         }
 418     }
 419 }
 420
 421 /**
 422  * cpml_segment_intersection:
 423  * @segment:  the first #CpmlSegment
 424  * @segment2: the second #CpmlSegment
 425  * @dest:     the destination vector of #CpmlPair
 426  * @max:      maximum number of intersections to return
 427  *
 428  * Computes the intersections between @segment and @segment2 and
 429  * returns the found points in @dest. If the intersections are more
 430  * than @max, only the first @max pairs are stored in @dest.
 431  *
 432  * To get the job done, the primitives of @segment are sequentially
 433  * scanned for intersections with any primitive in @segment2. This
 434  * means @segment has a higher precedence over @segment2.
 435  *
 436  * Return value: the number of intersections found
 437  **/
 438 int
 439 cpml_segment_intersection(const CpmlSegment *segment,
 440                           const CpmlSegment *segment2,
 441                           CpmlPair *dest, int max)
 442 {
 443     CpmlPrimitive portion;
 444     int partial, total;
 445
 446     cpml_primitive_from_segment(&portion, (CpmlSegment *) segment);
 447     total = 0;
 448
 449     do {
 450         partial = cpml_primitive_intersection_with_segment(&portion,
 451                                                            segment2,
 452                                                            dest + total,
 453                                                            max - total);
 454         total += partial;
 455     } while (total < max && cpml_primitive_next(&portion));
 456
 457     return total;
 458 }
 459
 460 /**
 461  * cpml_segment_offset:
 462  * @segment: a #CpmlSegment
 463  * @offset: the offset distance
 464  *
 465  * Offsets a segment of the specified amount, that is builds a "parallel"
 466  * segment at the @offset distance from the original one and returns the
 467  * result by replacing the original @segment.
 468  *
 469  * <important>
 470  * <title>TODO</title>
 471  * <itemizedlist>
 472  * <listitem>Closed path are not yet managed: an elegant solution is not
 473  *           so obvious: use cpml_close_offset() when available.</listitem>
 474  * <listitem>Degenerated primitives, such as lines of length 0, are not
 475  *           managed properly.</listitem>
 476  * </itemizedlist>
 477  * </important>
 478  **/
 479 void
 480 cpml_segment_offset(CpmlSegment *segment, double offset)
 481 {
 482     CpmlPrimitive primitive;
 483     CpmlPrimitive last_primitive;
 484     cairo_path_data_t org, old_end;
 485     cairo_bool_t first_cycle;
 486
 487     cpml_primitive_from_segment(&primitive, segment);
 488     first_cycle = 1;
 489
 490     do {
 491         if (!first_cycle) {
 492             org = old_end;
 493             primitive.org = &org;
 494         }
 495
 496         old_end = *cpml_primitive_get_point(&primitive, -1);
 497         cpml_primitive_offset(&primitive, offset);
 498
 499         if (!first_cycle) {
 500             cpml_primitive_join(&last_primitive, &primitive);
 501             primitive.org = cpml_primitive_get_point(&last_primitive, -1);
 502         }
 503
 504         cpml_primitive_copy(&last_primitive, &primitive);
 505         first_cycle = 0;
 506     } while (cpml_primitive_next(&primitive));
 507 }
 508
 509 /**
 510  * normalize:
 511  * @segment: a #CpmlSegment
 512  *
 513  * Strips the leading %CAIRO_PATH_MOVE_TO primitives, updating
 514  * the CpmlSegment structure accordling. One, and only one,
 515  * %CAIRO_PATH_MOVE_TO primitive is left.
 516  *
 517  * Return value: 1 on success, 0 on no leading MOVE_TOs or on errors
 518  **/
 519 static cairo_bool_t
 520 normalize(CpmlSegment *segment)
 521 {
 522     if (!ensure_one_move_to(segment))
 523         return 0;
 524
 525     reshape(segment);
 526     return 1;
 527 }
 528
 529 /**
 530  * ensure_one_move_to:
 531  * @segment: a #CpmlSegment
 532  *
 533  * Strips the leading %CAIRO_PATH_MOVE_TO primitives, updating
 534  * the <structname>CpmlSegment</structname> structure accordling.
 535  * One, and only one, %CAIRO_PATH_MOVE_TO primitive is left.
 536  *
 537  * Return value: 1 on success, 0 on no leading MOVE_TOs or on empty path
 538  **/
 539 static cairo_bool_t
 540 ensure_one_move_to(CpmlSegment *segment)
 541 {
 542     cairo_path_data_t *new_data;
 543     int new_num_data, length;
 544
 545     new_data = segment->data;
 546
 547     /* Check for at least one move to */
 548     if (new_data->header.type != CAIRO_PATH_MOVE_TO)
 549         return 0;
 550
 551     new_num_data = segment->num_data;
 552     length = 0;
 553
 554     /* Strip the leading CAIRO_PATH_MOVE_TO, leaving only the last one */
 555     do {
 556         new_data += length;
 557         new_num_data -= length;
 558         length = new_data->header.length;
 559
 560         /* Check for end of cairo path data */
 561         if (length >= new_num_data)
 562             return 0;
 563     } while (new_data[length].header.type == CAIRO_PATH_MOVE_TO);
 564
 565     segment->data = new_data;
 566     segment->num_data = new_num_data;
 567
 568     return 1;
 569 }
 570
 571 /**
 572  * reshape:
 573  * @segment: a #CpmlSegment
 574  *
 575  * Looks for the segment termination and modify the
 576  * <structfield>num_data</structfield> field of @segment accordling.
 577  * @segment must have only one leading %CAIRO_PATH_MOVE_TO and
 578  * it is supposed to be non-empty, conditions yet imposed by the
 579  * ensure_one_move_to() function.
 580  **/
 581 static void
 582 reshape(CpmlSegment *segment)
 583 {
 584     cairo_path_data_t *data;
 585     int num_data, new_num_data, length;
 586
 587     /* Skip the leading move to */
 588     new_num_data = 2;
 589     data = segment->data + new_num_data;
 590
 591     /* Calculate the remaining data in the cairo path */
 592     num_data = segment->path->num_data -
 593                (segment->data - segment->path->data);
 594
 595     while (new_num_data < num_data) {
 596         /* A primitive is considered valid if it has implemented
 597          * its own type_get_npoints() */
 598         if (cpml_primitive_type_get_npoints(data->header.type) < 0)
 599             break;
 600
 601         length = data->header.length;
 602         data += length;
 603         new_num_data += length;
 604     }
 605
 606     segment->num_data = new_num_data;
 607 }