src/cairo-stroke-style.c

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