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  * SECTION:segment
  22  * @title: CpmlSegment
  23  * @short_description: A contiguous line that can be a fragment
  24  *                     or a whole cairo path
  25  *
  26  * A segment is a single contiguous line got from a cairo path. The
  27  * CPML library relies on one assumption to let the data be independent
  28  * from the current point (and thus from the cairo context): any segment
  29  * MUST be preceded by at least one %CAIRO_PATH_MOVE_TO primitive.
  30  * This means a valid segment in cairo could be rejected by CPML.
  31  *
  32  * #CpmlSegment provides an unobtrusive way to access a cairo path.
  33  * This means #CpmlSegment itsself does not hold any coordinates but
  34  * instead a bunch of pointers to the original #cairo_path_t struct:
  35  * modifying data throught this struct also changes the original path.
  36  *
  37  * Every #CpmlPath struct can contain more than one segment: the CPML
  38  * library provides iteration APIs to browse the segments of a path.
  39  * Use cpml_segment_reset() to reset the iterator at the start of the
  40  * cairo path (will point the first segment) and cpml_segment_next()
  41  * to get the next segment. Getting the previous segment is not provided
  42  * as the underlying cairo struct is not accessible in reverse order.
  43  *
  44  * When initialized, #CpmlSegment yet refers to the first segment so
  45  * the initial reset is not required.
  46  **/
  47
  48 /**
  49  * CpmlPath:
  50  *
  51  * This is another name for the #cairo_path_t type. Although phisically
  52  * they are the same struct, #CpmlPath conceptually embodies an important
  53  * difference: it is a cairo path that can embed %CAIRO_PATH_ARC_TO
  54  * primitives. This is not a native cairo primitive and having two
  55  * different data types is a good way to make clear when a function
  56  * expect or not embedded arc-to primitives.
  57  **/
  58
  59 /**
  60  * CpmlSegment:
  61  * @path:     the source #CpmlPath struct
  62  * @data:     the data points of the segment; the first primitive
  63  *            will always be a %CAIRO_PATH_MOVE_TO
  64  * @num_data: size of @data
  65  *
  66  * This is an unobtrusive struct to identify a segment inside a
  67  * cairo path. Unobtrusive means that the real coordinates are
  68  * still stored in @path: CpmlSegment only provides a way to
  69  * access them.
  70  **/
  71
  72 #include "cpml-segment.h"
  73 #include "cpml-primitive.h"
  74 #include "cpml-line.h"
  75 #include "cpml-curve.h"
  76 #include "cpml-pair.h"
  77 #include "cpml-alloca.h"
  78
  79 #include <stdio.h>
  80 #include <string.h>
  81
  82 static cairo_bool_t     normalize               (CpmlSegment       *segment);
  83 static cairo_bool_t     ensure_one_move_to      (CpmlSegment       *segment);
  84 static void             reshape                 (CpmlSegment       *segment);
  85
  86
  87 /**
  88  * cpml_segment_from_cairo:
  89  * @segment: a #CpmlSegment
  90  * @path: the source #CpmlPath
  91  *
  92  * Builds a CpmlSegment from a #CpmlPath structure. This operation
  93  * involves stripping the leading %CAIRO_PATH_MOVE_TO primitives and
  94  * setting the internal segment structure accordling. A pointer to the
  95  * source cairo path is kept.
  96  *
  97  * This function will fail if @path is null, empty or if its
  98  * <structfield>status</structfield> member is not %CAIRO_STATUS_SUCCESS.
  99  * Also, the first primitive must be a %CAIRO_PATH_MOVE_TO, so no
 100  * dependency on the cairo context is needed.
 101  *
 102  * Return value: 1 on success, 0 on errors
 103  **/
 104 cairo_bool_t
 105 cpml_segment_from_cairo(CpmlSegment *segment, CpmlPath *path)
 106 {
 107     /* The cairo path should be defined and in a perfect state */
 108     if (path == NULL || path->num_data == 0 ||
 109         path->status != CAIRO_STATUS_SUCCESS)
 110         return 0;
 111
 112     segment->path = path;
 113     segment->data = path->data;
 114     segment->num_data = path->num_data;
 115
 116     return normalize(segment);
 117 }
 118
 119 /**
 120  * cpml_segment_copy:
 121  * @segment: a #CpmlSegment
 122  * @src: the source segment to copy
 123  *
 124  * Makes a shallow copy of @src into @segment.
 125  *
 126  * Return value: @segment or %NULL on errors
 127  **/
 128 CpmlSegment *
 129 cpml_segment_copy(CpmlSegment *segment, const CpmlSegment *src)
 130 {
 131     if (segment == NULL || src == NULL)
 132         return NULL;
 133
 134     return memcpy(segment, src, sizeof(CpmlSegment));
 135 }
 136
 137
 138 /**
 139  * cpml_segment_reset:
 140  * @segment: a #CpmlSegment
 141  *
 142  * Modifies @segment to point to the first segment of the source cairo path.
 143  **/
 144 void
 145 cpml_segment_reset(CpmlSegment *segment)
 146 {
 147     segment->data = segment->path->data;
 148     segment->num_data = segment->path->num_data;
 149     normalize(segment);
 150 }
 151
 152 /**
 153  * cpml_segment_next:
 154  * @segment: a #CpmlSegment
 155  *
 156  * Modifies @segment to point to the next segment of the source cairo path.
 157  *
 158  * Return value: 1 on success, 0 if no next segment found or errors
 159  **/
 160 cairo_bool_t
 161 cpml_segment_next(CpmlSegment *segment)
 162 {
 163     int rest = segment->path->num_data - segment->num_data +
 164         segment->path->data - segment->data;
 165
 166     if (rest <= 0)
 167         return 0;
 168
 169     segment->data += segment->num_data;
 170     segment->num_data = rest;
 171
 172     return normalize(segment);
 173 }
 174
 175
 176 /**
 177  * cpml_segment_to_cairo:
 178  * @segment: a #CpmlSegment
 179  * @cr: the destination cairo context
 180  *
 181  * Appends the path of @segment to @cr. The segment is "flattened",
 182  * that is %CAIRO_PATH_ARC_TO primitives are approximated by one
 183  * or more %CAIRO_PATH_CURVE_TO using cpml_arc_to_cairo(). Check
 184  * its documentation for further details.
 185  **/
 186 void
 187 cpml_segment_to_cairo(const CpmlSegment *segment, cairo_t *cr)
 188 {
 189     CpmlPrimitive primitive;
 190
 191     cpml_primitive_from_segment(&primitive, (CpmlSegment *) segment);
 192
 193     do {
 194         cpml_primitive_to_cairo(&primitive, cr);
 195     } while (cpml_primitive_next(&primitive));
 196 }
 197
 198 /**
 199  * cpml_segment_dump:
 200  * @segment: a #CpmlSegment
 201  *
 202  * Dumps the specified @segment to stdout. Useful for debugging purposes.
 203  **/
 204 void
 205 cpml_segment_dump(const CpmlSegment *segment)
 206 {
 207     CpmlPrimitive primitive;
 208     cairo_bool_t first_call = 1;
 209
 210     cpml_primitive_from_segment(&primitive, (CpmlSegment *) segment);
 211
 212     do {
 213         cpml_primitive_dump(&primitive, first_call);
 214         first_call = 0;
 215     } while (cpml_primitive_next(&primitive));
 216 }
 217
 218
 219 /**
 220  * cpml_segment_reverse:
 221  * @segment: a #CpmlSegment
 222  *
 223  * Reverses @segment in-place. The resulting rendering will be the same,
 224  * but with the primitives generated in reverse order.
 225  **/
 226 void
 227 cpml_segment_reverse(CpmlSegment *segment)
 228 {
 229     cairo_path_data_t *data, *dst_data;
 230     size_t data_size;
 231     double end_x, end_y;
 232     int n, num_points, n_point;
 233     const cairo_path_data_t *src_data;
 234
 235     data_size = sizeof(cairo_path_data_t) * segment->num_data;
 236     data = cpml_alloca(data_size);
 237     end_x = segment->data[1].point.x;
 238     end_y = segment->data[1].point.y;
 239
 240     for (n = 2; n < segment->num_data; ++n) {
 241         src_data = segment->data + n;
 242         num_points = src_data->header.length;
 243
 244         dst_data = data + segment->num_data - n - num_points + 2;
 245         dst_data->header.type = src_data->header.type;
 246         dst_data->header.length = num_points;
 247
 248         for (n_point = 1; n_point < num_points; ++n_point) {
 249             dst_data[num_points - n_point].point.x = end_x;
 250             dst_data[num_points - n_point].point.y = end_y;
 251             end_x = src_data[n_point].point.x;
 252             end_y = src_data[n_point].point.y;
 253         }
 254
 255         n += n_point - 1;
 256     }
 257
 258     data[0].header.type = CAIRO_PATH_MOVE_TO;
 259     data[0].header.length = 2;
 260     data[1].point.x = end_x;
 261     data[1].point.y = end_y;
 262     memcpy(segment->data, data, data_size);
 263 }
 264
 265 /**
 266  * cpml_segment_transform:
 267  * @segment: a #CpmlSegment
 268  * @matrix: the matrix to be applied
 269  *
 270  * Applies @matrix on all the points of @segment.
 271  **/
 272 void
 273 cpml_segment_transform(CpmlSegment *segment, const cairo_matrix_t *matrix)
 274 {
 275     cairo_path_data_t *data;
 276     int n, n_point, num_points;
 277
 278     data = segment->data;
 279
 280     for (n = 0; n < segment->num_data; n += num_points) {
 281         num_points = data->header.length;
 282         ++data;
 283         for (n_point = 1; n_point < num_points; ++n_point) {
 284             cairo_matrix_transform_point(matrix, &data->point.x, &data->point.y);
 285             ++data;
 286         }
 287     }
 288 }
 289
 290 /**
 291  * cpml_segment_intersection:
 292  * @segment:  the first #CpmlSegment
 293  * @segment2: the second #CpmlSegment
 294  * @dest:     the destination vector of #CpmlPair
 295  * @max:      maximum number of intersections to return
 296  *
 297  * Computes the intersections between @segment and @segment2 and
 298  * returns the found points in @dest. If the intersections are more
 299  * than @max, only the first @max pairs are stored in @dest.
 300  *
 301  * To get the job done, the primitives of @segment are sequentially
 302  * scanned for intersections with any primitive in @segment2. This
 303  * means @segment has a higher precedence over @segment2.
 304  *
 305  * Return value: the number of intersections found
 306  **/
 307 int
 308 cpml_segment_intersection(const CpmlSegment *segment,
 309                           const CpmlSegment *segment2,
 310                           CpmlPair *dest, int max)
 311 {
 312     CpmlPrimitive portion;
 313     int partial, total;
 314
 315     cpml_primitive_from_segment(&portion, (CpmlSegment *) segment);
 316     total = 0;
 317
 318     do {
 319         partial = cpml_primitive_intersection_with_segment(&portion,
 320                                                            segment2,
 321                                                            dest + total,
 322                                                            max - total);
 323         total += partial;
 324     } while (total < max && cpml_primitive_next(&portion));
 325
 326     return total;
 327 }
 328
 329 /**
 330  * cpml_segment_offset:
 331  * @segment: a #CpmlSegment
 332  * @offset: the offset distance
 333  *
 334  * Offsets a segment of the specified amount, that is builds a "parallel"
 335  * segment at the @offset distance from the original one and returns the
 336  * result by replacing the original @segment.
 337  *
 338  * <important>
 339  * <title>TODO</title>
 340  * <itemizedlist>
 341  * <listitem>Closed path are not yet managed: an elegant solution is not
 342  *           so obvious: use cpml_close_offset() when available.</listitem>
 343  * <listitem>Degenerated primitives, such as lines of length 0, are not
 344  *           managed properly.</listitem>
 345  * </itemizedlist>
 346  * </important>
 347  **/
 348 void
 349 cpml_segment_offset(CpmlSegment *segment, double offset)
 350 {
 351     CpmlPrimitive primitive;
 352     CpmlPrimitive last_primitive;
 353     cairo_path_data_t org, old_end;
 354     cairo_bool_t first_cycle;
 355
 356     cpml_primitive_from_segment(&primitive, segment);
 357     first_cycle = 1;
 358
 359     do {
 360         if (!first_cycle) {
 361             org = old_end;
 362             primitive.org = &org;
 363         }
 364
 365         old_end = *cpml_primitive_get_point(&primitive, -1);
 366         cpml_primitive_offset(&primitive, offset);
 367
 368         if (!first_cycle) {
 369             cpml_primitive_join(&last_primitive, &primitive);
 370             primitive.org = cpml_primitive_get_point(&last_primitive, -1);
 371         }
 372
 373         cpml_primitive_copy(&last_primitive, &primitive);
 374         first_cycle = 0;
 375     } while (cpml_primitive_next(&primitive));
 376 }
 377
 378 /**
 379  * normalize:
 380  * @segment: a #CpmlSegment
 381  *
 382  * Strips the leading %CAIRO_PATH_MOVE_TO primitives, updating
 383  * the CpmlSegment structure accordling. One, and only one,
 384  * %CAIRO_PATH_MOVE_TO primitive is left.
 385  *
 386  * Return value: 1 on success, 0 on no leading MOVE_TOs or on errors
 387  **/
 388 static cairo_bool_t
 389 normalize(CpmlSegment *segment)
 390 {
 391     if (!ensure_one_move_to(segment))
 392         return 0;
 393
 394     reshape(segment);
 395     return 1;
 396 }
 397
 398 /**
 399  * ensure_one_move_to:
 400  * @segment: a #CpmlSegment
 401  *
 402  * Strips the leading %CAIRO_PATH_MOVE_TO primitives, updating
 403  * the <structname>CpmlSegment</structname> structure accordling.
 404  * One, and only one, %CAIRO_PATH_MOVE_TO primitive is left.
 405  *
 406  * Return value: 1 on success, 0 on no leading MOVE_TOs or on empty path
 407  **/
 408 static cairo_bool_t
 409 ensure_one_move_to(CpmlSegment *segment)
 410 {
 411     cairo_path_data_t *new_data;
 412     int new_num_data, length;
 413
 414     new_data = segment->data;
 415
 416     /* Check for at least one move to */
 417     if (new_data->header.type != CAIRO_PATH_MOVE_TO)
 418         return 0;
 419
 420     new_num_data = segment->num_data;
 421     length = 0;
 422
 423     /* Strip the leading CAIRO_PATH_MOVE_TO, leaving only the last one */
 424     do {
 425         new_data += length;
 426         new_num_data -= length;
 427         length = new_data->header.length;
 428
 429         /* Check for end of cairo path data */
 430         if (length >= new_num_data)
 431             return 0;
 432     } while (new_data[length].header.type == CAIRO_PATH_MOVE_TO);
 433
 434     segment->data = new_data;
 435     segment->num_data = new_num_data;
 436
 437     return 1;
 438 }
 439
 440 /**
 441  * reshape:
 442  * @segment: a #CpmlSegment
 443  *
 444  * Looks for the segment termination and modify the
 445  * <structfield>num_data</structfield> field of @segment accordling.
 446  * @segment must have only one leading %CAIRO_PATH_MOVE_TO and
 447  * it is supposed to be non-empty, conditions yet imposed by the
 448  * ensure_one_move_to() function.
 449  **/
 450 static void
 451 reshape(CpmlSegment *segment)
 452 {
 453     cairo_path_data_t *data;
 454     int num_data, new_num_data, length;
 455
 456     /* Skip the leading move to */
 457     new_num_data = 2;
 458     data = segment->data + new_num_data;
 459
 460     /* Calculate the remaining data in the cairo path */
 461     num_data = segment->path->num_data -
 462                (segment->data - segment->path->data);
 463
 464     while (new_num_data < num_data) {
 465         /* A primitive is considered valid if it has implemented
 466          * its own type_get_npoints() */
 467         if (cpml_primitive_type_get_npoints(data->header.type) < 0)
 468             break;
 469
 470         length = data->header.length;
 471         data += length;
 472         new_num_data += length;
 473     }
 474
 475     segment->num_data = new_num_data;
 476 }