cpml/cpml-arc.c

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