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 /**
  22  * SECTION:cpml-arc
  23  * @Section_Id:CpmlArc
  24  * @title: CpmlArc
  25  * @short_description: Manipulation of circular arcs
  26  *
  27  * The following functions manipulate #CAIRO_PATH_ARC_TO #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 #CAIRO_PATH_ARC_TO 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
  64
  65 #include "cpml-arc.h"
  66 #include "cpml-pair.h"
  67
  68 #include <stdlib.h>
  69 #include <math.h>
  70
  71
  72 /* Hardcoded max angle of the arc to be approximated by a Bézier curve:
  73  * this influence the arc quality (the default value is got from cairo) */
  74 #define ARC_MAX_ANGLE   M_PI_2
  75
  76
  77 static cairo_bool_t     get_center      (const CpmlPair *p,
  78                                          CpmlPair       *dest);
  79 static void             get_angles      (const CpmlPair *p,
  80                                          const CpmlPair *center,
  81                                          double         *start,
  82                                          double         *end);
  83 static void             arc_to_curve    (CpmlPrimitive  *curve,
  84                                          const CpmlPair *center,
  85                                          double          r,
  86                                          double          start,
  87                                          double          end);
  88
  89
  90 /**
  91  * cpml_arc_type_get_npoints:
  92  *
  93  * Returns the number of point needed to properly specify an arc primitive.
  94  *
  95  * Returns: 3
  96  **/
  97 int
  98 cpml_arc_type_get_npoints(void)
  99 {
 100     return 3;
 101 }
 102
 103 /**
 104  * cpml_arc_info:
 105  * @arc:    the #CpmlPrimitive arc data
 106  * @center: where to store the center coordinates (can be %NULL)
 107  * @r:      where to store the radius (can be %NULL)
 108  * @start:  where to store the starting angle (can be %NULL)
 109  * @end:    where to store the ending angle (can be %NULL)
 110  *
 111  * Given an @arc, this function calculates and returns its basic data.
 112  * Any pointer can be %NULL, in which case the requested info is not
 113  * returned. This function can fail (when the three points lay on a
 114  * straight line, for example) in which case 0 is returned and no
 115  * data can be considered valid.
 116  *
 117  * The radius @r can be 0 when the three points are coincidents: a
 118  * circle with radius 0 is considered a valid path.
 119  *
 120  * When the start and end angle are returned, together with their
 121  * values these angles implicitely gives another important information:
 122  * the arc direction.
 123  *
 124  * If @start < @end the arc must be rendered with increasing angle
 125  * value (clockwise direction using the ordinary cairo coordinate
 126  * system) while if @start > @end the arc must be rendered in reverse
 127  * order (that is counterclockwise in the cairo world). This is the
 128  * reason the angle values are returned in the range
 129  * { -M_PI < value < 3*M_PI } inclusive instead of the usual
 130  * { -M_PI < value < M_PI } range.
 131  *
 132  * Returns: 1 if the function worked succesfully, 0 on errors
 133  **/
 134 cairo_bool_t
 135 cpml_arc_info(const CpmlPrimitive *arc, CpmlPair *center,
 136               double *r, double *start, double *end)
 137 {
 138     CpmlPair p[3], l_center;
 139
 140     cpml_pair_from_cairo(&p[0], arc->org);
 141     cpml_pair_from_cairo(&p[1], &arc->data[1]);
 142     cpml_pair_from_cairo(&p[2], &arc->data[2]);
 143
 144     if (!get_center(p, &l_center))
 145         return 0;
 146
 147     if (center)
 148         *center = l_center;
 149
 150     if (r != NULL)
 151         *r = cpml_pair_distance(&p[0], &l_center);
 152
 153     if (start != NULL || end != NULL) {
 154         double l_start, l_end;
 155
 156         get_angles(p, &l_center, &l_start, &l_end);
 157
 158         if (start != NULL)
 159             *start = l_start;
 160         if (end != NULL)
 161             *end = l_end;
 162     }
 163
 164     return 1;
 165 }
 166
 167 /**
 168  * cpml_arc_get_length:
 169  * @arc:  the #CpmlPrimitive arc data
 170  *
 171  * Given the @arc primitive, returns its length.
 172  *
 173  * Returns: the requested length or 0 on errors
 174  **/
 175 double
 176 cpml_arc_get_length(const CpmlPrimitive *arc)
 177 {
 178     double r, start, end, delta;
 179
 180     if (!cpml_arc_info(arc, NULL, &r, &start, &end) || start == end)
 181         return 0.;
 182
 183     delta = end - start;
 184     if (delta < 0)
 185         delta += M_PI*2;
 186
 187     return r*delta;
 188 }
 189
 190 /* Hardcoded macro to save a lot of typing and make the
 191  * cpml_arc_extents() code clearer */
 192 #define ANGLE_INCLUDED(d) \
 193     ((start < (d) && end > (d)) || (start > (d) && end < (d)))
 194
 195 /**
 196  * cpml_arc_extents:
 197  * @arc: the #CpmlPrimitive arc data
 198  * @extents: where to store the extents
 199  *
 200  * Given an @arc primitive, returns its boundary box in @extents.
 201  **/
 202 void
 203 cpml_arc_extents(const CpmlPrimitive *arc, CpmlExtents *extents)
 204 {
 205     double r, start, end;
 206     CpmlPair center, pair;
 207
 208     extents->is_defined = 0;
 209
 210     if (!cpml_arc_info(arc, &center, &r, &start, &end))
 211         return;
 212
 213     /* Add the right quadrant point if needed */
 214     if (ANGLE_INCLUDED(0) || ANGLE_INCLUDED(M_PI * 2)) {
 215         pair.x = center.x + r;
 216         pair.y = center.y;
 217         cpml_extents_pair_add(extents, &pair);
 218     }
 219
 220     /* Add the bottom quadrant point if needed */
 221     if (ANGLE_INCLUDED(M_PI_2) || ANGLE_INCLUDED(M_PI_2 * 5)) {
 222         pair.x = center.x;
 223         pair.y = center.y + r;
 224         cpml_extents_pair_add(extents, &pair);
 225     }
 226
 227     /* Add the left quadrant point if needed */
 228     if (ANGLE_INCLUDED(M_PI)) {
 229         pair.x = center.x - r;
 230         pair.y = center.y;
 231         cpml_extents_pair_add(extents, &pair);
 232     }
 233
 234     /* Add the top quadrant point if needed */
 235     if (ANGLE_INCLUDED(M_PI_2 * 3) || ANGLE_INCLUDED(-M_PI_2)) {
 236         pair.x = center.x;
 237         pair.y = center.y - r;
 238         cpml_extents_pair_add(extents, &pair);
 239     }
 240
 241     /* Add the start point */
 242     cpml_pair_from_cairo(&pair, cpml_primitive_get_point(arc, 0));
 243     cpml_extents_pair_add(extents, &pair);
 244
 245     /* Add the end point */
 246     cpml_pair_from_cairo(&pair, cpml_primitive_get_point(arc, -1));
 247     cpml_extents_pair_add(extents, &pair);
 248 }
 249
 250 /**
 251  * cpml_arc_pair_at:
 252  * @arc:  the #CpmlPrimitive arc data
 253  * @pair: the destination #CpmlPair
 254  * @pos:  the position value
 255  *
 256  * Given an @arc, finds the coordinates at position @pos (where 0 is
 257  * the start and 1 is the end) and stores the result in @pair.
 258  *
 259  * @pos can also be outside the 0..1 limit, as interpolating on an
 260  * arc is quite trivial.
 261  **/
 262 void
 263 cpml_arc_pair_at(const CpmlPrimitive *arc, CpmlPair *pair, double pos)
 264 {
 265     if (pos == 0.) {
 266         cpml_pair_from_cairo(pair, arc->org);
 267     } else if (pos == 1.) {
 268         cpml_pair_from_cairo(pair, &arc->data[2]);
 269     } else {
 270         CpmlPair center;
 271         double r, start, end, angle;
 272
 273         if (!cpml_arc_info(arc, &center, &r, &start, &end))
 274             return;
 275
 276         angle = (end-start)*pos + start;
 277         cpml_vector_from_angle(pair, angle);
 278         cpml_vector_set_length(pair, r);
 279         cpml_pair_add(pair, &center);
 280     }
 281 }
 282
 283 /**
 284  * cpml_arc_vector_at:
 285  * @arc:    the #CpmlPrimitive arc data
 286  * @vector: the destination vector
 287  * @pos:    the position value
 288  *
 289  * Given an @arc, finds the slope at position @pos (where 0 is
 290  * the start and 1 is the end) and stores the result in @vector.
 291  *
 292  * @pos can also be outside the 0..1 limit, as interpolating on an
 293  * arc is quite trivial.
 294  **/
 295 void
 296 cpml_arc_vector_at(const CpmlPrimitive *arc, CpmlVector *vector, double pos)
 297 {
 298     double start, end, angle;
 299
 300     if (!cpml_arc_info(arc, NULL, NULL, &start, &end))
 301         return;
 302
 303     angle = (end-start)*pos + start;
 304     cpml_vector_from_angle(vector, angle);
 305     cpml_vector_normal(vector);
 306
 307     if (start > end)
 308         cpml_pair_negate(vector);
 309 }
 310
 311 /**
 312  * cpml_arc_near_pos:
 313  * @arc: the #CpmlPrimitive arc data
 314  * @pair: the coordinates of the subject point
 315  *
 316  * Returns the pos value of the point on @arc nearest to @pair.
 317  * The returned value is always between 0 and 1.
 318  *
 319  * <important>
 320  * <title>TODO</title>
 321  * <itemizedlist>
 322  * <listitem>To be implemented...</listitem>
 323  * </itemizedlist>
 324  * </important>
 325  *
 326  * Returns: the pos value, always between 0 and 1
 327  **/
 328 double
 329 cpml_arc_near_pos(const CpmlPrimitive *arc, const CpmlPair *pair)
 330 {
 331     /* TODO */
 332
 333     return 0;
 334 }
 335
 336 /**
 337  * cpml_arc_intersection:
 338  * @arc:  the first arc
 339  * @arc2: the second arc
 340  * @dest: a vector of #CpmlPair
 341  * @max:  maximum number of intersections to return
 342  *        (that is, the size of @dest)
 343  *
 344  * Given two arcs (@arc and @arc2), gets their intersection points
 345  * and store the result in @dest. Keep in mind two arcs can have
 346  * up to 2 intersections.
 347  *
 348  * If @max is 0, the function returns 0 immediately without any
 349  * further processing. If @arc and @arc2 are cohincident (same
 350  * center and same radius), their intersections are not considered.
 351  *
 352  * <important>
 353  * <title>TODO</title>
 354  * <itemizedlist>
 355  * <listitem>To be implemented...</listitem>
 356  * </itemizedlist>
 357  * </important>
 358  *
 359  * Returns: the number of intersections found (max 2)
 360  *          or 0 if the primitives do not intersect
 361  **/
 362 int
 363 cpml_arc_intersection(const CpmlPrimitive *arc, const CpmlPrimitive *arc2,
 364                       CpmlPair *dest, int max)
 365 {
 366     return 0;
 367 }
 368
 369 /**
 370  * cpml_arc_intersection_with_line:
 371  * @arc:  an arc
 372  * @line: a line
 373  * @dest: a vector of #CpmlPair
 374  * @max:  maximum number of intersections to return
 375  *        (that is, the size of @dest)
 376  *
 377  * Given an @arc and a @line, gets their intersection points
 378  * and store the result in @dest. Keep in mind an arc and a
 379  * line can have up to 2 intersections.
 380  *
 381  * If @max is 0, the function returns 0 immediately without any
 382  * further processing.
 383  *
 384  * <important>
 385  * <title>TODO</title>
 386  * <itemizedlist>
 387  * <listitem>To be implemented...</listitem>
 388  * </itemizedlist>
 389  * </important>
 390  *
 391  * Returns: the number of intersections found (max 2)
 392  *          or 0 if the primitives do not intersect
 393  **/
 394 int
 395 cpml_arc_intersection_with_line(const CpmlPrimitive *arc,
 396                                 const CpmlPrimitive *line,
 397                                 CpmlPair *dest, int max)
 398 {
 399     return 0;
 400 }
 401
 402 /**
 403  * cpml_arc_offset:
 404  * @arc:    the #CpmlPrimitive arc data
 405  * @offset: distance for the computed parallel arc
 406  *
 407  * Given an @arc, this function computes the parallel arc at
 408  * distance @offset. The three points needed to build the
 409  * new arc are returned in the @arc data (substituting the
 410  * previous ones.
 411  **/
 412 void
 413 cpml_arc_offset(CpmlPrimitive *arc, double offset)
 414 {
 415     CpmlPair p[3], center;
 416     double r;
 417
 418     cpml_pair_from_cairo(&p[0], arc->org);
 419     cpml_pair_from_cairo(&p[1], &arc->data[1]);
 420     cpml_pair_from_cairo(&p[2], &arc->data[2]);
 421
 422     if (!get_center(p, &center))
 423         return;
 424
 425     r = cpml_pair_distance(&p[0], &center) + offset;
 426
 427     /* Offset the three points by calculating their vector from the center,
 428      * setting the new radius as length and readding the center */
 429     cpml_pair_sub(&p[0], &center);
 430     cpml_pair_sub(&p[1], &center);
 431     cpml_pair_sub(&p[2], &center);
 432
 433     cpml_vector_set_length(&p[0], r);
 434     cpml_vector_set_length(&p[1], r);
 435     cpml_vector_set_length(&p[2], r);
 436
 437     cpml_pair_add(&p[0], &center);
 438     cpml_pair_add(&p[1], &center);
 439     cpml_pair_add(&p[2], &center);
 440
 441     cpml_pair_to_cairo(&p[0], arc->org);
 442     cpml_pair_to_cairo(&p[1], &arc->data[1]);
 443     cpml_pair_to_cairo(&p[2], &arc->data[2]);
 444 }
 445
 446 /**
 447  * cpml_arc_to_cairo:
 448  * @arc: the #CpmlPrimitive arc data
 449  * @cr:  the destination cairo context
 450  *
 451  * Renders @arc to the @cr cairo context. As cairo does not support
 452  * arcs natively, it is approximated using one or more Bézier curves.
 453  *
 454  * The number of curves used is dependent from the angle of the arc.
 455  * Anyway, this function uses internally the hardcoded %M_PI_2 value
 456  * as threshold value. This means the maximum arc approximated by a
 457  * single curve will be a quarter of a circle and, consequently, a
 458  * whole circle will be approximated by 4 Bézier curves.
 459  **/
 460 void
 461 cpml_arc_to_cairo(const CpmlPrimitive *arc, cairo_t *cr)
 462 {
 463     CpmlPair center;
 464     double r, start, end;
 465     int n_curves;
 466     double step, angle;
 467     CpmlPrimitive curve;
 468     cairo_path_data_t data[4];
 469
 470     if (!cpml_arc_info(arc, &center, &r, &start, &end))
 471         return;
 472
 473     n_curves = ceil(fabs(end-start) / ARC_MAX_ANGLE);
 474     step = (end-start) / (double) n_curves;
 475     curve.data = data;
 476
 477     for (angle = start; n_curves--; angle += step) {
 478         arc_to_curve(&curve, &center, r, angle, angle+step);
 479         cairo_curve_to(cr,
 480                        curve.data[1].point.x, curve.data[1].point.y,
 481                        curve.data[2].point.x, curve.data[2].point.y,
 482                        curve.data[3].point.x, curve.data[3].point.y);
 483     }
 484 }
 485
 486 /**
 487  * cpml_arc_to_curves:
 488  * @arc:      the #CpmlPrimitive arc data
 489  * @segment:  the destination #CpmlSegment
 490  * @n_curves: number of Bézier to use
 491  *
 492  * Converts @arc to a serie of @n_curves Bézier curves and puts them
 493  * inside @segment. Obviously, @segment must have enough space to
 494  * contain at least @n_curves curves.
 495  *
 496  * This function works in a similar way as cpml_arc_to_cairo() but
 497  * has two important differences: it does not need a cairo context
 498  * and the number of curves to be generated is explicitely defined.
 499  * The latter difference allows a more specific error control from
 500  * the application: in the file src/cairo-arc.c, found in the cairo
 501  * tarball (at least in cairo-1.9.1), there is a table showing the
 502  * magnitude of error of this curve approximation algorithm.
 503  **/
 504 void
 505 cpml_arc_to_curves(const CpmlPrimitive *arc, CpmlSegment *segment,
 506                    int n_curves)
 507 {
 508     CpmlPair center;
 509     double r, start, end;
 510     double step, angle;
 511     CpmlPrimitive curve;
 512
 513     if (!cpml_arc_info(arc, &center, &r, &start, &end))
 514         return;
 515
 516     step = (end-start) / (double) n_curves;
 517     segment->num_data = n_curves*4;
 518     curve.segment = segment;
 519     curve.data = segment->data;
 520
 521     for (angle = start; n_curves--; angle += step) {
 522         arc_to_curve(&curve, &center, r, angle, angle+step);
 523         curve.data += 4;
 524     }
 525 }
 526
 527
 528 static cairo_bool_t
 529 get_center(const CpmlPair *p, CpmlPair *dest)
 530 {
 531     CpmlPair b, c;
 532     double d, b2, c2;
 533
 534     /* When p[0] == p[2], p[0]..p[1] is considered the diameter of a circle */
 535     if (p[0].x == p[2].x && p[0].y == p[2].y) {
 536         dest->x = (p[0].x + p[1].x) / 2;
 537         dest->y = (p[0].y + p[1].y) / 2;
 538         return 1;
 539     }
 540
 541     /* Translate the 3 points of -p0, to simplify the formula */
 542     cpml_pair_copy(&b, &p[1]);
 543     cpml_pair_sub(&b, &p[0]);
 544     cpml_pair_copy(&c, &p[2]);
 545     cpml_pair_sub(&c, &p[0]);
 546
 547     /* Check for division by 0, that is the case where the 3 given points
 548      * are laying on a straight line and there is no fitting circle */
 549     d = (b.x*c.y - b.y*c.x) * 2;
 550     if (d == 0.)
 551         return 0;
 552
 553     b2 = b.x*b.x + b.y*b.y;
 554     c2 = c.x*c.x + c.y*c.y;
 555
 556     dest->x = (c.y*b2 - b.y*c2) / d + p[0].x;
 557     dest->y = (b.x*c2 - c.x*b2) / d + p[0].y;
 558
 559     return 1;
 560 }
 561
 562 static void
 563 get_angles(const CpmlPair *p, const CpmlPair *center,
 564            double *start, double *end)
 565 {
 566     CpmlVector vector;
 567     double mid;
 568
 569     /* Calculate the starting angle */
 570     cpml_pair_copy(&vector, &p[0]);
 571     cpml_pair_sub(&vector, center);
 572     *start = cpml_vector_angle(&vector);
 573
 574     if (p[0].x == p[2].x && p[0].y == p[2].y) {
 575         /* When p[0] and p[2] are cohincidents, p[0]..p[1] is the diameter
 576          * of a circle: return by convention start=start end=start+2PI */
 577         *end = *start + M_PI*2;
 578     } else {
 579         /* Calculate the mid and end angle: cpml_vector_angle()
 580          * returns an angle between -M_PI and M_PI */
 581         cpml_pair_copy(&vector, &p[1]);
 582         cpml_pair_sub(&vector, center);
 583         mid = cpml_vector_angle(&vector);
 584         cpml_pair_copy(&vector, &p[2]);
 585         cpml_pair_sub(&vector, center);
 586         *end = cpml_vector_angle(&vector);
 587
 588         if (*end > *start) {
 589             /* If the middle angle is outside the start..end range,
 590              * the arc should be reversed (that is, start must
 591              * be greather than end) */
 592             if (mid < *start || mid > *end)
 593                 *start += M_PI*2;
 594         } else {
 595             /* Here the arc is reversed: if the middle angle is
 596              * outside the end..start range, the arc should be
 597              * re-reversed to get a straight arc (that is, end
 598              * must be greather than start) */
 599             if (mid < *end || mid > *start)
 600                 *end += M_PI*2;
 601         }
 602     }
 603 }
 604
 605 static void
 606 arc_to_curve(CpmlPrimitive *curve, const CpmlPair *center,
 607              double r, double start, double end)
 608 {
 609     double r_sin1, r_cos1;
 610     double r_sin2, r_cos2;
 611     double h;
 612
 613     r_sin1 = r*sin(start);
 614     r_cos1 = r*cos(start);
 615     r_sin2 = r*sin(end);
 616     r_cos2 = r*cos(end);
 617
 618     h = 4./3. * tan((end-start) / 4.);
 619
 620     curve->data[0].header.type = CAIRO_PATH_CURVE_TO;
 621     curve->data[0].header.length = 4;
 622     curve->data[1].point.x = center->x + r_cos1 - h*r_sin1;
 623     curve->data[1].point.y = center->y + r_sin1 + h*r_cos1;
 624     curve->data[2].point.x = center->x + r_cos2 + h*r_sin2;
 625     curve->data[2].point.y = center->y + r_sin2 - h*r_cos2;
 626     curve->data[3].point.x = center->x + r_cos2;
 627     curve->data[3].point.y = center->y + r_sin2;
 628 }