src/cairo-pen.c

   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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 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 static int
  42 _cairo_pen_vertices_needed (double tolerance,
  43                             double radius,
  44                             const cairo_matrix_t *matrix);
  45
  46 static void
  47 _cairo_pen_compute_slopes (cairo_pen_t *pen);
  48
  49 cairo_status_t
  50 _cairo_pen_init (cairo_pen_t    *pen,
  51                  double          radius,
  52                  double          tolerance,
  53                  const cairo_matrix_t   *ctm)
  54 {
  55     int i;
  56     int reflect;
  57
  58     if (CAIRO_INJECT_FAULT ())
  59         return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  60
  61     VG (VALGRIND_MAKE_MEM_UNDEFINED (pen, sizeof (cairo_pen_t)));
  62
  63     pen->radius = radius;
  64     pen->tolerance = tolerance;
  65
  66     reflect = _cairo_matrix_compute_determinant (ctm) < 0.;
  67
  68     pen->num_vertices = _cairo_pen_vertices_needed (tolerance,
  69                                                     radius,
  70                                                     ctm);
  71
  72     if (pen->num_vertices > ARRAY_LENGTH (pen->vertices_embedded)) {
  73         pen->vertices = _cairo_malloc_ab (pen->num_vertices,
  74                                           sizeof (cairo_pen_vertex_t));
  75         if (unlikely (pen->vertices == NULL))
  76             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  77     } else {
  78         pen->vertices = pen->vertices_embedded;
  79     }
  80
  81     /*
  82      * Compute pen coordinates.  To generate the right ellipse, compute points around
  83      * a circle in user space and transform them to device space.  To get a consistent
  84      * orientation in device space, flip the pen if the transformation matrix
  85      * is reflecting
  86      */
  87     for (i=0; i < pen->num_vertices; i++) {
  88         double theta = 2 * M_PI * i / (double) pen->num_vertices;
  89         double dx = radius * cos (reflect ? -theta : theta);
  90         double dy = radius * sin (reflect ? -theta : theta);
  91         cairo_pen_vertex_t *v = &pen->vertices[i];
  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);
  95     }
  96
  97     _cairo_pen_compute_slopes (pen);
  98
  99     return CAIRO_STATUS_SUCCESS;
 100 }
 101
 102 void
 103 _cairo_pen_fini (cairo_pen_t *pen)
 104 {
 105     if (pen->vertices != pen->vertices_embedded)
 106         free (pen->vertices);
 107
 108
 109     VG (VALGRIND_MAKE_MEM_NOACCESS (pen, sizeof (cairo_pen_t)));
 110 }
 111
 112 cairo_status_t
 113 _cairo_pen_init_copy (cairo_pen_t *pen, const cairo_pen_t *other)
 114 {
 115     VG (VALGRIND_MAKE_MEM_UNDEFINED (pen, sizeof (cairo_pen_t)));
 116
 117     *pen = *other;
 118
 119     if (CAIRO_INJECT_FAULT ())
 120         return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 121
 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);
 129         }
 130
 131         memcpy (pen->vertices, other->vertices,
 132                 pen->num_vertices * sizeof (cairo_pen_vertex_t));
 133     }
 134
 135     return CAIRO_STATUS_SUCCESS;
 136 }
 137
 138 cairo_status_t
 139 _cairo_pen_add_points (cairo_pen_t *pen, cairo_point_t *point, int num_points)
 140 {
 141     cairo_status_t status;
 142     int num_vertices;
 143     int i;
 144
 145     if (CAIRO_INJECT_FAULT ())
 146         return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 147
 148     num_vertices = pen->num_vertices + num_points;
 149     if (num_vertices > ARRAY_LENGTH (pen->vertices_embedded) ||
 150         pen->vertices != pen->vertices_embedded)
 151     {
 152         cairo_pen_vertex_t *vertices;
 153
 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);
 159
 160             memcpy (vertices, pen->vertices,
 161                     pen->num_vertices * sizeof (cairo_pen_vertex_t));
 162         } else {
 163             vertices = _cairo_realloc_ab (pen->vertices,
 164                                           num_vertices,
 165                                           sizeof (cairo_pen_vertex_t));
 166             if (unlikely (vertices == NULL))
 167                 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 168         }
 169
 170         pen->vertices = vertices;
 171     }
 172
 173     pen->num_vertices = num_vertices;
 174
 175     /* initialize new vertices */
 176     for (i=0; i < num_points; i++)
 177         pen->vertices[pen->num_vertices-num_points+i].point = point[i];
 178
 179     status = _cairo_hull_compute (pen->vertices, &pen->num_vertices);
 180     if (unlikely (status))
 181         return status;
 182
 183     _cairo_pen_compute_slopes (pen);
 184
 185     return CAIRO_STATUS_SUCCESS;
 186 }
 187
 188 /*
 189 The circular pen in user space is transformed into an ellipse in
 190 device space.
 191
 192 We construct the pen by computing points along the circumference
 193 using equally spaced angles.
 194
 195 We show that this approximation to the ellipse has maximum error at the
 196 major axis of the ellipse.
 197
 198 Set
 199
 200             M = major axis length
 201             m = minor axis length
 202
 203 Align 'M' along the X axis and 'm' along the Y axis and draw
 204 an ellipse parameterized by angle 't':
 205
 206             x = M cos t                 y = m sin t
 207
 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.
 212
 213             x+ = M cos (t+∆)          y+ = m sin (t+∆)
 214             x- = M cos (t-∆)          y- = m sin (t-∆)
 215
 216 Now compute the approximation error, E:
 217
 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(∆))
 224
 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(∆))
 231
 232         E² = Ex² + Ey²
 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²
 237
 238 Find the extremum by differentiation wrt t and setting that to zero
 239
 240 ∂(E²)/∂(t) = (1-cos(∆))² (M² - m²) (-2 cos(t) sin(t))
 241
 242          0 = 2 cos (t) sin (t)
 243          0 = sin (2t)
 244          t = nπ
 245
 246 Which is to say that the maximum and minimum errors occur on the
 247 axes of the ellipse at 0 and π radians:
 248
 249         E²(0) = (1-cos(∆))² (M² - m²) + (1-cos(∆))² m²
 250               = (1-cos(∆))² M²
 251         E²(π) = (1-cos(∆))² m²
 252
 253 maximum error = M (1-cos(∆))
 254 minimum error = m (1-cos(∆))
 255
 256 We must make maximum error ≤ tolerance, so compute the ∆ needed:
 257
 258             tolerance = M (1-cos(∆))
 259         tolerance / M = 1 - cos (∆)
 260                cos(∆) = 1 - tolerance/M
 261                     ∆ = acos (1 - tolerance / M);
 262
 263 Remembering that ∆ is half of our angle between vertices,
 264 the number of vertices is then
 265
 266              vertices = ceil(2π/2∆).
 267                       = ceil(π/∆).
 268
 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.
 271 */
 272
 273 static int
 274 _cairo_pen_vertices_needed (double          tolerance,
 275                             double          radius,
 276                             const cairo_matrix_t  *matrix)
 277 {
 278     /*
 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.
 282      */
 283
 284     double  major_axis = _cairo_matrix_transformed_circle_major_axis (matrix,
 285                                                                       radius);
 286
 287     /*
 288      * compute number of vertices needed
 289      */
 290     int     num_vertices;
 291
 292     /* Where tolerance / M is > 1, we use 4 points */
 293     if (tolerance >= major_axis) {
 294         num_vertices = 4;
 295     } else {
 296         double delta = acos (1 - tolerance / major_axis);
 297         num_vertices = ceil (M_PI / delta);
 298
 299         /* number of vertices must be even */
 300         if (num_vertices % 2)
 301             num_vertices++;
 302
 303         /* And we must always have at least 4 vertices. */
 304         if (num_vertices < 4)
 305             num_vertices = 4;
 306     }
 307
 308     return num_vertices;
 309 }
 310
 311 static void
 312 _cairo_pen_compute_slopes (cairo_pen_t *pen)
 313 {
 314     int i, i_prev;
 315     cairo_pen_vertex_t *prev, *v, *next;
 316
 317     for (i=0, i_prev = pen->num_vertices - 1;
 318          i < pen->num_vertices;
 319          i_prev = i++) {
 320         prev = &pen->vertices[i_prev];
 321         v = &pen->vertices[i];
 322         next = &pen->vertices[(i + 1) % pen->num_vertices];
 323
 324         _cairo_slope_init (&v->slope_cw, &prev->point, &v->point);
 325         _cairo_slope_init (&v->slope_ccw, &v->point, &next->point);
 326     }
 327 }
 328 /*
 329  * Find active pen vertex for clockwise edge of stroke at the given slope.
 330  *
 331  * The strictness of the inequalities here is delicate. The issue is
 332  * that the slope_ccw member of one pen vertex will be equivalent to
 333  * the slope_cw member of the next pen vertex in a counterclockwise
 334  * order. However, for this function, we care strongly about which
 335  * vertex is returned.
 336  *
 337  * [I think the "care strongly" above has to do with ensuring that the
 338  * pen's "extra points" from the spline's initial and final slopes are
 339  * properly found when beginning the spline stroking.]
 340  */
 341 int
 342 _cairo_pen_find_active_cw_vertex_index (const cairo_pen_t *pen,
 343                                         const cairo_slope_t *slope)
 344 {
 345     int i;
 346
 347     for (i=0; i < pen->num_vertices; i++) {
 348         if ((_cairo_slope_compare (slope, &pen->vertices[i].slope_ccw) < 0) &&
 349             (_cairo_slope_compare (slope, &pen->vertices[i].slope_cw) >= 0))
 350             break;
 351     }
 352
 353     /* If the desired slope cannot be found between any of the pen
 354      * vertices, then we must have a degenerate pen, (such as a pen
 355      * that's been transformed to a line). In that case, we consider
 356      * the first pen vertex as the appropriate clockwise vertex.
 357      */
 358     if (i == pen->num_vertices)
 359         i = 0;
 360
 361     return i;
 362 }
 363
 364 /* Find active pen vertex for counterclockwise edge of stroke at the given slope.
 365  *
 366  * Note: See the comments for _cairo_pen_find_active_cw_vertex_index
 367  * for some details about the strictness of the inequalities here.
 368  */
 369 int
 370 _cairo_pen_find_active_ccw_vertex_index (const cairo_pen_t *pen,
 371                                          const cairo_slope_t *slope)
 372 {
 373     cairo_slope_t slope_reverse;
 374     int i;
 375
 376     slope_reverse = *slope;
 377     slope_reverse.dx = -slope_reverse.dx;
 378     slope_reverse.dy = -slope_reverse.dy;
 379
 380     for (i=pen->num_vertices-1; i >= 0; i--) {
 381         if ((_cairo_slope_compare (&pen->vertices[i].slope_ccw, &slope_reverse) >= 0) &&
 382             (_cairo_slope_compare (&pen->vertices[i].slope_cw, &slope_reverse) < 0))
 383             break;
 384     }
 385
 386     /* If the desired slope cannot be found between any of the pen
 387      * vertices, then we must have a degenerate pen, (such as a pen
 388      * that's been transformed to a line). In that case, we consider
 389      * the last pen vertex as the appropriate counterclockwise vertex.
 390      */
 391     if (i < 0)
 392         i = pen->num_vertices - 1;
 393
 394     return i;
 395 }
 396
 397 static int
 398 _cairo_pen_stroke_spline_add_convolved_point (cairo_pen_stroke_spline_t *stroker,
 399                                               const cairo_point_t *last_point,
 400                                               const cairo_slope_t *slope,
 401                                               cairo_point_t *last_hull_point,
 402                                               int active,
 403                                               int step)
 404 {
 405     do {
 406         cairo_point_t hull_point;
 407
 408         hull_point.x = last_point->x + stroker->pen.vertices[active].point.x;
 409         hull_point.y = last_point->y + stroker->pen.vertices[active].point.y;
 410         _cairo_polygon_add_edge (&stroker->polygon,
 411                                  last_hull_point, &hull_point,
 412                                  step);
 413         *last_hull_point = hull_point;
 414
 415         /* The strict inequalities here ensure that if a spline slope
 416          * compares identically with either of the slopes of the
 417          * active vertex, then it remains the active vertex. This is
 418          * very important since otherwise we can trigger an infinite
 419          * loop in the case of a degenerate pen, (a line), where
 420          * neither vertex considers itself active for the slope---one
 421          * will consider it as equal and reject, and the other will
 422          * consider it unequal and reject. This is due to the inherent
 423          * ambiguity when comparing slopes that differ by exactly
 424          * pi. */
 425         if (_cairo_slope_compare (slope,
 426                                   &stroker->pen.vertices[active].slope_ccw) > 0)
 427         {
 428             if (++active == stroker->pen.num_vertices)
 429                 active = 0;
 430         }
 431         else if (_cairo_slope_compare (slope,
 432                                        &stroker->pen.vertices[active].slope_cw) < 0)
 433         {
 434             if (--active == -1)
 435                 active = stroker->pen.num_vertices - 1;
 436         }
 437         else
 438         {
 439             return active;
 440         }
 441     } while (TRUE);
 442 }
 443
 444
 445 /* Compute outline of a given spline using the pen.
 446  * The trapezoids needed to fill that outline will be added to traps
 447  */
 448 cairo_status_t
 449 _cairo_pen_stroke_spline (cairo_pen_stroke_spline_t     *stroker,
 450                           double                         tolerance,
 451                           cairo_traps_t                 *traps)
 452 {
 453     cairo_status_t status;
 454     cairo_slope_t slope;
 455
 456     /* If the line width is so small that the pen is reduced to a
 457        single point, then we have nothing to do. */
 458     if (stroker->pen.num_vertices <= 1)
 459         return CAIRO_STATUS_SUCCESS;
 460
 461     /* open the polygon */
 462     slope = stroker->spline.initial_slope;
 463     stroker->forward_vertex =
 464         _cairo_pen_find_active_cw_vertex_index (&stroker->pen, &slope);
 465     stroker->forward_hull_point.x = stroker->last_point.x +
 466         stroker->pen.vertices[stroker->forward_vertex].point.x;
 467     stroker->forward_hull_point.y = stroker->last_point.y +
 468         stroker->pen.vertices[stroker->forward_vertex].point.y;
 469
 470     slope.dx = -slope.dx;
 471     slope.dy = -slope.dy;
 472     stroker->backward_vertex =
 473         _cairo_pen_find_active_cw_vertex_index (&stroker->pen, &slope);
 474     stroker->backward_hull_point.x = stroker->last_point.x +
 475         stroker->pen.vertices[stroker->backward_vertex].point.x;
 476     stroker->backward_hull_point.y = stroker->last_point.y +
 477         stroker->pen.vertices[stroker->backward_vertex].point.y;
 478
 479     _cairo_polygon_add_edge (&stroker->polygon,
 480                              &stroker->backward_hull_point,
 481                              &stroker->forward_hull_point,
 482                              1);
 483
 484     status = _cairo_spline_decompose (&stroker->spline, tolerance);
 485     if (unlikely (status))
 486         return status;
 487
 488     /* close the polygon */
 489     slope = stroker->spline.final_slope;
 490     _cairo_pen_stroke_spline_add_convolved_point (stroker,
 491                                                   &stroker->last_point,
 492                                                   &slope,
 493                                                   &stroker->forward_hull_point,
 494                                                   stroker->forward_vertex,
 495                                                   1);
 496
 497     slope.dx = -slope.dx;
 498     slope.dy = -slope.dy;
 499     _cairo_pen_stroke_spline_add_convolved_point (stroker,
 500                                                   &stroker->last_point,
 501                                                   &slope,
 502                                                   &stroker->backward_hull_point,
 503                                                   stroker->backward_vertex,
 504                                                   -1);
 505
 506     _cairo_polygon_add_edge (&stroker->polygon,
 507                              &stroker->forward_hull_point,
 508                              &stroker->backward_hull_point,
 509                              1);
 510
 511     status = _cairo_polygon_status (&stroker->polygon);
 512     if (unlikely (status))
 513         return status;
 514
 515     status = _cairo_bentley_ottmann_tessellate_polygon (traps,
 516                                                         &stroker->polygon,
 517                                                         CAIRO_FILL_RULE_WINDING);
 518
 519     return status;
 520 }
 521
 522 static cairo_status_t
 523 _cairo_pen_stroke_spline_add_point (void                    *closure,
 524                                     const cairo_point_t     *point)
 525 {
 526     cairo_pen_stroke_spline_t   *stroker = closure;
 527     cairo_slope_t slope;
 528
 529     _cairo_slope_init (&slope, &stroker->last_point, point);
 530     stroker->forward_vertex =
 531         _cairo_pen_stroke_spline_add_convolved_point (stroker,
 532                                                       &stroker->last_point,
 533                                                       &slope,
 534                                                       &stroker->forward_hull_point,
 535                                                       stroker->forward_vertex,
 536                                                       1);
 537
 538     slope.dx = -slope.dx;
 539     slope.dy = -slope.dy;
 540     stroker->backward_vertex =
 541         _cairo_pen_stroke_spline_add_convolved_point (stroker,
 542                                                       &stroker->last_point,
 543                                                       &slope,
 544                                                       &stroker->backward_hull_point,
 545                                                       stroker->backward_vertex,
 546                                                       -1);
 547     stroker->last_point = *point;
 548
 549     return CAIRO_STATUS_SUCCESS;
 550 }
 551
 552 cairo_int_status_t
 553 _cairo_pen_stroke_spline_init (cairo_pen_stroke_spline_t *stroker,
 554                                const cairo_pen_t *pen,
 555                                const cairo_point_t *a,
 556                                const cairo_point_t *b,
 557                                const cairo_point_t *c,
 558                                const cairo_point_t *d)
 559 {
 560     cairo_int_status_t status;
 561
 562     if (! _cairo_spline_init (&stroker->spline,
 563                               _cairo_pen_stroke_spline_add_point,
 564                               stroker,
 565                               a, b, c, d))
 566     {
 567         return CAIRO_INT_STATUS_DEGENERATE;
 568     }
 569
 570     status = _cairo_pen_init_copy (&stroker->pen, pen);
 571     if (unlikely (status))
 572         return status;
 573
 574     _cairo_polygon_init (&stroker->polygon);
 575
 576     stroker->last_point = *a;
 577
 578     return CAIRO_STATUS_SUCCESS;
 579 }
 580
 581 void
 582 _cairo_pen_stroke_spline_fini (cairo_pen_stroke_spline_t *stroker)
 583 {
 584     _cairo_polygon_fini (&stroker->polygon);
 585     _cairo_pen_fini (&stroker->pen);
 586 }