src/cairo-arc.c

   1 /* cairo - a vector graphics library with display and print output
   2  *
   3  * Copyright © 2002 University of Southern California
   4  *
   5  * This library is free software; you can redistribute it and/or
   6  * modify it either under the terms of the GNU Lesser General Public
   7  * License version 2.1 as published by the Free Software Foundation
   8  * (the "LGPL") or, at your option, under the terms of the Mozilla
   9  * Public License Version 1.1 (the "MPL"). If you do not alter this
  10  * notice, a recipient may use your version of this file under either
  11  * the MPL or the LGPL.
  12  *
  13  * You should have received a copy of the LGPL along with this library
  14  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
  15  * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
  16  * You should have received a copy of the MPL along with this library
  17  * in the file COPYING-MPL-1.1
  18  *
  19  * The contents of this file are subject to the Mozilla Public License
  20  * Version 1.1 (the "License"); you may not use this file except in
  21  * compliance with the License. You may obtain a copy of the License at
  22  * http://www.mozilla.org/MPL/
  23  *
  24  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
  25  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
  26  * the specific language governing rights and limitations.
  27  *
  28  * The Original Code is the cairo graphics library.
  29  *
  30  * The Initial Developer of the Original Code is University of Southern
  31  * California.
  32  *
  33  * Contributor(s):
  34  *      Carl D. Worth <cworth@cworth.org>
  35  */
  36
  37 #include "cairoint.h"
  38
  39 #include "cairo-arc-private.h"
  40
  41 #define MAX_FULL_CIRCLES 65536
  42
  43 /* Spline deviation from the circle in radius would be given by:
  44
  45         error = sqrt (x**2 + y**2) - 1
  46
  47    A simpler error function to work with is:
  48
  49         e = x**2 + y**2 - 1
  50
  51    From "Good approximation of circles by curvature-continuous Bezier
  52    curves", Tor Dokken and Morten Daehlen, Computer Aided Geometric
  53    Design 8 (1990) 22-41, we learn:
  54
  55         abs (max(e)) = 4/27 * sin**6(angle/4) / cos**2(angle/4)
  56
  57    and
  58         abs (error) =~ 1/2 * e
  59
  60    Of course, this error value applies only for the particular spline
  61    approximation that is used in _cairo_gstate_arc_segment.
  62 */
  63 static double
  64 _arc_error_normalized (double angle)
  65 {
  66     return 2.0/27.0 * pow (sin (angle / 4), 6) / pow (cos (angle / 4), 2);
  67 }
  68
  69 static double
  70 _arc_max_angle_for_tolerance_normalized (double tolerance)
  71 {
  72     double angle, error;
  73     int i;
  74
  75     /* Use table lookup to reduce search time in most cases. */
  76     struct {
  77         double angle;
  78         double error;
  79     } table[] = {
  80         { M_PI / 1.0,   0.0185185185185185036127 },
  81         { M_PI / 2.0,   0.000272567143730179811158 },
  82         { M_PI / 3.0,   2.38647043651461047433e-05 },
  83         { M_PI / 4.0,   4.2455377443222443279e-06 },
  84         { M_PI / 5.0,   1.11281001494389081528e-06 },
  85         { M_PI / 6.0,   3.72662000942734705475e-07 },
  86         { M_PI / 7.0,   1.47783685574284411325e-07 },
  87         { M_PI / 8.0,   6.63240432022601149057e-08 },
  88         { M_PI / 9.0,   3.2715520137536980553e-08 },
  89         { M_PI / 10.0,  1.73863223499021216974e-08 },
  90         { M_PI / 11.0,  9.81410988043554039085e-09 },
  91     };
  92     int table_size = ARRAY_LENGTH (table);
  93
  94     for (i = 0; i < table_size; i++)
  95         if (table[i].error < tolerance)
  96             return table[i].angle;
  97
  98     ++i;
  99     do {
 100         angle = M_PI / i++;
 101         error = _arc_error_normalized (angle);
 102     } while (error > tolerance);
 103
 104     return angle;
 105 }
 106
 107 static int
 108 _arc_segments_needed (double          angle,
 109                       double          radius,
 110                       cairo_matrix_t *ctm,
 111                       double          tolerance)
 112 {
 113     double major_axis, max_angle;
 114
 115     /* the error is amplified by at most the length of the
 116      * major axis of the circle; see cairo-pen.c for a more detailed analysis
 117      * of this. */
 118     major_axis = _cairo_matrix_transformed_circle_major_axis (ctm, radius);
 119     max_angle = _arc_max_angle_for_tolerance_normalized (tolerance / major_axis);
 120
 121     return ceil (fabs (angle) / max_angle);
 122 }
 123
 124 /* We want to draw a single spline approximating a circular arc radius
 125    R from angle A to angle B. Since we want a symmetric spline that
 126    matches the endpoints of the arc in position and slope, we know
 127    that the spline control points must be:
 128
 129         (R * cos(A), R * sin(A))
 130         (R * cos(A) - h * sin(A), R * sin(A) + h * cos (A))
 131         (R * cos(B) + h * sin(B), R * sin(B) - h * cos (B))
 132         (R * cos(B), R * sin(B))
 133
 134    for some value of h.
 135
 136    "Approximation of circular arcs by cubic polynomials", Michael
 137    Goldapp, Computer Aided Geometric Design 8 (1991) 227-238, provides
 138    various values of h along with error analysis for each.
 139
 140    From that paper, a very practical value of h is:
 141
 142         h = 4/3 * R * tan(angle/4)
 143
 144    This value does not give the spline with minimal error, but it does
 145    provide a very good approximation, (6th-order convergence), and the
 146    error expression is quite simple, (see the comment for
 147    _arc_error_normalized).
 148 */
 149 static void
 150 _cairo_arc_segment (cairo_t *cr,
 151                     double   xc,
 152                     double   yc,
 153                     double   radius,
 154                     double   angle_A,
 155                     double   angle_B)
 156 {
 157     double r_sin_A, r_cos_A;
 158     double r_sin_B, r_cos_B;
 159     double h;
 160
 161     r_sin_A = radius * sin (angle_A);
 162     r_cos_A = radius * cos (angle_A);
 163     r_sin_B = radius * sin (angle_B);
 164     r_cos_B = radius * cos (angle_B);
 165
 166     h = 4.0/3.0 * tan ((angle_B - angle_A) / 4.0);
 167
 168     cairo_curve_to (cr,
 169                     xc + r_cos_A - h * r_sin_A,
 170                     yc + r_sin_A + h * r_cos_A,
 171                     xc + r_cos_B + h * r_sin_B,
 172                     yc + r_sin_B - h * r_cos_B,
 173                     xc + r_cos_B,
 174                     yc + r_sin_B);
 175 }
 176
 177 static void
 178 _cairo_arc_in_direction (cairo_t          *cr,
 179                          double            xc,
 180                          double            yc,
 181                          double            radius,
 182                          double            angle_min,
 183                          double            angle_max,
 184                          cairo_direction_t dir)
 185 {
 186     if (cairo_status (cr))
 187         return;
 188
 189     assert (angle_max >= angle_min);
 190
 191     if (angle_max - angle_min > 2 * M_PI * MAX_FULL_CIRCLES) {
 192         angle_max = fmod (angle_max - angle_min, 2 * M_PI);
 193         angle_min = fmod (angle_min, 2 * M_PI);
 194         angle_max += angle_min + 2 * M_PI * MAX_FULL_CIRCLES;
 195     }
 196
 197     /* Recurse if drawing arc larger than pi */
 198     if (angle_max - angle_min > M_PI) {
 199         double angle_mid = angle_min + (angle_max - angle_min) / 2.0;
 200         if (dir == CAIRO_DIRECTION_FORWARD) {
 201             _cairo_arc_in_direction (cr, xc, yc, radius,
 202                                      angle_min, angle_mid,
 203                                      dir);
 204
 205             _cairo_arc_in_direction (cr, xc, yc, radius,
 206                                      angle_mid, angle_max,
 207                                      dir);
 208         } else {
 209             _cairo_arc_in_direction (cr, xc, yc, radius,
 210                                      angle_mid, angle_max,
 211                                      dir);
 212
 213             _cairo_arc_in_direction (cr, xc, yc, radius,
 214                                      angle_min, angle_mid,
 215                                      dir);
 216         }
 217     } else if (angle_max != angle_min) {
 218         cairo_matrix_t ctm;
 219         int i, segments;
 220         double step;
 221
 222         cairo_get_matrix (cr, &ctm);
 223         segments = _arc_segments_needed (angle_max - angle_min,
 224                                          radius, &ctm,
 225                                          cairo_get_tolerance (cr));
 226         step = (angle_max - angle_min) / segments;
 227         segments -= 1;
 228
 229         if (dir == CAIRO_DIRECTION_REVERSE) {
 230             double t;
 231
 232             t = angle_min;
 233             angle_min = angle_max;
 234             angle_max = t;
 235
 236             step = -step;
 237         }
 238
 239         cairo_line_to (cr,
 240                        xc + radius * cos (angle_min),
 241                        yc + radius * sin (angle_min));
 242
 243         for (i = 0; i < segments; i++, angle_min += step) {
 244             _cairo_arc_segment (cr, xc, yc, radius,
 245                                 angle_min, angle_min + step);
 246         }
 247
 248         _cairo_arc_segment (cr, xc, yc, radius,
 249                             angle_min, angle_max);
 250     } else {
 251         cairo_line_to (cr,
 252                        xc + radius * cos (angle_min),
 253                        yc + radius * sin (angle_min));
 254     }
 255 }
 256
 257 /**
 258  * _cairo_arc_path:
 259  * @cr: a cairo context
 260  * @xc: X position of the center of the arc
 261  * @yc: Y position of the center of the arc
 262  * @radius: the radius of the arc
 263  * @angle1: the start angle, in radians
 264  * @angle2: the end angle, in radians
 265  *
 266  * Compute a path for the given arc and append it onto the current
 267  * path within @cr. The arc will be accurate within the current
 268  * tolerance and given the current transformation.
 269  **/
 270 void
 271 _cairo_arc_path (cairo_t *cr,
 272                  double   xc,
 273                  double   yc,
 274                  double   radius,
 275                  double   angle1,
 276                  double   angle2)
 277 {
 278     _cairo_arc_in_direction (cr, xc, yc,
 279                              radius,
 280                              angle1, angle2,
 281                              CAIRO_DIRECTION_FORWARD);
 282 }
 283
 284 /**
 285  * _cairo_arc_path_negative:
 286  * @xc: X position of the center of the arc
 287  * @yc: Y position of the center of the arc
 288  * @radius: the radius of the arc
 289  * @angle1: the start angle, in radians
 290  * @angle2: the end angle, in radians
 291  * @ctm: the current transformation matrix
 292  * @tolerance: the current tolerance value
 293  * @path: the path onto which the arc will be appended
 294  *
 295  * Compute a path for the given arc (defined in the negative
 296  * direction) and append it onto the current path within @cr. The arc
 297  * will be accurate within the current tolerance and given the current
 298  * transformation.
 299  **/
 300 void
 301 _cairo_arc_path_negative (cairo_t *cr,
 302                           double   xc,
 303                           double   yc,
 304                           double   radius,
 305                           double   angle1,
 306                           double   angle2)
 307 {
 308     _cairo_arc_in_direction (cr, xc, yc,
 309                              radius,
 310                              angle2, angle1,
 311                              CAIRO_DIRECTION_REVERSE);
 312 }