1 /* CPML - Cairo Path Manipulation Library
2 * Copyright (C) 2008, 2009 Nicola Fontana <ntd at entidi.it>
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.
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.
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.
22 * SECTION:cpml-primitive
23 * @Section_Id:CpmlPrimitive
24 * @title: CpmlPrimitive
25 * @short_description: Basic component of segments
27 * A primitive is an atomic geometric element found inside #CpmlSegment.
28 * The available primitives are the same defined by #cairo_path_data_type_t
29 * with the additional %CAIRO_PATH_ARC_TO type (check #CpmlPrimitiveType
30 * for further information) and without %CAIRO_PATH_MOVE_TO as it is not
31 * considered a primitive and it is managed in different way: the move-to
32 * primitives are only used to define the origin of a segment.
38 * This is another name for #cairo_path_data_type_t type. Although
39 * phisically they are the same struct, #CpmlPrimitiveType conceptually
40 * embodies an important difference: it can be used to specify the
41 * special %CAIRO_PATH_ARC_TO primitive. This is not a native cairo
42 * primitive and having two different types is a good way to make clear
43 * when a function expect or not embedded arc-to primitives.
48 * @segment: the source #CpmlSegment
49 * @org: a pointer to the first point of the primitive
50 * @data: the array of the path data, prepended by the header
52 * As for #CpmlSegment, also the primitive is unobtrusive. This
53 * means CpmlPrimitive does not include any coordinates but instead
54 * keeps pointers to the original segment (and, by transition, to
55 * the underlying #CpmlPath struct).
59 #include "cpml-internal.h"
60 #include "cpml-extents.h"
61 #include "cpml-segment.h"
62 #include "cpml-primitive.h"
63 #include "cpml-primitive-private.h"
64 #include "cpml-line.h"
66 #include "cpml-curve.h"
67 #include "cpml-close.h"
73 static const _CpmlPrimitiveClass
*
74 get_class_from_type (CpmlPrimitiveType type
);
75 static const _CpmlPrimitiveClass
*
76 get_class (const CpmlPrimitive
*primitive
);
77 static void dump_cairo_point (const cairo_path_data_t
*path_data
);
81 * cpml_primitive_copy:
82 * @primitive: the destination #CpmlPrimitive
83 * @src: the source #CpmlPrimitive
85 * Copies @src in @primitive. This is a shallow copy: the internal fields
86 * of @primitive refer to the same memory as the original @src primitive.
91 cpml_primitive_copy(CpmlPrimitive
*primitive
, const CpmlPrimitive
*src
)
93 return memcpy(primitive
, src
, sizeof(CpmlPrimitive
));
97 * cpml_primitive_from_segment:
98 * @primitive: the destination #CpmlPrimitive struct
99 * @segment: the source segment
101 * Initializes @primitive to the first primitive of @segment.
103 * Returns: @primitive
106 cpml_primitive_from_segment(CpmlPrimitive
*primitive
, CpmlSegment
*segment
)
108 primitive
->segment
= segment
;
110 /* The first element of a CpmlSegment is always a CAIRO_PATH_MOVE_TO,
111 * as ensured by cpml_segment_from_cairo() and by the browsing APIs,
112 * so the origin is in the second data item */
113 primitive
->org
= &segment
->data
[1];
115 /* Also, the segment APIs ensure that @segment is prepended by
116 * only one CAIRO_PATH_MOVE_TO */
117 primitive
->data
= segment
->data
+ segment
->data
[0].header
.length
;
123 * cpml_primitive_reset:
124 * @primitive: a #CpmlPrimitive
126 * Resets @primitive so it refers to the first primitive of the
130 cpml_primitive_reset(CpmlPrimitive
*primitive
)
132 cpml_primitive_from_segment(primitive
, primitive
->segment
);
136 * cpml_primitive_next:
137 * @primitive: a #CpmlPrimitive
140 * Changes @primitive so it refers to the next primitive on the
141 * source segment. If there are no more primitives, @primitive is
142 * not changed and 0 is returned.
144 * Returns: 1 on success, 0 if no next primitive found or errors
147 cpml_primitive_next(CpmlPrimitive
*primitive
)
149 cairo_path_data_t
*new_data
;
151 new_data
= primitive
->data
+ primitive
->data
->header
.length
;
152 if (new_data
- primitive
->segment
->data
>= primitive
->segment
->num_data
)
155 /* TODO: this is a temporary workaround to be removed as soon as
156 * the issue #21 will be resolved */
157 if (new_data
->header
.type
== CAIRO_PATH_MOVE_TO
)
160 primitive
->org
= cpml_primitive_get_point(primitive
, -1);
161 primitive
->data
= new_data
;
167 * cpml_primitive_get_n_points:
168 * @primitive: a #CpmlPrimitive
170 * Gets the number of points required to identify @primitive.
171 * It is similar to cpml_primitive_type_get_n_points() but using
172 * a @primitive instance instead of a type.
174 * Returns: the number of points or -1 on errors
177 cpml_primitive_get_n_points(const CpmlPrimitive
*primitive
)
179 return cpml_primitive_type_get_n_points(primitive
->data
->header
.type
);
183 * cpml_primitive_get_point:
184 * @primitive: a #CpmlPrimitive
185 * @n_point: the index of the point to retrieve
187 * Gets the specified @n_point from @primitive. The index starts
188 * at 0: if @n_point is 0, the start point (the origin) is
189 * returned, 1 for the second point and so on. If @n_point is
190 * negative, it is considered as a negative index from the end,
191 * so that -1 is the end point, -2 the point before the end point
194 * %CAIRO_PATH_CLOSE_PATH is managed in a special way: if @n_point
195 * is -1 or 1 and @primitive is a close-path, this function cycles
196 * the source #CpmlSegment and returns the first point. This is
197 * needed because requesting the end point (or the second point)
198 * of a close path is a valid operation and must returns the start
201 * Returns: a pointer to the requested point (in cairo format)
202 * or %NULL if the point is outside the valid range
205 cpml_primitive_get_point(const CpmlPrimitive
*primitive
, int n_point
)
209 /* For a start point request, simply return the origin
210 * without further checking */
212 return primitive
->org
;
214 /* The CAIRO_PATH_CLOSE_PATH special case */
215 if (primitive
->data
->header
.type
== CAIRO_PATH_CLOSE_PATH
&&
216 (n_point
== 1 || n_point
== -1))
217 return &primitive
->segment
->data
[1];
219 n_points
= cpml_primitive_get_n_points(primitive
);
223 /* If n_point is negative, consider it as a negative index from the end */
225 n_point
= n_points
+ n_point
;
227 /* Out of range condition */
228 if (n_point
< 0 || n_point
>= n_points
)
231 return n_point
== 0 ? primitive
->org
: &primitive
->data
[n_point
];
235 * cpml_primitive_to_cairo:
236 * @primitive: a #CpmlPrimitive
237 * @cr: the destination cairo context
239 * Renders a single @primitive to the @cr cairo context.
240 * As a special case, if the primitive is a #CAIRO_PATH_CLOSE_PATH,
241 * an equivalent line is rendered, because a close path left alone
244 * Also a #CAIRO_PATH_ARC_TO primitive is treated specially, as it
245 * is not natively supported by cairo and has its own rendering API.
248 cpml_primitive_to_cairo(const CpmlPrimitive
*primitive
, cairo_t
*cr
)
251 cairo_path_data_t
*path_data
;
253 cairo_move_to(cr
, primitive
->org
->point
.x
, primitive
->org
->point
.y
);
255 switch (primitive
->data
->header
.type
) {
257 case CAIRO_PATH_CLOSE_PATH
:
258 path_data
= cpml_primitive_get_point(primitive
, -1);
259 cairo_line_to(cr
, path_data
->point
.x
, path_data
->point
.y
);
262 case CAIRO_PATH_ARC_TO
:
263 cpml_arc_to_cairo(primitive
, cr
);
267 path
.status
= CAIRO_STATUS_SUCCESS
;
268 path
.data
= primitive
->data
;
269 path
.num_data
= primitive
->data
->header
.length
;
270 cairo_append_path(cr
, &path
);
276 * cpml_primitive_dump:
277 * @primitive: a #CpmlPrimitive
278 * @org_also: whether to output also the origin coordinates
280 * Dumps info on the specified @primitive to stdout: useful for
281 * debugging purposes. If @org_also is 1, a %CAIRO_PATH_MOVE_TO
282 * to the origin is prepended to the data otherwise the
283 * <structfield>org</structfield> field is not used.
286 cpml_primitive_dump(const CpmlPrimitive
*primitive
, cairo_bool_t org_also
)
288 const cairo_path_data_t
*data
;
289 int type
, n
, n_points
;
291 data
= primitive
->data
;
292 type
= data
->header
.type
;
293 n_points
= cpml_primitive_get_n_points(primitive
);
295 printf("Unhandled primitive type (%d)\n", type
);
299 /* Dump the origin movement, if requested */
302 dump_cairo_point(primitive
->org
);
308 case CAIRO_PATH_LINE_TO
:
312 case CAIRO_PATH_ARC_TO
:
316 case CAIRO_PATH_CURVE_TO
:
320 case CAIRO_PATH_CLOSE_PATH
:
321 printf("Path close");
325 printf("Unknown primitive (type = %d)", type
);
329 for (n
= 1; n
< n_points
; ++n
)
330 dump_cairo_point(cpml_primitive_get_point(primitive
, n
));
336 * cpml_primitive_put_intersections_with_segment:
337 * @primitive: a #CpmlPrimitive
338 * @segment: a #CpmlSegment
339 * @dest: the destination vector of #CpmlPair
340 * @max: maximum number of intersections to return
342 * Computes the intersections between @segment and @primitive by
343 * sequentially scanning the primitives in @segment and looking
344 * for intersections with @primitive.
345 * If the intersections are more than @max, only the first @max pairs
346 * are stored in @dest.
348 * Returns: the number of intersections found
351 cpml_primitive_put_intersections_with_segment(const CpmlPrimitive
*primitive
,
352 const CpmlSegment
*segment
,
353 CpmlPair
*dest
, int max
)
355 CpmlPrimitive portion
;
358 cpml_primitive_from_segment(&portion
, (CpmlSegment
*) segment
);
361 while (found
< max
) {
362 found
+= cpml_primitive_put_intersections(&portion
, primitive
,
363 max
-found
, dest
+found
);
364 if (!cpml_primitive_next(&portion
))
373 * cpml_primitive_type_get_n_points:
374 * @type: a primitive type
376 * Gets the number of points required to identify the @type primitive.
379 * This function is primitive dependent, that is every primitive has
380 * its own implementation.
383 * Returns: the number of points or -1 on errors
386 cpml_primitive_type_get_n_points(CpmlPrimitiveType type
)
388 const _CpmlPrimitiveClass
*class_data
= get_class_from_type(type
);
390 if (class_data
== NULL
)
393 return class_data
->n_points
;
397 * cpml_primitive_get_length:
398 * @primitive: a #CpmlPrimitive
400 * Abstracts the length() family functions by providing a common
401 * way to access the underlying primitive-specific implementation.
402 * The function returns the length of @primitive.
404 * Returns: the requested length or 0 on errors
407 cpml_primitive_get_length(const CpmlPrimitive
*primitive
)
409 const _CpmlPrimitiveClass
*class_data
= get_class(primitive
);
411 if (class_data
== NULL
|| class_data
->get_length
== NULL
)
414 return class_data
->get_length(primitive
);
418 * cpml_primitive_put_extents:
419 * @primitive: a #CpmlPrimitive
420 * @extents: where to store the extents
422 * Abstracts the extents() family functions by providing a common
423 * way to access the underlying primitive-specific implementation.
425 * This function stores in @extents the bounding box of @primitive.
427 * On errors, that is if the extents cannot be calculated for some
428 * reason, this function does nothing.
431 cpml_primitive_put_extents(const CpmlPrimitive
*primitive
,
432 CpmlExtents
*extents
)
434 const _CpmlPrimitiveClass
*class_data
= get_class(primitive
);
436 if (class_data
== NULL
|| class_data
->put_extents
== NULL
)
439 class_data
->put_extents(primitive
, extents
);
443 * cpml_primitive_put_pair_at:
444 * @primitive: a #CpmlPrimitive
445 * @pos: the position value
446 * @pair: the destination #CpmlPair
448 * Abstracts the put_pair_at() family functions by providing a common
449 * way to access the underlying primitive-specific implementation.
451 * It gets the coordinates of the point lying on @primitive
452 * at position @pos. @pos is an homogeneous factor where 0 is the
453 * start point, 1 the end point, 0.5 the mid point and so on.
454 * @pos can be less than 0 or greater than %1, in which case the
455 * coordinates of @pair are interpolated.
457 * On errors, that is if the coordinates cannot be calculated for
458 * some reason, this function does nothing.
461 cpml_primitive_put_pair_at(const CpmlPrimitive
*primitive
, double pos
,
464 const _CpmlPrimitiveClass
*class_data
= get_class(primitive
);
466 if (class_data
== NULL
|| class_data
->put_pair_at
== NULL
)
469 class_data
->put_pair_at(primitive
, pos
, pair
);
473 * cpml_primitive_put_vector_at:
474 * @primitive: a #CpmlPrimitive
475 * @pos: the position value
476 * @vector: the destination #CpmlVector
478 * Abstracts the put_vector_at() family functions by providing a common
479 * way to access the underlying primitive-specific implementation.
481 * It gets the steepness of the point at position @pos on @primitive.
482 * @pos is an homogeneous factor where 0 is the start point, 1 the
483 * end point, 0.5 the mid point and so on.
484 * @pos can be less than 0 or greater than %1, in which case the
485 * coordinates of @pair are interpolated.
487 * On errors, that is if the steepness cannot be calculated for
488 * some reason, this function does nothing.
491 cpml_primitive_put_vector_at(const CpmlPrimitive
*primitive
, double pos
,
494 const _CpmlPrimitiveClass
*class_data
= get_class(primitive
);
496 if (class_data
== NULL
|| class_data
->put_vector_at
== NULL
)
499 class_data
->put_vector_at(primitive
, pos
, vector
);
503 * cpml_primitive_get_closest_pos:
504 * @primitive: a #CpmlPrimitive
505 * @pair: the coordinates of the subject point
507 * Returns the pos value of the point on @primitive nearest to @pair.
508 * The returned value is always clamped between %0 and %1.
510 * Returns: the requested pos value between %0 and %1, or %-1 on errors
513 cpml_primitive_get_closest_pos(const CpmlPrimitive
*primitive
,
514 const CpmlPair
*pair
)
516 const _CpmlPrimitiveClass
*class_data
= get_class(primitive
);
518 if (class_data
== NULL
|| class_data
->get_closest_pos
== NULL
)
521 return class_data
->get_closest_pos(primitive
, pair
);
525 * cpml_primitive_join:
526 * @primitive: the first #CpmlPrimitive
527 * @primitive2: the second #CpmlPrimitive
529 * Joins two primitive modifying the end point of @primitive and the
530 * start point of @primitive2 so that the resulting points will overlap.
533 * <title>TODO</title>
535 * <listitem>Actually, the join is done by extending the end vector
536 * of @primitive and the start vector of @primitive2 and
537 * interpolating the intersection: this means no primitive
538 * dependent code is needed. Anyway, it is likely to change
539 * in the future because this approach is quite naive when
540 * curves are involved.</listitem>
544 * Returns: 1 on success, 0 if the end vector of @primitive
545 * and the start vector of @primitive2 are parallel
548 cpml_primitive_join(CpmlPrimitive
*primitive
, CpmlPrimitive
*primitive2
)
550 cairo_path_data_t
*end1
, *start2
;
551 CpmlPrimitive line1
, line2
;
552 cairo_path_data_t data1
[2], data2
[2];
555 end1
= cpml_primitive_get_point(primitive
, -1);
556 start2
= cpml_primitive_get_point(primitive2
, 0);
558 /* Check if the primitives are yet connected */
559 if (end1
->point
.x
== start2
->point
.x
&& end1
->point
.y
== start2
->point
.y
)
562 line1
.org
= cpml_primitive_get_point(primitive
, -2);
564 data1
[0].header
.type
= CAIRO_PATH_LINE_TO
;
569 data2
[0].header
.type
= CAIRO_PATH_LINE_TO
;
570 data2
[1] = *cpml_primitive_get_point(primitive2
, 1);
572 if (!cpml_line_put_intersections(&line1
, &line2
, 1, &joint
))
575 cpml_pair_to_cairo(&joint
, end1
);
576 cpml_pair_to_cairo(&joint
, start2
);
582 * cpml_primitive_put_intersections:
583 * @primitive: the first #CpmlPrimitive
584 * @primitive2: the second #CpmlPrimitive
585 * @max: maximum number of intersections to return
586 * @dest: the destination buffer that can contain @max #CpmlPair
588 * Finds the intersection points between the given primitives and
589 * returns the result in @dest. The size of @dest should be enough
590 * to store @max #CpmlPair. The absoulte max number of intersections
591 * is dependent from the type of the primitive involved in the
592 * operation. If there are at least one Bézier curve involved, up to
593 * 4 intersections could be returned. Otherwise, if there is an arc
594 * the intersections will be 2 at maximum. For line line primitives,
595 * there is only 1 point (or obviously 0 if the lines do not intersect).
598 * This function is primitive dependent: every new primitive must
599 * expose API to get intersections with any other primitive type
600 * (excluding %CAIRO_PATH_CLOSE_PATH, as it is converted to a line
602 * <para>The convention used by CPML is that a primitive should
603 * expose only intersection APIs dealing with lower complexity
604 * primitives. This is required to avoid double functions:
605 * you will have only a cpml_curve_put_intersections_with_line()
606 * function, not a cpml_line_put_intersections_with_curve(), as
607 * the latter is easily reproduced by calling the former with
608 * @primitive2 and @primitive swapped.
611 * Returns: the number of intersection points found or 0 if the
612 * primitives do not intersect
615 cpml_primitive_put_intersections(const CpmlPrimitive
*primitive
,
616 const CpmlPrimitive
*primitive2
,
617 int max
, CpmlPair
*dest
)
619 CpmlPrimitiveType type1
, type2
;
621 type1
= primitive
->data
->header
.type
;
622 type2
= primitive
->data
->header
.type
;
624 /* Close path primitives are treated as line-to */
625 if (type1
== CAIRO_PATH_CLOSE_PATH
)
626 type1
= CAIRO_PATH_LINE_TO
;
627 if (type2
== CAIRO_PATH_CLOSE_PATH
)
628 type2
= CAIRO_PATH_LINE_TO
;
630 /* Order the two primitives in ascending complexity, to facilitate
631 * the dispatcher logic */
632 if (cpml_primitive_type_get_n_points(type1
) > cpml_primitive_type_get_n_points(type2
)) {
633 const CpmlPrimitive
*tmp_primitive
;
634 CpmlPrimitiveType tmp_type
;
637 tmp_primitive
= primitive
;
640 primitive
= primitive2
;
643 primitive2
= tmp_primitive
;
646 /* Dispatcher: probably there's a smarter way to do this */
649 case CAIRO_PATH_LINE_TO
:
650 if (type2
== CAIRO_PATH_LINE_TO
)
651 return cpml_line_put_intersections(primitive2
, primitive
,
653 else if (type2
== CAIRO_PATH_ARC_TO
)
654 return cpml_arc_put_intersections_with_line(primitive2
, primitive
,
656 else if (type2
== CAIRO_PATH_CURVE_TO
)
657 return cpml_curve_put_intersections_with_line(primitive2
, primitive
,
661 case CAIRO_PATH_ARC_TO
:
662 if (type2
== CAIRO_PATH_ARC_TO
)
663 return cpml_arc_put_intersections(primitive2
, primitive
,
665 else if (type2
== CAIRO_PATH_CURVE_TO
)
666 return cpml_curve_put_intersections_with_arc(primitive2
, primitive
,
670 case CAIRO_PATH_CURVE_TO
:
671 if (type2
== CAIRO_PATH_CURVE_TO
)
672 return cpml_curve_put_intersections(primitive2
, primitive
,
680 /* Primitive combination not found */
685 * cpml_primitive_offset:
686 * @primitive: a #CpmlPrimitive
687 * @offset: distance for the computed offset primitive
689 * Given a primitive, computes the same (or approximated) parallel
690 * primitive distant @offset from the original one and returns
691 * the result by changing @primitive.
694 * This function is primitive dependent, that is every primitive has
695 * its own implementation.
699 cpml_primitive_offset(CpmlPrimitive
*primitive
, double offset
)
701 switch (primitive
->data
->header
.type
) {
703 case CAIRO_PATH_LINE_TO
:
704 cpml_line_offset(primitive
, offset
);
707 case CAIRO_PATH_ARC_TO
:
708 cpml_arc_offset(primitive
, offset
);
711 case CAIRO_PATH_CURVE_TO
:
712 cpml_curve_offset(primitive
, offset
);
715 case CAIRO_PATH_CLOSE_PATH
:
716 cpml_close_offset(primitive
, offset
);
725 static const _CpmlPrimitiveClass
*
726 get_class_from_type(CpmlPrimitiveType type
)
729 case CAIRO_PATH_LINE_TO
:
730 return _cpml_line_get_class();
731 case CAIRO_PATH_ARC_TO
:
732 return _cpml_arc_get_class();
733 case CAIRO_PATH_CURVE_TO
:
734 return _cpml_curve_get_class();
735 case CAIRO_PATH_CLOSE_PATH
:
736 return _cpml_close_get_class();
744 static const _CpmlPrimitiveClass
*
745 get_class(const CpmlPrimitive
*primitive
)
747 return get_class_from_type(primitive
->data
->header
.type
);
751 dump_cairo_point(const cairo_path_data_t
*path_data
)
753 printf("(%g %g) ", path_data
->point
.x
, path_data
->point
.y
);