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_compute_slopes (cairo_pen_t
*pen
);
48 _cairo_pen_init (cairo_pen_t
*pen
,
51 const cairo_matrix_t
*ctm
)
56 if (CAIRO_INJECT_FAULT ())
57 return _cairo_error (CAIRO_STATUS_NO_MEMORY
);
59 VG (VALGRIND_MAKE_MEM_UNDEFINED (pen
, sizeof (cairo_pen_t
)));
62 pen
->tolerance
= tolerance
;
64 reflect
= _cairo_matrix_compute_determinant (ctm
) < 0.;
66 pen
->num_vertices
= _cairo_pen_vertices_needed (tolerance
,
70 if (pen
->num_vertices
> ARRAY_LENGTH (pen
->vertices_embedded
)) {
71 pen
->vertices
= _cairo_malloc_ab (pen
->num_vertices
,
72 sizeof (cairo_pen_vertex_t
));
73 if (unlikely (pen
->vertices
== NULL
))
74 return _cairo_error (CAIRO_STATUS_NO_MEMORY
);
76 pen
->vertices
= pen
->vertices_embedded
;
80 * Compute pen coordinates. To generate the right ellipse, compute points around
81 * a circle in user space and transform them to device space. To get a consistent
82 * orientation in device space, flip the pen if the transformation matrix
85 for (i
=0; i
< pen
->num_vertices
; i
++) {
86 cairo_pen_vertex_t
*v
= &pen
->vertices
[i
];
87 double theta
= 2 * M_PI
* i
/ (double) pen
->num_vertices
, dx
, dy
;
90 dx
= radius
* cos (theta
);
91 dy
= radius
* sin (theta
);
92 cairo_matrix_transform_distance (ctm
, &dx
, &dy
);
93 v
->point
.x
= _cairo_fixed_from_double (dx
);
94 v
->point
.y
= _cairo_fixed_from_double (dy
);
97 _cairo_pen_compute_slopes (pen
);
99 return CAIRO_STATUS_SUCCESS
;
103 _cairo_pen_fini (cairo_pen_t
*pen
)
105 if (pen
->vertices
!= pen
->vertices_embedded
)
106 free (pen
->vertices
);
109 VG (VALGRIND_MAKE_MEM_NOACCESS (pen
, sizeof (cairo_pen_t
)));
113 _cairo_pen_init_copy (cairo_pen_t
*pen
, const cairo_pen_t
*other
)
115 VG (VALGRIND_MAKE_MEM_UNDEFINED (pen
, sizeof (cairo_pen_t
)));
119 if (CAIRO_INJECT_FAULT ())
120 return _cairo_error (CAIRO_STATUS_NO_MEMORY
);
122 pen
->vertices
= pen
->vertices_embedded
;
123 if (pen
->num_vertices
) {
124 if (pen
->num_vertices
> ARRAY_LENGTH (pen
->vertices_embedded
)) {
125 pen
->vertices
= _cairo_malloc_ab (pen
->num_vertices
,
126 sizeof (cairo_pen_vertex_t
));
127 if (unlikely (pen
->vertices
== NULL
))
128 return _cairo_error (CAIRO_STATUS_NO_MEMORY
);
131 memcpy (pen
->vertices
, other
->vertices
,
132 pen
->num_vertices
* sizeof (cairo_pen_vertex_t
));
135 return CAIRO_STATUS_SUCCESS
;
139 _cairo_pen_add_points (cairo_pen_t
*pen
, cairo_point_t
*point
, int num_points
)
141 cairo_status_t status
;
145 if (CAIRO_INJECT_FAULT ())
146 return _cairo_error (CAIRO_STATUS_NO_MEMORY
);
148 num_vertices
= pen
->num_vertices
+ num_points
;
149 if (num_vertices
> ARRAY_LENGTH (pen
->vertices_embedded
) ||
150 pen
->vertices
!= pen
->vertices_embedded
)
152 cairo_pen_vertex_t
*vertices
;
154 if (pen
->vertices
== pen
->vertices_embedded
) {
155 vertices
= _cairo_malloc_ab (num_vertices
,
156 sizeof (cairo_pen_vertex_t
));
157 if (unlikely (vertices
== NULL
))
158 return _cairo_error (CAIRO_STATUS_NO_MEMORY
);
160 memcpy (vertices
, pen
->vertices
,
161 pen
->num_vertices
* sizeof (cairo_pen_vertex_t
));
163 vertices
= _cairo_realloc_ab (pen
->vertices
,
165 sizeof (cairo_pen_vertex_t
));
166 if (unlikely (vertices
== NULL
))
167 return _cairo_error (CAIRO_STATUS_NO_MEMORY
);
170 pen
->vertices
= vertices
;
173 pen
->num_vertices
= num_vertices
;
175 /* initialize new vertices */
176 for (i
=0; i
< num_points
; i
++)
177 pen
->vertices
[pen
->num_vertices
-num_points
+i
].point
= point
[i
];
179 status
= _cairo_hull_compute (pen
->vertices
, &pen
->num_vertices
);
180 if (unlikely (status
))
183 _cairo_pen_compute_slopes (pen
);
185 return CAIRO_STATUS_SUCCESS
;
189 The circular pen in user space is transformed into an ellipse in
192 We construct the pen by computing points along the circumference
193 using equally spaced angles.
195 We show that this approximation to the ellipse has maximum error at the
196 major axis of the ellipse.
200 M = major axis length
201 m = minor axis length
203 Align 'M' along the X axis and 'm' along the Y axis and draw
204 an ellipse parameterized by angle 't':
206 x = M cos t y = m sin t
208 Perturb t by ± d and compute two new points (x+,y+), (x-,y-).
209 The distance from the average of these two points to (x,y) represents
210 the maximum error in approximating the ellipse with a polygon formed
211 from vertices 2∆ radians apart.
213 x+ = M cos (t+∆) y+ = m sin (t+∆)
214 x- = M cos (t-∆) y- = m sin (t-∆)
216 Now compute the approximation error, E:
218 Ex = (x - (x+ + x-) / 2)
219 Ex = (M cos(t) - (Mcos(t+∆) + Mcos(t-∆))/2)
220 = M (cos(t) - (cos(t)cos(∆) + sin(t)sin(∆) +
221 cos(t)cos(∆) - sin(t)sin(∆))/2)
222 = M(cos(t) - cos(t)cos(∆))
223 = M cos(t) (1 - cos(∆))
225 Ey = y - (y+ - y-) / 2
226 = m sin (t) - (m sin(t+∆) + m sin(t-∆)) / 2
227 = m (sin(t) - (sin(t)cos(∆) + cos(t)sin(∆) +
228 sin(t)cos(∆) - cos(t)sin(∆))/2)
229 = m (sin(t) - sin(t)cos(∆))
230 = m sin(t) (1 - cos(∆))
233 = (M cos(t) (1 - cos (∆)))² + (m sin(t) (1-cos(∆)))²
234 = (1 - cos(∆))² (M² cos²(t) + m² sin²(t))
235 = (1 - cos(∆))² ((m² + M² - m²) cos² (t) + m² sin²(t))
236 = (1 - cos(∆))² (M² - m²) cos² (t) + (1 - cos(∆))² m²
238 Find the extremum by differentiation wrt t and setting that to zero
240 ∂(E²)/∂(t) = (1-cos(∆))² (M² - m²) (-2 cos(t) sin(t))
242 0 = 2 cos (t) sin (t)
246 Which is to say that the maximum and minimum errors occur on the
247 axes of the ellipse at 0 and π radians:
249 E²(0) = (1-cos(∆))² (M² - m²) + (1-cos(∆))² m²
251 E²(π) = (1-cos(∆))² m²
253 maximum error = M (1-cos(∆))
254 minimum error = m (1-cos(∆))
256 We must make maximum error ≤ tolerance, so compute the ∆ needed:
258 tolerance = M (1-cos(∆))
259 tolerance / M = 1 - cos (∆)
260 cos(∆) = 1 - tolerance/M
261 ∆ = acos (1 - tolerance / M);
263 Remembering that ∆ is half of our angle between vertices,
264 the number of vertices is then
266 vertices = ceil(2π/2∆).
269 Note that this also equation works for M == m (a circle) as it
270 doesn't matter where on the circle the error is computed.
274 _cairo_pen_vertices_needed (double tolerance
,
276 const cairo_matrix_t
*matrix
)
279 * the pen is a circle that gets transformed to an ellipse by matrix.
280 * compute major axis length for a pen with the specified radius.
281 * we don't need the minor axis length.
283 double major_axis
= _cairo_matrix_transformed_circle_major_axis (matrix
,
287 if (tolerance
>= 4*major_axis
) { /* XXX relaxed from 2*major for inkscape */
289 } else if (tolerance
>= major_axis
) {
292 num_vertices
= ceil (2*M_PI
/ acos (1 - tolerance
/ major_axis
));
294 /* number of vertices must be even */
295 if (num_vertices
% 2)
298 /* And we must always have at least 4 vertices. */
299 if (num_vertices
< 4)
307 _cairo_pen_compute_slopes (cairo_pen_t
*pen
)
310 cairo_pen_vertex_t
*prev
, *v
, *next
;
312 for (i
=0, i_prev
= pen
->num_vertices
- 1;
313 i
< pen
->num_vertices
;
315 prev
= &pen
->vertices
[i_prev
];
316 v
= &pen
->vertices
[i
];
317 next
= &pen
->vertices
[(i
+ 1) % pen
->num_vertices
];
319 _cairo_slope_init (&v
->slope_cw
, &prev
->point
, &v
->point
);
320 _cairo_slope_init (&v
->slope_ccw
, &v
->point
, &next
->point
);
324 * Find active pen vertex for clockwise edge of stroke at the given slope.
326 * The strictness of the inequalities here is delicate. The issue is
327 * that the slope_ccw member of one pen vertex will be equivalent to
328 * the slope_cw member of the next pen vertex in a counterclockwise
329 * order. However, for this function, we care strongly about which
330 * vertex is returned.
332 * [I think the "care strongly" above has to do with ensuring that the
333 * pen's "extra points" from the spline's initial and final slopes are
334 * properly found when beginning the spline stroking.]
337 _cairo_pen_find_active_cw_vertex_index (const cairo_pen_t
*pen
,
338 const cairo_slope_t
*slope
)
342 for (i
=0; i
< pen
->num_vertices
; i
++) {
343 if ((_cairo_slope_compare (slope
, &pen
->vertices
[i
].slope_ccw
) < 0) &&
344 (_cairo_slope_compare (slope
, &pen
->vertices
[i
].slope_cw
) >= 0))
348 /* If the desired slope cannot be found between any of the pen
349 * vertices, then we must have a degenerate pen, (such as a pen
350 * that's been transformed to a line). In that case, we consider
351 * the first pen vertex as the appropriate clockwise vertex.
353 if (i
== pen
->num_vertices
)
359 /* Find active pen vertex for counterclockwise edge of stroke at the given slope.
361 * Note: See the comments for _cairo_pen_find_active_cw_vertex_index
362 * for some details about the strictness of the inequalities here.
365 _cairo_pen_find_active_ccw_vertex_index (const cairo_pen_t
*pen
,
366 const cairo_slope_t
*slope
)
368 cairo_slope_t slope_reverse
;
371 slope_reverse
= *slope
;
372 slope_reverse
.dx
= -slope_reverse
.dx
;
373 slope_reverse
.dy
= -slope_reverse
.dy
;
375 for (i
=pen
->num_vertices
-1; i
>= 0; i
--) {
376 if ((_cairo_slope_compare (&pen
->vertices
[i
].slope_ccw
, &slope_reverse
) >= 0) &&
377 (_cairo_slope_compare (&pen
->vertices
[i
].slope_cw
, &slope_reverse
) < 0))
381 /* If the desired slope cannot be found between any of the pen
382 * vertices, then we must have a degenerate pen, (such as a pen
383 * that's been transformed to a line). In that case, we consider
384 * the last pen vertex as the appropriate counterclockwise vertex.
387 i
= pen
->num_vertices
- 1;
393 _cairo_pen_find_active_cw_vertices (const cairo_pen_t
*pen
,
394 const cairo_slope_t
*in
,
395 const cairo_slope_t
*out
,
396 int *start
, int *stop
)
399 int lo
= 0, hi
= pen
->num_vertices
;
404 if (_cairo_slope_compare (&pen
->vertices
[i
].slope_cw
, in
) < 0)
409 } while (hi
- lo
> 1);
410 if (_cairo_slope_compare (&pen
->vertices
[i
].slope_cw
, in
) < 0)
411 if (++i
== pen
->num_vertices
)
415 if (_cairo_slope_compare (out
, &pen
->vertices
[i
].slope_ccw
) >= 0) {
417 hi
= i
+ pen
->num_vertices
;
421 if (j
>= pen
->num_vertices
)
422 j
-= pen
->num_vertices
;
423 if (_cairo_slope_compare (&pen
->vertices
[j
].slope_cw
, out
) > 0)
428 } while (hi
- lo
> 1);
429 if (i
>= pen
->num_vertices
)
430 i
-= pen
->num_vertices
;
436 _cairo_pen_find_active_ccw_vertices (const cairo_pen_t
*pen
,
437 const cairo_slope_t
*in
,
438 const cairo_slope_t
*out
,
439 int *start
, int *stop
)
441 int lo
= 0, hi
= pen
->num_vertices
;
446 if (_cairo_slope_compare (in
, &pen
->vertices
[i
].slope_ccw
) < 0)
451 } while (hi
- lo
> 1);
452 if (_cairo_slope_compare (in
, &pen
->vertices
[i
].slope_ccw
) < 0)
453 if (++i
== pen
->num_vertices
)
457 if (_cairo_slope_compare (&pen
->vertices
[i
].slope_cw
, out
) <= 0) {
459 hi
= i
+ pen
->num_vertices
;
463 if (j
>= pen
->num_vertices
)
464 j
-= pen
->num_vertices
;
465 if (_cairo_slope_compare (out
, &pen
->vertices
[j
].slope_ccw
) > 0)
470 } while (hi
- lo
> 1);
471 if (i
>= pen
->num_vertices
)
472 i
-= pen
->num_vertices
;