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