Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
1892 | serge | 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 |
||
35 | */ |
||
36 | |||
37 | #include "cairoint.h" |
||
38 | |||
39 | #include "cairo-arc-private.h" |
||
40 | |||
3959 | Serge | 41 | #define MAX_FULL_CIRCLES 65536 |
42 | |||
1892 | serge | 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 | |||
3959 | Serge | 136 | "Approximation of circular arcs by cubic polynomials", Michael |
1892 | serge | 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 | |||
3959 | Serge | 142 | h = 4/3 * R * tan(angle/4) |
1892 | serge | 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 | |||
3959 | Serge | 189 | assert (angle_max >= angle_min); |
1892 | serge | 190 | |
3959 | Serge | 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 | |||
1892 | serge | 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; |
||
3959 | Serge | 220 | double step; |
1892 | serge | 221 | |
222 | cairo_get_matrix (cr, &ctm); |
||
223 | segments = _arc_segments_needed (angle_max - angle_min, |
||
224 | radius, &ctm, |
||
225 | cairo_get_tolerance (cr)); |
||
3959 | Serge | 226 | step = (angle_max - angle_min) / segments; |
227 | segments -= 1; |
||
1892 | serge | 228 | |
3959 | Serge | 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; |
||
1892 | serge | 237 | } |
238 | |||
3959 | Serge | 239 | for (i = 0; i < segments; i++, angle_min += step) { |
240 | _cairo_arc_segment (cr, xc, yc, radius, |
||
241 | angle_min, angle_min + step); |
||
1892 | serge | 242 | } |
3959 | Serge | 243 | |
244 | _cairo_arc_segment (cr, xc, yc, radius, |
||
245 | angle_min, angle_max); |
||
1892 | serge | 246 | } else { |
247 | cairo_line_to (cr, |
||
248 | xc + radius * cos (angle_min), |
||
249 | yc + radius * sin (angle_min)); |
||
250 | } |
||
251 | } |
||
252 | |||
253 | /** |
||
3959 | Serge | 254 | * _cairo_arc_path: |
1892 | serge | 255 | * @cr: a cairo context |
256 | * @xc: X position of the center of the arc |
||
257 | * @yc: Y position of the center of the arc |
||
258 | * @radius: the radius of the arc |
||
259 | * @angle1: the start angle, in radians |
||
260 | * @angle2: the end angle, in radians |
||
261 | * |
||
262 | * Compute a path for the given arc and append it onto the current |
||
263 | * path within @cr. The arc will be accurate within the current |
||
264 | * tolerance and given the current transformation. |
||
265 | **/ |
||
266 | void |
||
267 | _cairo_arc_path (cairo_t *cr, |
||
268 | double xc, |
||
269 | double yc, |
||
270 | double radius, |
||
271 | double angle1, |
||
272 | double angle2) |
||
273 | { |
||
274 | _cairo_arc_in_direction (cr, xc, yc, |
||
275 | radius, |
||
276 | angle1, angle2, |
||
277 | CAIRO_DIRECTION_FORWARD); |
||
278 | } |
||
279 | |||
280 | /** |
||
281 | * _cairo_arc_path_negative: |
||
282 | * @xc: X position of the center of the arc |
||
283 | * @yc: Y position of the center of the arc |
||
284 | * @radius: the radius of the arc |
||
285 | * @angle1: the start angle, in radians |
||
286 | * @angle2: the end angle, in radians |
||
287 | * @ctm: the current transformation matrix |
||
288 | * @tolerance: the current tolerance value |
||
289 | * @path: the path onto which the arc will be appended |
||
290 | * |
||
291 | * Compute a path for the given arc (defined in the negative |
||
292 | * direction) and append it onto the current path within @cr. The arc |
||
293 | * will be accurate within the current tolerance and given the current |
||
294 | * transformation. |
||
295 | **/ |
||
296 | void |
||
297 | _cairo_arc_path_negative (cairo_t *cr, |
||
298 | double xc, |
||
299 | double yc, |
||
300 | double radius, |
||
301 | double angle1, |
||
302 | double angle2) |
||
303 | { |
||
304 | _cairo_arc_in_direction (cr, xc, yc, |
||
305 | radius, |
||
306 | angle2, angle1, |
||
307 | CAIRO_DIRECTION_REVERSE); |
||
308 | }>>> |