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 * @title: CpmlPrimitive
23 * @short_description: Basic component of segments
25 * A primitive is an atomic geometric element found inside #CpmlSegment.
26 * The available primitives are defined in the #cairo_path_data_type_t
27 * enum, excluding %CAIRO_PATH_MOVE_TO, as it is not considered a valid
28 * primitive and it is managed in different way (the moveto primitives
29 * are used to set the origin of the first primitive in a segment).
34 * @segment: the source #CpmlSegment
35 * @org: a pointer to the first point of the primitive
36 * @data: the array of the path data, prepended by the header
38 * As for #CpmlSegment, also the primitive is unobtrusive. This
39 * means CpmlPrimitive does not include any coordinates but instead
40 * keeps pointers to the original segment (and, by transition, to
41 * the underlying #CpmlPath struct).
44 #include "cpml-primitive.h"
45 #include "cpml-line.h"
47 #include "cpml-curve.h"
48 #include "cpml-close.h"
54 static void dump_cairo_point (const cairo_path_data_t
*path_data
);
58 * cpml_primitive_copy:
59 * @primitive: the destination #CpmlPrimitive
60 * @src: the source #CpmlPrimitive
62 * Copies @src in @primitive.
64 * Return value: @primitive
67 cpml_primitive_copy(CpmlPrimitive
*primitive
, const CpmlPrimitive
*src
)
69 return memcpy(primitive
, src
, sizeof(CpmlPrimitive
));
73 * cpml_primitive_from_segment:
74 * @primitive: the destination #CpmlPrimitive struct
75 * @segment: the source segment
77 * Initializes @primitive to the first primitive of @segment.
79 * Return value: @primitive
82 cpml_primitive_from_segment(CpmlPrimitive
*primitive
, CpmlSegment
*segment
)
84 primitive
->segment
= segment
;
86 /* The first element of a CpmlSegment is always a CAIRO_PATH_MOVE_TO,
87 * as ensured by cpml_segment_from_cairo() and by the browsing APIs,
88 * so the origin is in the second data item */
89 primitive
->org
= &segment
->data
[1];
91 /* Also, the segment APIs ensure that @segment is prepended by
92 * only one CAIRO_PATH_MOVE_TO */
93 primitive
->data
= segment
->data
+ 2;
99 * cpml_primitive_reset:
100 * @primitive: a #CpmlPrimitive
102 * Resets @primitive so it refers to the first primitive of the
106 cpml_primitive_reset(CpmlPrimitive
*primitive
)
108 primitive
->org
= &primitive
->segment
->data
[1];
109 primitive
->data
= primitive
->segment
->data
+ 2;
113 * cpml_primitive_next:
114 * @primitive: a #CpmlPrimitive
117 * Changes @primitive so it refers to the next primitive on the
118 * source segment. If there are no more primitives, @primitive is
119 * not changed and 0 is returned.
121 * Return value: 1 on success, 0 if no next primitive found or errors
124 cpml_primitive_next(CpmlPrimitive
*primitive
)
126 cairo_path_data_t
*new_data
;
128 new_data
= primitive
->data
+ primitive
->data
->header
.length
;
129 if (new_data
- primitive
->segment
->data
>= primitive
->segment
->num_data
)
132 primitive
->org
= cpml_primitive_get_point(primitive
, -1);
133 primitive
->data
= new_data
;
139 * cpml_primitive_get_npoints:
140 * @primitive: a #CpmlPrimitive
142 * Gets the number of points required to identify @primitive.
143 * It is similar to cpml_primitive_type_get_npoints() but using
144 * a @primitive instance instead of a type.
146 * Return value: the number of points or -1 on errors
149 cpml_primitive_get_npoints(const CpmlPrimitive
*primitive
)
151 return cpml_primitive_type_get_npoints(primitive
->data
->header
.type
);
155 * cpml_primitive_get_point:
156 * @primitive: a #CpmlPrimitive
157 * @npoint: the index of the point to retrieve
159 * Gets the specified @npoint from @primitive. The index starts
160 * at 0: if @npoint is 0, the start point (the origin) is
161 * returned, 1 for the second point and so on. If @npoint is
162 * negative, it is considered as a negative index from the end,
163 * so that -1 is the end point, -2 the point before the end point
166 * %CAIRO_PATH_CLOSE_PATH is managed in a special way: if @npoint
167 * is -1 or 1 and @primitive is a close-path, this function cycles
168 * the source #CpmlSegment and returns the first point. This is
169 * needed because requesting the end point (or the second point)
170 * of a close path is a valid operation and must returns the start
173 * Return value: a pointer to the requested point (in cairo format)
174 * or %NULL if the point is outside the valid range
177 cpml_primitive_get_point(const CpmlPrimitive
*primitive
, int npoint
)
181 /* For a start point request, simply return the origin
182 * without further checking */
184 return primitive
->org
;
186 /* The CAIRO_PATH_CLOSE_PATH special case */
187 if (primitive
->data
->header
.type
== CAIRO_PATH_CLOSE_PATH
&&
188 (npoint
== 1 || npoint
== -1))
189 return &primitive
->segment
->data
[1];
191 npoints
= cpml_primitive_get_npoints(primitive
);
195 /* If npoint is negative, consider it as a negative index from the end */
197 npoint
= npoints
+ npoint
;
199 /* Out of range condition */
200 if (npoint
< 0 || npoint
>= npoints
)
203 return npoint
== 0 ? primitive
->org
: &primitive
->data
[npoint
];
207 * cpml_primitive_to_cairo:
208 * @primitive: a #CpmlPrimitive
209 * @cr: the destination cairo context
211 * Renders a single @primitive to the @cr cairo context.
212 * As a special case, if the primitive is a #CAIRO_PATH_CLOSE_PATH,
213 * an equivalent line is rendered, because a close path left alone
216 * Also a #CAIRO_PATH_ARC_TO primitive is treated specially, as it
217 * is not natively supported by cairo and has its own rendering API.
220 cpml_primitive_to_cairo(const CpmlPrimitive
*primitive
, cairo_t
*cr
)
223 cairo_path_data_t
*path_data
;
225 cairo_move_to(cr
, primitive
->org
->point
.x
, primitive
->org
->point
.y
);
227 switch (primitive
->data
->header
.type
) {
229 case CAIRO_PATH_CLOSE_PATH
:
230 path_data
= cpml_primitive_get_point(primitive
, -1);
231 cairo_line_to(cr
, path_data
->point
.x
, path_data
->point
.y
);
234 case CAIRO_PATH_ARC_TO
:
235 cpml_arc_to_cairo(primitive
, cr
);
239 path
.status
= CAIRO_STATUS_SUCCESS
;
240 path
.data
= primitive
->data
;
241 path
.num_data
= primitive
->data
->header
.length
;
242 cairo_append_path(cr
, &path
);
248 * cpml_primitive_dump:
249 * @primitive: a #CpmlPrimitive
250 * @org_also: whether to output also the origin coordinates
252 * Dumps info on the specified @primitive to stdout: useful for
253 * debugging purposes. If @org_also is 1, a %CAIRO_PATH_MOVE_TO
254 * to the origin is prepended to the data otherwise the
255 * <structfield>org</structfield> field is not used.
258 cpml_primitive_dump(const CpmlPrimitive
*primitive
, cairo_bool_t org_also
)
260 const cairo_path_data_t
*data
;
261 int type
, n
, npoints
;
263 data
= primitive
->data
;
264 type
= data
->header
.type
;
265 npoints
= cpml_primitive_get_npoints(primitive
);
267 printf("Unhandled primitive type (%d)\n", type
);
271 /* Dump the origin movement, if requested */
274 dump_cairo_point(primitive
->org
);
280 case CAIRO_PATH_LINE_TO
:
284 case CAIRO_PATH_ARC_TO
:
288 case CAIRO_PATH_CURVE_TO
:
292 case CAIRO_PATH_CLOSE_PATH
:
293 printf("Path close");
297 printf("Unknown primitive (type = %d)", type
);
301 for (n
= 1; n
< npoints
; ++n
)
302 dump_cairo_point(cpml_primitive_get_point(primitive
, n
));
308 * cpml_primitive_intersection_with_segment:
309 * @primitive: a #CpmlPrimitive
310 * @segment: a #CpmlSegment
311 * @dest: the destination vector of #CpmlPair
312 * @max: maximum number of intersections to return
314 * Computes the intersections between @segment and @primitive by
315 * sequentially scanning the primitives in @segment and looking
316 * for intersections with @primitive.
317 * If the intersections are more than @max, only the first @max pairs
318 * are stored in @dest.
320 * Return value: the number of intersections found
323 cpml_primitive_intersection_with_segment(const CpmlPrimitive
*primitive
,
324 const CpmlSegment
*segment
,
325 CpmlPair
*dest
, int max
)
327 CpmlPrimitive portion
;
329 CpmlPair tmp_pairs
[4];
331 cpml_primitive_from_segment(&portion
, (CpmlSegment
*) segment
);
335 partial
= cpml_primitive_intersection(&portion
, primitive
, tmp_pairs
);
336 if (total
+ partial
> max
)
337 partial
= max
- total
;
340 memcpy(dest
+ total
, tmp_pairs
, partial
* sizeof(CpmlPair
));
343 } while (total
< max
&& cpml_primitive_next(&portion
));
350 * cpml_primitive_type_get_npoints:
351 * @type: a primitive type
353 * Gets the number of points required to identify the @type primitive.
356 * This function is primitive dependent, that is every primitive has
357 * its own implementation.
360 * Return value: the number of points or -1 on errors
363 cpml_primitive_type_get_npoints(cairo_path_data_type_t type
)
367 case CAIRO_PATH_LINE_TO
:
368 return cpml_line_type_get_npoints();
370 case CAIRO_PATH_ARC_TO
:
371 return cpml_arc_type_get_npoints();
373 case CAIRO_PATH_CURVE_TO
:
374 return cpml_curve_type_get_npoints();
376 case CAIRO_PATH_CLOSE_PATH
:
377 return cpml_close_type_get_npoints();
387 * cpml_primitive_length:
388 * @primitive: a #CpmlPrimitive
390 * Abstracts the length() family functions by providing a common
391 * way to access the underlying primitive-specific implementation.
392 * The function returns the length of @primitive.
395 * This function is primitive dependent, that is every primitive has
396 * its own implementation.
399 * Return value: the requested length or 0 on errors
402 cpml_primitive_length(const CpmlPrimitive
*primitive
)
404 switch (primitive
->data
->header
.type
) {
406 case CAIRO_PATH_LINE_TO
:
407 case CAIRO_PATH_CLOSE_PATH
:
408 return cpml_line_length(primitive
);
410 case CAIRO_PATH_ARC_TO
:
411 return cpml_arc_length(primitive
);
413 case CAIRO_PATH_CURVE_TO
:
414 return cpml_curve_length(primitive
);
424 * cpml_primitive_pair_at:
425 * @primitive: a #CpmlPrimitive
426 * @pair: the destination #CpmlPair
427 * @pos: the position value
429 * Abstracts the pair_at() family functions by providing a common
430 * way to access the underlying primitive-specific implementation.
432 * It gets the coordinates of the point lying on @primitive
433 * at position @pos. @pos is an homogeneous factor where 0 is the
434 * start point, 1 the end point, 0.5 the mid point and so on.
435 * The relation 0 < @pos < 1 should be satisfied, although some
436 * primitives accept value outside this range.
439 * This function is primitive dependent, that is every primitive has
440 * its own implementation.
444 cpml_primitive_pair_at(const CpmlPrimitive
*primitive
,
445 CpmlPair
*pair
, double pos
)
447 switch (primitive
->data
->header
.type
) {
449 case CAIRO_PATH_LINE_TO
:
450 cpml_line_pair_at(primitive
, pair
, pos
);
453 case CAIRO_PATH_ARC_TO
:
454 cpml_arc_pair_at(primitive
, pair
, pos
);
457 case CAIRO_PATH_CURVE_TO
:
458 cpml_curve_pair_at(primitive
, pair
, pos
);
461 case CAIRO_PATH_CLOSE_PATH
:
462 cpml_close_pair_at(primitive
, pair
, pos
);
471 * cpml_primitive_vector_at:
472 * @primitive: a #CpmlPrimitive
473 * @vector: the destination #CpmlVector
474 * @pos: the position value
476 * Abstracts the vector_at() family functions by providing a common
477 * way to access the underlying primitive-specific implementation.
479 * It gets the steepness of the point at position @pos on @primitive.
480 * @pos is an homogeneous factor where 0 is the start point, 1 the
481 * end point, 0.5 the mid point and so on.
482 * The relation 0 < @pos < 1 should be satisfied, although some
483 * primitives accept value outside this range.
486 * This function is primitive dependent, that is every primitive has
487 * its own implementation.
491 cpml_primitive_vector_at(const CpmlPrimitive
*primitive
,
492 CpmlVector
*vector
, double pos
)
494 switch (primitive
->data
->header
.type
) {
496 case CAIRO_PATH_LINE_TO
:
497 cpml_line_vector_at(primitive
, vector
, pos
);
500 case CAIRO_PATH_ARC_TO
:
501 cpml_arc_vector_at(primitive
, vector
, pos
);
504 case CAIRO_PATH_CURVE_TO
:
505 cpml_curve_vector_at(primitive
, vector
, pos
);
508 case CAIRO_PATH_CLOSE_PATH
:
509 cpml_close_vector_at(primitive
, vector
, pos
);
518 * cpml_primitive_join:
519 * @primitive: the first #CpmlPrimitive
520 * @primitive2: the second #CpmlPrimitive
522 * Joins two primitive modifying the end point of @primitive and the
523 * start point of @primitive2 so that the resulting points will overlap.
526 * <title>TODO</title>
528 * <listitem>Actually, the join is done by extending the end vector
529 * of @primitive and the start vector of @primitive2 and
530 * interpolating the intersection: this means no primitive
531 * dependent code is needed. Anyway, it is likely to change
532 * in the future because this approach is quite naive when
533 * curves are involved.</listitem>
537 * Return value: 1 on success, 0 if the end vector of @primitive
538 * and the start vector of @primitive2 are parallel
541 cpml_primitive_join(CpmlPrimitive
*primitive
, CpmlPrimitive
*primitive2
)
543 cairo_path_data_t
*end1
, *start2
;
544 CpmlPrimitive line1
, line2
;
545 cairo_path_data_t data1
[2], data2
[2];
548 end1
= cpml_primitive_get_point(primitive
, -1);
549 start2
= cpml_primitive_get_point(primitive2
, 0);
551 /* Check if the primitives are yet connected */
552 if (end1
->point
.x
== start2
->point
.x
&& end1
->point
.y
== start2
->point
.y
)
555 line1
.org
= cpml_primitive_get_point(primitive
, -2);
557 data1
[0].header
.type
= CAIRO_PATH_LINE_TO
;
562 data2
[0].header
.type
= CAIRO_PATH_LINE_TO
;
563 data2
[1] = *cpml_primitive_get_point(primitive2
, 1);
565 if (!cpml_line_intersection(&line1
, &line2
, &joint
))
568 cpml_pair_to_cairo(&joint
, end1
);
569 cpml_pair_to_cairo(&joint
, start2
);
575 * cpml_primitive_intersection:
576 * @primitive: the first #CpmlPrimitive
577 * @primitive2: the second #CpmlPrimitive
578 * @dest: the destination #CpmlPair (or a vector of #CpmlPair)
580 * Finds the intersection points between the given primitives and
581 * returns the result in @dest. The size of @dest is dependent
582 * from the type of the most complex primitive involved in the
583 * operation. If there are curves involved, @dest MUST be an array
584 * of at least 4 #CpmlPair. If an arc is the most complex primitive
585 * involved, @dest MUST be sized to 2 #CpmlPair. In the simplest
586 * case, that is intersection between two lines, only 1 #CpmlPair
589 * If the primitive types are not known in advance, simply suppose
590 * the worst case and leave room for 4 #CpmlPair in @dest.
593 * This function is primitive dependent: every new primitive must
594 * expose API to get intersections with any other primitive type
595 * (excluding %CAIRO_PATH_CLOSE_PATH, as it is converted to a line
597 * <para>The convention used by CPML is that a primitive should
598 * expose only APIs dealing with lower complexity primitives.
599 * This is required to avoid double functions: you will have
600 * only a cpml_curve_intersection_with_line() function not a
601 * cpml_line_intersection_with_curve(), as the latter is
602 * easily reproduced by calling the former with @primitive2
603 * and @primitive switched.
606 * Return value: the number of intersection points found
609 cpml_primitive_intersection(const CpmlPrimitive
*primitive
,
610 const CpmlPrimitive
*primitive2
,
613 cairo_path_data_type_t type1
, type2
;
615 type1
= primitive
->data
->header
.type
;
616 type2
= primitive
->data
->header
.type
;
618 /* Close path primitives are treated as line-to */
619 if (type1
== CAIRO_PATH_CLOSE_PATH
)
620 type1
= CAIRO_PATH_LINE_TO
;
621 if (type2
== CAIRO_PATH_CLOSE_PATH
)
622 type2
= CAIRO_PATH_LINE_TO
;
624 /* Order the two primitives in ascending complexity, to facilitate
625 * the dispatcher logic */
626 if (cpml_primitive_type_get_npoints(type1
) > cpml_primitive_type_get_npoints(type2
)) {
627 const CpmlPrimitive
*tmp_primitive
;
628 cairo_path_data_type_t tmp_type
;
631 tmp_primitive
= primitive
;
634 primitive
= primitive2
;
637 primitive2
= tmp_primitive
;
640 /* Dispatcher: probably there's a smarter way to do this */
643 case CAIRO_PATH_LINE_TO
:
644 if (type2
== CAIRO_PATH_LINE_TO
)
645 return cpml_line_intersection(primitive2
, primitive
, dest
);
646 else if (type2
== CAIRO_PATH_ARC_TO
)
647 return cpml_arc_intersection_with_line(primitive2
, primitive
, dest
);
648 else if (type2
== CAIRO_PATH_CURVE_TO
)
649 return cpml_curve_intersection_with_line(primitive2
, primitive
, dest
);
652 case CAIRO_PATH_ARC_TO
:
653 if (type2
== CAIRO_PATH_ARC_TO
)
654 return cpml_arc_intersection(primitive2
, primitive
, dest
);
655 else if (type2
== CAIRO_PATH_CURVE_TO
)
656 return cpml_curve_intersection_with_arc(primitive2
, primitive
, dest
);
659 case CAIRO_PATH_CURVE_TO
:
660 if (type2
== CAIRO_PATH_CURVE_TO
)
661 return cpml_curve_intersection(primitive2
, primitive
, dest
);
668 /* Primitive combination not found */
673 * cpml_primitive_offset:
674 * @primitive: a #CpmlPrimitive
675 * @offset: distance for the computed offset primitive
677 * Given a primitive, computes the same (or approximated) parallel
678 * primitive distant @offset from the original one and returns
679 * the result by changing @primitive.
682 * This function is primitive dependent, that is every primitive has
683 * its own implementation.
687 cpml_primitive_offset(CpmlPrimitive
*primitive
, double offset
)
689 switch (primitive
->data
->header
.type
) {
691 case CAIRO_PATH_LINE_TO
:
692 cpml_line_offset(primitive
, offset
);
695 case CAIRO_PATH_ARC_TO
:
696 cpml_arc_offset(primitive
, offset
);
699 case CAIRO_PATH_CURVE_TO
:
700 cpml_curve_offset(primitive
, offset
);
703 case CAIRO_PATH_CLOSE_PATH
:
704 cpml_close_offset(primitive
, offset
);
713 dump_cairo_point(const cairo_path_data_t
*path_data
)
715 printf("(%g %g) ", path_data
->point
.x
, path_data
->point
.y
);