cpml/cpml-arc.c

   1 /* CPML - Cairo Path Manipulation Library
   2  * Copyright (C) 2008,2009,2010  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 /**
  22  * SECTION:cpml-arc
  23  * @Section_Id:CpmlArc
  24  * @title: CpmlArc
  25  * @short_description: Manipulation of circular arcs
  26  *
  27  * The following functions manipulate #CPML_ARC #CpmlPrimitive.
  28  * No validation is made on the input so use the following methods
  29  * only when you are sure the <varname>primitive</varname> argument
  30  * is effectively an arc-to.
  31  *
  32  * The arc primitive is defined by 3 points: the first one is the usual
  33  * implicit point got from the previous primitive, the second point is
  34  * an arbitrary intermediate point laying on the arc and the third point
  35  * is the end of the arc. These points identify univocally an arc:
  36  * furthermore, the intermediate point also gives the side of
  37  * the arc.
  38  *
  39  * As a special case, when the first point is coincident with the end
  40  * point the primitive is considered a circle with diameter defined by
  41  * the segment between the first and the intermediate point.
  42  *
  43  * <important>
  44  * <para>
  45  * An arc is not a native cairo primitive and should be treated specially.
  46  * </para>
  47  * </important>
  48  *
  49  * Using these CPML APIs you are free to use #CPML_ARC whenever
  50  * you want but, if you are directly accessing the struct fields, you
  51  * are responsible of converting arcs to curves before passing them
  52  * to cairo. In other words, do not directly feed #CpmlPath struct to
  53  * cairo (throught cairo_append_path() for example) or at least do not
  54  * expect it will work.
  55  *
  56  * The conversion is provided by two APIs: cpml_arc_to_cairo() and
  57  * cpml_arc_to_curves(). The former directly renders to a cairo context
  58  * and is internally used by all the ..._to_cairo() functions when an
  59  * arc is met. The latter provided a more powerful (and more complex)
  60  * approach as it allows to specify the number of curves to use and do
  61  * not need a cairo context.
  62  *
  63  * <important>
  64  * <title>TODO</title>
  65  * <itemizedlist>
  66  * <listitem>the get_closest_pos() method must be implemented;</listitem>
  67  * <listitem>the put_intersections() method must be implemented;</listitem>
  68  * </itemizedlist>
  69  * </important>
  70  **/
  71
  72 /**
  73  * CPML_ARC:
  74  *
  75  * The type code used to identify "arc-to" primitives.
  76  * This is expected to be defined by cairo whenever (and if) cairo
  77  * will support arc primitives. Actually (cairo-1.8.8) it is resolved
  78  * to an harcoded constant (%100).
  79  **/
  80
  81
  82 #include "cpml-internal.h"
  83 #include "cpml-extents.h"
  84 #include "cpml-segment.h"
  85 #include "cpml-primitive.h"
  86 #include "cpml-primitive-private.h"
  87 #include "cpml-arc.h"
  88 #include "cpml-curve.h"
  89 #include <math.h>
  90
  91
  92 /* Hardcoded max angle of the arc to be approximated by a Bézier curve:
  93  * this influence the arc quality (the default value is got from cairo) */
  94 #define ARC_MAX_ANGLE   M_PI_2
  95
  96 /* Macro to save typing and make put_extents() code cleaner */
  97 #define ANGLE_INCLUDED(d) \
  98     ((start < (d) && end > (d)) || (start > (d) && end < (d)))
  99
 100
 101 static double           get_length      (const CpmlPrimitive    *arc);
 102 static void             put_extents     (const CpmlPrimitive    *arc,
 103                                          CpmlExtents            *extents);
 104 static void             put_pair_at     (const CpmlPrimitive    *arc,
 105                                          double                  pos,
 106                                          CpmlPair               *pair);
 107 static void             put_vector_at   (const CpmlPrimitive    *arc,
 108                                          double                  pos,
 109                                          CpmlVector             *vector);
 110 static void             offset          (CpmlPrimitive          *arc,
 111                                          double                  offset);
 112 static cairo_bool_t     get_center      (const CpmlPair         *p,
 113                                          CpmlPair               *dest);
 114 static void             get_angles      (const CpmlPair         *p,
 115                                          const CpmlPair         *center,
 116                                          double                 *start,
 117                                          double                 *end);
 118 static void             arc_to_curve    (CpmlPrimitive          *curve,
 119                                          const CpmlPair         *center,
 120                                          double                  r,
 121                                          double                  start,
 122                                          double                  end);
 123
 124
 125 const _CpmlPrimitiveClass *
 126 _cpml_arc_get_class(void)
 127 {
 128     static _CpmlPrimitiveClass *p_class = NULL;
 129
 130     if (p_class == NULL) {
 131         static _CpmlPrimitiveClass class_data = {
 132             "arc to", 3,
 133             get_length,
 134             put_extents,
 135             put_pair_at,
 136             put_vector_at,
 137             NULL,
 138             NULL,
 139             offset,
 140             NULL
 141         };
 142         p_class = &class_data;
 143     }
 144
 145     return p_class;
 146 }
 147
 148
 149 /**
 150  * cpml_arc_info:
 151  * @arc:    the #CpmlPrimitive arc data
 152  * @center: where to store the center coordinates (can be %NULL)
 153  * @r:      where to store the radius (can be %NULL)
 154  * @start:  where to store the starting angle (can be %NULL)
 155  * @end:    where to store the ending angle (can be %NULL)
 156  *
 157  * Given an @arc, this function calculates and returns its basic data.
 158  * Any pointer can be %NULL, in which case the requested info is not
 159  * returned. This function can fail (when the three points lay on a
 160  * straight line, for example) in which case 0 is returned and no
 161  * data can be considered valid.
 162  *
 163  * The radius @r can be 0 when the three points are coincidents: a
 164  * circle with radius 0 is considered a valid path.
 165  *
 166  * When the start and end angle are returned, together with their
 167  * values these angles implicitely gives another important information:
 168  * the arc direction.
 169  *
 170  * If @start < @end the arc must be rendered with increasing angle
 171  * value (clockwise direction using the ordinary cairo coordinate
 172  * system) while if @start > @end the arc must be rendered in reverse
 173  * order (that is counterclockwise in the cairo world). This is the
 174  * reason the angle values are returned in the range
 175  * { -M_PI < value < 3*M_PI } inclusive instead of the usual
 176  * { -M_PI < value < M_PI } range.
 177  *
 178  * Returns: 1 if the function worked succesfully, 0 on errors
 179  **/
 180 cairo_bool_t
 181 cpml_arc_info(const CpmlPrimitive *arc, CpmlPair *center,
 182               double *r, double *start, double *end)
 183 {
 184     CpmlPair p[3], l_center;
 185
 186     cpml_pair_from_cairo(&p[0], arc->org);
 187     cpml_pair_from_cairo(&p[1], &arc->data[1]);
 188     cpml_pair_from_cairo(&p[2], &arc->data[2]);
 189
 190     if (!get_center(p, &l_center))
 191         return 0;
 192
 193     if (center)
 194         *center = l_center;
 195
 196     if (r != NULL)
 197         *r = cpml_pair_distance(&p[0], &l_center);
 198
 199     if (start != NULL || end != NULL) {
 200         double l_start, l_end;
 201
 202         get_angles(p, &l_center, &l_start, &l_end);
 203
 204         if (start != NULL)
 205             *start = l_start;
 206         if (end != NULL)
 207             *end = l_end;
 208     }
 209
 210     return 1;
 211 }
 212
 213 /**
 214  * cpml_arc_to_cairo:
 215  * @arc: the #CpmlPrimitive arc data
 216  * @cr:  the destination cairo context
 217  *
 218  * Renders @arc to the @cr cairo context. As cairo does not support
 219  * arcs natively, it is approximated using one or more Bézier curves.
 220  *
 221  * The number of curves used is dependent from the angle of the arc.
 222  * Anyway, this function uses internally the hardcoded %M_PI_2 value
 223  * as threshold value. This means the maximum arc approximated by a
 224  * single curve will be a quarter of a circle and, consequently, a
 225  * whole circle will be approximated by 4 Bézier curves.
 226  **/
 227 void
 228 cpml_arc_to_cairo(const CpmlPrimitive *arc, cairo_t *cr)
 229 {
 230     CpmlPair center;
 231     double r, start, end;
 232     size_t n_curves;
 233     double step, angle;
 234     CpmlPrimitive curve;
 235     cairo_path_data_t data[4];
 236
 237     if (!cpml_arc_info(arc, &center, &r, &start, &end))
 238         return;
 239
 240     n_curves = ceil(fabs(end-start) / ARC_MAX_ANGLE);
 241     step = (end-start) / (double) n_curves;
 242     curve.data = data;
 243
 244     for (angle = start; n_curves--; angle += step) {
 245         arc_to_curve(&curve, &center, r, angle, angle+step);
 246         cairo_curve_to(cr,
 247                        curve.data[1].point.x, curve.data[1].point.y,
 248                        curve.data[2].point.x, curve.data[2].point.y,
 249                        curve.data[3].point.x, curve.data[3].point.y);
 250     }
 251 }
 252
 253 /**
 254  * cpml_arc_to_curves:
 255  * @arc:      the #CpmlPrimitive arc data
 256  * @segment:  the destination #CpmlSegment
 257  * @n_curves: number of Bézier to use
 258  *
 259  * Converts @arc to a serie of @n_curves Bézier curves and puts them
 260  * inside @segment. Obviously, @segment must have enough space to
 261  * contain at least @n_curves curves.
 262  *
 263  * This function works in a similar way as cpml_arc_to_cairo() but
 264  * has two important differences: it does not need a cairo context
 265  * and the number of curves to be generated is explicitely defined.
 266  * The latter difference allows a more specific error control from
 267  * the application: in the file src/cairo-arc.c, found in the cairo
 268  * tarball (at least in cairo-1.9.1), there is a table showing the
 269  * magnitude of error of this curve approximation algorithm.
 270  **/
 271 void
 272 cpml_arc_to_curves(const CpmlPrimitive *arc, CpmlSegment *segment,
 273                    size_t n_curves)
 274 {
 275     CpmlPair center;
 276     double r, start, end;
 277     double step, angle;
 278     CpmlPrimitive curve;
 279
 280     if (!cpml_arc_info(arc, &center, &r, &start, &end))
 281         return;
 282
 283     step = (end-start) / (double) n_curves;
 284     segment->num_data = n_curves*4;
 285     curve.segment = segment;
 286     curve.data = segment->data;
 287
 288     for (angle = start; n_curves--; angle += step) {
 289         arc_to_curve(&curve, &center, r, angle, angle+step);
 290         curve.data += 4;
 291     }
 292 }
 293
 294
 295 static double
 296 get_length(const CpmlPrimitive *arc)
 297 {
 298     double r, start, end, delta;
 299
 300     if (!cpml_arc_info(arc, NULL, &r, &start, &end) || start == end)
 301         return 0.;
 302
 303     delta = end - start;
 304     if (delta < 0)
 305         delta += M_PI*2;
 306
 307     return r*delta;
 308 }
 309
 310 static void
 311 put_extents(const CpmlPrimitive *arc, CpmlExtents *extents)
 312 {
 313     double r, start, end;
 314     CpmlPair center, pair;
 315
 316     extents->is_defined = 0;
 317
 318     if (!cpml_arc_info(arc, &center, &r, &start, &end))
 319         return;
 320
 321     /* Add the right quadrant point if needed */
 322     if (ANGLE_INCLUDED(0) || ANGLE_INCLUDED(M_PI * 2)) {
 323         pair.x = center.x + r;
 324         pair.y = center.y;
 325         cpml_extents_pair_add(extents, &pair);
 326     }
 327
 328     /* Add the bottom quadrant point if needed */
 329     if (ANGLE_INCLUDED(M_PI_2) || ANGLE_INCLUDED(M_PI_2 * 5)) {
 330         pair.x = center.x;
 331         pair.y = center.y + r;
 332         cpml_extents_pair_add(extents, &pair);
 333     }
 334
 335     /* Add the left quadrant point if needed */
 336     if (ANGLE_INCLUDED(M_PI)) {
 337         pair.x = center.x - r;
 338         pair.y = center.y;
 339         cpml_extents_pair_add(extents, &pair);
 340     }
 341
 342     /* Add the top quadrant point if needed */
 343     if (ANGLE_INCLUDED(M_PI_2 * 3) || ANGLE_INCLUDED(-M_PI_2)) {
 344         pair.x = center.x;
 345         pair.y = center.y - r;
 346         cpml_extents_pair_add(extents, &pair);
 347     }
 348
 349     /* Add the start point */
 350     cpml_pair_from_cairo(&pair, cpml_primitive_get_point(arc, 0));
 351     cpml_extents_pair_add(extents, &pair);
 352
 353     /* Add the end point */
 354     cpml_pair_from_cairo(&pair, cpml_primitive_get_point(arc, -1));
 355     cpml_extents_pair_add(extents, &pair);
 356 }
 357
 358 static void
 359 put_pair_at(const CpmlPrimitive *arc, double pos, CpmlPair *pair)
 360 {
 361     if (pos == 0.) {
 362         cpml_pair_from_cairo(pair, arc->org);
 363     } else if (pos == 1.) {
 364         cpml_pair_from_cairo(pair, &arc->data[2]);
 365     } else {
 366         CpmlPair center;
 367         double r, start, end, angle;
 368
 369         if (!cpml_arc_info(arc, &center, &r, &start, &end))
 370             return;
 371
 372         angle = (end-start)*pos + start;
 373         cpml_vector_from_angle(pair, angle);
 374         cpml_vector_set_length(pair, r);
 375
 376         pair->x += center.x;
 377         pair->y += center.y;
 378     }
 379 }
 380
 381 static void
 382 put_vector_at(const CpmlPrimitive *arc, double pos, CpmlVector *vector)
 383 {
 384     double start, end, angle;
 385
 386     if (!cpml_arc_info(arc, NULL, NULL, &start, &end))
 387         return;
 388
 389     angle = (end-start)*pos + start;
 390     cpml_vector_from_angle(vector, angle);
 391     cpml_vector_normal(vector);
 392
 393     if (start > end) {
 394         vector->x = -vector->x;
 395         vector->y = -vector->y;
 396     }
 397 }
 398
 399 static void
 400 offset(CpmlPrimitive *arc, double offset)
 401 {
 402     CpmlPair p[3], center;
 403     double r;
 404
 405     cpml_pair_from_cairo(&p[0], arc->org);
 406     cpml_pair_from_cairo(&p[1], &arc->data[1]);
 407     cpml_pair_from_cairo(&p[2], &arc->data[2]);
 408
 409     if (!get_center(p, &center))
 410         return;
 411
 412     r = cpml_pair_distance(&p[0], &center) + offset;
 413
 414     /* Offset the three points by calculating their vector from the center,
 415      * setting the new radius as length and readding the center */
 416     p[0].x -= center.x;
 417     p[0].y -= center.y;
 418     p[1].x -= center.x;
 419     p[1].y -= center.y;
 420     p[2].x -= center.x;
 421     p[2].y -= center.y;
 422
 423     cpml_vector_set_length(&p[0], r);
 424     cpml_vector_set_length(&p[1], r);
 425     cpml_vector_set_length(&p[2], r);
 426
 427     p[0].x += center.x;
 428     p[0].y += center.y;
 429     p[1].x += center.x;
 430     p[1].y += center.y;
 431     p[2].x += center.x;
 432     p[2].y += center.y;
 433
 434     cpml_pair_to_cairo(&p[0], arc->org);
 435     cpml_pair_to_cairo(&p[1], &arc->data[1]);
 436     cpml_pair_to_cairo(&p[2], &arc->data[2]);
 437 }
 438
 439 static cairo_bool_t
 440 get_center(const CpmlPair *p, CpmlPair *dest)
 441 {
 442     CpmlPair b, c;
 443     double d, b2, c2;
 444
 445     /* When p[0] == p[2], p[0]..p[1] is considered the diameter of a circle */
 446     if (p[0].x == p[2].x && p[0].y == p[2].y) {
 447         dest->x = (p[0].x + p[1].x) / 2;
 448         dest->y = (p[0].y + p[1].y) / 2;
 449         return 1;
 450     }
 451
 452     /* Translate the 3 points of -p0, to simplify the formula */
 453     b.x = p[1].x - p[0].x;
 454     b.y = p[1].y - p[0].y;
 455     c.x = p[2].x - p[0].x;
 456     c.y = p[2].y - p[0].y;
 457
 458     /* Check for division by 0, that is the case where the 3 given points
 459      * are laying on a straight line and there is no fitting circle */
 460     d = (b.x*c.y - b.y*c.x) * 2;
 461     if (d == 0.)
 462         return 0;
 463
 464     b2 = b.x*b.x + b.y*b.y;
 465     c2 = c.x*c.x + c.y*c.y;
 466
 467     dest->x = (c.y*b2 - b.y*c2) / d + p[0].x;
 468     dest->y = (b.x*c2 - c.x*b2) / d + p[0].y;
 469
 470     return 1;
 471 }
 472
 473 static void
 474 get_angles(const CpmlPair *p, const CpmlPair *center,
 475            double *start, double *end)
 476 {
 477     CpmlVector vector;
 478     double mid;
 479
 480     /* Calculate the starting angle */
 481     vector.x = p[0].x - center->x;
 482     vector.y = p[0].y - center->y;
 483     *start = cpml_vector_angle(&vector);
 484
 485     if (p[0].x == p[2].x && p[0].y == p[2].y) {
 486         /* When p[0] and p[2] are cohincidents, p[0]..p[1] is the diameter
 487          * of a circle: return by convention start=start end=start+2PI */
 488         *end = *start + M_PI*2;
 489     } else {
 490         /* Calculate the mid and end angle: cpml_vector_angle()
 491          * returns an angle between -M_PI and M_PI */
 492         vector.x = p[1].x - center->x;
 493         vector.y = p[1].y - center->y;
 494         mid = cpml_vector_angle(&vector);
 495         vector.x = p[2].x - center->x;
 496         vector.y = p[2].y - center->y;
 497         *end = cpml_vector_angle(&vector);
 498
 499         if (*end > *start) {
 500             /* If the middle angle is outside the start..end range,
 501              * the arc should be reversed (that is, start must
 502              * be greather than end) */
 503             if (mid < *start || mid > *end)
 504                 *start += M_PI*2;
 505         } else {
 506             /* Here the arc is reversed: if the middle angle is
 507              * outside the end..start range, the arc should be
 508              * re-reversed to get a straight arc (that is, end
 509              * must be greather than start) */
 510             if (mid < *end || mid > *start)
 511                 *end += M_PI*2;
 512         }
 513     }
 514 }
 515
 516 static void
 517 arc_to_curve(CpmlPrimitive *curve, const CpmlPair *center,
 518              double r, double start, double end)
 519 {
 520     double r_sin1, r_cos1;
 521     double r_sin2, r_cos2;
 522     double h;
 523
 524     r_sin1 = r*sin(start);
 525     r_cos1 = r*cos(start);
 526     r_sin2 = r*sin(end);
 527     r_cos2 = r*cos(end);
 528
 529     h = 4./3. * tan((end-start) / 4.);
 530
 531     curve->data[0].header.type = CPML_CURVE;
 532     curve->data[0].header.length = 4;
 533     curve->data[1].point.x = center->x + r_cos1 - h*r_sin1;
 534     curve->data[1].point.y = center->y + r_sin1 + h*r_cos1;
 535     curve->data[2].point.x = center->x + r_cos2 + h*r_sin2;
 536     curve->data[2].point.y = center->y + r_sin2 - h*r_cos2;
 537     curve->data[3].point.x = center->x + r_cos2;
 538     curve->data[3].point.y = center->y + r_sin2;
 539 }