1 /* cairo - a vector graphics library with display and print output
2 *
3 * Copyright © 2002 University of Southern California
4 * Copyright © 2008 Chris Wilson
5 *
6 * This library is free software; you can redistribute it and/or
7 * modify it either under the terms of the GNU Lesser General Public
8 * License version 2.1 as published by the Free Software Foundation
9 * (the "LGPL") or, at your option, under the terms of the Mozilla
10 * Public License Version 1.1 (the "MPL"). If you do not alter this
11 * notice, a recipient may use your version of this file under either
12 * the MPL or the LGPL.
13 *
14 * You should have received a copy of the LGPL along with this library
15 * in the file COPYING-LGPL-2.1; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
17 * You should have received a copy of the MPL along with this library
18 * in the file COPYING-MPL-1.1
19 *
20 * The contents of this file are subject to the Mozilla Public License
21 * Version 1.1 (the "License"); you may not use this file except in
22 * compliance with the License. You may obtain a copy of the License at
23 * http://www.mozilla.org/MPL/
24 *
25 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
26 * OF ANY KIND, either express or implied. See the LGPL or the MPL for
27 * the specific language governing rights and limitations.
28 *
29 * The Original Code is the cairo graphics library.
30 *
31 * The Initial Developer of the Original Code is University of Southern
32 * California.
33 *
34 * Contributor(s):
35 * Carl D. Worth <cworth@cworth.org>
36 * Chris Wilson <chris@chris-wilson.co.uk>
37 */
38
39 #include "cairoint.h"
40
41 #include "cairo-error-private.h"
42 #include "cairo-slope-private.h"
43
44 static int
45 _cairo_pen_vertices_needed (double tolerance,
46 double radius,
47 const cairo_matrix_t *matrix);
48
49 static void
50 _cairo_pen_compute_slopes (cairo_pen_t *pen);
51
52 cairo_status_t
_cairo_pen_init(cairo_pen_t * pen,double radius,double tolerance,const cairo_matrix_t * ctm)53 _cairo_pen_init (cairo_pen_t *pen,
54 double radius,
55 double tolerance,
56 const cairo_matrix_t *ctm)
57 {
58 int i;
59 int reflect;
60
61 if (CAIRO_INJECT_FAULT ())
62 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
63
64 VG (VALGRIND_MAKE_MEM_UNDEFINED (pen, sizeof (cairo_pen_t)));
65
66 pen->radius = radius;
67 pen->tolerance = tolerance;
68
69 reflect = _cairo_matrix_compute_determinant (ctm) < 0.;
70
71 pen->num_vertices = _cairo_pen_vertices_needed (tolerance,
72 radius,
73 ctm);
74
75 if (pen->num_vertices > ARRAY_LENGTH (pen->vertices_embedded)) {
76 pen->vertices = _cairo_malloc_ab (pen->num_vertices,
77 sizeof (cairo_pen_vertex_t));
78 if (unlikely (pen->vertices == NULL))
79 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
80 } else {
81 pen->vertices = pen->vertices_embedded;
82 }
83
84 /*
85 * Compute pen coordinates. To generate the right ellipse, compute points around
86 * a circle in user space and transform them to device space. To get a consistent
87 * orientation in device space, flip the pen if the transformation matrix
88 * is reflecting
89 */
90 for (i=0; i < pen->num_vertices; i++) {
91 double theta = 2 * M_PI * i / (double) pen->num_vertices;
92 double dx = radius * cos (reflect ? -theta : theta);
93 double dy = radius * sin (reflect ? -theta : theta);
94 cairo_pen_vertex_t *v = &pen->vertices[i];
95 cairo_matrix_transform_distance (ctm, &dx, &dy);
96 v->point.x = _cairo_fixed_from_double (dx);
97 v->point.y = _cairo_fixed_from_double (dy);
98 }
99
100 _cairo_pen_compute_slopes (pen);
101
102 return CAIRO_STATUS_SUCCESS;
103 }
104
105 void
_cairo_pen_fini(cairo_pen_t * pen)106 _cairo_pen_fini (cairo_pen_t *pen)
107 {
108 if (pen->vertices != pen->vertices_embedded)
109 free (pen->vertices);
110
111
112 VG (VALGRIND_MAKE_MEM_NOACCESS (pen, sizeof (cairo_pen_t)));
113 }
114
115 cairo_status_t
_cairo_pen_init_copy(cairo_pen_t * pen,const cairo_pen_t * other)116 _cairo_pen_init_copy (cairo_pen_t *pen, const cairo_pen_t *other)
117 {
118 VG (VALGRIND_MAKE_MEM_UNDEFINED (pen, sizeof (cairo_pen_t)));
119
120 *pen = *other;
121
122 if (CAIRO_INJECT_FAULT ())
123 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
124
125 pen->vertices = pen->vertices_embedded;
126 if (pen->num_vertices) {
127 if (pen->num_vertices > ARRAY_LENGTH (pen->vertices_embedded)) {
128 pen->vertices = _cairo_malloc_ab (pen->num_vertices,
129 sizeof (cairo_pen_vertex_t));
130 if (unlikely (pen->vertices == NULL))
131 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
132 }
133
134 memcpy (pen->vertices, other->vertices,
135 pen->num_vertices * sizeof (cairo_pen_vertex_t));
136 }
137
138 return CAIRO_STATUS_SUCCESS;
139 }
140
141 cairo_status_t
_cairo_pen_add_points(cairo_pen_t * pen,cairo_point_t * point,int num_points)142 _cairo_pen_add_points (cairo_pen_t *pen, cairo_point_t *point, int num_points)
143 {
144 cairo_status_t status;
145 int num_vertices;
146 int i;
147
148 if (CAIRO_INJECT_FAULT ())
149 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
150
151 num_vertices = pen->num_vertices + num_points;
152 if (num_vertices > ARRAY_LENGTH (pen->vertices_embedded) ||
153 pen->vertices != pen->vertices_embedded)
154 {
155 cairo_pen_vertex_t *vertices;
156
157 if (pen->vertices == pen->vertices_embedded) {
158 vertices = _cairo_malloc_ab (num_vertices,
159 sizeof (cairo_pen_vertex_t));
160 if (unlikely (vertices == NULL))
161 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
162
163 memcpy (vertices, pen->vertices,
164 pen->num_vertices * sizeof (cairo_pen_vertex_t));
165 } else {
166 vertices = _cairo_realloc_ab (pen->vertices,
167 num_vertices,
168 sizeof (cairo_pen_vertex_t));
169 if (unlikely (vertices == NULL))
170 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
171 }
172
173 pen->vertices = vertices;
174 }
175
176 pen->num_vertices = num_vertices;
177
178 /* initialize new vertices */
179 for (i=0; i < num_points; i++)
180 pen->vertices[pen->num_vertices-num_points+i].point = point[i];
181
182 status = _cairo_hull_compute (pen->vertices, &pen->num_vertices);
183 if (unlikely (status))
184 return status;
185
186 _cairo_pen_compute_slopes (pen);
187
188 return CAIRO_STATUS_SUCCESS;
189 }
190
191 /*
192 The circular pen in user space is transformed into an ellipse in
193 device space.
194
195 We construct the pen by computing points along the circumference
196 using equally spaced angles.
197
198 We show that this approximation to the ellipse has maximum error at the
199 major axis of the ellipse.
200
201 Set
202
203 M = major axis length
204 m = minor axis length
205
206 Align 'M' along the X axis and 'm' along the Y axis and draw
207 an ellipse parameterized by angle 't':
208
209 x = M cos t y = m sin t
210
211 Perturb t by ± d and compute two new points (x+,y+), (x-,y-).
212 The distance from the average of these two points to (x,y) represents
213 the maximum error in approximating the ellipse with a polygon formed
214 from vertices 2∆ radians apart.
215
216 x+ = M cos (t+∆) y+ = m sin (t+∆)
217 x- = M cos (t-∆) y- = m sin (t-∆)
218
219 Now compute the approximation error, E:
220
221 Ex = (x - (x+ + x-) / 2)
222 Ex = (M cos(t) - (Mcos(t+∆) + Mcos(t-∆))/2)
223 = M (cos(t) - (cos(t)cos(∆) + sin(t)sin(∆) +
224 cos(t)cos(∆) - sin(t)sin(∆))/2)
225 = M(cos(t) - cos(t)cos(∆))
226 = M cos(t) (1 - cos(∆))
227
228 Ey = y - (y+ - y-) / 2
229 = m sin (t) - (m sin(t+∆) + m sin(t-∆)) / 2
230 = m (sin(t) - (sin(t)cos(∆) + cos(t)sin(∆) +
231 sin(t)cos(∆) - cos(t)sin(∆))/2)
232 = m (sin(t) - sin(t)cos(∆))
233 = m sin(t) (1 - cos(∆))
234
235 E² = Ex² + Ey²
236 = (M cos(t) (1 - cos (∆)))² + (m sin(t) (1-cos(∆)))²
237 = (1 - cos(∆))² (M² cos²(t) + m² sin²(t))
238 = (1 - cos(∆))² ((m² + M² - m²) cos² (t) + m² sin²(t))
239 = (1 - cos(∆))² (M² - m²) cos² (t) + (1 - cos(∆))² m²
240
241 Find the extremum by differentiation wrt t and setting that to zero
242
243 ∂(E²)/∂(t) = (1-cos(∆))² (M² - m²) (-2 cos(t) sin(t))
244
245 0 = 2 cos (t) sin (t)
246 0 = sin (2t)
247 t = nπ
248
249 Which is to say that the maximum and minimum errors occur on the
250 axes of the ellipse at 0 and π radians:
251
252 E²(0) = (1-cos(∆))² (M² - m²) + (1-cos(∆))² m²
253 = (1-cos(∆))² M²
254 E²(π) = (1-cos(∆))² m²
255
256 maximum error = M (1-cos(∆))
257 minimum error = m (1-cos(∆))
258
259 We must make maximum error ≤ tolerance, so compute the ∆ needed:
260
261 tolerance = M (1-cos(∆))
262 tolerance / M = 1 - cos (∆)
263 cos(∆) = 1 - tolerance/M
264 ∆ = acos (1 - tolerance / M);
265
266 Remembering that ∆ is half of our angle between vertices,
267 the number of vertices is then
268
269 vertices = ceil(2π/2∆).
270 = ceil(π/∆).
271
272 Note that this also equation works for M == m (a circle) as it
273 doesn't matter where on the circle the error is computed.
274 */
275
276 static int
_cairo_pen_vertices_needed(double tolerance,double radius,const cairo_matrix_t * matrix)277 _cairo_pen_vertices_needed (double tolerance,
278 double radius,
279 const cairo_matrix_t *matrix)
280 {
281 /*
282 * the pen is a circle that gets transformed to an ellipse by matrix.
283 * compute major axis length for a pen with the specified radius.
284 * we don't need the minor axis length.
285 */
286
287 double major_axis = _cairo_matrix_transformed_circle_major_axis (matrix,
288 radius);
289
290 /*
291 * compute number of vertices needed
292 */
293 int num_vertices;
294
295 /* Where tolerance / M is > 1, we use 4 points */
296 if (tolerance >= major_axis) {
297 num_vertices = 4;
298 } else {
299 double delta = acos (1 - tolerance / major_axis);
300 num_vertices = ceil (M_PI / delta);
301
302 /* number of vertices must be even */
303 if (num_vertices % 2)
304 num_vertices++;
305
306 /* And we must always have at least 4 vertices. */
307 if (num_vertices < 4)
308 num_vertices = 4;
309 }
310
311 return num_vertices;
312 }
313
314 static void
_cairo_pen_compute_slopes(cairo_pen_t * pen)315 _cairo_pen_compute_slopes (cairo_pen_t *pen)
316 {
317 int i, i_prev;
318 cairo_pen_vertex_t *prev, *v, *next;
319
320 for (i=0, i_prev = pen->num_vertices - 1;
321 i < pen->num_vertices;
322 i_prev = i++) {
323 prev = &pen->vertices[i_prev];
324 v = &pen->vertices[i];
325 next = &pen->vertices[(i + 1) % pen->num_vertices];
326
327 _cairo_slope_init (&v->slope_cw, &prev->point, &v->point);
328 _cairo_slope_init (&v->slope_ccw, &v->point, &next->point);
329 }
330 }
331 /*
332 * Find active pen vertex for clockwise edge of stroke at the given slope.
333 *
334 * The strictness of the inequalities here is delicate. The issue is
335 * that the slope_ccw member of one pen vertex will be equivalent to
336 * the slope_cw member of the next pen vertex in a counterclockwise
337 * order. However, for this function, we care strongly about which
338 * vertex is returned.
339 *
340 * [I think the "care strongly" above has to do with ensuring that the
341 * pen's "extra points" from the spline's initial and final slopes are
342 * properly found when beginning the spline stroking.]
343 */
344 int
_cairo_pen_find_active_cw_vertex_index(const cairo_pen_t * pen,const cairo_slope_t * slope)345 _cairo_pen_find_active_cw_vertex_index (const cairo_pen_t *pen,
346 const cairo_slope_t *slope)
347 {
348 int i;
349
350 for (i=0; i < pen->num_vertices; i++) {
351 if ((_cairo_slope_compare (slope, &pen->vertices[i].slope_ccw) < 0) &&
352 (_cairo_slope_compare (slope, &pen->vertices[i].slope_cw) >= 0))
353 break;
354 }
355
356 /* If the desired slope cannot be found between any of the pen
357 * vertices, then we must have a degenerate pen, (such as a pen
358 * that's been transformed to a line). In that case, we consider
359 * the first pen vertex as the appropriate clockwise vertex.
360 */
361 if (i == pen->num_vertices)
362 i = 0;
363
364 return i;
365 }
366
367 /* Find active pen vertex for counterclockwise edge of stroke at the given slope.
368 *
369 * Note: See the comments for _cairo_pen_find_active_cw_vertex_index
370 * for some details about the strictness of the inequalities here.
371 */
372 int
_cairo_pen_find_active_ccw_vertex_index(const cairo_pen_t * pen,const cairo_slope_t * slope)373 _cairo_pen_find_active_ccw_vertex_index (const cairo_pen_t *pen,
374 const cairo_slope_t *slope)
375 {
376 cairo_slope_t slope_reverse;
377 int i;
378
379 slope_reverse = *slope;
380 slope_reverse.dx = -slope_reverse.dx;
381 slope_reverse.dy = -slope_reverse.dy;
382
383 for (i=pen->num_vertices-1; i >= 0; i--) {
384 if ((_cairo_slope_compare (&pen->vertices[i].slope_ccw, &slope_reverse) >= 0) &&
385 (_cairo_slope_compare (&pen->vertices[i].slope_cw, &slope_reverse) < 0))
386 break;
387 }
388
389 /* If the desired slope cannot be found between any of the pen
390 * vertices, then we must have a degenerate pen, (such as a pen
391 * that's been transformed to a line). In that case, we consider
392 * the last pen vertex as the appropriate counterclockwise vertex.
393 */
394 if (i < 0)
395 i = pen->num_vertices - 1;
396
397 return i;
398 }
399