Rev 1892 | Go to most recent revision | Details | Compare with Previous | 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 © 2005 Red Hat, Inc |
||
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 Red Hat, Inc. |
||
31 | * |
||
32 | * Contributor(s): |
||
33 | * Carl Worth |
||
34 | */ |
||
35 | |||
36 | #include "cairoint.h" |
||
37 | #include "cairo-error-private.h" |
||
38 | |||
39 | void |
||
40 | _cairo_stroke_style_init (cairo_stroke_style_t *style) |
||
41 | { |
||
42 | VG (VALGRIND_MAKE_MEM_UNDEFINED (style, sizeof (cairo_stroke_style_t))); |
||
43 | |||
44 | style->line_width = CAIRO_GSTATE_LINE_WIDTH_DEFAULT; |
||
45 | style->line_cap = CAIRO_GSTATE_LINE_CAP_DEFAULT; |
||
46 | style->line_join = CAIRO_GSTATE_LINE_JOIN_DEFAULT; |
||
47 | style->miter_limit = CAIRO_GSTATE_MITER_LIMIT_DEFAULT; |
||
48 | |||
49 | style->dash = NULL; |
||
50 | style->num_dashes = 0; |
||
51 | style->dash_offset = 0.0; |
||
52 | } |
||
53 | |||
54 | cairo_status_t |
||
55 | _cairo_stroke_style_init_copy (cairo_stroke_style_t *style, |
||
56 | const cairo_stroke_style_t *other) |
||
57 | { |
||
58 | if (CAIRO_INJECT_FAULT ()) |
||
59 | return _cairo_error (CAIRO_STATUS_NO_MEMORY); |
||
60 | |||
61 | VG (VALGRIND_MAKE_MEM_UNDEFINED (style, sizeof (cairo_stroke_style_t))); |
||
62 | |||
63 | style->line_width = other->line_width; |
||
64 | style->line_cap = other->line_cap; |
||
65 | style->line_join = other->line_join; |
||
66 | style->miter_limit = other->miter_limit; |
||
67 | |||
68 | style->num_dashes = other->num_dashes; |
||
69 | |||
70 | if (other->dash == NULL) { |
||
71 | style->dash = NULL; |
||
72 | } else { |
||
73 | style->dash = _cairo_malloc_ab (style->num_dashes, sizeof (double)); |
||
74 | if (unlikely (style->dash == NULL)) |
||
75 | return _cairo_error (CAIRO_STATUS_NO_MEMORY); |
||
76 | |||
77 | memcpy (style->dash, other->dash, |
||
78 | style->num_dashes * sizeof (double)); |
||
79 | } |
||
80 | |||
81 | style->dash_offset = other->dash_offset; |
||
82 | |||
83 | return CAIRO_STATUS_SUCCESS; |
||
84 | } |
||
85 | |||
86 | void |
||
87 | _cairo_stroke_style_fini (cairo_stroke_style_t *style) |
||
88 | { |
||
3959 | Serge | 89 | free (style->dash); |
90 | style->dash = NULL; |
||
91 | |||
1892 | serge | 92 | style->num_dashes = 0; |
93 | |||
94 | VG (VALGRIND_MAKE_MEM_NOACCESS (style, sizeof (cairo_stroke_style_t))); |
||
95 | } |
||
96 | |||
97 | /* |
||
98 | * For a stroke in the given style, compute the maximum distance |
||
99 | * from the path that vertices could be generated. In the case |
||
100 | * of rotation in the ctm, the distance will not be exact. |
||
101 | */ |
||
102 | void |
||
103 | _cairo_stroke_style_max_distance_from_path (const cairo_stroke_style_t *style, |
||
3959 | Serge | 104 | const cairo_path_fixed_t *path, |
1892 | serge | 105 | const cairo_matrix_t *ctm, |
106 | double *dx, double *dy) |
||
107 | { |
||
108 | double style_expansion = 0.5; |
||
109 | |||
110 | if (style->line_cap == CAIRO_LINE_CAP_SQUARE) |
||
111 | style_expansion = M_SQRT1_2; |
||
112 | |||
113 | if (style->line_join == CAIRO_LINE_JOIN_MITER && |
||
3959 | Serge | 114 | ! path->stroke_is_rectilinear && |
1892 | serge | 115 | style_expansion < M_SQRT2 * style->miter_limit) |
116 | { |
||
117 | style_expansion = M_SQRT2 * style->miter_limit; |
||
118 | } |
||
119 | |||
120 | style_expansion *= style->line_width; |
||
121 | |||
3959 | Serge | 122 | if (_cairo_matrix_has_unity_scale (ctm)) { |
123 | *dx = *dy = style_expansion; |
||
124 | } else { |
||
125 | *dx = style_expansion * hypot (ctm->xx, ctm->xy); |
||
126 | *dy = style_expansion * hypot (ctm->yy, ctm->yx); |
||
127 | } |
||
1892 | serge | 128 | } |
129 | |||
3959 | Serge | 130 | void |
131 | _cairo_stroke_style_max_line_distance_from_path (const cairo_stroke_style_t *style, |
||
132 | const cairo_path_fixed_t *path, |
||
133 | const cairo_matrix_t *ctm, |
||
134 | double *dx, double *dy) |
||
135 | { |
||
136 | double style_expansion = 0.5 * style->line_width; |
||
137 | if (_cairo_matrix_has_unity_scale (ctm)) { |
||
138 | *dx = *dy = style_expansion; |
||
139 | } else { |
||
140 | *dx = style_expansion * hypot (ctm->xx, ctm->xy); |
||
141 | *dy = style_expansion * hypot (ctm->yy, ctm->yx); |
||
142 | } |
||
143 | } |
||
144 | |||
145 | void |
||
146 | _cairo_stroke_style_max_join_distance_from_path (const cairo_stroke_style_t *style, |
||
147 | const cairo_path_fixed_t *path, |
||
148 | const cairo_matrix_t *ctm, |
||
149 | double *dx, double *dy) |
||
150 | { |
||
151 | double style_expansion = 0.5; |
||
152 | |||
153 | if (style->line_join == CAIRO_LINE_JOIN_MITER && |
||
154 | ! path->stroke_is_rectilinear && |
||
155 | style_expansion < M_SQRT2 * style->miter_limit) |
||
156 | { |
||
157 | style_expansion = M_SQRT2 * style->miter_limit; |
||
158 | } |
||
159 | |||
160 | style_expansion *= style->line_width; |
||
161 | |||
162 | if (_cairo_matrix_has_unity_scale (ctm)) { |
||
163 | *dx = *dy = style_expansion; |
||
164 | } else { |
||
165 | *dx = style_expansion * hypot (ctm->xx, ctm->xy); |
||
166 | *dy = style_expansion * hypot (ctm->yy, ctm->yx); |
||
167 | } |
||
168 | } |
||
1892 | serge | 169 | /* |
170 | * Computes the period of a dashed stroke style. |
||
171 | * Returns 0 for non-dashed styles. |
||
172 | */ |
||
173 | double |
||
174 | _cairo_stroke_style_dash_period (const cairo_stroke_style_t *style) |
||
175 | { |
||
176 | double period; |
||
177 | unsigned int i; |
||
178 | |||
179 | period = 0.0; |
||
180 | for (i = 0; i < style->num_dashes; i++) |
||
181 | period += style->dash[i]; |
||
182 | |||
183 | if (style->num_dashes & 1) |
||
184 | period *= 2.0; |
||
185 | |||
186 | return period; |
||
187 | } |
||
188 | |||
189 | /* |
||
190 | * Coefficient of the linear approximation (minimizing square difference) |
||
191 | * of the surface covered by round caps |
||
192 | * |
||
193 | * This can be computed in the following way: |
||
194 | * the area inside the circle with radius w/2 and the region -d/2 <= x <= d/2 is: |
||
195 | * f(w,d) = 2 * integrate (sqrt (w*w/4 - x*x), x, -d/2, d/2) |
||
196 | * The square difference to a generic linear approximation (c*d) in the range (0,w) would be: |
||
197 | * integrate ((f(w,d) - c*d)^2, d, 0, w) |
||
198 | * To minimize this difference it is sufficient to find a solution of the differential with |
||
199 | * respect to c: |
||
200 | * solve ( diff (integrate ((f(w,d) - c*d)^2, d, 0, w), c), c) |
||
201 | * Which leads to c = 9/32*pi*w |
||
202 | * Since we're not interested in the true area, but just in a coverage extimate, |
||
203 | * we always divide the real area by the line width (w). |
||
204 | * The same computation for square caps would be |
||
205 | * f(w,d) = 2 * integrate(w/2, x, -d/2, d/2) |
||
206 | * c = 1*w |
||
207 | * but in this case it would not be an approximation, since f is already linear in d. |
||
208 | */ |
||
209 | #define ROUND_MINSQ_APPROXIMATION (9*M_PI/32) |
||
210 | |||
211 | /* |
||
212 | * Computes the length of the "on" part of a dashed stroke style, |
||
213 | * taking into account also line caps. |
||
214 | * Returns 0 for non-dashed styles. |
||
215 | */ |
||
216 | double |
||
217 | _cairo_stroke_style_dash_stroked (const cairo_stroke_style_t *style) |
||
218 | { |
||
219 | double stroked, cap_scale; |
||
220 | unsigned int i; |
||
221 | |||
222 | switch (style->line_cap) { |
||
223 | default: ASSERT_NOT_REACHED; |
||
224 | case CAIRO_LINE_CAP_BUTT: cap_scale = 0.0; break; |
||
225 | case CAIRO_LINE_CAP_ROUND: cap_scale = ROUND_MINSQ_APPROXIMATION; break; |
||
226 | case CAIRO_LINE_CAP_SQUARE: cap_scale = 1.0; break; |
||
227 | } |
||
228 | |||
229 | stroked = 0.0; |
||
230 | if (style->num_dashes & 1) { |
||
231 | /* Each dash element is used both as on and as off. The order in which they are summed is |
||
232 | * irrelevant, so sum the coverage of one dash element, taken both on and off at each iteration */ |
||
233 | for (i = 0; i < style->num_dashes; i++) |
||
234 | stroked += style->dash[i] + cap_scale * MIN (style->dash[i], style->line_width); |
||
235 | } else { |
||
236 | /* Even (0, 2, ...) dashes are on and simply counted for the coverage, odd dashes are off, thus |
||
237 | * their coverage is approximated based on the area covered by the caps of adjacent on dases. */ |
||
3959 | Serge | 238 | for (i = 0; i + 1 < style->num_dashes; i += 2) |
1892 | serge | 239 | stroked += style->dash[i] + cap_scale * MIN (style->dash[i+1], style->line_width); |
240 | } |
||
241 | |||
242 | return stroked; |
||
243 | } |
||
244 | |||
245 | /* |
||
246 | * Verifies if _cairo_stroke_style_dash_approximate should be used to generate |
||
247 | * an approximation of the dash pattern in the specified style, when used for |
||
248 | * stroking a path with the given CTM and tolerance. |
||
249 | * Always %FALSE for non-dashed styles. |
||
250 | */ |
||
251 | cairo_bool_t |
||
252 | _cairo_stroke_style_dash_can_approximate (const cairo_stroke_style_t *style, |
||
253 | const cairo_matrix_t *ctm, |
||
254 | double tolerance) |
||
255 | { |
||
256 | double period; |
||
257 | |||
258 | if (! style->num_dashes) |
||
259 | return FALSE; |
||
260 | |||
261 | period = _cairo_stroke_style_dash_period (style); |
||
262 | return _cairo_matrix_transformed_circle_major_axis (ctm, period) < tolerance; |
||
263 | } |
||
264 | |||
265 | /* |
||
266 | * Create a 2-dashes approximation of a dashed style, by making the "on" and "off" |
||
267 | * parts respect the original ratio. |
||
268 | */ |
||
269 | void |
||
270 | _cairo_stroke_style_dash_approximate (const cairo_stroke_style_t *style, |
||
271 | const cairo_matrix_t *ctm, |
||
272 | double tolerance, |
||
273 | double *dash_offset, |
||
274 | double *dashes, |
||
275 | unsigned int *num_dashes) |
||
276 | { |
||
277 | double coverage, scale, offset; |
||
278 | cairo_bool_t on = TRUE; |
||
279 | unsigned int i = 0; |
||
280 | |||
281 | coverage = _cairo_stroke_style_dash_stroked (style) / _cairo_stroke_style_dash_period (style); |
||
282 | coverage = MIN (coverage, 1.0); |
||
283 | scale = tolerance / _cairo_matrix_transformed_circle_major_axis (ctm, 1.0); |
||
284 | |||
285 | /* We stop searching for a starting point as soon as the |
||
286 | * offset reaches zero. Otherwise when an initial dash |
||
287 | * segment shrinks to zero it will be skipped over. */ |
||
288 | offset = style->dash_offset; |
||
289 | while (offset > 0.0 && offset >= style->dash[i]) { |
||
290 | offset -= style->dash[i]; |
||
291 | on = !on; |
||
292 | if (++i == style->num_dashes) |
||
293 | i = 0; |
||
294 | } |
||
295 | |||
296 | *num_dashes = 2; |
||
297 | |||
298 | /* |
||
299 | * We want to create a new dash pattern with the same relative coverage, |
||
300 | * but composed of just 2 elements with total length equal to scale. |
||
301 | * Based on the formula in _cairo_stroke_style_dash_stroked: |
||
302 | * scale * coverage = dashes[0] + cap_scale * MIN (dashes[1], line_width) |
||
303 | * = MIN (dashes[0] + cap_scale * (scale - dashes[0]), |
||
304 | * dashes[0] + cap_scale * line_width) = |
||
305 | * = MIN (dashes[0] * (1 - cap_scale) + cap_scale * scale, |
||
306 | * dashes[0] + cap_scale * line_width) |
||
307 | * |
||
308 | * Solving both cases we get: |
||
309 | * dashes[0] = scale * (coverage - cap_scale) / (1 - cap_scale) |
||
310 | * when scale - dashes[0] <= line_width |
||
311 | * dashes[0] = scale * coverage - cap_scale * line_width |
||
312 | * when scale - dashes[0] > line_width. |
||
313 | * |
||
314 | * Comparing the two cases we get: |
||
315 | * second > first |
||
316 | * second > scale * (coverage - cap_scale) / (1 - cap_scale) |
||
317 | * second - cap_scale * second - scale * coverage + scale * cap_scale > 0 |
||
318 | * (scale * coverage - cap_scale * line_width) - cap_scale * second - scale * coverage + scale * cap_scale > 0 |
||
319 | * - line_width - second + scale > 0 |
||
320 | * scale - second > line_width |
||
321 | * which is the condition for the second solution to be the valid one. |
||
322 | * So when second > first, the second solution is the correct one (i.e. |
||
323 | * the solution is always MAX (first, second). |
||
324 | */ |
||
325 | switch (style->line_cap) { |
||
326 | default: |
||
327 | ASSERT_NOT_REACHED; |
||
328 | dashes[0] = 0.0; |
||
329 | break; |
||
330 | |||
331 | case CAIRO_LINE_CAP_BUTT: |
||
332 | /* Simplified formula (substituting 0 for cap_scale): */ |
||
333 | dashes[0] = scale * coverage; |
||
334 | break; |
||
335 | |||
336 | case CAIRO_LINE_CAP_ROUND: |
||
337 | dashes[0] = MAX(scale * (coverage - ROUND_MINSQ_APPROXIMATION) / (1.0 - ROUND_MINSQ_APPROXIMATION), |
||
338 | scale * coverage - ROUND_MINSQ_APPROXIMATION * style->line_width); |
||
339 | break; |
||
340 | |||
341 | case CAIRO_LINE_CAP_SQUARE: |
||
342 | /* |
||
343 | * Special attention is needed to handle the case cap_scale == 1 (since the first solution |
||
344 | * is either indeterminate or -inf in this case). Since dash lengths are always >=0, using |
||
345 | * 0 as first solution always leads to the correct solution. |
||
346 | */ |
||
347 | dashes[0] = MAX(0.0, scale * coverage - style->line_width); |
||
348 | break; |
||
349 | } |
||
350 | |||
351 | dashes[1] = scale - dashes[0]; |
||
352 | |||
353 | *dash_offset = on ? 0.0 : dashes[0]; |
||
354 | }=>>>>=>=>>>> |