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