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