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 directly feed #CpmlPath struct to
  51  * cairo (throught cairo_append_path() for example) or at least do not
  52  * 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_length:
 166  * @arc:  the #CpmlPrimitive arc data
 167  *
 168  * Given the @arc primitive, returns its length.
 169  *
 170  * Return value: the requested length or 0 on errors
 171  **/
 172 double
 173 cpml_arc_length(const CpmlPrimitive *arc)
 174 {
 175     double r, start, end, delta;
 176
 177     if (!cpml_arc_info(arc, NULL, &r, &start, &end) || start == end)
 178         return 0.;
 179
 180     delta = end - start;
 181     if (delta < 0)
 182         delta += M_PI*2;
 183
 184     return r*delta;
 185 }
 186
 187 /**
 188  * cpml_arc_pair_at:
 189  * @arc:  the #CpmlPrimitive arc data
 190  * @pair: the destination #CpmlPair
 191  * @pos:  the position value
 192  *
 193  * Given an @arc, finds the coordinates at position @pos (where 0 is
 194  * the start and 1 is the end) and stores the result in @pair.
 195  *
 196  * @pos can also be outside the 0..1 limit, as interpolating on an
 197  * arc is quite trivial.
 198  **/
 199 void
 200 cpml_arc_pair_at(const CpmlPrimitive *arc, CpmlPair *pair, double pos)
 201 {
 202     if (pos == 0.) {
 203         cpml_pair_from_cairo(pair, arc->org);
 204     } else if (pos == 1.) {
 205         cpml_pair_from_cairo(pair, &arc->data[2]);
 206     } else {
 207         CpmlPair center;
 208         double r, start, end, angle;
 209
 210         if (!cpml_arc_info(arc, &center, &r, &start, &end))
 211             return;
 212
 213         angle = (end-start)*pos + start;
 214         cpml_vector_from_angle(pair, angle, r);
 215         cpml_pair_add(pair, &center);
 216     }
 217 }
 218
 219 /**
 220  * cpml_arc_vector_at:
 221  * @arc:    the #CpmlPrimitive arc data
 222  * @vector: the destination vector
 223  * @pos:    the position value
 224  *
 225  * Given an @arc, finds the slope at position @pos (where 0 is
 226  * the start and 1 is the end) and stores the result in @vector.
 227  *
 228  * @pos can also be outside the 0..1 limit, as interpolating on an
 229  * arc is quite trivial.
 230  **/
 231 void
 232 cpml_arc_vector_at(const CpmlPrimitive *arc, CpmlVector *vector, double pos)
 233 {
 234     double start, end, angle;
 235
 236     if (!cpml_arc_info(arc, NULL, NULL, &start, &end))
 237         return;
 238
 239     angle = (end-start)*pos + start;
 240     cpml_vector_from_angle(vector, angle, 1.);
 241     cpml_vector_normal(vector);
 242 }
 243
 244 /**
 245  * cpml_arc_near_pos:
 246  * @arc: the #CpmlPrimitive arc data
 247  * @pair: the coordinates of the subject point
 248  *
 249  * Returns the pos value of the point on @arc nearest to @pair.
 250  * The returned value is always between 0 and 1.
 251  *
 252  * <important>
 253  * <title>TODO</title>
 254  * <itemizedlist>
 255  * <listitem>To be implemented...</listitem>
 256  * </itemizedlist>
 257  * </important>
 258  *
 259  * Return value: the pos value, always between 0 and 1
 260  **/
 261 double
 262 cpml_arc_near_pos(const CpmlPrimitive *arc, const CpmlPair *pair)
 263 {
 264     /* TODO */
 265
 266     return 0;
 267 }
 268
 269 /**
 270  * cpml_arc_intersection:
 271  * @arc:  the first arc
 272  * @arc2: the second arc
 273  * @dest: a vector of #CpmlPair
 274  * @max:  maximum number of intersections to return
 275  *        (that is, the size of @dest)
 276  *
 277  * Given two arcs (@arc and @arc2), gets their intersection points
 278  * and store the result in @dest. Keep in mind two arcs can have
 279  * up to 2 intersections.
 280  *
 281  * If @max is 0, the function returns 0 immediately without any
 282  * further processing. If @arc and @arc2 are cohincident (same
 283  * center and same radius), their intersections are not considered.
 284  *
 285  * <important>
 286  * <title>TODO</title>
 287  * <itemizedlist>
 288  * <listitem>To be implemented...</listitem>
 289  * </itemizedlist>
 290  * </important>
 291  *
 292  * Return value: the number of intersections found (max 2)
 293  *               or 0 if the primitives do not intersect
 294  **/
 295 int
 296 cpml_arc_intersection(const CpmlPrimitive *arc, const CpmlPrimitive *arc2,
 297                       CpmlPair *dest, int max)
 298 {
 299     return 0;
 300 }
 301
 302 /**
 303  * cpml_arc_intersection_with_line:
 304  * @arc:  an arc
 305  * @line: a line
 306  * @dest: a vector of #CpmlPair
 307  * @max:  maximum number of intersections to return
 308  *        (that is, the size of @dest)
 309  *
 310  * Given an @arc and a @line, gets their intersection points
 311  * and store the result in @dest. Keep in mind an arc and a
 312  * line can have up to 2 intersections.
 313  *
 314  * If @max is 0, the function returns 0 immediately without any
 315  * further processing.
 316  *
 317  * <important>
 318  * <title>TODO</title>
 319  * <itemizedlist>
 320  * <listitem>To be implemented...</listitem>
 321  * </itemizedlist>
 322  * </important>
 323  *
 324  * Return value: the number of intersections found (max 2)
 325  *               or 0 if the primitives do not intersect
 326  **/
 327 int
 328 cpml_arc_intersection_with_line(const CpmlPrimitive *arc,
 329                                 const CpmlPrimitive *line,
 330                                 CpmlPair *dest, int max)
 331 {
 332     return 0;
 333 }
 334
 335 /**
 336  * cpml_arc_offset:
 337  * @arc:    the #CpmlPrimitive arc data
 338  * @offset: distance for the computed parallel arc
 339  *
 340  * Given an @arc, this function computes the parallel arc at
 341  * distance @offset. The three points needed to build the
 342  * new arc are returned in the @arc data (substituting the
 343  * previous ones.
 344  **/
 345 void
 346 cpml_arc_offset(CpmlPrimitive *arc, double offset)
 347 {
 348     CpmlPair p[3], center;
 349     double r;
 350
 351     cpml_pair_from_cairo(&p[0], arc->org);
 352     cpml_pair_from_cairo(&p[1], &arc->data[1]);
 353     cpml_pair_from_cairo(&p[2], &arc->data[2]);
 354
 355     if (!get_center(p, &center))
 356         return;
 357
 358     r = cpml_pair_distance(&p[0], &center) + offset;
 359
 360     /* Offset the three points by calculating their vector from the center,
 361      * setting the new radius as length and readding the center */
 362     cpml_pair_sub(&p[0], &center);
 363     cpml_pair_sub(&p[1], &center);
 364     cpml_pair_sub(&p[2], &center);
 365
 366     cpml_vector_set_length(&p[0], r);
 367     cpml_vector_set_length(&p[1], r);
 368     cpml_vector_set_length(&p[2], r);
 369
 370     cpml_pair_add(&p[0], &center);
 371     cpml_pair_add(&p[1], &center);
 372     cpml_pair_add(&p[2], &center);
 373
 374     cpml_pair_to_cairo(&p[0], arc->org);
 375     cpml_pair_to_cairo(&p[1], &arc->data[1]);
 376     cpml_pair_to_cairo(&p[2], &arc->data[2]);
 377 }
 378
 379 /**
 380  * cpml_arc_to_cairo:
 381  * @arc: the #CpmlPrimitive arc data
 382  * @cr:  the destination cairo context
 383  *
 384  * Renders @arc to the @cr cairo context. As cairo does not support
 385  * arcs natively, it is approximated using one or more Bézier curves.
 386  *
 387  * The number of curves used is dependent from the angle of the arc.
 388  * Anyway, this function uses internally the hardcoded %M_PI_2 value
 389  * as threshold value. This means the maximum arc approximated by a
 390  * single curve will be a quarter of a circle and, consequently, a
 391  * whole circle will be approximated by 4 Bézier curves.
 392  **/
 393 void
 394 cpml_arc_to_cairo(const CpmlPrimitive *arc, cairo_t *cr)
 395 {
 396     CpmlPair center;
 397     double r, start, end;
 398     int n_curves;
 399     double step, angle;
 400     CpmlPrimitive curve;
 401     cairo_path_data_t data[4];
 402
 403     if (!cpml_arc_info(arc, &center, &r, &start, &end))
 404         return;
 405
 406     n_curves = ceil(fabs(end-start) / ARC_MAX_ANGLE);
 407     step = (end-start) / (double) n_curves;
 408     curve.data = data;
 409
 410     for (angle = start; n_curves--; angle += step) {
 411         arc_to_curve(&curve, &center, r, angle, angle+step);
 412         cairo_curve_to(cr,
 413                        curve.data[1].point.x, curve.data[1].point.y,
 414                        curve.data[2].point.x, curve.data[2].point.y,
 415                        curve.data[3].point.x, curve.data[3].point.y);
 416     }
 417 }
 418
 419 /**
 420  * cpml_arc_to_curves:
 421  * @arc:      the #CpmlPrimitive arc data
 422  * @segment:  the destination #CpmlSegment
 423  * @n_curves: number of Bézier to use
 424  *
 425  * Converts @arc to a serie of @n_curves Bézier curves and puts them
 426  * inside @segment. Obviously, @segment must have enough space to
 427  * contain at least @n_curves curves.
 428  *
 429  * This function works in a similar way as cpml_arc_to_cairo() but
 430  * has two important differences: it does not need a cairo context
 431  * and the number of curves to be generated is explicitely defined.
 432  * The latter difference allows a more specific error control from
 433  * the application: in the file src/cairo-arc.c, found in the cairo
 434  * tarball (at least in cairo-1.9.1), there is a table showing the
 435  * magnitude of error of this curve approximation algorithm.
 436  **/
 437 void
 438 cpml_arc_to_curves(const CpmlPrimitive *arc, CpmlSegment *segment,
 439                    int n_curves)
 440 {
 441     CpmlPair center;
 442     double r, start, end;
 443     double step, angle;
 444     CpmlPrimitive curve;
 445
 446     if (!cpml_arc_info(arc, &center, &r, &start, &end))
 447         return;
 448
 449     step = (end-start) / (double) n_curves;
 450     segment->num_data = n_curves*4;
 451     curve.segment = segment;
 452     curve.data = segment->data;
 453
 454     for (angle = start; n_curves--; angle += step) {
 455         arc_to_curve(&curve, &center, r, angle, angle+step);
 456         curve.data += 4;
 457     }
 458 }
 459
 460
 461 static cairo_bool_t
 462 get_center(const CpmlPair *p, CpmlPair *dest)
 463 {
 464     CpmlPair b, c;
 465     double d, b2, c2;
 466
 467     /* When p[0] == p[2], p[0]..p[1] is considered the diameter of a circle */
 468     if (p[0].x == p[2].x && p[0].y == p[2].y) {
 469         dest->x = (p[0].x + p[1].x) / 2;
 470         dest->y = (p[0].y + p[1].y) / 2;
 471         return 1;
 472     }
 473
 474     /* Translate the 3 points of -p0, to simplify the formula */
 475     cpml_pair_sub(cpml_pair_copy(&b, &p[1]), &p[0]);
 476     cpml_pair_sub(cpml_pair_copy(&c, &p[2]), &p[0]);
 477
 478     /* Check for division by 0, that is the case where the 3 given points
 479      * are laying on a straight line and there is no fitting circle */
 480     d = (b.x*c.y - b.y*c.x) * 2;
 481     if (d == 0.)
 482         return 0;
 483
 484     b2 = b.x*b.x + b.y*b.y;
 485     c2 = c.x*c.x + c.y*c.y;
 486
 487     dest->x = (c.y*b2 - b.y*c2) / d + p[0].x;
 488     dest->y = (b.x*c2 - c.x*b2) / d + p[0].y;
 489
 490     return 1;
 491 }
 492
 493 static void
 494 get_angles(const CpmlPair *p, const CpmlPair *center,
 495            double *start, double *end)
 496 {
 497     CpmlVector vector;
 498     double mid;
 499
 500     /* Calculate the starting angle */
 501     cpml_pair_sub(cpml_pair_copy(&vector, &p[0]), center);
 502     *start = cpml_vector_angle(&vector);
 503
 504     if (p[0].x == p[2].x && p[0].y == p[2].y) {
 505         /* When p[0] and p[2] are cohincidents, p[0]..p[1] is the diameter
 506          * of a circle: return by convention start=start end=start+2PI */
 507         *end = *start + M_PI*2;
 508     } else {
 509         /* Calculate the mid and end angle */
 510         cpml_pair_sub(cpml_pair_copy(&vector, &p[1]), center);
 511         mid = cpml_vector_angle(&vector);
 512         cpml_pair_sub(cpml_pair_copy(&vector, &p[2]), center);
 513         *end = cpml_vector_angle(&vector);
 514
 515         if (*end > *start) {
 516             if (mid > *end || mid < *start)
 517                 *start += M_PI*2;
 518         } else {
 519             if (mid < *end || mid > *start)
 520                 *end += M_PI*2;
 521         }
 522     }
 523 }
 524
 525 static void
 526 arc_to_curve(CpmlPrimitive *curve, const CpmlPair *center,
 527              double r, double start, double end)
 528 {
 529     double r_sin1, r_cos1;
 530     double r_sin2, r_cos2;
 531     double h;
 532
 533     r_sin1 = r*sin(start);
 534     r_cos1 = r*cos(start);
 535     r_sin2 = r*sin(end);
 536     r_cos2 = r*cos(end);
 537
 538     h = 4./3. * tan((end-start) / 4.);
 539
 540     curve->data[0].header.type = CAIRO_PATH_CURVE_TO;
 541     curve->data[0].header.length = 4;
 542     curve->data[1].point.x = center->x + r_cos1 - h*r_sin1;
 543     curve->data[1].point.y = center->y + r_sin1 + h*r_cos1;
 544     curve->data[2].point.x = center->x + r_cos2 + h*r_sin2;
 545     curve->data[2].point.y = center->y + r_sin2 - h*r_cos2;
 546     curve->data[3].point.x = center->x + r_cos2;
 547     curve->data[3].point.y = center->y + r_sin2;
 548 }