src/cairo-traps.c

   1 /* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */
   2 /*
   3  * Copyright © 2002 Keith Packard
   4  * Copyright © 2007 Red Hat, Inc.
   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 Keith Packard
  32  *
  33  * Contributor(s):
  34  *      Keith R. Packard <keithp@keithp.com>
  35  *      Carl D. Worth <cworth@cworth.org>
  36  *
  37  * 2002-07-15: Converted from XRenderCompositeDoublePoly to #cairo_trap_t. Carl D. Worth
  38  */
  39
  40 #include "cairoint.h"
  41
  42 #include "cairo-box-inline.h"
  43 #include "cairo-boxes-private.h"
  44 #include "cairo-error-private.h"
  45 #include "cairo-region-private.h"
  46 #include "cairo-slope-private.h"
  47 #include "cairo-traps-private.h"
  48 #include "cairo-spans-private.h"
  49
  50 /* private functions */
  51
  52 void
  53 _cairo_traps_init (cairo_traps_t *traps)
  54 {
  55     VG (VALGRIND_MAKE_MEM_UNDEFINED (traps, sizeof (cairo_traps_t)));
  56
  57     traps->status = CAIRO_STATUS_SUCCESS;
  58
  59     traps->maybe_region = 1;
  60     traps->is_rectilinear = 0;
  61     traps->is_rectangular = 0;
  62
  63     traps->num_traps = 0;
  64
  65     traps->traps_size = ARRAY_LENGTH (traps->traps_embedded);
  66     traps->traps = traps->traps_embedded;
  67
  68     traps->num_limits = 0;
  69     traps->has_intersections = FALSE;
  70 }
  71
  72 void
  73 _cairo_traps_limit (cairo_traps_t       *traps,
  74                     const cairo_box_t   *limits,
  75                     int                  num_limits)
  76 {
  77     int i;
  78
  79     traps->limits = limits;
  80     traps->num_limits = num_limits;
  81
  82     traps->bounds = limits[0];
  83     for (i = 1; i < num_limits; i++)
  84         _cairo_box_add_box (&traps->bounds, &limits[i]);
  85 }
  86
  87 void
  88 _cairo_traps_init_with_clip (cairo_traps_t *traps,
  89                              const cairo_clip_t *clip)
  90 {
  91     _cairo_traps_init (traps);
  92     if (clip)
  93         _cairo_traps_limit (traps, clip->boxes, clip->num_boxes);
  94 }
  95
  96 void
  97 _cairo_traps_clear (cairo_traps_t *traps)
  98 {
  99     traps->status = CAIRO_STATUS_SUCCESS;
 100
 101     traps->maybe_region = 1;
 102     traps->is_rectilinear = 0;
 103     traps->is_rectangular = 0;
 104
 105     traps->num_traps = 0;
 106     traps->has_intersections = FALSE;
 107 }
 108
 109 void
 110 _cairo_traps_fini (cairo_traps_t *traps)
 111 {
 112     if (traps->traps != traps->traps_embedded)
 113         free (traps->traps);
 114
 115     VG (VALGRIND_MAKE_MEM_NOACCESS (traps, sizeof (cairo_traps_t)));
 116 }
 117
 118 /* make room for at least one more trap */
 119 static cairo_bool_t
 120 _cairo_traps_grow (cairo_traps_t *traps)
 121 {
 122     cairo_trapezoid_t *new_traps;
 123     int new_size = 4 * traps->traps_size;
 124
 125     if (CAIRO_INJECT_FAULT ()) {
 126         traps->status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
 127         return FALSE;
 128     }
 129
 130     if (traps->traps == traps->traps_embedded) {
 131         new_traps = _cairo_malloc_ab (new_size, sizeof (cairo_trapezoid_t));
 132         if (new_traps != NULL)
 133             memcpy (new_traps, traps->traps, sizeof (traps->traps_embedded));
 134     } else {
 135         new_traps = _cairo_realloc_ab (traps->traps,
 136                                        new_size, sizeof (cairo_trapezoid_t));
 137     }
 138
 139     if (unlikely (new_traps == NULL)) {
 140         traps->status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
 141         return FALSE;
 142     }
 143
 144     traps->traps = new_traps;
 145     traps->traps_size = new_size;
 146     return TRUE;
 147 }
 148
 149 void
 150 _cairo_traps_add_trap (cairo_traps_t *traps,
 151                        cairo_fixed_t top, cairo_fixed_t bottom,
 152                        cairo_line_t *left, cairo_line_t *right)
 153 {
 154     cairo_trapezoid_t *trap;
 155
 156     if (unlikely (traps->num_traps == traps->traps_size)) {
 157         if (unlikely (! _cairo_traps_grow (traps)))
 158             return;
 159     }
 160
 161     trap = &traps->traps[traps->num_traps++];
 162     trap->top = top;
 163     trap->bottom = bottom;
 164     trap->left = *left;
 165     trap->right = *right;
 166 }
 167
 168 static void
 169 _cairo_traps_add_clipped_trap (cairo_traps_t *traps,
 170                                cairo_fixed_t _top, cairo_fixed_t _bottom,
 171                                cairo_line_t *_left, cairo_line_t *_right)
 172 {
 173     /* Note: With the goofy trapezoid specification, (where an
 174      * arbitrary two points on the lines can specified for the left
 175      * and right edges), these limit checks would not work in
 176      * general. For example, one can imagine a trapezoid entirely
 177      * within the limits, but with two points used to specify the left
 178      * edge entirely to the right of the limits.  Fortunately, for our
 179      * purposes, cairo will never generate such a crazy
 180      * trapezoid. Instead, cairo always uses for its points the
 181      * extreme positions of the edge that are visible on at least some
 182      * trapezoid. With this constraint, it's impossible for both
 183      * points to be outside the limits while the relevant edge is
 184      * entirely inside the limits.
 185      */
 186     if (traps->num_limits) {
 187         const cairo_box_t *b = &traps->bounds;
 188         cairo_fixed_t top = _top, bottom = _bottom;
 189         cairo_line_t left = *_left, right = *_right;
 190
 191         /* Trivially reject if trapezoid is entirely to the right or
 192          * to the left of the limits. */
 193         if (left.p1.x >= b->p2.x && left.p2.x >= b->p2.x)
 194             return;
 195
 196         if (right.p1.x <= b->p1.x && right.p2.x <= b->p1.x)
 197             return;
 198
 199         /* And reject if the trapezoid is entirely above or below */
 200         if (top >= b->p2.y || bottom <= b->p1.y)
 201             return;
 202
 203         /* Otherwise, clip the trapezoid to the limits. We only clip
 204          * where an edge is entirely outside the limits. If we wanted
 205          * to be more clever, we could handle cases where a trapezoid
 206          * edge intersects the edge of the limits, but that would
 207          * require slicing this trapezoid into multiple trapezoids,
 208          * and I'm not sure the effort would be worth it. */
 209         if (top < b->p1.y)
 210             top = b->p1.y;
 211
 212         if (bottom > b->p2.y)
 213             bottom = b->p2.y;
 214
 215         if (left.p1.x <= b->p1.x && left.p2.x <= b->p1.x)
 216             left.p1.x = left.p2.x = b->p1.x;
 217
 218         if (right.p1.x >= b->p2.x && right.p2.x >= b->p2.x)
 219             right.p1.x = right.p2.x = b->p2.x;
 220
 221         /* Trivial discards for empty trapezoids that are likely to
 222          * be produced by our tessellators (most notably convex_quad
 223          * when given a simple rectangle).
 224          */
 225         if (top >= bottom)
 226             return;
 227
 228         /* cheap colinearity check */
 229         if (right.p1.x <= left.p1.x && right.p1.y == left.p1.y &&
 230             right.p2.x <= left.p2.x && right.p2.y == left.p2.y)
 231             return;
 232
 233         _cairo_traps_add_trap (traps, top, bottom, &left, &right);
 234     } else
 235         _cairo_traps_add_trap (traps, _top, _bottom, _left, _right);
 236 }
 237
 238 static int
 239 _compare_point_fixed_by_y (const void *av, const void *bv)
 240 {
 241     const cairo_point_t *a = av, *b = bv;
 242     int ret = a->y - b->y;
 243     if (ret == 0)
 244         ret = a->x - b->x;
 245     return ret;
 246 }
 247
 248 void
 249 _cairo_traps_tessellate_convex_quad (cairo_traps_t *traps,
 250                                      const cairo_point_t q[4])
 251 {
 252     int a, b, c, d;
 253     int i;
 254     cairo_slope_t ab, ad;
 255     cairo_bool_t b_left_of_d;
 256     cairo_line_t left;
 257     cairo_line_t right;
 258
 259     /* Choose a as a point with minimal y */
 260     a = 0;
 261     for (i = 1; i < 4; i++)
 262         if (_compare_point_fixed_by_y (&q[i], &q[a]) < 0)
 263             a = i;
 264
 265     /* b and d are adjacent to a, while c is opposite */
 266     b = (a + 1) % 4;
 267     c = (a + 2) % 4;
 268     d = (a + 3) % 4;
 269
 270     /* Choose between b and d so that b.y is less than d.y */
 271     if (_compare_point_fixed_by_y (&q[d], &q[b]) < 0) {
 272         b = (a + 3) % 4;
 273         d = (a + 1) % 4;
 274     }
 275
 276     /* Without freedom left to choose anything else, we have four
 277      * cases to tessellate.
 278      *
 279      * First, we have to determine the Y-axis sort of the four
 280      * vertices, (either abcd or abdc). After that we need to detemine
 281      * which edges will be "left" and which will be "right" in the
 282      * resulting trapezoids. This can be determined by computing a
 283      * slope comparison of ab and ad to determine if b is left of d or
 284      * not.
 285      *
 286      * Note that "left of" here is in the sense of which edges should
 287      * be the left vs. right edges of the trapezoid. In particular, b
 288      * left of d does *not* mean that b.x is less than d.x.
 289      *
 290      * This should hopefully be made clear in the lame ASCII art
 291      * below. Since the same slope comparison is used in all cases, we
 292      * compute it before testing for the Y-value sort. */
 293
 294     /* Note: If a == b then the ab slope doesn't give us any
 295      * information. In that case, we can replace it with the ac (or
 296      * equivalenly the bc) slope which gives us exactly the same
 297      * information we need. At worst the names of the identifiers ab
 298      * and b_left_of_d are inaccurate in this case, (would be ac, and
 299      * c_left_of_d). */
 300     if (q[a].x == q[b].x && q[a].y == q[b].y)
 301         _cairo_slope_init (&ab, &q[a], &q[c]);
 302     else
 303         _cairo_slope_init (&ab, &q[a], &q[b]);
 304
 305     _cairo_slope_init (&ad, &q[a], &q[d]);
 306
 307     b_left_of_d = _cairo_slope_compare (&ab, &ad) > 0;
 308
 309     if (q[c].y <= q[d].y) {
 310         if (b_left_of_d) {
 311             /* Y-sort is abcd and b is left of d, (slope(ab) > slope (ad))
 312              *
 313              *                      top bot left right
 314              *        _a  a  a
 315              *      / /  /|  |\      a.y b.y  ab   ad
 316              *     b /  b |  b \
 317              *    / /   | |   \ \    b.y c.y  bc   ad
 318              *   c /    c |    c \
 319              *  | /      \|     \ \  c.y d.y  cd   ad
 320              *  d         d       d
 321              */
 322             left.p1  = q[a]; left.p2  = q[b];
 323             right.p1 = q[a]; right.p2 = q[d];
 324             _cairo_traps_add_clipped_trap (traps, q[a].y, q[b].y, &left, &right);
 325             left.p1  = q[b]; left.p2  = q[c];
 326             _cairo_traps_add_clipped_trap (traps, q[b].y, q[c].y, &left, &right);
 327             left.p1  = q[c]; left.p2  = q[d];
 328             _cairo_traps_add_clipped_trap (traps, q[c].y, q[d].y, &left, &right);
 329         } else {
 330             /* Y-sort is abcd and b is right of d, (slope(ab) <= slope (ad))
 331              *
 332              *       a  a  a_
 333              *      /|  |\  \ \     a.y b.y  ad  ab
 334              *     / b  | b  \ b
 335              *    / /   | |   \ \   b.y c.y  ad  bc
 336              *   / c    | c    \ c
 337              *  / /     |/      \ | c.y d.y  ad  cd
 338              *  d       d         d
 339              */
 340             left.p1  = q[a]; left.p2  = q[d];
 341             right.p1 = q[a]; right.p2 = q[b];
 342             _cairo_traps_add_clipped_trap (traps, q[a].y, q[b].y, &left, &right);
 343             right.p1 = q[b]; right.p2 = q[c];
 344             _cairo_traps_add_clipped_trap (traps, q[b].y, q[c].y, &left, &right);
 345             right.p1 = q[c]; right.p2 = q[d];
 346             _cairo_traps_add_clipped_trap (traps, q[c].y, q[d].y, &left, &right);
 347         }
 348     } else {
 349         if (b_left_of_d) {
 350             /* Y-sort is abdc and b is left of d, (slope (ab) > slope (ad))
 351              *
 352              *        a   a     a
 353              *       //  / \    |\     a.y b.y  ab  ad
 354              *     /b/  b   \   b \
 355              *    / /    \   \   \ \   b.y d.y  bc  ad
 356              *   /d/      \   d   \ d
 357              *  //         \ /     \|  d.y c.y  bc  dc
 358              *  c           c       c
 359              */
 360             left.p1  = q[a]; left.p2  = q[b];
 361             right.p1 = q[a]; right.p2 = q[d];
 362             _cairo_traps_add_clipped_trap (traps, q[a].y, q[b].y, &left, &right);
 363             left.p1  = q[b]; left.p2  = q[c];
 364             _cairo_traps_add_clipped_trap (traps, q[b].y, q[d].y, &left, &right);
 365             right.p1 = q[d]; right.p2 = q[c];
 366             _cairo_traps_add_clipped_trap (traps, q[d].y, q[c].y, &left, &right);
 367         } else {
 368             /* Y-sort is abdc and b is right of d, (slope (ab) <= slope (ad))
 369              *
 370              *      a     a   a
 371              *     /|    / \  \\       a.y b.y  ad  ab
 372              *    / b   /   b  \b\
 373              *   / /   /   /    \ \    b.y d.y  ad  bc
 374              *  d /   d   /      \d\
 375              *  |/     \ /         \\  d.y c.y  dc  bc
 376              *  c       c          c
 377              */
 378             left.p1  = q[a]; left.p2  = q[d];
 379             right.p1 = q[a]; right.p2 = q[b];
 380             _cairo_traps_add_clipped_trap (traps, q[a].y, q[b].y, &left, &right);
 381             right.p1 = q[b]; right.p2 = q[c];
 382             _cairo_traps_add_clipped_trap (traps, q[b].y, q[d].y, &left, &right);
 383             left.p1  = q[d]; left.p2  = q[c];
 384             _cairo_traps_add_clipped_trap (traps, q[d].y, q[c].y, &left, &right);
 385         }
 386     }
 387 }
 388
 389 /* A triangle is simply a degenerate case of a convex
 390  * quadrilateral. We would not benefit from having any distinct
 391  * implementation of triangle vs. quadrilateral tessellation here. */
 392 void
 393 _cairo_traps_tessellate_triangle (cairo_traps_t *traps,
 394                                   const cairo_point_t t[3])
 395 {
 396     cairo_point_t quad[4];
 397
 398     quad[0] = t[0];
 399     quad[1] = t[0];
 400     quad[2] = t[1];
 401     quad[3] = t[2];
 402
 403     _cairo_traps_tessellate_convex_quad (traps, quad);
 404 }
 405
 406
 407 /**
 408  * _cairo_traps_init_boxes:
 409  * @traps: a #cairo_traps_t
 410  * @box: an array box that will each be converted to a single trapezoid
 411  *       to store in @traps.
 412  *
 413  * Initializes a #cairo_traps_t to contain an array of rectangular
 414  * trapezoids.
 415  **/
 416 cairo_status_t
 417 _cairo_traps_init_boxes (cairo_traps_t      *traps,
 418                          const cairo_boxes_t *boxes)
 419 {
 420     cairo_trapezoid_t *trap;
 421     const struct _cairo_boxes_chunk *chunk;
 422
 423     _cairo_traps_init (traps);
 424
 425     while (traps->traps_size < boxes->num_boxes) {
 426         if (unlikely (! _cairo_traps_grow (traps))) {
 427             _cairo_traps_fini (traps);
 428             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 429         }
 430     }
 431
 432     traps->num_traps = boxes->num_boxes;
 433     traps->is_rectilinear = TRUE;
 434     traps->is_rectangular = TRUE;
 435     traps->maybe_region = boxes->is_pixel_aligned;
 436
 437     trap = &traps->traps[0];
 438     for (chunk = &boxes->chunks; chunk != NULL; chunk = chunk->next) {
 439         const cairo_box_t *box;
 440         int i;
 441
 442         box = chunk->base;
 443         for (i = 0; i < chunk->count; i++) {
 444             trap->top    = box->p1.y;
 445             trap->bottom = box->p2.y;
 446
 447             trap->left.p1   = box->p1;
 448             trap->left.p2.x = box->p1.x;
 449             trap->left.p2.y = box->p2.y;
 450
 451             trap->right.p1.x = box->p2.x;
 452             trap->right.p1.y = box->p1.y;
 453             trap->right.p2   = box->p2;
 454
 455             box++, trap++;
 456         }
 457     }
 458
 459     return CAIRO_STATUS_SUCCESS;
 460 }
 461
 462 cairo_status_t
 463 _cairo_traps_tessellate_rectangle (cairo_traps_t *traps,
 464                                    const cairo_point_t *top_left,
 465                                    const cairo_point_t *bottom_right)
 466 {
 467     cairo_line_t left;
 468     cairo_line_t right;
 469     cairo_fixed_t top, bottom;
 470
 471     if (top_left->y == bottom_right->y)
 472         return CAIRO_STATUS_SUCCESS;
 473
 474     if (top_left->x == bottom_right->x)
 475         return CAIRO_STATUS_SUCCESS;
 476
 477      left.p1.x =  left.p2.x = top_left->x;
 478      left.p1.y = right.p1.y = top_left->y;
 479     right.p1.x = right.p2.x = bottom_right->x;
 480      left.p2.y = right.p2.y = bottom_right->y;
 481
 482      top = top_left->y;
 483      bottom = bottom_right->y;
 484
 485     if (traps->num_limits) {
 486         cairo_bool_t reversed;
 487         int n;
 488
 489         if (top >= traps->bounds.p2.y || bottom <= traps->bounds.p1.y)
 490             return CAIRO_STATUS_SUCCESS;
 491
 492         /* support counter-clockwise winding for rectangular tessellation */
 493         reversed = top_left->x > bottom_right->x;
 494         if (reversed) {
 495             right.p1.x = right.p2.x = top_left->x;
 496             left.p1.x = left.p2.x = bottom_right->x;
 497         }
 498
 499         if (left.p1.x >= traps->bounds.p2.x || right.p1.x <= traps->bounds.p1.x)
 500             return CAIRO_STATUS_SUCCESS;
 501
 502         for (n = 0; n < traps->num_limits; n++) {
 503             const cairo_box_t *limits = &traps->limits[n];
 504             cairo_line_t _left, _right;
 505             cairo_fixed_t _top, _bottom;
 506
 507             if (top >= limits->p2.y)
 508                 continue;
 509             if (bottom <= limits->p1.y)
 510                 continue;
 511
 512             /* Trivially reject if trapezoid is entirely to the right or
 513              * to the left of the limits. */
 514             if (left.p1.x >= limits->p2.x)
 515                 continue;
 516             if (right.p1.x <= limits->p1.x)
 517                 continue;
 518
 519             /* Otherwise, clip the trapezoid to the limits. */
 520             _top = top;
 521             if (_top < limits->p1.y)
 522                 _top = limits->p1.y;
 523
 524             _bottom = bottom;
 525             if (_bottom > limits->p2.y)
 526                 _bottom = limits->p2.y;
 527
 528             if (_bottom <= _top)
 529                 continue;
 530
 531             _left = left;
 532             if (_left.p1.x < limits->p1.x) {
 533                 _left.p1.x = limits->p1.x;
 534                 _left.p1.y = limits->p1.y;
 535                 _left.p2.x = limits->p1.x;
 536                 _left.p2.y = limits->p2.y;
 537             }
 538
 539             _right = right;
 540             if (_right.p1.x > limits->p2.x) {
 541                 _right.p1.x = limits->p2.x;
 542                 _right.p1.y = limits->p1.y;
 543                 _right.p2.x = limits->p2.x;
 544                 _right.p2.y = limits->p2.y;
 545             }
 546
 547             if (left.p1.x >= right.p1.x)
 548                 continue;
 549
 550             if (reversed)
 551                 _cairo_traps_add_trap (traps, _top, _bottom, &_right, &_left);
 552             else
 553                 _cairo_traps_add_trap (traps, _top, _bottom, &_left, &_right);
 554         }
 555     } else {
 556         _cairo_traps_add_trap (traps, top, bottom, &left, &right);
 557     }
 558
 559     return traps->status;
 560 }
 561
 562 void
 563 _cairo_traps_translate (cairo_traps_t *traps, int x, int y)
 564 {
 565     cairo_fixed_t xoff, yoff;
 566     cairo_trapezoid_t *t;
 567     int i;
 568
 569     /* Ugh. The cairo_composite/(Render) interface doesn't allow
 570        an offset for the trapezoids. Need to manually shift all
 571        the coordinates to align with the offset origin of the
 572        intermediate surface. */
 573
 574     xoff = _cairo_fixed_from_int (x);
 575     yoff = _cairo_fixed_from_int (y);
 576
 577     for (i = 0, t = traps->traps; i < traps->num_traps; i++, t++) {
 578         t->top += yoff;
 579         t->bottom += yoff;
 580         t->left.p1.x += xoff;
 581         t->left.p1.y += yoff;
 582         t->left.p2.x += xoff;
 583         t->left.p2.y += yoff;
 584         t->right.p1.x += xoff;
 585         t->right.p1.y += yoff;
 586         t->right.p2.x += xoff;
 587         t->right.p2.y += yoff;
 588     }
 589 }
 590
 591 void
 592 _cairo_trapezoid_array_translate_and_scale (cairo_trapezoid_t *offset_traps,
 593                                             cairo_trapezoid_t *src_traps,
 594                                             int num_traps,
 595                                             double tx, double ty,
 596                                             double sx, double sy)
 597 {
 598     int i;
 599     cairo_fixed_t xoff = _cairo_fixed_from_double (tx);
 600     cairo_fixed_t yoff = _cairo_fixed_from_double (ty);
 601
 602     if (sx == 1.0 && sy == 1.0) {
 603         for (i = 0; i < num_traps; i++) {
 604             offset_traps[i].top = src_traps[i].top + yoff;
 605             offset_traps[i].bottom = src_traps[i].bottom + yoff;
 606             offset_traps[i].left.p1.x = src_traps[i].left.p1.x + xoff;
 607             offset_traps[i].left.p1.y = src_traps[i].left.p1.y + yoff;
 608             offset_traps[i].left.p2.x = src_traps[i].left.p2.x + xoff;
 609             offset_traps[i].left.p2.y = src_traps[i].left.p2.y + yoff;
 610             offset_traps[i].right.p1.x = src_traps[i].right.p1.x + xoff;
 611             offset_traps[i].right.p1.y = src_traps[i].right.p1.y + yoff;
 612             offset_traps[i].right.p2.x = src_traps[i].right.p2.x + xoff;
 613             offset_traps[i].right.p2.y = src_traps[i].right.p2.y + yoff;
 614         }
 615     } else {
 616         cairo_fixed_t xsc = _cairo_fixed_from_double (sx);
 617         cairo_fixed_t ysc = _cairo_fixed_from_double (sy);
 618
 619         for (i = 0; i < num_traps; i++) {
 620             offset_traps[i].top = _cairo_fixed_mul (src_traps[i].top + yoff, ysc);
 621             offset_traps[i].bottom = _cairo_fixed_mul (src_traps[i].bottom + yoff, ysc);
 622             offset_traps[i].left.p1.x = _cairo_fixed_mul (src_traps[i].left.p1.x + xoff, xsc);
 623             offset_traps[i].left.p1.y = _cairo_fixed_mul (src_traps[i].left.p1.y + yoff, ysc);
 624             offset_traps[i].left.p2.x = _cairo_fixed_mul (src_traps[i].left.p2.x + xoff, xsc);
 625             offset_traps[i].left.p2.y = _cairo_fixed_mul (src_traps[i].left.p2.y + yoff, ysc);
 626             offset_traps[i].right.p1.x = _cairo_fixed_mul (src_traps[i].right.p1.x + xoff, xsc);
 627             offset_traps[i].right.p1.y = _cairo_fixed_mul (src_traps[i].right.p1.y + yoff, ysc);
 628             offset_traps[i].right.p2.x = _cairo_fixed_mul (src_traps[i].right.p2.x + xoff, xsc);
 629             offset_traps[i].right.p2.y = _cairo_fixed_mul (src_traps[i].right.p2.y + yoff, ysc);
 630         }
 631     }
 632 }
 633
 634 static cairo_bool_t
 635 _cairo_trap_contains (cairo_trapezoid_t *t, cairo_point_t *pt)
 636 {
 637     cairo_slope_t slope_left, slope_pt, slope_right;
 638
 639     if (t->top > pt->y)
 640         return FALSE;
 641     if (t->bottom < pt->y)
 642         return FALSE;
 643
 644     _cairo_slope_init (&slope_left, &t->left.p1, &t->left.p2);
 645     _cairo_slope_init (&slope_pt, &t->left.p1, pt);
 646
 647     if (_cairo_slope_compare (&slope_left, &slope_pt) < 0)
 648         return FALSE;
 649
 650     _cairo_slope_init (&slope_right, &t->right.p1, &t->right.p2);
 651     _cairo_slope_init (&slope_pt, &t->right.p1, pt);
 652
 653     if (_cairo_slope_compare (&slope_pt, &slope_right) < 0)
 654         return FALSE;
 655
 656     return TRUE;
 657 }
 658
 659 cairo_bool_t
 660 _cairo_traps_contain (const cairo_traps_t *traps,
 661                       double x, double y)
 662 {
 663     int i;
 664     cairo_point_t point;
 665
 666     point.x = _cairo_fixed_from_double (x);
 667     point.y = _cairo_fixed_from_double (y);
 668
 669     for (i = 0; i < traps->num_traps; i++) {
 670         if (_cairo_trap_contains (&traps->traps[i], &point))
 671             return TRUE;
 672     }
 673
 674     return FALSE;
 675 }
 676
 677 static cairo_fixed_t
 678 _line_compute_intersection_x_for_y (const cairo_line_t *line,
 679                                     cairo_fixed_t y)
 680 {
 681     return _cairo_edge_compute_intersection_x_for_y (&line->p1, &line->p2, y);
 682 }
 683
 684 void
 685 _cairo_traps_extents (const cairo_traps_t *traps,
 686                       cairo_box_t *extents)
 687 {
 688     int i;
 689
 690     if (traps->num_traps == 0) {
 691         extents->p1.x = extents->p1.y = 0;
 692         extents->p2.x = extents->p2.y = 0;
 693         return;
 694     }
 695
 696     extents->p1.x = extents->p1.y = INT32_MAX;
 697     extents->p2.x = extents->p2.y = INT32_MIN;
 698
 699     for (i = 0; i < traps->num_traps; i++) {
 700         const cairo_trapezoid_t *trap =  &traps->traps[i];
 701
 702         if (trap->top < extents->p1.y)
 703             extents->p1.y = trap->top;
 704         if (trap->bottom > extents->p2.y)
 705             extents->p2.y = trap->bottom;
 706
 707         if (trap->left.p1.x < extents->p1.x) {
 708             cairo_fixed_t x = trap->left.p1.x;
 709             if (trap->top != trap->left.p1.y) {
 710                 x = _line_compute_intersection_x_for_y (&trap->left,
 711                                                         trap->top);
 712                 if (x < extents->p1.x)
 713                     extents->p1.x = x;
 714             } else
 715                 extents->p1.x = x;
 716         }
 717         if (trap->left.p2.x < extents->p1.x) {
 718             cairo_fixed_t x = trap->left.p2.x;
 719             if (trap->bottom != trap->left.p2.y) {
 720                 x = _line_compute_intersection_x_for_y (&trap->left,
 721                                                         trap->bottom);
 722                 if (x < extents->p1.x)
 723                     extents->p1.x = x;
 724             } else
 725                 extents->p1.x = x;
 726         }
 727
 728         if (trap->right.p1.x > extents->p2.x) {
 729             cairo_fixed_t x = trap->right.p1.x;
 730             if (trap->top != trap->right.p1.y) {
 731                 x = _line_compute_intersection_x_for_y (&trap->right,
 732                                                         trap->top);
 733                 if (x > extents->p2.x)
 734                     extents->p2.x = x;
 735             } else
 736                 extents->p2.x = x;
 737         }
 738         if (trap->right.p2.x > extents->p2.x) {
 739             cairo_fixed_t x = trap->right.p2.x;
 740             if (trap->bottom != trap->right.p2.y) {
 741                 x = _line_compute_intersection_x_for_y (&trap->right,
 742                                                         trap->bottom);
 743                 if (x > extents->p2.x)
 744                     extents->p2.x = x;
 745             } else
 746                 extents->p2.x = x;
 747         }
 748     }
 749 }
 750
 751 static cairo_bool_t
 752 _mono_edge_is_vertical (const cairo_line_t *line)
 753 {
 754     return _cairo_fixed_integer_round_down (line->p1.x) == _cairo_fixed_integer_round_down (line->p2.x);
 755 }
 756
 757 static cairo_bool_t
 758 _traps_are_pixel_aligned (cairo_traps_t *traps,
 759                           cairo_antialias_t antialias)
 760 {
 761     int i;
 762
 763     if (antialias == CAIRO_ANTIALIAS_NONE) {
 764         for (i = 0; i < traps->num_traps; i++) {
 765             if (! _mono_edge_is_vertical (&traps->traps[i].left)   ||
 766                 ! _mono_edge_is_vertical (&traps->traps[i].right))
 767             {
 768                 traps->maybe_region = FALSE;
 769                 return FALSE;
 770             }
 771         }
 772     } else {
 773         for (i = 0; i < traps->num_traps; i++) {
 774             if (traps->traps[i].left.p1.x != traps->traps[i].left.p2.x   ||
 775                 traps->traps[i].right.p1.x != traps->traps[i].right.p2.x ||
 776                 ! _cairo_fixed_is_integer (traps->traps[i].top)          ||
 777                 ! _cairo_fixed_is_integer (traps->traps[i].bottom)       ||
 778                 ! _cairo_fixed_is_integer (traps->traps[i].left.p1.x)    ||
 779                 ! _cairo_fixed_is_integer (traps->traps[i].right.p1.x))
 780             {
 781                 traps->maybe_region = FALSE;
 782                 return FALSE;
 783             }
 784         }
 785     }
 786
 787     return TRUE;
 788 }
 789
 790 /**
 791  * _cairo_traps_extract_region:
 792  * @traps: a #cairo_traps_t
 793  * @region: a #cairo_region_t
 794  *
 795  * Determines if a set of trapezoids are exactly representable as a
 796  * cairo region.  If so, the passed-in region is initialized to
 797  * the area representing the given traps.  It should be finalized
 798  * with cairo_region_fini().  If not, %CAIRO_INT_STATUS_UNSUPPORTED
 799  * is returned.
 800  *
 801  * Return value: %CAIRO_STATUS_SUCCESS, %CAIRO_INT_STATUS_UNSUPPORTED
 802  * or %CAIRO_STATUS_NO_MEMORY
 803  **/
 804 cairo_int_status_t
 805 _cairo_traps_extract_region (cairo_traps_t   *traps,
 806                              cairo_antialias_t antialias,
 807                              cairo_region_t **region)
 808 {
 809     cairo_rectangle_int_t stack_rects[CAIRO_STACK_ARRAY_LENGTH (cairo_rectangle_int_t)];
 810     cairo_rectangle_int_t *rects = stack_rects;
 811     cairo_int_status_t status;
 812     int i, rect_count;
 813
 814     /* we only treat this a hint... */
 815     if (antialias != CAIRO_ANTIALIAS_NONE && ! traps->maybe_region)
 816         return CAIRO_INT_STATUS_UNSUPPORTED;
 817
 818     if (! _traps_are_pixel_aligned (traps, antialias)) {
 819         traps->maybe_region = FALSE;
 820         return CAIRO_INT_STATUS_UNSUPPORTED;
 821     }
 822
 823     if (traps->num_traps > ARRAY_LENGTH (stack_rects)) {
 824         rects = _cairo_malloc_ab (traps->num_traps, sizeof (cairo_rectangle_int_t));
 825
 826         if (unlikely (rects == NULL))
 827             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 828     }
 829
 830     rect_count = 0;
 831     for (i = 0; i < traps->num_traps; i++) {
 832         int x1, y1, x2, y2;
 833
 834         if (antialias == CAIRO_ANTIALIAS_NONE) {
 835             x1 = _cairo_fixed_integer_round_down (traps->traps[i].left.p1.x);
 836             y1 = _cairo_fixed_integer_round_down (traps->traps[i].top);
 837             x2 = _cairo_fixed_integer_round_down (traps->traps[i].right.p1.x);
 838             y2 = _cairo_fixed_integer_round_down (traps->traps[i].bottom);
 839         } else {
 840             x1 = _cairo_fixed_integer_part (traps->traps[i].left.p1.x);
 841             y1 = _cairo_fixed_integer_part (traps->traps[i].top);
 842             x2 = _cairo_fixed_integer_part (traps->traps[i].right.p1.x);
 843             y2 = _cairo_fixed_integer_part (traps->traps[i].bottom);
 844         }
 845
 846         if (x2 > x1 && y2 > y1) {
 847             rects[rect_count].x = x1;
 848             rects[rect_count].y = y1;
 849             rects[rect_count].width  = x2 - x1;
 850             rects[rect_count].height = y2 - y1;
 851             rect_count++;
 852         }
 853     }
 854
 855
 856     *region = cairo_region_create_rectangles (rects, rect_count);
 857     status = (*region)->status;
 858
 859     if (rects != stack_rects)
 860         free (rects);
 861
 862     return status;
 863 }
 864
 865 cairo_bool_t
 866 _cairo_traps_to_boxes (cairo_traps_t *traps,
 867                        cairo_antialias_t antialias,
 868                        cairo_boxes_t *boxes)
 869 {
 870     int i;
 871
 872     for (i = 0; i < traps->num_traps; i++) {
 873         if (traps->traps[i].left.p1.x  != traps->traps[i].left.p2.x ||
 874             traps->traps[i].right.p1.x != traps->traps[i].right.p2.x)
 875             return FALSE;
 876     }
 877
 878     _cairo_boxes_init (boxes);
 879
 880     boxes->num_boxes    = traps->num_traps;
 881     boxes->chunks.base  = (cairo_box_t *) traps->traps;
 882     boxes->chunks.count = traps->num_traps;
 883     boxes->chunks.size  = traps->num_traps;
 884
 885     if (antialias != CAIRO_ANTIALIAS_NONE) {
 886         for (i = 0; i < traps->num_traps; i++) {
 887             /* Note the traps and boxes alias so we need to take the local copies first. */
 888             cairo_fixed_t x1 = traps->traps[i].left.p1.x;
 889             cairo_fixed_t x2 = traps->traps[i].right.p1.x;
 890             cairo_fixed_t y1 = traps->traps[i].top;
 891             cairo_fixed_t y2 = traps->traps[i].bottom;
 892
 893             boxes->chunks.base[i].p1.x = x1;
 894             boxes->chunks.base[i].p1.y = y1;
 895             boxes->chunks.base[i].p2.x = x2;
 896             boxes->chunks.base[i].p2.y = y2;
 897
 898             if (boxes->is_pixel_aligned) {
 899                 boxes->is_pixel_aligned =
 900                     _cairo_fixed_is_integer (x1) && _cairo_fixed_is_integer (y1) &&
 901                     _cairo_fixed_is_integer (x2) && _cairo_fixed_is_integer (y2);
 902             }
 903         }
 904     } else {
 905         boxes->is_pixel_aligned = TRUE;
 906
 907         for (i = 0; i < traps->num_traps; i++) {
 908             /* Note the traps and boxes alias so we need to take the local copies first. */
 909             cairo_fixed_t x1 = traps->traps[i].left.p1.x;
 910             cairo_fixed_t x2 = traps->traps[i].right.p1.x;
 911             cairo_fixed_t y1 = traps->traps[i].top;
 912             cairo_fixed_t y2 = traps->traps[i].bottom;
 913
 914             /* round down here to match Pixman's behavior when using traps. */
 915             boxes->chunks.base[i].p1.x = _cairo_fixed_round_down (x1);
 916             boxes->chunks.base[i].p1.y = _cairo_fixed_round_down (y1);
 917             boxes->chunks.base[i].p2.x = _cairo_fixed_round_down (x2);
 918             boxes->chunks.base[i].p2.y = _cairo_fixed_round_down (y2);
 919         }
 920     }
 921
 922     return TRUE;
 923 }
 924
 925 /* moves trap points such that they become the actual corners of the trapezoid */
 926 static void
 927 _sanitize_trap (cairo_trapezoid_t *t)
 928 {
 929     cairo_trapezoid_t s = *t;
 930
 931 #define FIX(lr, tb, p) \
 932     if (t->lr.p.y != t->tb) { \
 933         t->lr.p.x = s.lr.p2.x + _cairo_fixed_mul_div_floor (s.lr.p1.x - s.lr.p2.x, s.tb - s.lr.p2.y, s.lr.p1.y - s.lr.p2.y); \
 934         t->lr.p.y = s.tb; \
 935     }
 936     FIX (left,  top,    p1);
 937     FIX (left,  bottom, p2);
 938     FIX (right, top,    p1);
 939     FIX (right, bottom, p2);
 940 }
 941
 942 cairo_private cairo_status_t
 943 _cairo_traps_path (const cairo_traps_t *traps,
 944                    cairo_path_fixed_t  *path)
 945 {
 946     int i;
 947
 948     for (i = 0; i < traps->num_traps; i++) {
 949         cairo_status_t status;
 950         cairo_trapezoid_t trap = traps->traps[i];
 951
 952         if (trap.top == trap.bottom)
 953             continue;
 954
 955         _sanitize_trap (&trap);
 956
 957         status = _cairo_path_fixed_move_to (path, trap.left.p1.x, trap.top);
 958         if (unlikely (status)) return status;
 959         status = _cairo_path_fixed_line_to (path, trap.right.p1.x, trap.top);
 960         if (unlikely (status)) return status;
 961         status = _cairo_path_fixed_line_to (path, trap.right.p2.x, trap.bottom);
 962         if (unlikely (status)) return status;
 963         status = _cairo_path_fixed_line_to (path, trap.left.p2.x, trap.bottom);
 964         if (unlikely (status)) return status;
 965         status = _cairo_path_fixed_close_path (path);
 966         if (unlikely (status)) return status;
 967     }
 968
 969     return CAIRO_STATUS_SUCCESS;
 970 }
 971
 972 void
 973 _cairo_debug_print_traps (FILE *file, const cairo_traps_t *traps)
 974 {
 975     cairo_box_t extents;
 976     int n;
 977
 978 #if 0
 979     if (traps->has_limits) {
 980         printf ("%s: limits=(%d, %d, %d, %d)\n",
 981                 filename,
 982                 traps->limits.p1.x, traps->limits.p1.y,
 983                 traps->limits.p2.x, traps->limits.p2.y);
 984     }
 985 #endif
 986
 987     _cairo_traps_extents (traps, &extents);
 988     fprintf (file, "extents=(%d, %d, %d, %d)\n",
 989              extents.p1.x, extents.p1.y,
 990              extents.p2.x, extents.p2.y);
 991
 992     for (n = 0; n < traps->num_traps; n++) {
 993         fprintf (file, "%d %d L:(%d, %d), (%d, %d) R:(%d, %d), (%d, %d)\n",
 994                  traps->traps[n].top,
 995                  traps->traps[n].bottom,
 996                  traps->traps[n].left.p1.x,
 997                  traps->traps[n].left.p1.y,
 998                  traps->traps[n].left.p2.x,
 999                  traps->traps[n].left.p2.y,
1000                  traps->traps[n].right.p1.x,
1001                  traps->traps[n].right.p1.y,
1002                  traps->traps[n].right.p2.x,
1003                  traps->traps[n].right.p2.y);
1004     }
1005 }
1006
1007 struct cairo_trap_renderer {
1008     cairo_span_renderer_t base;
1009     cairo_traps_t *traps;
1010 };
1011
1012 static cairo_status_t
1013 span_to_traps (void *abstract_renderer, int y, int h,
1014                const cairo_half_open_span_t *spans, unsigned num_spans)
1015 {
1016     struct cairo_trap_renderer *r = abstract_renderer;
1017     cairo_fixed_t top, bot;
1018
1019     if (num_spans == 0)
1020         return CAIRO_STATUS_SUCCESS;
1021
1022     top = _cairo_fixed_from_int (y);
1023     bot = _cairo_fixed_from_int (y + h);
1024     do {
1025         if (spans[0].coverage) {
1026             cairo_fixed_t x0 = _cairo_fixed_from_int(spans[0].x);
1027             cairo_fixed_t x1 = _cairo_fixed_from_int(spans[1].x);
1028             cairo_line_t left = { { x0, top }, { x0, bot } },
1029                          right = { { x1, top }, { x1, bot } };
1030             _cairo_traps_add_trap (r->traps, top, bot, &left, &right);
1031         }
1032         spans++;
1033     } while (--num_spans > 1);
1034
1035     return CAIRO_STATUS_SUCCESS;
1036 }
1037
1038 cairo_int_status_t
1039 _cairo_rasterise_polygon_to_traps (cairo_polygon_t                      *polygon,
1040                                    cairo_fill_rule_t                     fill_rule,
1041                                    cairo_antialias_t                     antialias,
1042                                    cairo_traps_t *traps)
1043 {
1044     struct cairo_trap_renderer renderer;
1045     cairo_scan_converter_t *converter;
1046     cairo_int_status_t status;
1047     cairo_rectangle_int_t r;
1048
1049     TRACE ((stderr, "%s: fill_rule=%d, antialias=%d\n",
1050             __FUNCTION__, fill_rule, antialias));
1051     assert(antialias == CAIRO_ANTIALIAS_NONE);
1052
1053     renderer.traps = traps;
1054     renderer.base.render_rows = span_to_traps;
1055
1056     _cairo_box_round_to_rectangle (&polygon->extents, &r);
1057     converter = _cairo_mono_scan_converter_create (r.x, r.y,
1058                                                    r.x + r.width,
1059                                                    r.y + r.height,
1060                                                    fill_rule);
1061     status = _cairo_mono_scan_converter_add_polygon (converter, polygon);
1062     if (likely (status == CAIRO_INT_STATUS_SUCCESS))
1063         status = converter->generate (converter, &renderer.base);
1064     converter->destroy (converter);
1065     return status;
1066 }