Line data Source code
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 : /* 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 0 : _arc_error_normalized (double angle)
63 : {
64 0 : return 2.0/27.0 * pow (sin (angle / 4), 6) / pow (cos (angle / 4), 2);
65 : }
66 :
67 : static double
68 0 : _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 0 : } 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 0 : int table_size = ARRAY_LENGTH (table);
91 :
92 0 : for (i = 0; i < table_size; i++)
93 0 : if (table[i].error < tolerance)
94 0 : return table[i].angle;
95 :
96 0 : ++i;
97 : do {
98 0 : angle = M_PI / i++;
99 0 : error = _arc_error_normalized (angle);
100 0 : } while (error > tolerance);
101 :
102 0 : return angle;
103 : }
104 :
105 : static int
106 0 : _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 0 : major_axis = _cairo_matrix_transformed_circle_major_axis (ctm, radius);
117 0 : max_angle = _arc_max_angle_for_tolerance_normalized (tolerance / major_axis);
118 :
119 0 : 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 0 : _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 0 : r_sin_A = radius * sin (angle_A);
160 0 : r_cos_A = radius * cos (angle_A);
161 0 : r_sin_B = radius * sin (angle_B);
162 0 : r_cos_B = radius * cos (angle_B);
163 :
164 0 : h = 4.0/3.0 * tan ((angle_B - angle_A) / 4.0);
165 :
166 0 : cairo_curve_to (cr,
167 0 : xc + r_cos_A - h * r_sin_A,
168 0 : yc + r_sin_A + h * r_cos_A,
169 0 : xc + r_cos_B + h * r_sin_B,
170 0 : yc + r_sin_B - h * r_cos_B,
171 : xc + r_cos_B,
172 : yc + r_sin_B);
173 0 : }
174 :
175 : static void
176 0 : _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 0 : if (cairo_status (cr))
185 0 : return;
186 :
187 0 : while (angle_max - angle_min > 4 * M_PI)
188 0 : angle_max -= 2 * M_PI;
189 :
190 : /* Recurse if drawing arc larger than pi */
191 0 : if (angle_max - angle_min > M_PI) {
192 0 : double angle_mid = angle_min + (angle_max - angle_min) / 2.0;
193 0 : if (dir == CAIRO_DIRECTION_FORWARD) {
194 0 : _cairo_arc_in_direction (cr, xc, yc, radius,
195 : angle_min, angle_mid,
196 : dir);
197 :
198 0 : _cairo_arc_in_direction (cr, xc, yc, radius,
199 : angle_mid, angle_max,
200 : dir);
201 : } else {
202 0 : _cairo_arc_in_direction (cr, xc, yc, radius,
203 : angle_mid, angle_max,
204 : dir);
205 :
206 0 : _cairo_arc_in_direction (cr, xc, yc, radius,
207 : angle_min, angle_mid,
208 : dir);
209 : }
210 0 : } else if (angle_max != angle_min) {
211 : cairo_matrix_t ctm;
212 : int i, segments;
213 : double angle, angle_step;
214 :
215 0 : cairo_get_matrix (cr, &ctm);
216 0 : segments = _arc_segments_needed (angle_max - angle_min,
217 : radius, &ctm,
218 : cairo_get_tolerance (cr));
219 0 : angle_step = (angle_max - angle_min) / (double) segments;
220 :
221 0 : if (dir == CAIRO_DIRECTION_FORWARD) {
222 0 : angle = angle_min;
223 : } else {
224 0 : angle = angle_max;
225 0 : angle_step = - angle_step;
226 : }
227 :
228 0 : for (i = 0; i < segments; i++, angle += angle_step) {
229 0 : _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 0 : _cairo_arc_path (cairo_t *cr,
252 : double xc,
253 : double yc,
254 : double radius,
255 : double angle1,
256 : double angle2)
257 : {
258 0 : _cairo_arc_in_direction (cr, xc, yc,
259 : radius,
260 : angle1, angle2,
261 : CAIRO_DIRECTION_FORWARD);
262 0 : }
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 0 : _cairo_arc_path_negative (cairo_t *cr,
282 : double xc,
283 : double yc,
284 : double radius,
285 : double angle1,
286 : double angle2)
287 : {
288 0 : _cairo_arc_in_direction (cr, xc, yc,
289 : radius,
290 : angle2, angle1,
291 : CAIRO_DIRECTION_REVERSE);
292 0 : }
|
