[nodist] Updated the logo
[adg.git] / cpml / cpml-primitive.c
blob76233b4fdca549caffe34a4887e44b45fbe2b999
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.
21 /**
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.
33 **/
35 /**
36 * CpmlPrimitiveType:
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.
44 **/
46 /**
47 * CpmlPrimitive:
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).
56 **/
59 #include "cpml-primitive.h"
60 #include "cpml-line.h"
61 #include "cpml-arc.h"
62 #include "cpml-curve.h"
63 #include "cpml-close.h"
65 #include <stdlib.h>
66 #include <string.h>
67 #include <stdio.h>
70 static void dump_cairo_point (const cairo_path_data_t *path_data);
73 /**
74 * cpml_primitive_copy:
75 * @primitive: the destination #CpmlPrimitive
76 * @src: the source #CpmlPrimitive
78 * Copies @src in @primitive. This is a shallow copy: the internal fields
79 * of @primitive refer to the same memory as the original @src primitive.
81 * Return value: @primitive
82 **/
83 CpmlPrimitive *
84 cpml_primitive_copy(CpmlPrimitive *primitive, const CpmlPrimitive *src)
86 return memcpy(primitive, src, sizeof(CpmlPrimitive));
89 /**
90 * cpml_primitive_from_segment:
91 * @primitive: the destination #CpmlPrimitive struct
92 * @segment: the source segment
94 * Initializes @primitive to the first primitive of @segment.
96 * Return value: @primitive
97 **/
98 CpmlPrimitive *
99 cpml_primitive_from_segment(CpmlPrimitive *primitive, CpmlSegment *segment)
101 primitive->segment = segment;
103 /* The first element of a CpmlSegment is always a CAIRO_PATH_MOVE_TO,
104 * as ensured by cpml_segment_from_cairo() and by the browsing APIs,
105 * so the origin is in the second data item */
106 primitive->org = &segment->data[1];
108 /* Also, the segment APIs ensure that @segment is prepended by
109 * only one CAIRO_PATH_MOVE_TO */
110 primitive->data = segment->data + 2;
112 return primitive;
116 * cpml_primitive_reset:
117 * @primitive: a #CpmlPrimitive
119 * Resets @primitive so it refers to the first primitive of the
120 * source segment.
122 void
123 cpml_primitive_reset(CpmlPrimitive *primitive)
125 primitive->org = &primitive->segment->data[1];
126 primitive->data = primitive->segment->data + 2;
130 * cpml_primitive_next:
131 * @primitive: a #CpmlPrimitive
134 * Changes @primitive so it refers to the next primitive on the
135 * source segment. If there are no more primitives, @primitive is
136 * not changed and 0 is returned.
138 * Return value: 1 on success, 0 if no next primitive found or errors
140 cairo_bool_t
141 cpml_primitive_next(CpmlPrimitive *primitive)
143 cairo_path_data_t *new_data;
145 new_data = primitive->data + primitive->data->header.length;
146 if (new_data - primitive->segment->data >= primitive->segment->num_data)
147 return 0;
149 primitive->org = cpml_primitive_get_point(primitive, -1);
150 primitive->data = new_data;
152 return 1;
156 * cpml_primitive_get_npoints:
157 * @primitive: a #CpmlPrimitive
159 * Gets the number of points required to identify @primitive.
160 * It is similar to cpml_primitive_type_get_npoints() but using
161 * a @primitive instance instead of a type.
163 * Return value: the number of points or -1 on errors
166 cpml_primitive_get_npoints(const CpmlPrimitive *primitive)
168 return cpml_primitive_type_get_npoints(primitive->data->header.type);
172 * cpml_primitive_get_point:
173 * @primitive: a #CpmlPrimitive
174 * @npoint: the index of the point to retrieve
176 * Gets the specified @npoint from @primitive. The index starts
177 * at 0: if @npoint is 0, the start point (the origin) is
178 * returned, 1 for the second point and so on. If @npoint is
179 * negative, it is considered as a negative index from the end,
180 * so that -1 is the end point, -2 the point before the end point
181 * and so on.
183 * %CAIRO_PATH_CLOSE_PATH is managed in a special way: if @npoint
184 * is -1 or 1 and @primitive is a close-path, this function cycles
185 * the source #CpmlSegment and returns the first point. This is
186 * needed because requesting the end point (or the second point)
187 * of a close path is a valid operation and must returns the start
188 * of the segment.
190 * Return value: a pointer to the requested point (in cairo format)
191 * or %NULL if the point is outside the valid range
193 cairo_path_data_t *
194 cpml_primitive_get_point(const CpmlPrimitive *primitive, int npoint)
196 int npoints;
198 /* For a start point request, simply return the origin
199 * without further checking */
200 if (npoint == 0)
201 return primitive->org;
203 /* The CAIRO_PATH_CLOSE_PATH special case */
204 if (primitive->data->header.type == CAIRO_PATH_CLOSE_PATH &&
205 (npoint == 1 || npoint == -1))
206 return &primitive->segment->data[1];
208 npoints = cpml_primitive_get_npoints(primitive);
209 if (npoints < 0)
210 return NULL;
212 /* If npoint is negative, consider it as a negative index from the end */
213 if (npoint < 0)
214 npoint = npoints + npoint;
216 /* Out of range condition */
217 if (npoint < 0 || npoint >= npoints)
218 return NULL;
220 return npoint == 0 ? primitive->org : &primitive->data[npoint];
224 * cpml_primitive_to_cairo:
225 * @primitive: a #CpmlPrimitive
226 * @cr: the destination cairo context
228 * Renders a single @primitive to the @cr cairo context.
229 * As a special case, if the primitive is a #CAIRO_PATH_CLOSE_PATH,
230 * an equivalent line is rendered, because a close path left alone
231 * is not renderable.
233 * Also a #CAIRO_PATH_ARC_TO primitive is treated specially, as it
234 * is not natively supported by cairo and has its own rendering API.
236 void
237 cpml_primitive_to_cairo(const CpmlPrimitive *primitive, cairo_t *cr)
239 cairo_path_t path;
240 cairo_path_data_t *path_data;
242 cairo_move_to(cr, primitive->org->point.x, primitive->org->point.y);
244 switch (primitive->data->header.type) {
246 case CAIRO_PATH_CLOSE_PATH:
247 path_data = cpml_primitive_get_point(primitive, -1);
248 cairo_line_to(cr, path_data->point.x, path_data->point.y);
249 break;
251 case CAIRO_PATH_ARC_TO:
252 cpml_arc_to_cairo(primitive, cr);
253 break;
255 default:
256 path.status = CAIRO_STATUS_SUCCESS;
257 path.data = primitive->data;
258 path.num_data = primitive->data->header.length;
259 cairo_append_path(cr, &path);
260 break;
265 * cpml_primitive_dump:
266 * @primitive: a #CpmlPrimitive
267 * @org_also: whether to output also the origin coordinates
269 * Dumps info on the specified @primitive to stdout: useful for
270 * debugging purposes. If @org_also is 1, a %CAIRO_PATH_MOVE_TO
271 * to the origin is prepended to the data otherwise the
272 * <structfield>org</structfield> field is not used.
274 void
275 cpml_primitive_dump(const CpmlPrimitive *primitive, cairo_bool_t org_also)
277 const cairo_path_data_t *data;
278 int type, n, npoints;
280 data = primitive->data;
281 type = data->header.type;
282 npoints = cpml_primitive_get_npoints(primitive);
283 if (npoints < 0) {
284 printf("Unhandled primitive type (%d)\n", type);
285 return;
288 /* Dump the origin movement, if requested */
289 if (org_also) {
290 printf("Move to ");
291 dump_cairo_point(primitive->org);
292 printf("\n");
295 switch (type) {
297 case CAIRO_PATH_LINE_TO:
298 printf("Line to ");
299 break;
301 case CAIRO_PATH_ARC_TO:
302 printf("Arc to ");
303 break;
305 case CAIRO_PATH_CURVE_TO:
306 printf("Curve to ");
307 break;
309 case CAIRO_PATH_CLOSE_PATH:
310 printf("Path close");
311 break;
313 default:
314 printf("Unknown primitive (type = %d)", type);
315 break;
318 for (n = 1; n < npoints; ++n)
319 dump_cairo_point(cpml_primitive_get_point(primitive, n));
321 printf("\n");
325 * cpml_primitive_intersection_with_segment:
326 * @primitive: a #CpmlPrimitive
327 * @segment: a #CpmlSegment
328 * @dest: the destination vector of #CpmlPair
329 * @max: maximum number of intersections to return
331 * Computes the intersections between @segment and @primitive by
332 * sequentially scanning the primitives in @segment and looking
333 * for intersections with @primitive.
334 * If the intersections are more than @max, only the first @max pairs
335 * are stored in @dest.
337 * Return value: the number of intersections found
340 cpml_primitive_intersection_with_segment(const CpmlPrimitive *primitive,
341 const CpmlSegment *segment,
342 CpmlPair *dest, int max)
344 CpmlPrimitive portion;
345 int found;
347 cpml_primitive_from_segment(&portion, (CpmlSegment *) segment);
348 found = 0;
350 while (found < max) {
351 found += cpml_primitive_intersection(&portion, primitive,
352 dest+found, max-found);
353 if (!cpml_primitive_next(&portion))
354 break;
357 return found;
362 * cpml_primitive_type_get_npoints:
363 * @type: a primitive type
365 * Gets the number of points required to identify the @type primitive.
367 * <note><para>
368 * This function is primitive dependent, that is every primitive has
369 * its own implementation.
370 * </para></note>
372 * Return value: the number of points or -1 on errors
375 cpml_primitive_type_get_npoints(CpmlPrimitiveType type)
377 switch (type) {
379 case CAIRO_PATH_LINE_TO:
380 return cpml_line_type_get_npoints();
382 case CAIRO_PATH_ARC_TO:
383 return cpml_arc_type_get_npoints();
385 case CAIRO_PATH_CURVE_TO:
386 return cpml_curve_type_get_npoints();
388 case CAIRO_PATH_CLOSE_PATH:
389 return cpml_close_type_get_npoints();
391 default:
392 break;
395 return -1;
399 * cpml_primitive_length:
400 * @primitive: a #CpmlPrimitive
402 * Abstracts the length() family functions by providing a common
403 * way to access the underlying primitive-specific implementation.
404 * The function returns the length of @primitive.
406 * <note><para>
407 * This function is primitive dependent, that is every primitive has
408 * its own implementation.
409 * </para></note>
411 * Return value: the requested length or 0 on errors
413 double
414 cpml_primitive_length(const CpmlPrimitive *primitive)
416 switch (primitive->data->header.type) {
418 case CAIRO_PATH_LINE_TO:
419 case CAIRO_PATH_CLOSE_PATH:
420 return cpml_line_length(primitive);
422 case CAIRO_PATH_ARC_TO:
423 return cpml_arc_length(primitive);
425 case CAIRO_PATH_CURVE_TO:
426 return cpml_curve_length(primitive);
428 default:
429 break;
432 return 0.;
436 * cpml_primitive_extents:
437 * @primitive: a #CpmlPrimitive
438 * @extents: where to store the extents
440 * Abstracts the extents() family functions by providing a common
441 * way to access the underlying primitive-specific implementation.
442 * The function stores in @extents the bounding box of @primitive.
444 * <note><para>
445 * This function is primitive dependent, that is every primitive has
446 * its own implementation.
447 * </para></note>
449 void
450 cpml_primitive_extents(const CpmlPrimitive *primitive, CpmlExtents *extents)
452 switch (primitive->data->header.type) {
454 case CAIRO_PATH_LINE_TO:
455 case CAIRO_PATH_CLOSE_PATH:
456 return cpml_line_extents(primitive, extents);
458 case CAIRO_PATH_ARC_TO:
459 return cpml_arc_extents(primitive, extents);
461 case CAIRO_PATH_CURVE_TO:
462 return cpml_curve_extents(primitive, extents);
464 default:
465 break;
470 * cpml_primitive_pair_at:
471 * @primitive: a #CpmlPrimitive
472 * @pair: the destination #CpmlPair
473 * @pos: the position value
475 * Abstracts the pair_at() family functions by providing a common
476 * way to access the underlying primitive-specific implementation.
478 * It gets the coordinates of the point lying on @primitive
479 * at position @pos. @pos is an homogeneous factor where 0 is the
480 * start point, 1 the end point, 0.5 the mid point and so on.
481 * The relation 0 < @pos < 1 should be satisfied, although some
482 * primitives accept value outside this range.
484 * <note><para>
485 * This function is primitive dependent, that is every primitive has
486 * its own implementation.
487 * </para></note>
489 void
490 cpml_primitive_pair_at(const CpmlPrimitive *primitive,
491 CpmlPair *pair, double pos)
493 switch (primitive->data->header.type) {
495 case CAIRO_PATH_LINE_TO:
496 cpml_line_pair_at(primitive, pair, pos);
497 break;
499 case CAIRO_PATH_ARC_TO:
500 cpml_arc_pair_at(primitive, pair, pos);
501 break;
503 case CAIRO_PATH_CURVE_TO:
504 cpml_curve_pair_at(primitive, pair, pos);
505 break;
507 case CAIRO_PATH_CLOSE_PATH:
508 cpml_close_pair_at(primitive, pair, pos);
509 break;
511 default:
512 break;
517 * cpml_primitive_vector_at:
518 * @primitive: a #CpmlPrimitive
519 * @vector: the destination #CpmlVector
520 * @pos: the position value
522 * Abstracts the vector_at() family functions by providing a common
523 * way to access the underlying primitive-specific implementation.
525 * It gets the steepness of the point at position @pos on @primitive.
526 * @pos is an homogeneous factor where 0 is the start point, 1 the
527 * end point, 0.5 the mid point and so on.
528 * The relation 0 < @pos < 1 should be satisfied, although some
529 * primitives accept value outside this range.
531 * <note><para>
532 * This function is primitive dependent, that is every primitive has
533 * its own implementation.
534 * </para></note>
536 void
537 cpml_primitive_vector_at(const CpmlPrimitive *primitive,
538 CpmlVector *vector, double pos)
540 switch (primitive->data->header.type) {
542 case CAIRO_PATH_LINE_TO:
543 cpml_line_vector_at(primitive, vector, pos);
544 break;
546 case CAIRO_PATH_ARC_TO:
547 cpml_arc_vector_at(primitive, vector, pos);
548 break;
550 case CAIRO_PATH_CURVE_TO:
551 cpml_curve_vector_at(primitive, vector, pos);
552 break;
554 case CAIRO_PATH_CLOSE_PATH:
555 cpml_close_vector_at(primitive, vector, pos);
556 break;
558 default:
559 break;
564 * cpml_primitive_near_pos:
565 * @primitive: a #CpmlPrimitive
566 * @pair: the coordinates of the subject point
568 * Returns the pos value of the point on @primitive nearest to @pair.
569 * The returned value is always between 0 and 1 or -1 in case of errors.
571 * <note><para>
572 * This function is primitive dependent, that is every primitive has
573 * its own implementation.
574 * </para></note>
576 * Return value: the requested pos value between 0 and 1 or -1 on errors
578 double
579 cpml_primitive_near_pos(const CpmlPrimitive *primitive, const CpmlPair *pair)
581 switch (primitive->data->header.type) {
583 case CAIRO_PATH_LINE_TO:
584 return cpml_line_near_pos(primitive, pair);
586 case CAIRO_PATH_ARC_TO:
587 return cpml_arc_near_pos(primitive, pair);
589 case CAIRO_PATH_CURVE_TO:
590 return cpml_curve_near_pos(primitive, pair);
592 case CAIRO_PATH_CLOSE_PATH:
593 return cpml_close_near_pos(primitive, pair);
595 default:
596 break;
599 return -1.;
603 * cpml_primitive_join:
604 * @primitive: the first #CpmlPrimitive
605 * @primitive2: the second #CpmlPrimitive
607 * Joins two primitive modifying the end point of @primitive and the
608 * start point of @primitive2 so that the resulting points will overlap.
610 * <important>
611 * <title>TODO</title>
612 * <itemizedlist>
613 * <listitem>Actually, the join is done by extending the end vector
614 * of @primitive and the start vector of @primitive2 and
615 * interpolating the intersection: this means no primitive
616 * dependent code is needed. Anyway, it is likely to change
617 * in the future because this approach is quite naive when
618 * curves are involved.</listitem>
619 * </itemizedlist>
620 * </important>
622 * Return value: 1 on success, 0 if the end vector of @primitive
623 * and the start vector of @primitive2 are parallel
625 cairo_bool_t
626 cpml_primitive_join(CpmlPrimitive *primitive, CpmlPrimitive *primitive2)
628 cairo_path_data_t *end1, *start2;
629 CpmlPrimitive line1, line2;
630 cairo_path_data_t data1[2], data2[2];
631 CpmlPair joint;
633 end1 = cpml_primitive_get_point(primitive, -1);
634 start2 = cpml_primitive_get_point(primitive2, 0);
636 /* Check if the primitives are yet connected */
637 if (end1->point.x == start2->point.x && end1->point.y == start2->point.y)
638 return 1;
640 line1.org = cpml_primitive_get_point(primitive, -2);
641 line1.data = data1;
642 data1[0].header.type = CAIRO_PATH_LINE_TO;
643 data1[1] = *end1;
645 line2.org = start2;
646 line2.data = data2;
647 data2[0].header.type = CAIRO_PATH_LINE_TO;
648 data2[1] = *cpml_primitive_get_point(primitive2, 1);
650 if (!cpml_line_intersection(&line1, &line2, &joint, 1))
651 return 0;
653 cpml_pair_to_cairo(&joint, end1);
654 cpml_pair_to_cairo(&joint, start2);
656 return 1;
660 * cpml_primitive_intersection:
661 * @primitive: the first #CpmlPrimitive
662 * @primitive2: the second #CpmlPrimitive
663 * @dest: the destination #CpmlPair (or a vector of #CpmlPair)
664 * @max: maximum number of intersections to return
666 * Finds the intersection points between the given primitives and
667 * returns the result in @dest. The size of @dest should be enough
668 * to store @max #CpmlPair. The absoulte max number of intersections
669 * is dependent from the type of the primitive involved in the
670 * operation. If there are at least one Bézier curve involved, up to
671 * 4 intersections could be returned. Otherwise, if there is an arc
672 * the intersections will be 2 at maximum. For line line primitives,
673 * there is only 1 point (or obviously 0 if the lines do not intersect).
675 * <note><para>
676 * This function is primitive dependent: every new primitive must
677 * expose API to get intersections with any other primitive type
678 * (excluding %CAIRO_PATH_CLOSE_PATH, as it is converted to a line
679 * primitive).</para>
680 * <para>The convention used by CPML is that a primitive should
681 * expose only intersection APIs dealing with lower complexity
682 * primitives. This is required to avoid double functions:
683 * you will have only a cpml_curve_intersection_with_line() function,
684 * not a cpml_line_intersection_with_curve(), as the latter is
685 * easily reproduced by calling the former with @primitive2
686 * and @primitive swapped.
687 * </para></note>
689 * Return value: the number of intersection points found or 0 if the
690 * primitives do not intersect
693 cpml_primitive_intersection(const CpmlPrimitive *primitive,
694 const CpmlPrimitive *primitive2,
695 CpmlPair *dest, int max)
697 CpmlPrimitiveType type1, type2;
699 type1 = primitive->data->header.type;
700 type2 = primitive->data->header.type;
702 /* Close path primitives are treated as line-to */
703 if (type1 == CAIRO_PATH_CLOSE_PATH)
704 type1 = CAIRO_PATH_LINE_TO;
705 if (type2 == CAIRO_PATH_CLOSE_PATH)
706 type2 = CAIRO_PATH_LINE_TO;
708 /* Order the two primitives in ascending complexity, to facilitate
709 * the dispatcher logic */
710 if (cpml_primitive_type_get_npoints(type1) > cpml_primitive_type_get_npoints(type2)) {
711 const CpmlPrimitive *tmp_primitive;
712 CpmlPrimitiveType tmp_type;
714 tmp_type = type1;
715 tmp_primitive = primitive;
717 type1 = type2;
718 primitive = primitive2;
720 type2 = tmp_type;
721 primitive2 = tmp_primitive;
724 /* Dispatcher: probably there's a smarter way to do this */
725 switch (type1) {
727 case CAIRO_PATH_LINE_TO:
728 if (type2 == CAIRO_PATH_LINE_TO)
729 return cpml_line_intersection(primitive2, primitive,
730 dest, max);
731 else if (type2 == CAIRO_PATH_ARC_TO)
732 return cpml_arc_intersection_with_line(primitive2, primitive,
733 dest, max);
734 else if (type2 == CAIRO_PATH_CURVE_TO)
735 return cpml_curve_intersection_with_line(primitive2, primitive,
736 dest, max);
737 break;
739 case CAIRO_PATH_ARC_TO:
740 if (type2 == CAIRO_PATH_ARC_TO)
741 return cpml_arc_intersection(primitive2, primitive,
742 dest, max);
743 else if (type2 == CAIRO_PATH_CURVE_TO)
744 return cpml_curve_intersection_with_arc(primitive2, primitive,
745 dest, max);
746 break;
748 case CAIRO_PATH_CURVE_TO:
749 if (type2 == CAIRO_PATH_CURVE_TO)
750 return cpml_curve_intersection(primitive2, primitive,
751 dest, max);
752 break;
754 default:
755 break;
758 /* Primitive combination not found */
759 return 0;
763 * cpml_primitive_offset:
764 * @primitive: a #CpmlPrimitive
765 * @offset: distance for the computed offset primitive
767 * Given a primitive, computes the same (or approximated) parallel
768 * primitive distant @offset from the original one and returns
769 * the result by changing @primitive.
771 * <note><para>
772 * This function is primitive dependent, that is every primitive has
773 * its own implementation.
774 * </para></note>
776 void
777 cpml_primitive_offset(CpmlPrimitive *primitive, double offset)
779 switch (primitive->data->header.type) {
781 case CAIRO_PATH_LINE_TO:
782 cpml_line_offset(primitive, offset);
783 break;
785 case CAIRO_PATH_ARC_TO:
786 cpml_arc_offset(primitive, offset);
787 break;
789 case CAIRO_PATH_CURVE_TO:
790 cpml_curve_offset(primitive, offset);
791 break;
793 case CAIRO_PATH_CLOSE_PATH:
794 cpml_close_offset(primitive, offset);
795 break;
797 default:
798 break;
802 static void
803 dump_cairo_point(const cairo_path_data_t *path_data)
805 printf("(%g %g) ", path_data->point.x, path_data->point.y);