Subversion Repositories Scribus

Rev

Rev 14952 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
14952 fschmid 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
18122 mrdocs 15
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
14952 fschmid 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
/* Spline deviation from the circle in radius would be given by:
42
 
43
        error = sqrt (x**2 + y**2) - 1
44
 
45
   A simpler error function to work with is:
46
 
47
        e = x**2 + y**2 - 1
48
 
49
   From "Good approximation of circles by curvature-continuous Bezier
50
   curves", Tor Dokken and Morten Daehlen, Computer Aided Geometric
51
   Design 8 (1990) 22-41, we learn:
52
 
53
        abs (max(e)) = 4/27 * sin**6(angle/4) / cos**2(angle/4)
54
 
55
   and
56
        abs (error) =~ 1/2 * e
57
 
58
   Of course, this error value applies only for the particular spline
59
   approximation that is used in _cairo_gstate_arc_segment.
60
*/
61
static double
62
_arc_error_normalized (double angle)
63
{
64
    return 2.0/27.0 * pow (sin (angle / 4), 6) / pow (cos (angle / 4), 2);
65
}
66
 
67
static double
68
_arc_max_angle_for_tolerance_normalized (double tolerance)
69
{
70
    double angle, error;
71
    int i;
72
 
73
    /* Use table lookup to reduce search time in most cases. */
74
    struct {
75
        double angle;
76
        double error;
77
    } table[] = {
78
        { M_PI / 1.0,   0.0185185185185185036127 },
79
        { M_PI / 2.0,   0.000272567143730179811158 },
80
        { M_PI / 3.0,   2.38647043651461047433e-05 },
81
        { M_PI / 4.0,   4.2455377443222443279e-06 },
82
        { M_PI / 5.0,   1.11281001494389081528e-06 },
83
        { M_PI / 6.0,   3.72662000942734705475e-07 },
84
        { M_PI / 7.0,   1.47783685574284411325e-07 },
85
        { M_PI / 8.0,   6.63240432022601149057e-08 },
86
        { M_PI / 9.0,   3.2715520137536980553e-08 },
87
        { M_PI / 10.0,  1.73863223499021216974e-08 },
88
        { M_PI / 11.0,  9.81410988043554039085e-09 },
89
    };
90
    int table_size = ARRAY_LENGTH (table);
91
 
92
    for (i = 0; i < table_size; i++)
93
        if (table[i].error < tolerance)
94
            return table[i].angle;
95
 
96
    ++i;
97
    do {
98
        angle = M_PI / i++;
99
        error = _arc_error_normalized (angle);
100
    } while (error > tolerance);
101
 
102
    return angle;
103
}
104
 
105
static int
106
_arc_segments_needed (double          angle,
107
                      double          radius,
108
                      cairo_matrix_t *ctm,
109
                      double          tolerance)
110
{
111
    double major_axis, max_angle;
112
 
113
    /* the error is amplified by at most the length of the
114
     * major axis of the circle; see cairo-pen.c for a more detailed analysis
115
     * of this. */
116
    major_axis = _cairo_matrix_transformed_circle_major_axis (ctm, radius);
117
    max_angle = _arc_max_angle_for_tolerance_normalized (tolerance / major_axis);
118
 
119
    return ceil (fabs (angle) / max_angle);
120
}
121
 
122
/* We want to draw a single spline approximating a circular arc radius
123
   R from angle A to angle B. Since we want a symmetric spline that
124
   matches the endpoints of the arc in position and slope, we know
125
   that the spline control points must be:
126
 
127
        (R * cos(A), R * sin(A))
128
        (R * cos(A) - h * sin(A), R * sin(A) + h * cos (A))
129
        (R * cos(B) + h * sin(B), R * sin(B) - h * cos (B))
130
        (R * cos(B), R * sin(B))
131
 
132
   for some value of h.
133
 
134
   "Approximation of circular arcs by cubic poynomials", Michael
135
   Goldapp, Computer Aided Geometric Design 8 (1991) 227-238, provides
136
   various values of h along with error analysis for each.
137
 
138
   From that paper, a very practical value of h is:
139
 
140
        h = 4/3 * tan(angle/4)
141
 
142
   This value does not give the spline with minimal error, but it does
143
   provide a very good approximation, (6th-order convergence), and the
144
   error expression is quite simple, (see the comment for
145
   _arc_error_normalized).
146
*/
147
static void
148
_cairo_arc_segment (cairo_t *cr,
149
                    double   xc,
150
                    double   yc,
151
                    double   radius,
152
                    double   angle_A,
153
                    double   angle_B)
154
{
155
    double r_sin_A, r_cos_A;
156
    double r_sin_B, r_cos_B;
157
    double h;
158
 
159
    r_sin_A = radius * sin (angle_A);
160
    r_cos_A = radius * cos (angle_A);
161
    r_sin_B = radius * sin (angle_B);
162
    r_cos_B = radius * cos (angle_B);
163
 
164
    h = 4.0/3.0 * tan ((angle_B - angle_A) / 4.0);
165
 
166
    cairo_curve_to (cr,
167
                    xc + r_cos_A - h * r_sin_A,
168
                    yc + r_sin_A + h * r_cos_A,
169
                    xc + r_cos_B + h * r_sin_B,
170
                    yc + r_sin_B - h * r_cos_B,
171
                    xc + r_cos_B,
172
                    yc + r_sin_B);
173
}
174
 
175
static void
176
_cairo_arc_in_direction (cairo_t          *cr,
177
                         double            xc,
178
                         double            yc,
179
                         double            radius,
180
                         double            angle_min,
181
                         double            angle_max,
182
                         cairo_direction_t dir)
183
{
184
    if (cairo_status (cr))
185
        return;
186
 
187
    while (angle_max - angle_min > 4 * M_PI)
188
        angle_max -= 2 * M_PI;
189
 
190
    /* Recurse if drawing arc larger than pi */
191
    if (angle_max - angle_min > M_PI) {
192
        double angle_mid = angle_min + (angle_max - angle_min) / 2.0;
193
        if (dir == CAIRO_DIRECTION_FORWARD) {
194
            _cairo_arc_in_direction (cr, xc, yc, radius,
195
                                     angle_min, angle_mid,
196
                                     dir);
197
 
198
            _cairo_arc_in_direction (cr, xc, yc, radius,
199
                                     angle_mid, angle_max,
200
                                     dir);
201
        } else {
202
            _cairo_arc_in_direction (cr, xc, yc, radius,
203
                                     angle_mid, angle_max,
204
                                     dir);
205
 
206
            _cairo_arc_in_direction (cr, xc, yc, radius,
207
                                     angle_min, angle_mid,
208
                                     dir);
209
        }
210
    } else if (angle_max != angle_min) {
211
        cairo_matrix_t ctm;
212
        int i, segments;
213
        double angle, angle_step;
214
 
215
        cairo_get_matrix (cr, &ctm);
216
        segments = _arc_segments_needed (angle_max - angle_min,
217
                                         radius, &ctm,
218
                                         cairo_get_tolerance (cr));
219
        angle_step = (angle_max - angle_min) / (double) segments;
220
 
221
        if (dir == CAIRO_DIRECTION_FORWARD) {
222
            angle = angle_min;
223
        } else {
224
            angle = angle_max;
225
            angle_step = - angle_step;
226
        }
227
 
228
        for (i = 0; i < segments; i++, angle += angle_step) {
229
            _cairo_arc_segment (cr, xc, yc,
230
                                radius,
231
                                angle,
232
                                angle + angle_step);
233
        }
234
    }
235
}
236
 
237
/**
238
 * _cairo_arc_path
239
 * @cr: a cairo context
240
 * @xc: X position of the center of the arc
241
 * @yc: Y position of the center of the arc
242
 * @radius: the radius of the arc
243
 * @angle1: the start angle, in radians
244
 * @angle2: the end angle, in radians
245
 *
246
 * Compute a path for the given arc and append it onto the current
247
 * path within @cr. The arc will be accurate within the current
248
 * tolerance and given the current transformation.
249
 **/
250
void
251
_cairo_arc_path (cairo_t *cr,
252
                 double   xc,
253
                 double   yc,
254
                 double   radius,
255
                 double   angle1,
256
                 double   angle2)
257
{
258
    _cairo_arc_in_direction (cr, xc, yc,
259
                             radius,
260
                             angle1, angle2,
261
                             CAIRO_DIRECTION_FORWARD);
262
}
263
 
264
/**
265
 * _cairo_arc_path_negative:
266
 * @xc: X position of the center of the arc
267
 * @yc: Y position of the center of the arc
268
 * @radius: the radius of the arc
269
 * @angle1: the start angle, in radians
270
 * @angle2: the end angle, in radians
271
 * @ctm: the current transformation matrix
272
 * @tolerance: the current tolerance value
273
 * @path: the path onto which the arc will be appended
274
 *
275
 * Compute a path for the given arc (defined in the negative
276
 * direction) and append it onto the current path within @cr. The arc
277
 * will be accurate within the current tolerance and given the current
278
 * transformation.
279
 **/
280
void
281
_cairo_arc_path_negative (cairo_t *cr,
282
                          double   xc,
283
                          double   yc,
284
                          double   radius,
285
                          double   angle1,
286
                          double   angle2)
287
{
288
    _cairo_arc_in_direction (cr, xc, yc,
289
                             radius,
290
                             angle2, angle1,
291
                             CAIRO_DIRECTION_REVERSE);
292
}