[AdgPath] Added a stub fillet operation
[adg.git] / cpml / cpml-primitive.c
blob6071b1df0c910d4e17ffd6e30b1600dd004fa39a
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.
20 /**
21 * SECTION:primitive
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).
30 **/
32 /**
33 * CpmlPrimitive:
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).
42 **/
44 #include "cpml-primitive.h"
45 #include "cpml-line.h"
46 #include "cpml-arc.h"
47 #include "cpml-curve.h"
48 #include "cpml-close.h"
50 #include <stdlib.h>
51 #include <string.h>
52 #include <stdio.h>
54 static void dump_cairo_point (const cairo_path_data_t *path_data);
57 /**
58 * cpml_primitive_copy:
59 * @primitive: the destination #CpmlPrimitive
60 * @src: the source #CpmlPrimitive
62 * Copies @src in @primitive.
64 * Return value: @primitive
65 **/
66 CpmlPrimitive *
67 cpml_primitive_copy(CpmlPrimitive *primitive, const CpmlPrimitive *src)
69 return memcpy(primitive, src, sizeof(CpmlPrimitive));
72 /**
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
80 **/
81 CpmlPrimitive *
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;
95 return primitive;
98 /**
99 * cpml_primitive_reset:
100 * @primitive: a #CpmlPrimitive
102 * Resets @primitive so it refers to the first primitive of the
103 * source segment.
105 void
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
123 cairo_bool_t
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)
130 return 0;
132 primitive->org = cpml_primitive_get_point(primitive, -1);
133 primitive->data = new_data;
135 return 1;
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
164 * and so on.
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
171 * of the segment.
173 * Return value: a pointer to the requested point (in cairo format)
174 * or %NULL if the point is outside the valid range
176 cairo_path_data_t *
177 cpml_primitive_get_point(const CpmlPrimitive *primitive, int npoint)
179 int npoints;
181 /* For a start point request, simply return the origin
182 * without further checking */
183 if (npoint == 0)
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);
192 if (npoints < 0)
193 return NULL;
195 /* If npoint is negative, consider it as a negative index from the end */
196 if (npoint < 0)
197 npoint = npoints + npoint;
199 /* Out of range condition */
200 if (npoint < 0 || npoint >= npoints)
201 return NULL;
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
214 * is not renderable.
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.
219 void
220 cpml_primitive_to_cairo(const CpmlPrimitive *primitive, cairo_t *cr)
222 cairo_path_t path;
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);
232 break;
234 case CAIRO_PATH_ARC_TO:
235 cpml_arc_to_cairo(primitive, cr);
236 break;
238 default:
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);
243 break;
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.
257 void
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);
266 if (npoints < 0) {
267 printf("Unhandled primitive type (%d)\n", type);
268 return;
271 /* Dump the origin movement, if requested */
272 if (org_also) {
273 printf("Move to ");
274 dump_cairo_point(primitive->org);
275 printf("\n");
278 switch (type) {
280 case CAIRO_PATH_LINE_TO:
281 printf("Line to ");
282 break;
284 case CAIRO_PATH_ARC_TO:
285 printf("Arc to ");
286 break;
288 case CAIRO_PATH_CURVE_TO:
289 printf("Curve to ");
290 break;
292 case CAIRO_PATH_CLOSE_PATH:
293 printf("Path close");
294 break;
296 default:
297 printf("Unknown primitive (type = %d)", type);
298 break;
301 for (n = 1; n < npoints; ++n)
302 dump_cairo_point(cpml_primitive_get_point(primitive, n));
304 printf("\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;
328 int partial, total;
329 CpmlPair tmp_pairs[4];
331 cpml_primitive_from_segment(&portion, (CpmlSegment *) segment);
332 total = 0;
334 do {
335 partial = cpml_primitive_intersection(&portion, primitive, tmp_pairs);
336 if (total + partial > max)
337 partial = max - total;
339 if (partial > 0) {
340 memcpy(dest + total, tmp_pairs, partial * sizeof(CpmlPair));
341 total += partial;
343 } while (total < max && cpml_primitive_next(&portion));
345 return total;
350 * cpml_primitive_type_get_npoints:
351 * @type: a primitive type
353 * Gets the number of points required to identify the @type primitive.
355 * <note><para>
356 * This function is primitive dependent, that is every primitive has
357 * its own implementation.
358 * </para></note>
360 * Return value: the number of points or -1 on errors
363 cpml_primitive_type_get_npoints(cairo_path_data_type_t type)
365 switch (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();
379 default:
380 break;
383 return -1;
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.
394 * <note><para>
395 * This function is primitive dependent, that is every primitive has
396 * its own implementation.
397 * </para></note>
399 * Return value: the requested length or 0 on errors
401 double
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);
416 default:
417 break;
420 return 0.;
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.
438 * <note><para>
439 * This function is primitive dependent, that is every primitive has
440 * its own implementation.
441 * </para></note>
443 void
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);
451 break;
453 case CAIRO_PATH_ARC_TO:
454 cpml_arc_pair_at(primitive, pair, pos);
455 break;
457 case CAIRO_PATH_CURVE_TO:
458 cpml_curve_pair_at(primitive, pair, pos);
459 break;
461 case CAIRO_PATH_CLOSE_PATH:
462 cpml_close_pair_at(primitive, pair, pos);
463 break;
465 default:
466 break;
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.
485 * <note><para>
486 * This function is primitive dependent, that is every primitive has
487 * its own implementation.
488 * </para></note>
490 void
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);
498 break;
500 case CAIRO_PATH_ARC_TO:
501 cpml_arc_vector_at(primitive, vector, pos);
502 break;
504 case CAIRO_PATH_CURVE_TO:
505 cpml_curve_vector_at(primitive, vector, pos);
506 break;
508 case CAIRO_PATH_CLOSE_PATH:
509 cpml_close_vector_at(primitive, vector, pos);
510 break;
512 default:
513 break;
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.
525 * <important>
526 * <title>TODO</title>
527 * <itemizedlist>
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>
534 * </itemizedlist>
535 * </important>
537 * Return value: 1 on success, 0 if the end vector of @primitive
538 * and the start vector of @primitive2 are parallel
540 cairo_bool_t
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];
546 CpmlPair joint;
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)
553 return 1;
555 line1.org = cpml_primitive_get_point(primitive, -2);
556 line1.data = data1;
557 data1[0].header.type = CAIRO_PATH_LINE_TO;
558 data1[1] = *end1;
560 line2.org = start2;
561 line2.data = data2;
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))
566 return 0;
568 cpml_pair_to_cairo(&joint, end1);
569 cpml_pair_to_cairo(&joint, start2);
571 return 1;
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
587 * is required.
589 * If the primitive types are not known in advance, simply suppose
590 * the worst case and leave room for 4 #CpmlPair in @dest.
592 * <note><para>
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
596 * primitive).</para>
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.
604 * </para></note>
606 * Return value: the number of intersection points found
609 cpml_primitive_intersection(const CpmlPrimitive *primitive,
610 const CpmlPrimitive *primitive2,
611 CpmlPair *dest)
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;
630 tmp_type = type1;
631 tmp_primitive = primitive;
633 type1 = type2;
634 primitive = primitive2;
636 type2 = tmp_type;
637 primitive2 = tmp_primitive;
640 /* Dispatcher: probably there's a smarter way to do this */
641 switch (type1) {
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);
650 break;
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);
657 break;
659 case CAIRO_PATH_CURVE_TO:
660 if (type2 == CAIRO_PATH_CURVE_TO)
661 return cpml_curve_intersection(primitive2, primitive, dest);
662 break;
664 default:
665 break;
668 /* Primitive combination not found */
669 return 0;
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.
681 * <note><para>
682 * This function is primitive dependent, that is every primitive has
683 * its own implementation.
684 * </para></note>
686 void
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);
693 break;
695 case CAIRO_PATH_ARC_TO:
696 cpml_arc_offset(primitive, offset);
697 break;
699 case CAIRO_PATH_CURVE_TO:
700 cpml_curve_offset(primitive, offset);
701 break;
703 case CAIRO_PATH_CLOSE_PATH:
704 cpml_close_offset(primitive, offset);
705 break;
707 default:
708 break;
712 static void
713 dump_cairo_point(const cairo_path_data_t *path_data)
715 printf("(%g %g) ", path_data->point.x, path_data->point.y);