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-boxes-private.h"
  43 #include "cairo-error-private.h"
  44 #include "cairo-region-private.h"
  45 #include "cairo-slope-private.h"
  46 #include "cairo-traps-private.h"
  47
  48 /* private functions */
  49
  50 void
  51 _cairo_traps_init (cairo_traps_t *traps)
  52 {
  53     VG (VALGRIND_MAKE_MEM_UNDEFINED (traps, sizeof (cairo_traps_t)));
  54
  55     traps->status = CAIRO_STATUS_SUCCESS;
  56
  57     traps->maybe_region = 1;
  58     traps->is_rectilinear = 0;
  59     traps->is_rectangular = 0;
  60
  61     traps->num_traps = 0;
  62
  63     traps->traps_size = ARRAY_LENGTH (traps->traps_embedded);
  64     traps->traps = traps->traps_embedded;
  65
  66     traps->num_limits = 0;
  67     traps->has_intersections = FALSE;
  68 }
  69
  70 void
  71 _cairo_traps_limit (cairo_traps_t       *traps,
  72                     const cairo_box_t   *limits,
  73                     int                  num_limits)
  74 {
  75     traps->limits = limits;
  76     traps->num_limits = num_limits;
  77 }
  78
  79 void
  80 _cairo_traps_init_with_clip (cairo_traps_t *traps,
  81                              const cairo_clip_t *clip)
  82 {
  83     _cairo_traps_init (traps);
  84     if (clip)
  85         _cairo_traps_limit (traps, clip->boxes, clip->num_boxes);
  86 }
  87
  88 void
  89 _cairo_traps_clear (cairo_traps_t *traps)
  90 {
  91     traps->status = CAIRO_STATUS_SUCCESS;
  92
  93     traps->maybe_region = 1;
  94     traps->is_rectilinear = 0;
  95     traps->is_rectangular = 0;
  96
  97     traps->num_traps = 0;
  98     traps->has_intersections = FALSE;
  99 }
 100
 101 void
 102 _cairo_traps_fini (cairo_traps_t *traps)
 103 {
 104     if (traps->traps != traps->traps_embedded)
 105         free (traps->traps);
 106
 107     VG (VALGRIND_MAKE_MEM_NOACCESS (traps, sizeof (cairo_traps_t)));
 108 }
 109
 110 /* make room for at least one more trap */
 111 static cairo_bool_t
 112 _cairo_traps_grow (cairo_traps_t *traps)
 113 {
 114     cairo_trapezoid_t *new_traps;
 115     int new_size = 4 * traps->traps_size;
 116
 117     if (CAIRO_INJECT_FAULT ()) {
 118         traps->status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
 119         return FALSE;
 120     }
 121
 122     if (traps->traps == traps->traps_embedded) {
 123         new_traps = _cairo_malloc_ab (new_size, sizeof (cairo_trapezoid_t));
 124         if (new_traps != NULL)
 125             memcpy (new_traps, traps->traps, sizeof (traps->traps_embedded));
 126     } else {
 127         new_traps = _cairo_realloc_ab (traps->traps,
 128                                        new_size, sizeof (cairo_trapezoid_t));
 129     }
 130
 131     if (unlikely (new_traps == NULL)) {
 132         traps->status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
 133         return FALSE;
 134     }
 135
 136     traps->traps = new_traps;
 137     traps->traps_size = new_size;
 138     return TRUE;
 139 }
 140
 141 void
 142 _cairo_traps_add_trap (cairo_traps_t *traps,
 143                        cairo_fixed_t top, cairo_fixed_t bottom,
 144                        cairo_line_t *left, cairo_line_t *right)
 145 {
 146     cairo_trapezoid_t *trap;
 147
 148     if (unlikely (traps->num_traps == traps->traps_size)) {
 149         if (unlikely (! _cairo_traps_grow (traps)))
 150             return;
 151     }
 152
 153     trap = &traps->traps[traps->num_traps++];
 154     trap->top = top;
 155     trap->bottom = bottom;
 156     trap->left = *left;
 157     trap->right = *right;
 158 }
 159
 160 /**
 161  * _cairo_traps_init_box:
 162  * @traps: a #cairo_traps_t
 163  * @box: an array box that will each be converted to a single trapezoid
 164  *       to store in @traps.
 165  *
 166  * Initializes a #cairo_traps_t to contain an array of rectangular
 167  * trapezoids.
 168  **/
 169 cairo_status_t
 170 _cairo_traps_init_boxes (cairo_traps_t      *traps,
 171                          const cairo_boxes_t *boxes)
 172 {
 173     cairo_trapezoid_t *trap;
 174     const struct _cairo_boxes_chunk *chunk;
 175
 176     _cairo_traps_init (traps);
 177
 178     while (traps->traps_size < boxes->num_boxes) {
 179         if (unlikely (! _cairo_traps_grow (traps))) {
 180             _cairo_traps_fini (traps);
 181             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 182         }
 183     }
 184
 185     traps->num_traps = boxes->num_boxes;
 186     traps->is_rectilinear = TRUE;
 187     traps->is_rectangular = TRUE;
 188     traps->maybe_region = boxes->is_pixel_aligned;
 189
 190     trap = &traps->traps[0];
 191     for (chunk = &boxes->chunks; chunk != NULL; chunk = chunk->next) {
 192         const cairo_box_t *box;
 193         int i;
 194
 195         box = chunk->base;
 196         for (i = 0; i < chunk->count; i++) {
 197             trap->top    = box->p1.y;
 198             trap->bottom = box->p2.y;
 199
 200             trap->left.p1   = box->p1;
 201             trap->left.p2.x = box->p1.x;
 202             trap->left.p2.y = box->p2.y;
 203
 204             trap->right.p1.x = box->p2.x;
 205             trap->right.p1.y = box->p1.y;
 206             trap->right.p2   = box->p2;
 207
 208             box++, trap++;
 209         }
 210     }
 211
 212     return CAIRO_STATUS_SUCCESS;
 213 }
 214
 215 cairo_status_t
 216 _cairo_traps_tessellate_rectangle (cairo_traps_t *traps,
 217                                    const cairo_point_t *top_left,
 218                                    const cairo_point_t *bottom_right)
 219 {
 220     cairo_line_t left;
 221     cairo_line_t right;
 222     cairo_fixed_t top, bottom;
 223
 224     if (top_left->y == bottom_right->y)
 225         return CAIRO_STATUS_SUCCESS;
 226
 227     if (top_left->x == bottom_right->x)
 228         return CAIRO_STATUS_SUCCESS;
 229
 230      left.p1.x =  left.p2.x = top_left->x;
 231      left.p1.y = right.p1.y = top_left->y;
 232     right.p1.x = right.p2.x = bottom_right->x;
 233      left.p2.y = right.p2.y = bottom_right->y;
 234
 235      top = top_left->y;
 236      bottom = bottom_right->y;
 237
 238     if (traps->num_limits) {
 239         cairo_bool_t reversed;
 240         int n;
 241
 242         /* support counter-clockwise winding for rectangular tessellation */
 243         reversed = top_left->x > bottom_right->x;
 244         if (reversed) {
 245             right.p1.x = right.p2.x = top_left->x;
 246             left.p1.x = left.p2.x = bottom_right->x;
 247         }
 248
 249         for (n = 0; n < traps->num_limits; n++) {
 250             const cairo_box_t *limits = &traps->limits[n];
 251             cairo_line_t _left, _right;
 252             cairo_fixed_t _top, _bottom;
 253
 254             if (top >= limits->p2.y)
 255                 continue;
 256             if (bottom <= limits->p1.y)
 257                 continue;
 258
 259             /* Trivially reject if trapezoid is entirely to the right or
 260              * to the left of the limits. */
 261             if (left.p1.x >= limits->p2.x)
 262                 continue;
 263             if (right.p1.x <= limits->p1.x)
 264                 continue;
 265
 266             /* Otherwise, clip the trapezoid to the limits. */
 267             _top = top;
 268             if (_top < limits->p1.y)
 269                 _top = limits->p1.y;
 270
 271             _bottom = bottom;
 272             if (_bottom > limits->p2.y)
 273                 _bottom = limits->p2.y;
 274
 275             if (_bottom <= _top)
 276                 continue;
 277
 278             _left = left;
 279             if (_left.p1.x < limits->p1.x) {
 280                 _left.p1.x = limits->p1.x;
 281                 _left.p1.y = limits->p1.y;
 282                 _left.p2.x = limits->p1.x;
 283                 _left.p2.y = limits->p2.y;
 284             }
 285
 286             _right = right;
 287             if (_right.p1.x > limits->p2.x) {
 288                 _right.p1.x = limits->p2.x;
 289                 _right.p1.y = limits->p1.y;
 290                 _right.p2.x = limits->p2.x;
 291                 _right.p2.y = limits->p2.y;
 292             }
 293
 294             if (left.p1.x >= right.p1.x)
 295                 continue;
 296
 297             if (reversed)
 298                 _cairo_traps_add_trap (traps, _top, _bottom, &_right, &_left);
 299             else
 300                 _cairo_traps_add_trap (traps, _top, _bottom, &_left, &_right);
 301         }
 302     } else {
 303         _cairo_traps_add_trap (traps, top, bottom, &left, &right);
 304     }
 305
 306     return traps->status;
 307 }
 308
 309 void
 310 _cairo_traps_translate (cairo_traps_t *traps, int x, int y)
 311 {
 312     cairo_fixed_t xoff, yoff;
 313     cairo_trapezoid_t *t;
 314     int i;
 315
 316     /* Ugh. The cairo_composite/(Render) interface doesn't allow
 317        an offset for the trapezoids. Need to manually shift all
 318        the coordinates to align with the offset origin of the
 319        intermediate surface. */
 320
 321     xoff = _cairo_fixed_from_int (x);
 322     yoff = _cairo_fixed_from_int (y);
 323
 324     for (i = 0, t = traps->traps; i < traps->num_traps; i++, t++) {
 325         t->top += yoff;
 326         t->bottom += yoff;
 327         t->left.p1.x += xoff;
 328         t->left.p1.y += yoff;
 329         t->left.p2.x += xoff;
 330         t->left.p2.y += yoff;
 331         t->right.p1.x += xoff;
 332         t->right.p1.y += yoff;
 333         t->right.p2.x += xoff;
 334         t->right.p2.y += yoff;
 335     }
 336 }
 337
 338 void
 339 _cairo_trapezoid_array_translate_and_scale (cairo_trapezoid_t *offset_traps,
 340                                             cairo_trapezoid_t *src_traps,
 341                                             int num_traps,
 342                                             double tx, double ty,
 343                                             double sx, double sy)
 344 {
 345     int i;
 346     cairo_fixed_t xoff = _cairo_fixed_from_double (tx);
 347     cairo_fixed_t yoff = _cairo_fixed_from_double (ty);
 348
 349     if (sx == 1.0 && sy == 1.0) {
 350         for (i = 0; i < num_traps; i++) {
 351             offset_traps[i].top = src_traps[i].top + yoff;
 352             offset_traps[i].bottom = src_traps[i].bottom + yoff;
 353             offset_traps[i].left.p1.x = src_traps[i].left.p1.x + xoff;
 354             offset_traps[i].left.p1.y = src_traps[i].left.p1.y + yoff;
 355             offset_traps[i].left.p2.x = src_traps[i].left.p2.x + xoff;
 356             offset_traps[i].left.p2.y = src_traps[i].left.p2.y + yoff;
 357             offset_traps[i].right.p1.x = src_traps[i].right.p1.x + xoff;
 358             offset_traps[i].right.p1.y = src_traps[i].right.p1.y + yoff;
 359             offset_traps[i].right.p2.x = src_traps[i].right.p2.x + xoff;
 360             offset_traps[i].right.p2.y = src_traps[i].right.p2.y + yoff;
 361         }
 362     } else {
 363         cairo_fixed_t xsc = _cairo_fixed_from_double (sx);
 364         cairo_fixed_t ysc = _cairo_fixed_from_double (sy);
 365
 366         for (i = 0; i < num_traps; i++) {
 367             offset_traps[i].top = _cairo_fixed_mul (src_traps[i].top + yoff, ysc);
 368             offset_traps[i].bottom = _cairo_fixed_mul (src_traps[i].bottom + yoff, ysc);
 369             offset_traps[i].left.p1.x = _cairo_fixed_mul (src_traps[i].left.p1.x + xoff, xsc);
 370             offset_traps[i].left.p1.y = _cairo_fixed_mul (src_traps[i].left.p1.y + yoff, ysc);
 371             offset_traps[i].left.p2.x = _cairo_fixed_mul (src_traps[i].left.p2.x + xoff, xsc);
 372             offset_traps[i].left.p2.y = _cairo_fixed_mul (src_traps[i].left.p2.y + yoff, ysc);
 373             offset_traps[i].right.p1.x = _cairo_fixed_mul (src_traps[i].right.p1.x + xoff, xsc);
 374             offset_traps[i].right.p1.y = _cairo_fixed_mul (src_traps[i].right.p1.y + yoff, ysc);
 375             offset_traps[i].right.p2.x = _cairo_fixed_mul (src_traps[i].right.p2.x + xoff, xsc);
 376             offset_traps[i].right.p2.y = _cairo_fixed_mul (src_traps[i].right.p2.y + yoff, ysc);
 377         }
 378     }
 379 }
 380
 381 static cairo_bool_t
 382 _cairo_trap_contains (cairo_trapezoid_t *t, cairo_point_t *pt)
 383 {
 384     cairo_slope_t slope_left, slope_pt, slope_right;
 385
 386     if (t->top > pt->y)
 387         return FALSE;
 388     if (t->bottom < pt->y)
 389         return FALSE;
 390
 391     _cairo_slope_init (&slope_left, &t->left.p1, &t->left.p2);
 392     _cairo_slope_init (&slope_pt, &t->left.p1, pt);
 393
 394     if (_cairo_slope_compare (&slope_left, &slope_pt) < 0)
 395         return FALSE;
 396
 397     _cairo_slope_init (&slope_right, &t->right.p1, &t->right.p2);
 398     _cairo_slope_init (&slope_pt, &t->right.p1, pt);
 399
 400     if (_cairo_slope_compare (&slope_pt, &slope_right) < 0)
 401         return FALSE;
 402
 403     return TRUE;
 404 }
 405
 406 cairo_bool_t
 407 _cairo_traps_contain (const cairo_traps_t *traps,
 408                       double x, double y)
 409 {
 410     int i;
 411     cairo_point_t point;
 412
 413     point.x = _cairo_fixed_from_double (x);
 414     point.y = _cairo_fixed_from_double (y);
 415
 416     for (i = 0; i < traps->num_traps; i++) {
 417         if (_cairo_trap_contains (&traps->traps[i], &point))
 418             return TRUE;
 419     }
 420
 421     return FALSE;
 422 }
 423
 424 static cairo_fixed_t
 425 _line_compute_intersection_x_for_y (const cairo_line_t *line,
 426                                     cairo_fixed_t y)
 427 {
 428     return _cairo_edge_compute_intersection_x_for_y (&line->p1, &line->p2, y);
 429 }
 430
 431 void
 432 _cairo_traps_extents (const cairo_traps_t *traps,
 433                       cairo_box_t *extents)
 434 {
 435     int i;
 436
 437     if (traps->num_traps == 0) {
 438         extents->p1.x = extents->p1.y = 0;
 439         extents->p2.x = extents->p2.y = 0;
 440         return;
 441     }
 442
 443     extents->p1.x = extents->p1.y = INT32_MAX;
 444     extents->p2.x = extents->p2.y = INT32_MIN;
 445
 446     for (i = 0; i < traps->num_traps; i++) {
 447         const cairo_trapezoid_t *trap =  &traps->traps[i];
 448
 449         if (trap->top < extents->p1.y)
 450             extents->p1.y = trap->top;
 451         if (trap->bottom > extents->p2.y)
 452             extents->p2.y = trap->bottom;
 453
 454         if (trap->left.p1.x < extents->p1.x) {
 455             cairo_fixed_t x = trap->left.p1.x;
 456             if (trap->top != trap->left.p1.y) {
 457                 x = _line_compute_intersection_x_for_y (&trap->left,
 458                                                         trap->top);
 459                 if (x < extents->p1.x)
 460                     extents->p1.x = x;
 461             } else
 462                 extents->p1.x = x;
 463         }
 464         if (trap->left.p2.x < extents->p1.x) {
 465             cairo_fixed_t x = trap->left.p2.x;
 466             if (trap->bottom != trap->left.p2.y) {
 467                 x = _line_compute_intersection_x_for_y (&trap->left,
 468                                                         trap->bottom);
 469                 if (x < extents->p1.x)
 470                     extents->p1.x = x;
 471             } else
 472                 extents->p1.x = x;
 473         }
 474
 475         if (trap->right.p1.x > extents->p2.x) {
 476             cairo_fixed_t x = trap->right.p1.x;
 477             if (trap->top != trap->right.p1.y) {
 478                 x = _line_compute_intersection_x_for_y (&trap->right,
 479                                                         trap->top);
 480                 if (x > extents->p2.x)
 481                     extents->p2.x = x;
 482             } else
 483                 extents->p2.x = x;
 484         }
 485         if (trap->right.p2.x > extents->p2.x) {
 486             cairo_fixed_t x = trap->right.p2.x;
 487             if (trap->bottom != trap->right.p2.y) {
 488                 x = _line_compute_intersection_x_for_y (&trap->right,
 489                                                         trap->bottom);
 490                 if (x > extents->p2.x)
 491                     extents->p2.x = x;
 492             } else
 493                 extents->p2.x = x;
 494         }
 495     }
 496 }
 497
 498 static cairo_bool_t
 499 _mono_edge_is_vertical (const cairo_line_t *line)
 500 {
 501     return _cairo_fixed_integer_round_down (line->p1.x) == _cairo_fixed_integer_round_down (line->p2.x);
 502 }
 503
 504 static cairo_bool_t
 505 _traps_are_pixel_aligned (cairo_traps_t *traps,
 506                           cairo_antialias_t antialias)
 507 {
 508     int i;
 509
 510     if (antialias == CAIRO_ANTIALIAS_NONE) {
 511         for (i = 0; i < traps->num_traps; i++) {
 512             if (! _mono_edge_is_vertical (&traps->traps[i].left)   ||
 513                 ! _mono_edge_is_vertical (&traps->traps[i].right))
 514             {
 515                 traps->maybe_region = FALSE;
 516                 return FALSE;
 517             }
 518         }
 519     } else {
 520         for (i = 0; i < traps->num_traps; i++) {
 521             if (traps->traps[i].left.p1.x != traps->traps[i].left.p2.x   ||
 522                 traps->traps[i].right.p1.x != traps->traps[i].right.p2.x ||
 523                 ! _cairo_fixed_is_integer (traps->traps[i].top)          ||
 524                 ! _cairo_fixed_is_integer (traps->traps[i].bottom)       ||
 525                 ! _cairo_fixed_is_integer (traps->traps[i].left.p1.x)    ||
 526                 ! _cairo_fixed_is_integer (traps->traps[i].right.p1.x))
 527             {
 528                 traps->maybe_region = FALSE;
 529                 return FALSE;
 530             }
 531         }
 532     }
 533
 534     return TRUE;
 535 }
 536
 537 /**
 538  * _cairo_traps_extract_region:
 539  * @traps: a #cairo_traps_t
 540  * @region: a #cairo_region_t
 541  *
 542  * Determines if a set of trapezoids are exactly representable as a
 543  * cairo region.  If so, the passed-in region is initialized to
 544  * the area representing the given traps.  It should be finalized
 545  * with cairo_region_fini().  If not, %CAIRO_INT_STATUS_UNSUPPORTED
 546  * is returned.
 547  *
 548  * Return value: %CAIRO_STATUS_SUCCESS, %CAIRO_INT_STATUS_UNSUPPORTED
 549  * or %CAIRO_STATUS_NO_MEMORY
 550  **/
 551 cairo_int_status_t
 552 _cairo_traps_extract_region (cairo_traps_t   *traps,
 553                              cairo_antialias_t antialias,
 554                              cairo_region_t **region)
 555 {
 556     cairo_rectangle_int_t stack_rects[CAIRO_STACK_ARRAY_LENGTH (cairo_rectangle_int_t)];
 557     cairo_rectangle_int_t *rects = stack_rects;
 558     cairo_int_status_t status;
 559     int i, rect_count;
 560
 561     /* we only treat this a hint... */
 562     if (antialias != CAIRO_ANTIALIAS_NONE && ! traps->maybe_region)
 563         return CAIRO_INT_STATUS_UNSUPPORTED;
 564
 565     if (! _traps_are_pixel_aligned (traps, antialias)) {
 566         traps->maybe_region = FALSE;
 567         return CAIRO_INT_STATUS_UNSUPPORTED;
 568     }
 569
 570     if (traps->num_traps > ARRAY_LENGTH (stack_rects)) {
 571         rects = _cairo_malloc_ab (traps->num_traps, sizeof (cairo_rectangle_int_t));
 572
 573         if (unlikely (rects == NULL))
 574             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 575     }
 576
 577     rect_count = 0;
 578     for (i = 0; i < traps->num_traps; i++) {
 579         int x1, y1, x2, y2;
 580
 581         if (antialias == CAIRO_ANTIALIAS_NONE) {
 582             x1 = _cairo_fixed_integer_round_down (traps->traps[i].left.p1.x);
 583             y1 = _cairo_fixed_integer_round_down (traps->traps[i].top);
 584             x2 = _cairo_fixed_integer_round_down (traps->traps[i].right.p1.x);
 585             y2 = _cairo_fixed_integer_round_down (traps->traps[i].bottom);
 586         } else {
 587             x1 = _cairo_fixed_integer_part (traps->traps[i].left.p1.x);
 588             y1 = _cairo_fixed_integer_part (traps->traps[i].top);
 589             x2 = _cairo_fixed_integer_part (traps->traps[i].right.p1.x);
 590             y2 = _cairo_fixed_integer_part (traps->traps[i].bottom);
 591         }
 592
 593         if (x2 > x1 && y2 > y1) {
 594             rects[rect_count].x = x1;
 595             rects[rect_count].y = y1;
 596             rects[rect_count].width  = x2 - x1;
 597             rects[rect_count].height = y2 - y1;
 598             rect_count++;
 599         }
 600     }
 601
 602
 603     *region = cairo_region_create_rectangles (rects, rect_count);
 604     status = (*region)->status;
 605
 606     if (rects != stack_rects)
 607         free (rects);
 608
 609     return status;
 610 }
 611
 612 cairo_bool_t
 613 _cairo_traps_to_boxes (cairo_traps_t *traps,
 614                        cairo_antialias_t antialias,
 615                        cairo_boxes_t *boxes)
 616 {
 617     int i;
 618
 619     for (i = 0; i < traps->num_traps; i++) {
 620         if (traps->traps[i].left.p1.x  != traps->traps[i].left.p2.x ||
 621             traps->traps[i].right.p1.x != traps->traps[i].right.p2.x)
 622             return FALSE;
 623     }
 624
 625     _cairo_boxes_init (boxes);
 626
 627     boxes->num_boxes    = traps->num_traps;
 628     boxes->chunks.base  = (cairo_box_t *) traps->traps;
 629     boxes->chunks.count = traps->num_traps;
 630     boxes->chunks.size  = traps->num_traps;
 631
 632     if (antialias != CAIRO_ANTIALIAS_NONE) {
 633         for (i = 0; i < traps->num_traps; i++) {
 634             /* Note the traps and boxes alias so we need to take the local copies first. */
 635             cairo_fixed_t x1 = traps->traps[i].left.p1.x;
 636             cairo_fixed_t x2 = traps->traps[i].right.p1.x;
 637             cairo_fixed_t y1 = traps->traps[i].top;
 638             cairo_fixed_t y2 = traps->traps[i].bottom;
 639
 640             boxes->chunks.base[i].p1.x = x1;
 641             boxes->chunks.base[i].p1.y = y1;
 642             boxes->chunks.base[i].p2.x = x2;
 643             boxes->chunks.base[i].p2.y = y2;
 644
 645             if (boxes->is_pixel_aligned) {
 646                 boxes->is_pixel_aligned =
 647                     _cairo_fixed_is_integer (x1) && _cairo_fixed_is_integer (y1) &&
 648                     _cairo_fixed_is_integer (x2) && _cairo_fixed_is_integer (y2);
 649             }
 650         }
 651     } else {
 652         boxes->is_pixel_aligned = TRUE;
 653
 654         for (i = 0; i < traps->num_traps; i++) {
 655             /* Note the traps and boxes alias so we need to take the local copies first. */
 656             cairo_fixed_t x1 = traps->traps[i].left.p1.x;
 657             cairo_fixed_t x2 = traps->traps[i].right.p1.x;
 658             cairo_fixed_t y1 = traps->traps[i].top;
 659             cairo_fixed_t y2 = traps->traps[i].bottom;
 660
 661             /* round down here to match Pixman's behavior when using traps. */
 662             boxes->chunks.base[i].p1.x = _cairo_fixed_round_down (x1);
 663             boxes->chunks.base[i].p1.y = _cairo_fixed_round_down (y1);
 664             boxes->chunks.base[i].p2.x = _cairo_fixed_round_down (x2);
 665             boxes->chunks.base[i].p2.y = _cairo_fixed_round_down (y2);
 666         }
 667     }
 668
 669     return TRUE;
 670 }
 671
 672 /* moves trap points such that they become the actual corners of the trapezoid */
 673 static void
 674 _sanitize_trap (cairo_trapezoid_t *t)
 675 {
 676     cairo_trapezoid_t s = *t;
 677
 678 #define FIX(lr, tb, p) \
 679     if (t->lr.p.y != t->tb) { \
 680         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); \
 681         t->lr.p.y = s.tb; \
 682     }
 683     FIX (left,  top,    p1);
 684     FIX (left,  bottom, p2);
 685     FIX (right, top,    p1);
 686     FIX (right, bottom, p2);
 687 }
 688
 689 cairo_private cairo_status_t
 690 _cairo_traps_path (const cairo_traps_t *traps,
 691                    cairo_path_fixed_t  *path)
 692 {
 693     int i;
 694
 695     for (i = 0; i < traps->num_traps; i++) {
 696         cairo_status_t status;
 697         cairo_trapezoid_t trap = traps->traps[i];
 698
 699         if (trap.top == trap.bottom)
 700             continue;
 701
 702         _sanitize_trap (&trap);
 703
 704         status = _cairo_path_fixed_move_to (path, trap.left.p1.x, trap.top);
 705         if (unlikely (status)) return status;
 706         status = _cairo_path_fixed_line_to (path, trap.right.p1.x, trap.top);
 707         if (unlikely (status)) return status;
 708         status = _cairo_path_fixed_line_to (path, trap.right.p2.x, trap.bottom);
 709         if (unlikely (status)) return status;
 710         status = _cairo_path_fixed_line_to (path, trap.left.p2.x, trap.bottom);
 711         if (unlikely (status)) return status;
 712         status = _cairo_path_fixed_close_path (path);
 713         if (unlikely (status)) return status;
 714     }
 715
 716     return CAIRO_STATUS_SUCCESS;
 717 }