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 /*
 131  * Computes the period of a dashed stroke style.
 132  * Returns 0 for non-dashed styles.
 133  */
 134 double
 135 _cairo_stroke_style_dash_period (const cairo_stroke_style_t *style)
 136 {
 137     double period;
 138     unsigned int i;
 139
 140     period = 0.0;
 141     for (i = 0; i < style->num_dashes; i++)
 142         period += style->dash[i];
 143
 144     if (style->num_dashes & 1)
 145         period *= 2.0;
 146
 147     return period;
 148 }
 149
 150 /*
 151  * Coefficient of the linear approximation (minimizing square difference)
 152  * of the surface covered by round caps
 153  *
 154  * This can be computed in the following way:
 155  * the area inside the circle with radius w/2 and the region -d/2 <= x <= d/2 is:
 156  *   f(w,d) = 2 * integrate (sqrt (w*w/4 - x*x), x, -d/2, d/2)
 157  * The square difference to a generic linear approximation (c*d) in the range (0,w) would be:
 158  *   integrate ((f(w,d) - c*d)^2, d, 0, w)
 159  * To minimize this difference it is sufficient to find a solution of the differential with
 160  * respect to c:
 161  *   solve ( diff (integrate ((f(w,d) - c*d)^2, d, 0, w), c), c)
 162  * Which leads to c = 9/32*pi*w
 163  * Since we're not interested in the true area, but just in a coverage extimate,
 164  * we always divide the real area by the line width (w).
 165  * The same computation for square caps would be
 166  *   f(w,d) = 2 * integrate(w/2, x, -d/2, d/2)
 167  *   c = 1*w
 168  * but in this case it would not be an approximation, since f is already linear in d.
 169  */
 170 #define ROUND_MINSQ_APPROXIMATION (9*M_PI/32)
 171
 172 /*
 173  * Computes the length of the "on" part of a dashed stroke style,
 174  * taking into account also line caps.
 175  * Returns 0 for non-dashed styles.
 176  */
 177 double
 178 _cairo_stroke_style_dash_stroked (const cairo_stroke_style_t *style)
 179 {
 180     double stroked, cap_scale;
 181     unsigned int i;
 182
 183     switch (style->line_cap) {
 184     default: ASSERT_NOT_REACHED;
 185     case CAIRO_LINE_CAP_BUTT:   cap_scale = 0.0; break;
 186     case CAIRO_LINE_CAP_ROUND:  cap_scale = ROUND_MINSQ_APPROXIMATION; break;
 187     case CAIRO_LINE_CAP_SQUARE: cap_scale = 1.0; break;
 188     }
 189
 190     stroked = 0.0;
 191     if (style->num_dashes & 1) {
 192         /* Each dash element is used both as on and as off. The order in which they are summed is
 193          * irrelevant, so sum the coverage of one dash element, taken both on and off at each iteration */
 194         for (i = 0; i < style->num_dashes; i++)
 195             stroked += style->dash[i] + cap_scale * MIN (style->dash[i], style->line_width);
 196     } else {
 197         /* Even (0, 2, ...) dashes are on and simply counted for the coverage, odd dashes are off, thus
 198          * their coverage is approximated based on the area covered by the caps of adjacent on dases. */
 199         for (i = 0; i + 1 < style->num_dashes; i += 2)
 200             stroked += style->dash[i] + cap_scale * MIN (style->dash[i+1], style->line_width);
 201     }
 202
 203     return stroked;
 204 }
 205
 206 /*
 207  * Verifies if _cairo_stroke_style_dash_approximate should be used to generate
 208  * an approximation of the dash pattern in the specified style, when used for
 209  * stroking a path with the given CTM and tolerance.
 210  * Always %FALSE for non-dashed styles.
 211  */
 212 cairo_bool_t
 213 _cairo_stroke_style_dash_can_approximate (const cairo_stroke_style_t *style,
 214                                           const cairo_matrix_t *ctm,
 215                                           double tolerance)
 216 {
 217     double period;
 218
 219     if (! style->num_dashes)
 220         return FALSE;
 221
 222     period = _cairo_stroke_style_dash_period (style);
 223     return _cairo_matrix_transformed_circle_major_axis (ctm, period) < tolerance;
 224 }
 225
 226 /*
 227  * Create a 2-dashes approximation of a dashed style, by making the "on" and "off"
 228  * parts respect the original ratio.
 229  */
 230 void
 231 _cairo_stroke_style_dash_approximate (const cairo_stroke_style_t *style,
 232                                       const cairo_matrix_t *ctm,
 233                                       double tolerance,
 234                                       double *dash_offset,
 235                                       double *dashes,
 236                                       unsigned int *num_dashes)
 237 {
 238     double coverage, scale, offset;
 239     cairo_bool_t on = TRUE;
 240     unsigned int i = 0;
 241
 242     coverage = _cairo_stroke_style_dash_stroked (style) / _cairo_stroke_style_dash_period (style);
 243     coverage = MIN (coverage, 1.0);
 244     scale = tolerance / _cairo_matrix_transformed_circle_major_axis (ctm, 1.0);
 245
 246     /* We stop searching for a starting point as soon as the
 247      * offset reaches zero.  Otherwise when an initial dash
 248      * segment shrinks to zero it will be skipped over. */
 249     offset = style->dash_offset;
 250     while (offset > 0.0 && offset >= style->dash[i]) {
 251         offset -= style->dash[i];
 252         on = !on;
 253         if (++i == style->num_dashes)
 254             i = 0;
 255     }
 256
 257     *num_dashes = 2;
 258
 259     /*
 260      * We want to create a new dash pattern with the same relative coverage,
 261      * but composed of just 2 elements with total length equal to scale.
 262      * Based on the formula in _cairo_stroke_style_dash_stroked:
 263      * scale * coverage = dashes[0] + cap_scale * MIN (dashes[1], line_width)
 264      *                  = MIN (dashes[0] + cap_scale * (scale - dashes[0]),
 265      *                         dashes[0] + cap_scale * line_width) =
 266      *                  = MIN (dashes[0] * (1 - cap_scale) + cap_scale * scale,
 267      *                         dashes[0] + cap_scale * line_width)
 268      *
 269      * Solving both cases we get:
 270      *   dashes[0] = scale * (coverage - cap_scale) / (1 - cap_scale)
 271      *    when scale - dashes[0] <= line_width
 272      *  dashes[0] = scale * coverage - cap_scale * line_width
 273      *    when scale - dashes[0] > line_width.
 274      *
 275      * Comparing the two cases we get:
 276      *   second > first
 277      *   second > scale * (coverage - cap_scale) / (1 - cap_scale)
 278      *   second - cap_scale * second - scale * coverage + scale * cap_scale > 0
 279      *   (scale * coverage - cap_scale * line_width) - cap_scale * second - scale * coverage + scale * cap_scale > 0
 280      *   - line_width - second + scale > 0
 281      *   scale - second > line_width
 282      * which is the condition for the second solution to be the valid one.
 283      * So when second > first, the second solution is the correct one (i.e.
 284      * the solution is always MAX (first, second).
 285      */
 286     switch (style->line_cap) {
 287     default:
 288         ASSERT_NOT_REACHED;
 289         dashes[0] = 0.0;
 290         break;
 291
 292     case CAIRO_LINE_CAP_BUTT:
 293         /* Simplified formula (substituting 0 for cap_scale): */
 294         dashes[0] = scale * coverage;
 295         break;
 296
 297     case CAIRO_LINE_CAP_ROUND:
 298         dashes[0] = MAX(scale * (coverage - ROUND_MINSQ_APPROXIMATION) / (1.0 - ROUND_MINSQ_APPROXIMATION),
 299                         scale * coverage - ROUND_MINSQ_APPROXIMATION * style->line_width);
 300         break;
 301
 302     case CAIRO_LINE_CAP_SQUARE:
 303         /*
 304          * Special attention is needed to handle the case cap_scale == 1 (since the first solution
 305          * is either indeterminate or -inf in this case). Since dash lengths are always >=0, using
 306          * 0 as first solution always leads to the correct solution.
 307          */
 308         dashes[0] = MAX(0.0, scale * coverage - style->line_width);
 309         break;
 310     }
 311
 312     dashes[1] = scale - dashes[0];
 313
 314     *dash_offset = on ? 0.0 : dashes[0];
 315 }