1 /* cairo - a vector graphics library with display and print output
3 * Copyright © 2002 University of Southern California
4 * Copyright © 2008 Chris Wilson
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.
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
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/
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.
29 * The Original Code is the cairo graphics library.
31 * The Initial Developer of the Original Code is University of Southern
35 * Carl D. Worth <cworth@cworth.org>
36 * Chris Wilson <chris@chris-wilson.co.uk>
41 #include "cairo-error-private.h"
42 #include "cairo-slope-private.h"
45 _cairo_pen_vertices_needed (double tolerance,
47 const cairo_matrix_t *matrix);
50 _cairo_pen_compute_slopes (cairo_pen_t *pen);
53 _cairo_pen_init (cairo_pen_t *pen,
56 const cairo_matrix_t *ctm)
61 if (CAIRO_INJECT_FAULT ())
62 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
64 VG (VALGRIND_MAKE_MEM_UNDEFINED (pen, sizeof (cairo_pen_t)));
67 pen->tolerance = tolerance;
69 reflect = _cairo_matrix_compute_determinant (ctm) < 0.;
71 pen->num_vertices = _cairo_pen_vertices_needed (tolerance,
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);
81 pen->vertices = pen->vertices_embedded;
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
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);
100 _cairo_pen_compute_slopes (pen);
102 return CAIRO_STATUS_SUCCESS;
106 _cairo_pen_fini (cairo_pen_t *pen)
108 if (pen->vertices != pen->vertices_embedded)
109 free (pen->vertices);
112 VG (VALGRIND_MAKE_MEM_NOACCESS (pen, sizeof (cairo_pen_t)));
116 _cairo_pen_init_copy (cairo_pen_t *pen, const cairo_pen_t *other)
118 VG (VALGRIND_MAKE_MEM_UNDEFINED (pen, sizeof (cairo_pen_t)));
122 if (CAIRO_INJECT_FAULT ())
123 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
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);
134 memcpy (pen->vertices, other->vertices,
135 pen->num_vertices * sizeof (cairo_pen_vertex_t));
138 return CAIRO_STATUS_SUCCESS;
142 _cairo_pen_add_points (cairo_pen_t *pen, cairo_point_t *point, int num_points)
144 cairo_status_t status;
148 if (CAIRO_INJECT_FAULT ())
149 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
151 num_vertices = pen->num_vertices + num_points;
152 if (num_vertices > ARRAY_LENGTH (pen->vertices_embedded) ||
153 pen->vertices != pen->vertices_embedded)
155 cairo_pen_vertex_t *vertices;
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);
163 memcpy (vertices, pen->vertices,
164 pen->num_vertices * sizeof (cairo_pen_vertex_t));
166 vertices = _cairo_realloc_ab (pen->vertices,
168 sizeof (cairo_pen_vertex_t));
169 if (unlikely (vertices == NULL))
170 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
173 pen->vertices = vertices;
176 pen->num_vertices = num_vertices;
178 /* initialize new vertices */
179 for (i=0; i < num_points; i++)
180 pen->vertices[pen->num_vertices-num_points+i].point = point[i];
182 status = _cairo_hull_compute (pen->vertices, &pen->num_vertices);
183 if (unlikely (status))
186 _cairo_pen_compute_slopes (pen);
188 return CAIRO_STATUS_SUCCESS;
192 The circular pen in user space is transformed into an ellipse in
195 We construct the pen by computing points along the circumference
196 using equally spaced angles.
198 We show that this approximation to the ellipse has maximum error at the
199 major axis of the ellipse.
203 M = major axis length
204 m = minor axis length
206 Align 'M' along the X axis and 'm' along the Y axis and draw
207 an ellipse parameterized by angle 't':
209 x = M cos t y = m sin t
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.
216 x+ = M cos (t+∆) y+ = m sin (t+∆)
217 x- = M cos (t-∆) y- = m sin (t-∆)
219 Now compute the approximation error, E:
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(∆))
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(∆))
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²
241 Find the extremum by differentiation wrt t and setting that to zero
243 ∂(E²)/∂(t) = (1-cos(∆))² (M² - m²) (-2 cos(t) sin(t))
245 0 = 2 cos (t) sin (t)
249 Which is to say that the maximum and minimum errors occur on the
250 axes of the ellipse at 0 and π radians:
252 E²(0) = (1-cos(∆))² (M² - m²) + (1-cos(∆))² m²
254 E²(π) = (1-cos(∆))² m²
256 maximum error = M (1-cos(∆))
257 minimum error = m (1-cos(∆))
259 We must make maximum error ≤ tolerance, so compute the ∆ needed:
261 tolerance = M (1-cos(∆))
262 tolerance / M = 1 - cos (∆)
263 cos(∆) = 1 - tolerance/M
264 ∆ = acos (1 - tolerance / M);
266 Remembering that ∆ is half of our angle between vertices,
267 the number of vertices is then
269 vertices = ceil(2π/2∆).
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.
277 _cairo_pen_vertices_needed (double tolerance,
279 const cairo_matrix_t *matrix)
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.
287 double major_axis = _cairo_matrix_transformed_circle_major_axis (matrix,
291 * compute number of vertices needed
295 /* Where tolerance / M is > 1, we use 4 points */
296 if (tolerance >= major_axis) {
299 double delta = acos (1 - tolerance / major_axis);
300 num_vertices = ceil (M_PI / delta);
302 /* number of vertices must be even */
303 if (num_vertices % 2)
306 /* And we must always have at least 4 vertices. */
307 if (num_vertices < 4)
315 _cairo_pen_compute_slopes (cairo_pen_t *pen)
318 cairo_pen_vertex_t *prev, *v, *next;
320 for (i=0, i_prev = pen->num_vertices - 1;
321 i < pen->num_vertices;
323 prev = &pen->vertices[i_prev];
324 v = &pen->vertices[i];
325 next = &pen->vertices[(i + 1) % pen->num_vertices];
327 _cairo_slope_init (&v->slope_cw, &prev->point, &v->point);
328 _cairo_slope_init (&v->slope_ccw, &v->point, &next->point);
332 * Find active pen vertex for clockwise edge of stroke at the given slope.
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.
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.]
345 _cairo_pen_find_active_cw_vertex_index (const cairo_pen_t *pen,
346 const cairo_slope_t *slope)
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))
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.
361 if (i == pen->num_vertices)
367 /* Find active pen vertex for counterclockwise edge of stroke at the given slope.
369 * Note: See the comments for _cairo_pen_find_active_cw_vertex_index
370 * for some details about the strictness of the inequalities here.
373 _cairo_pen_find_active_ccw_vertex_index (const cairo_pen_t *pen,
374 const cairo_slope_t *slope)
376 cairo_slope_t slope_reverse;
379 slope_reverse = *slope;
380 slope_reverse.dx = -slope_reverse.dx;
381 slope_reverse.dy = -slope_reverse.dy;
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))
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.
395 i = pen->num_vertices - 1;