Back to index

lightning-sunbird  0.9+nobinonly
cairo-arc.c
Go to the documentation of this file.
00001 /* cairo - a vector graphics library with display and print output
00002  *
00003  * Copyright © 2002 University of Southern California
00004  *
00005  * This library is free software; you can redistribute it and/or
00006  * modify it either under the terms of the GNU Lesser General Public
00007  * License version 2.1 as published by the Free Software Foundation
00008  * (the "LGPL") or, at your option, under the terms of the Mozilla
00009  * Public License Version 1.1 (the "MPL"). If you do not alter this
00010  * notice, a recipient may use your version of this file under either
00011  * the MPL or the LGPL.
00012  *
00013  * You should have received a copy of the LGPL along with this library
00014  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
00015  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
00016  * You should have received a copy of the MPL along with this library
00017  * in the file COPYING-MPL-1.1
00018  *
00019  * The contents of this file are subject to the Mozilla Public License
00020  * Version 1.1 (the "License"); you may not use this file except in
00021  * compliance with the License. You may obtain a copy of the License at
00022  * http://www.mozilla.org/MPL/
00023  *
00024  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
00025  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
00026  * the specific language governing rights and limitations.
00027  *
00028  * The Original Code is the cairo graphics library.
00029  *
00030  * The Initial Developer of the Original Code is University of Southern
00031  * California.
00032  *
00033  * Contributor(s):
00034  *     Carl D. Worth <cworth@cworth.org>
00035  */
00036 
00037 #include "cairo-arc-private.h"
00038 
00039 /* Spline deviation from the circle in radius would be given by:
00040 
00041        error = sqrt (x**2 + y**2) - 1
00042 
00043    A simpler error function to work with is:
00044 
00045        e = x**2 + y**2 - 1
00046 
00047    From "Good approximation of circles by curvature-continuous Bezier
00048    curves", Tor Dokken and Morten Daehlen, Computer Aided Geometric
00049    Design 8 (1990) 22-41, we learn:
00050 
00051        abs (max(e)) = 4/27 * sin**6(angle/4) / cos**2(angle/4)
00052 
00053    and
00054        abs (error) =~ 1/2 * e
00055 
00056    Of course, this error value applies only for the particular spline
00057    approximation that is used in _cairo_gstate_arc_segment.
00058 */
00059 static double
00060 _arc_error_normalized (double angle)
00061 {
00062     return 2.0/27.0 * pow (sin (angle / 4), 6) / pow (cos (angle / 4), 2);
00063 }
00064 
00065 static double
00066 _arc_max_angle_for_tolerance_normalized (double tolerance)
00067 {
00068     double angle, error;
00069     int i;
00070 
00071     /* Use table lookup to reduce search time in most cases. */
00072     struct {
00073        double angle;
00074        double error;
00075     } table[] = {
00076        { M_PI / 1.0,   0.0185185185185185036127 },
00077        { M_PI / 2.0,   0.000272567143730179811158 },
00078        { M_PI / 3.0,   2.38647043651461047433e-05 },
00079        { M_PI / 4.0,   4.2455377443222443279e-06 },
00080        { M_PI / 5.0,   1.11281001494389081528e-06 },
00081        { M_PI / 6.0,   3.72662000942734705475e-07 },
00082        { M_PI / 7.0,   1.47783685574284411325e-07 },
00083        { M_PI / 8.0,   6.63240432022601149057e-08 },
00084        { M_PI / 9.0,   3.2715520137536980553e-08 },
00085        { M_PI / 10.0,  1.73863223499021216974e-08 },
00086        { M_PI / 11.0,  9.81410988043554039085e-09 },
00087     };
00088     int table_size = (sizeof (table) / sizeof (table[0]));
00089 
00090     for (i = 0; i < table_size; i++)
00091        if (table[i].error < tolerance)
00092            return table[i].angle;
00093 
00094     ++i;
00095     do {
00096        angle = M_PI / i++;
00097        error = _arc_error_normalized (angle);
00098     } while (error > tolerance);
00099 
00100     return angle;
00101 }
00102 
00103 static int
00104 _arc_segments_needed (double             angle,
00105                     double        radius,
00106                     cairo_matrix_t *ctm,
00107                     double        tolerance)
00108 {
00109     double major_axis, max_angle;
00110 
00111     /* the error is amplified by at most the length of the
00112      * major axis of the circle; see cairo-pen.c for a more detailed analysis
00113      * of this. */
00114     major_axis = _cairo_matrix_transformed_circle_major_axis (ctm, radius);
00115     max_angle = _arc_max_angle_for_tolerance_normalized (tolerance / major_axis);
00116 
00117     return (int) ceil (angle / max_angle);
00118 }
00119 
00120 /* We want to draw a single spline approximating a circular arc radius
00121    R from angle A to angle B. Since we want a symmetric spline that
00122    matches the endpoints of the arc in position and slope, we know
00123    that the spline control points must be:
00124 
00125        (R * cos(A), R * sin(A))
00126        (R * cos(A) - h * sin(A), R * sin(A) + h * cos (A))
00127        (R * cos(B) + h * sin(B), R * sin(B) - h * cos (B))
00128        (R * cos(B), R * sin(B))
00129 
00130    for some value of h.
00131 
00132    "Approximation of circular arcs by cubic poynomials", Michael
00133    Goldapp, Computer Aided Geometric Design 8 (1991) 227-238, provides
00134    various values of h along with error analysis for each.
00135 
00136    From that paper, a very practical value of h is:
00137 
00138        h = 4/3 * tan(angle/4)
00139 
00140    This value does not give the spline with minimal error, but it does
00141    provide a very good approximation, (6th-order convergence), and the
00142    error expression is quite simple, (see the comment for
00143    _arc_error_normalized).
00144 */
00145 static void
00146 _cairo_arc_segment (cairo_t *cr,
00147                   double   xc,
00148                   double   yc,
00149                   double   radius,
00150                   double   angle_A,
00151                   double   angle_B)
00152 {
00153     double r_sin_A, r_cos_A;
00154     double r_sin_B, r_cos_B;
00155     double h;
00156 
00157     r_sin_A = radius * sin (angle_A);
00158     r_cos_A = radius * cos (angle_A);
00159     r_sin_B = radius * sin (angle_B);
00160     r_cos_B = radius * cos (angle_B);
00161 
00162     h = 4.0/3.0 * tan ((angle_B - angle_A) / 4.0);
00163 
00164     cairo_curve_to (cr,
00165                   xc + r_cos_A - h * r_sin_A,
00166                   yc + r_sin_A + h * r_cos_A,
00167                   xc + r_cos_B + h * r_sin_B,
00168                   yc + r_sin_B - h * r_cos_B,
00169                   xc + r_cos_B,
00170                   yc + r_sin_B);
00171 }
00172 
00173 static void
00174 _cairo_arc_in_direction (cairo_t     *cr,
00175                       double                 xc,
00176                       double                 yc,
00177                       double                 radius,
00178                       double                 angle_min,
00179                       double                 angle_max,
00180                       cairo_direction_t dir)
00181 {
00182     while (angle_max - angle_min > 4 * M_PI)
00183        angle_max -= 2 * M_PI;
00184 
00185     /* Recurse if drawing arc larger than pi */
00186     if (angle_max - angle_min > M_PI) {
00187        double angle_mid = angle_min + (angle_max - angle_min) / 2.0;
00188        /* XXX: Something tells me this block could be condensed. */
00189        if (dir == CAIRO_DIRECTION_FORWARD) {
00190            _cairo_arc_in_direction (cr, xc, yc, radius,
00191                                  angle_min, angle_mid,
00192                                  dir);
00193            
00194            _cairo_arc_in_direction (cr, xc, yc, radius,
00195                                  angle_mid, angle_max,
00196                                  dir);
00197        } else {
00198            _cairo_arc_in_direction (cr, xc, yc, radius,
00199                                  angle_mid, angle_max,
00200                                  dir);
00201 
00202            _cairo_arc_in_direction (cr, xc, yc, radius,
00203                                  angle_min, angle_mid,
00204                                  dir);
00205        }
00206     } else {
00207        cairo_matrix_t ctm;
00208        int i, segments;
00209        double angle, angle_step;
00210 
00211        cairo_get_matrix (cr, &ctm);
00212        segments = _arc_segments_needed (angle_max - angle_min,
00213                                     radius, &ctm,
00214                                     cairo_get_tolerance (cr));
00215        angle_step = (angle_max - angle_min) / (double) segments;
00216 
00217        if (dir == CAIRO_DIRECTION_FORWARD) {
00218            angle = angle_min;
00219        } else {
00220            angle = angle_max;
00221            angle_step = - angle_step;
00222        }
00223 
00224        for (i = 0; i < segments; i++, angle += angle_step) {
00225            _cairo_arc_segment (cr, xc, yc,
00226                             radius,
00227                             angle,
00228                             angle + angle_step);
00229        }
00230     }
00231 }
00232 
00246 void
00247 _cairo_arc_path (cairo_t *cr,
00248                double         xc,
00249                double         yc,
00250                double         radius,
00251                double         angle1,
00252                double         angle2)
00253 {
00254     _cairo_arc_in_direction (cr, xc, yc,
00255                           radius,
00256                           angle1, angle2,
00257                           CAIRO_DIRECTION_FORWARD);
00258 }
00259 
00276 void
00277 _cairo_arc_path_negative (cairo_t *cr,
00278                        double   xc,
00279                        double   yc,
00280                        double   radius,
00281                        double   angle1,
00282                        double   angle2)
00283 {
00284     _cairo_arc_in_direction (cr, xc, yc,
00285                           radius,
00286                           angle2, angle1,
00287                           CAIRO_DIRECTION_REVERSE);
00288 }