Line data Source code
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
53 0 : _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 0 : pen->radius = radius;
67 0 : pen->tolerance = tolerance;
68 :
69 0 : reflect = _cairo_matrix_compute_determinant (ctm) < 0.;
70 :
71 0 : pen->num_vertices = _cairo_pen_vertices_needed (tolerance,
72 : radius,
73 : ctm);
74 :
75 0 : if (pen->num_vertices > ARRAY_LENGTH (pen->vertices_embedded)) {
76 0 : pen->vertices = _cairo_malloc_ab (pen->num_vertices,
77 : sizeof (cairo_pen_vertex_t));
78 0 : if (unlikely (pen->vertices == NULL))
79 0 : return _cairo_error (CAIRO_STATUS_NO_MEMORY);
80 : } else {
81 0 : 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 0 : for (i=0; i < pen->num_vertices; i++) {
91 0 : double theta = 2 * M_PI * i / (double) pen->num_vertices;
92 0 : double dx = radius * cos (reflect ? -theta : theta);
93 0 : double dy = radius * sin (reflect ? -theta : theta);
94 0 : cairo_pen_vertex_t *v = &pen->vertices[i];
95 0 : cairo_matrix_transform_distance (ctm, &dx, &dy);
96 0 : v->point.x = _cairo_fixed_from_double (dx);
97 0 : v->point.y = _cairo_fixed_from_double (dy);
98 : }
99 :
100 0 : _cairo_pen_compute_slopes (pen);
101 :
102 0 : return CAIRO_STATUS_SUCCESS;
103 : }
104 :
105 : void
106 0 : _cairo_pen_fini (cairo_pen_t *pen)
107 : {
108 0 : if (pen->vertices != pen->vertices_embedded)
109 0 : free (pen->vertices);
110 :
111 :
112 : VG (VALGRIND_MAKE_MEM_NOACCESS (pen, sizeof (cairo_pen_t)));
113 0 : }
114 :
115 : cairo_status_t
116 0 : _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 0 : *pen = *other;
121 :
122 : if (CAIRO_INJECT_FAULT ())
123 : return _cairo_error (CAIRO_STATUS_NO_MEMORY);
124 :
125 0 : pen->vertices = pen->vertices_embedded;
126 0 : if (pen->num_vertices) {
127 0 : if (pen->num_vertices > ARRAY_LENGTH (pen->vertices_embedded)) {
128 0 : pen->vertices = _cairo_malloc_ab (pen->num_vertices,
129 : sizeof (cairo_pen_vertex_t));
130 0 : if (unlikely (pen->vertices == NULL))
131 0 : return _cairo_error (CAIRO_STATUS_NO_MEMORY);
132 : }
133 :
134 0 : memcpy (pen->vertices, other->vertices,
135 0 : pen->num_vertices * sizeof (cairo_pen_vertex_t));
136 : }
137 :
138 0 : return CAIRO_STATUS_SUCCESS;
139 : }
140 :
141 : cairo_status_t
142 0 : _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 0 : num_vertices = pen->num_vertices + num_points;
152 0 : if (num_vertices > ARRAY_LENGTH (pen->vertices_embedded) ||
153 0 : pen->vertices != pen->vertices_embedded)
154 : {
155 : cairo_pen_vertex_t *vertices;
156 :
157 0 : if (pen->vertices == pen->vertices_embedded) {
158 0 : vertices = _cairo_malloc_ab (num_vertices,
159 : sizeof (cairo_pen_vertex_t));
160 0 : if (unlikely (vertices == NULL))
161 0 : return _cairo_error (CAIRO_STATUS_NO_MEMORY);
162 :
163 0 : memcpy (vertices, pen->vertices,
164 0 : pen->num_vertices * sizeof (cairo_pen_vertex_t));
165 : } else {
166 0 : vertices = _cairo_realloc_ab (pen->vertices,
167 : num_vertices,
168 : sizeof (cairo_pen_vertex_t));
169 0 : if (unlikely (vertices == NULL))
170 0 : return _cairo_error (CAIRO_STATUS_NO_MEMORY);
171 : }
172 :
173 0 : pen->vertices = vertices;
174 : }
175 :
176 0 : pen->num_vertices = num_vertices;
177 :
178 : /* initialize new vertices */
179 0 : for (i=0; i < num_points; i++)
180 0 : pen->vertices[pen->num_vertices-num_points+i].point = point[i];
181 :
182 0 : status = _cairo_hull_compute (pen->vertices, &pen->num_vertices);
183 0 : if (unlikely (status))
184 0 : return status;
185 :
186 0 : _cairo_pen_compute_slopes (pen);
187 :
188 0 : 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
277 0 : _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 0 : 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 0 : if (tolerance >= major_axis) {
297 0 : num_vertices = 4;
298 : } else {
299 0 : double delta = acos (1 - tolerance / major_axis);
300 0 : num_vertices = ceil (M_PI / delta);
301 :
302 : /* number of vertices must be even */
303 0 : if (num_vertices % 2)
304 0 : num_vertices++;
305 :
306 : /* And we must always have at least 4 vertices. */
307 0 : if (num_vertices < 4)
308 0 : num_vertices = 4;
309 : }
310 :
311 0 : return num_vertices;
312 : }
313 :
314 : static void
315 0 : _cairo_pen_compute_slopes (cairo_pen_t *pen)
316 : {
317 : int i, i_prev;
318 : cairo_pen_vertex_t *prev, *v, *next;
319 :
320 0 : for (i=0, i_prev = pen->num_vertices - 1;
321 0 : i < pen->num_vertices;
322 0 : i_prev = i++) {
323 0 : prev = &pen->vertices[i_prev];
324 0 : v = &pen->vertices[i];
325 0 : next = &pen->vertices[(i + 1) % pen->num_vertices];
326 :
327 0 : _cairo_slope_init (&v->slope_cw, &prev->point, &v->point);
328 0 : _cairo_slope_init (&v->slope_ccw, &v->point, &next->point);
329 : }
330 0 : }
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
345 0 : _cairo_pen_find_active_cw_vertex_index (const cairo_pen_t *pen,
346 : const cairo_slope_t *slope)
347 : {
348 : int i;
349 :
350 0 : for (i=0; i < pen->num_vertices; i++) {
351 0 : if ((_cairo_slope_compare (slope, &pen->vertices[i].slope_ccw) < 0) &&
352 0 : (_cairo_slope_compare (slope, &pen->vertices[i].slope_cw) >= 0))
353 0 : 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 0 : if (i == pen->num_vertices)
362 0 : i = 0;
363 :
364 0 : 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
373 0 : _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 0 : slope_reverse = *slope;
380 0 : slope_reverse.dx = -slope_reverse.dx;
381 0 : slope_reverse.dy = -slope_reverse.dy;
382 :
383 0 : for (i=pen->num_vertices-1; i >= 0; i--) {
384 0 : if ((_cairo_slope_compare (&pen->vertices[i].slope_ccw, &slope_reverse) >= 0) &&
385 0 : (_cairo_slope_compare (&pen->vertices[i].slope_cw, &slope_reverse) < 0))
386 0 : 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 0 : if (i < 0)
395 0 : i = pen->num_vertices - 1;
396 :
397 0 : return i;
398 : }
|
