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