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 | } |