src/cairo-bentley-ottmann-rectangular.c

   1 /*
   2  * Copyright © 2004 Carl Worth
   3  * Copyright © 2006 Red Hat, Inc.
   4  * Copyright © 2009 Chris Wilson
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it either under the terms of the GNU Lesser General Public
   8  * License version 2.1 as published by the Free Software Foundation
   9  * (the "LGPL") or, at your option, under the terms of the Mozilla
  10  * Public License Version 1.1 (the "MPL"). If you do not alter this
  11  * notice, a recipient may use your version of this file under either
  12  * the MPL or the LGPL.
  13  *
  14  * You should have received a copy of the LGPL along with this library
  15  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
  16  * Foundation, Inc., 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 Carl Worth
  32  *
  33  * Contributor(s):
  34  *      Carl D. Worth <cworth@cworth.org>
  35  *      Chris Wilson <chris@chris-wilson.co.uk>
  36  */
  37
  38 /* Provide definitions for standalone compilation */
  39 #include "cairoint.h"
  40
  41 #include "cairo-boxes-private.h"
  42 #include "cairo-error-private.h"
  43 #include "cairo-combsort-inline.h"
  44 #include "cairo-list-private.h"
  45 #include "cairo-traps-private.h"
  46
  47 #include <setjmp.h>
  48
  49 typedef struct _rectangle rectangle_t;
  50 typedef struct _edge edge_t;
  51
  52 struct _edge {
  53     edge_t *next, *prev;
  54     edge_t *right;
  55     cairo_fixed_t x, top;
  56     int dir;
  57 };
  58
  59 struct _rectangle {
  60     edge_t left, right;
  61     int32_t top, bottom;
  62 };
  63
  64 #define UNROLL3(x) x x x
  65
  66 /* the parent is always given by index/2 */
  67 #define PQ_PARENT_INDEX(i) ((i) >> 1)
  68 #define PQ_FIRST_ENTRY 1
  69
  70 /* left and right children are index * 2 and (index * 2) +1 respectively */
  71 #define PQ_LEFT_CHILD_INDEX(i) ((i) << 1)
  72
  73 typedef struct _sweep_line {
  74     rectangle_t **rectangles;
  75     rectangle_t **stop;
  76     edge_t head, tail, *insert, *cursor;
  77     int32_t current_y;
  78     int32_t last_y;
  79     int stop_size;
  80
  81     int32_t insert_x;
  82     cairo_fill_rule_t fill_rule;
  83
  84     cairo_bool_t do_traps;
  85     void *container;
  86
  87     jmp_buf unwind;
  88 } sweep_line_t;
  89
  90 #define DEBUG_TRAPS 0
  91
  92 #if DEBUG_TRAPS
  93 static void
  94 dump_traps (cairo_traps_t *traps, const char *filename)
  95 {
  96     FILE *file;
  97     int n;
  98
  99     if (getenv ("CAIRO_DEBUG_TRAPS") == NULL)
 100         return;
 101
 102     file = fopen (filename, "a");
 103     if (file != NULL) {
 104         for (n = 0; n < traps->num_traps; n++) {
 105             fprintf (file, "%d %d L:(%d, %d), (%d, %d) R:(%d, %d), (%d, %d)\n",
 106                      traps->traps[n].top,
 107                      traps->traps[n].bottom,
 108                      traps->traps[n].left.p1.x,
 109                      traps->traps[n].left.p1.y,
 110                      traps->traps[n].left.p2.x,
 111                      traps->traps[n].left.p2.y,
 112                      traps->traps[n].right.p1.x,
 113                      traps->traps[n].right.p1.y,
 114                      traps->traps[n].right.p2.x,
 115                      traps->traps[n].right.p2.y);
 116         }
 117         fprintf (file, "\n");
 118         fclose (file);
 119     }
 120 }
 121 #else
 122 #define dump_traps(traps, filename)
 123 #endif
 124
 125 static inline int
 126 rectangle_compare_start (const rectangle_t *a,
 127                          const rectangle_t *b)
 128 {
 129     return a->top - b->top;
 130 }
 131
 132 static inline int
 133 rectangle_compare_stop (const rectangle_t *a,
 134                          const rectangle_t *b)
 135 {
 136     return a->bottom - b->bottom;
 137 }
 138
 139 static inline void
 140 pqueue_push (sweep_line_t *sweep, rectangle_t *rectangle)
 141 {
 142     rectangle_t **elements;
 143     int i, parent;
 144
 145     elements = sweep->stop;
 146     for (i = ++sweep->stop_size;
 147          i != PQ_FIRST_ENTRY &&
 148          rectangle_compare_stop (rectangle,
 149                                  elements[parent = PQ_PARENT_INDEX (i)]) < 0;
 150          i = parent)
 151     {
 152         elements[i] = elements[parent];
 153     }
 154
 155     elements[i] = rectangle;
 156 }
 157
 158 static inline void
 159 rectangle_pop_stop (sweep_line_t *sweep)
 160 {
 161     rectangle_t **elements = sweep->stop;
 162     rectangle_t *tail;
 163     int child, i;
 164
 165     tail = elements[sweep->stop_size--];
 166     if (sweep->stop_size == 0) {
 167         elements[PQ_FIRST_ENTRY] = NULL;
 168         return;
 169     }
 170
 171     for (i = PQ_FIRST_ENTRY;
 172          (child = PQ_LEFT_CHILD_INDEX (i)) <= sweep->stop_size;
 173          i = child)
 174     {
 175         if (child != sweep->stop_size &&
 176             rectangle_compare_stop (elements[child+1],
 177                                     elements[child]) < 0)
 178         {
 179             child++;
 180         }
 181
 182         if (rectangle_compare_stop (elements[child], tail) >= 0)
 183             break;
 184
 185         elements[i] = elements[child];
 186     }
 187     elements[i] = tail;
 188 }
 189
 190 static inline rectangle_t *
 191 rectangle_pop_start (sweep_line_t *sweep_line)
 192 {
 193     return *sweep_line->rectangles++;
 194 }
 195
 196 static inline rectangle_t *
 197 rectangle_peek_stop (sweep_line_t *sweep_line)
 198 {
 199     return sweep_line->stop[PQ_FIRST_ENTRY];
 200 }
 201
 202 CAIRO_COMBSORT_DECLARE (_rectangle_sort,
 203                         rectangle_t *,
 204                         rectangle_compare_start)
 205
 206 static void
 207 sweep_line_init (sweep_line_t    *sweep_line,
 208                  rectangle_t    **rectangles,
 209                  int              num_rectangles,
 210                  cairo_fill_rule_t fill_rule,
 211                  cairo_bool_t    do_traps,
 212                  void           *container)
 213 {
 214     rectangles[-2] = NULL;
 215     rectangles[-1] = NULL;
 216     rectangles[num_rectangles] = NULL;
 217     sweep_line->rectangles = rectangles;
 218     sweep_line->stop = rectangles - 2;
 219     sweep_line->stop_size = 0;
 220
 221     sweep_line->insert = NULL;
 222     sweep_line->insert_x = INT_MAX;
 223     sweep_line->cursor = &sweep_line->tail;
 224
 225     sweep_line->head.dir = 0;
 226     sweep_line->head.x = INT32_MIN;
 227     sweep_line->head.right = NULL;
 228     sweep_line->head.prev = NULL;
 229     sweep_line->head.next = &sweep_line->tail;
 230     sweep_line->tail.prev = &sweep_line->head;
 231     sweep_line->tail.next = NULL;
 232     sweep_line->tail.right = NULL;
 233     sweep_line->tail.x = INT32_MAX;
 234     sweep_line->tail.dir = 0;
 235
 236     sweep_line->current_y = INT32_MIN;
 237     sweep_line->last_y = INT32_MIN;
 238
 239     sweep_line->fill_rule = fill_rule;
 240     sweep_line->container = container;
 241     sweep_line->do_traps = do_traps;
 242 }
 243
 244 static void
 245 edge_end_box (sweep_line_t *sweep_line, edge_t *left, int32_t bot)
 246 {
 247     cairo_status_t status = CAIRO_STATUS_SUCCESS;
 248
 249     /* Only emit (trivial) non-degenerate trapezoids with positive height. */
 250     if (likely (left->top < bot)) {
 251         if (sweep_line->do_traps) {
 252             cairo_line_t _left = {
 253                 { left->x, left->top },
 254                 { left->x, bot },
 255             }, _right = {
 256                 { left->right->x, left->top },
 257                 { left->right->x, bot },
 258             };
 259             _cairo_traps_add_trap (sweep_line->container, left->top, bot, &_left, &_right);
 260             status = _cairo_traps_status ((cairo_traps_t *) sweep_line->container);
 261         } else {
 262             cairo_box_t box;
 263
 264             box.p1.x = left->x;
 265             box.p1.y = left->top;
 266             box.p2.x = left->right->x;
 267             box.p2.y = bot;
 268
 269             status = _cairo_boxes_add (sweep_line->container,
 270                                        CAIRO_ANTIALIAS_DEFAULT,
 271                                        &box);
 272         }
 273     }
 274     if (unlikely (status))
 275         longjmp (sweep_line->unwind, status);
 276
 277     left->right = NULL;
 278 }
 279
 280 /* Start a new trapezoid at the given top y coordinate, whose edges
 281  * are `edge' and `edge->next'. If `edge' already has a trapezoid,
 282  * then either add it to the traps in `traps', if the trapezoid's
 283  * right edge differs from `edge->next', or do nothing if the new
 284  * trapezoid would be a continuation of the existing one. */
 285 static inline void
 286 edge_start_or_continue_box (sweep_line_t *sweep_line,
 287                             edge_t      *left,
 288                             edge_t      *right,
 289                             int          top)
 290 {
 291     if (left->right == right)
 292         return;
 293
 294     if (left->right != NULL) {
 295         if (left->right->x == right->x) {
 296             /* continuation on right, so just swap edges */
 297             left->right = right;
 298             return;
 299         }
 300
 301         edge_end_box (sweep_line, left, top);
 302     }
 303
 304     if (left->x != right->x) {
 305         left->top = top;
 306         left->right = right;
 307     }
 308 }
 309 /*
 310  * Merge two sorted edge lists.
 311  * Input:
 312  *  - head_a: The head of the first list.
 313  *  - head_b: The head of the second list; head_b cannot be NULL.
 314  * Output:
 315  * Returns the head of the merged list.
 316  *
 317  * Implementation notes:
 318  * To make it fast (in particular, to reduce to an insertion sort whenever
 319  * one of the two input lists only has a single element) we iterate through
 320  * a list until its head becomes greater than the head of the other list,
 321  * then we switch their roles. As soon as one of the two lists is empty, we
 322  * just attach the other one to the current list and exit.
 323  * Writes to memory are only needed to "switch" lists (as it also requires
 324  * attaching to the output list the list which we will be iterating next) and
 325  * to attach the last non-empty list.
 326  */
 327 static edge_t *
 328 merge_sorted_edges (edge_t *head_a, edge_t *head_b)
 329 {
 330     edge_t *head, *prev;
 331     int32_t x;
 332
 333     prev = head_a->prev;
 334     if (head_a->x <= head_b->x) {
 335         head = head_a;
 336     } else {
 337         head_b->prev = prev;
 338         head = head_b;
 339         goto start_with_b;
 340     }
 341
 342     do {
 343         x = head_b->x;
 344         while (head_a != NULL && head_a->x <= x) {
 345             prev = head_a;
 346             head_a = head_a->next;
 347         }
 348
 349         head_b->prev = prev;
 350         prev->next = head_b;
 351         if (head_a == NULL)
 352             return head;
 353
 354 start_with_b:
 355         x = head_a->x;
 356         while (head_b != NULL && head_b->x <= x) {
 357             prev = head_b;
 358             head_b = head_b->next;
 359         }
 360
 361         head_a->prev = prev;
 362         prev->next = head_a;
 363         if (head_b == NULL)
 364             return head;
 365     } while (1);
 366 }
 367
 368 /*
 369  * Sort (part of) a list.
 370  * Input:
 371  *  - list: The list to be sorted; list cannot be NULL.
 372  *  - limit: Recursion limit.
 373  * Output:
 374  *  - head_out: The head of the sorted list containing the first 2^(level+1) elements of the
 375  *              input list; if the input list has fewer elements, head_out be a sorted list
 376  *              containing all the elements of the input list.
 377  * Returns the head of the list of unprocessed elements (NULL if the sorted list contains
 378  * all the elements of the input list).
 379  *
 380  * Implementation notes:
 381  * Special case single element list, unroll/inline the sorting of the first two elements.
 382  * Some tail recursion is used since we iterate on the bottom-up solution of the problem
 383  * (we start with a small sorted list and keep merging other lists of the same size to it).
 384  */
 385 static edge_t *
 386 sort_edges (edge_t  *list,
 387             unsigned int  level,
 388             edge_t **head_out)
 389 {
 390     edge_t *head_other, *remaining;
 391     unsigned int i;
 392
 393     head_other = list->next;
 394
 395     if (head_other == NULL) {
 396         *head_out = list;
 397         return NULL;
 398     }
 399
 400     remaining = head_other->next;
 401     if (list->x <= head_other->x) {
 402         *head_out = list;
 403         head_other->next = NULL;
 404     } else {
 405         *head_out = head_other;
 406         head_other->prev = list->prev;
 407         head_other->next = list;
 408         list->prev = head_other;
 409         list->next = NULL;
 410     }
 411
 412     for (i = 0; i < level && remaining; i++) {
 413         remaining = sort_edges (remaining, i, &head_other);
 414         *head_out = merge_sorted_edges (*head_out, head_other);
 415     }
 416
 417     return remaining;
 418 }
 419
 420 static edge_t *
 421 merge_unsorted_edges (edge_t *head, edge_t *unsorted)
 422 {
 423     sort_edges (unsorted, UINT_MAX, &unsorted);
 424     return merge_sorted_edges (head, unsorted);
 425 }
 426
 427 static void
 428 active_edges_insert (sweep_line_t *sweep)
 429 {
 430     edge_t *prev;
 431     int x;
 432
 433     x = sweep->insert_x;
 434     prev = sweep->cursor;
 435     if (prev->x > x) {
 436         do {
 437             prev = prev->prev;
 438         } while (prev->x > x);
 439     } else {
 440         while (prev->next->x < x)
 441             prev = prev->next;
 442     }
 443
 444     prev->next = merge_unsorted_edges (prev->next, sweep->insert);
 445     sweep->cursor = sweep->insert;
 446     sweep->insert = NULL;
 447     sweep->insert_x = INT_MAX;
 448 }
 449
 450 static inline void
 451 active_edges_to_traps (sweep_line_t *sweep)
 452 {
 453     int top = sweep->current_y;
 454     edge_t *pos;
 455
 456     if (sweep->last_y == sweep->current_y)
 457         return;
 458
 459     if (sweep->insert)
 460         active_edges_insert (sweep);
 461
 462     pos = sweep->head.next;
 463     if (pos == &sweep->tail)
 464         return;
 465
 466     if (sweep->fill_rule == CAIRO_FILL_RULE_WINDING) {
 467         do {
 468             edge_t *left, *right;
 469             int winding;
 470
 471             left = pos;
 472             winding = left->dir;
 473
 474             right = left->next;
 475
 476             /* Check if there is a co-linear edge with an existing trap */
 477             while (right->x == left->x) {
 478                 if (right->right != NULL) {
 479                     assert (left->right == NULL);
 480                     /* continuation on left */
 481                     left->top = right->top;
 482                     left->right = right->right;
 483                     right->right = NULL;
 484                 }
 485                 winding += right->dir;
 486                 right = right->next;
 487             }
 488
 489             if (winding == 0) {
 490                 pos = right;
 491                 continue;
 492             }
 493
 494             do {
 495                 /* End all subsumed traps */
 496                 if (unlikely (right->right != NULL))
 497                     edge_end_box (sweep, right, top);
 498
 499                 /* Greedily search for the closing edge, so that we generate
 500                  * the * maximal span width with the minimal number of
 501                  * boxes.
 502                  */
 503                 winding += right->dir;
 504                 if (winding == 0 && right->x != right->next->x)
 505                     break;
 506
 507                 right = right->next;
 508             } while (TRUE);
 509
 510             edge_start_or_continue_box (sweep, left, right, top);
 511
 512             pos = right->next;
 513         } while (pos != &sweep->tail);
 514     } else {
 515         do {
 516             edge_t *right = pos->next;
 517             int count = 0;
 518
 519             do {
 520                 /* End all subsumed traps */
 521                 if (unlikely (right->right != NULL))
 522                     edge_end_box (sweep, right, top);
 523
 524                     /* skip co-linear edges */
 525                 if (++count & 1 && right->x != right->next->x)
 526                     break;
 527
 528                 right = right->next;
 529             } while (TRUE);
 530
 531             edge_start_or_continue_box (sweep, pos, right, top);
 532
 533             pos = right->next;
 534         } while (pos != &sweep->tail);
 535     }
 536
 537     sweep->last_y = sweep->current_y;
 538 }
 539
 540 static inline void
 541 sweep_line_delete_edge (sweep_line_t *sweep, edge_t *edge)
 542 {
 543     if (edge->right != NULL) {
 544         edge_t *next = edge->next;
 545         if (next->x == edge->x) {
 546             next->top = edge->top;
 547             next->right = edge->right;
 548         } else
 549             edge_end_box (sweep, edge, sweep->current_y);
 550     }
 551
 552     if (sweep->cursor == edge)
 553         sweep->cursor = edge->prev;
 554
 555     edge->prev->next = edge->next;
 556     edge->next->prev = edge->prev;
 557 }
 558
 559 static inline cairo_bool_t
 560 sweep_line_delete (sweep_line_t *sweep, rectangle_t     *rectangle)
 561 {
 562     cairo_bool_t update;
 563
 564     update = TRUE;
 565     if (sweep->fill_rule == CAIRO_FILL_RULE_WINDING &&
 566         rectangle->left.prev->dir == rectangle->left.dir)
 567     {
 568         update = rectangle->left.next != &rectangle->right;
 569     }
 570
 571     sweep_line_delete_edge (sweep, &rectangle->left);
 572     sweep_line_delete_edge (sweep, &rectangle->right);
 573
 574     rectangle_pop_stop (sweep);
 575     return update;
 576 }
 577
 578 static inline void
 579 sweep_line_insert (sweep_line_t *sweep, rectangle_t *rectangle)
 580 {
 581     if (sweep->insert)
 582         sweep->insert->prev = &rectangle->right;
 583     rectangle->right.next = sweep->insert;
 584     rectangle->right.prev = &rectangle->left;
 585     rectangle->left.next = &rectangle->right;
 586     rectangle->left.prev = NULL;
 587     sweep->insert = &rectangle->left;
 588     if (rectangle->left.x < sweep->insert_x)
 589         sweep->insert_x = rectangle->left.x;
 590
 591     pqueue_push (sweep, rectangle);
 592 }
 593
 594 static cairo_status_t
 595 _cairo_bentley_ottmann_tessellate_rectangular (rectangle_t      **rectangles,
 596                                                int                        num_rectangles,
 597                                                cairo_fill_rule_t          fill_rule,
 598                                                cairo_bool_t              do_traps,
 599                                                void                     *container)
 600 {
 601     sweep_line_t sweep_line;
 602     rectangle_t *rectangle;
 603     cairo_status_t status;
 604     cairo_bool_t update = FALSE;
 605
 606     sweep_line_init (&sweep_line,
 607                      rectangles, num_rectangles,
 608                      fill_rule,
 609                      do_traps, container);
 610     if ((status = setjmp (sweep_line.unwind)))
 611         return status;
 612
 613     rectangle = rectangle_pop_start (&sweep_line);
 614     do {
 615         if (rectangle->top != sweep_line.current_y) {
 616             rectangle_t *stop;
 617
 618             stop = rectangle_peek_stop (&sweep_line);
 619             while (stop != NULL && stop->bottom < rectangle->top) {
 620                 if (stop->bottom != sweep_line.current_y) {
 621                     if (update) {
 622                         active_edges_to_traps (&sweep_line);
 623                         update = FALSE;
 624                     }
 625
 626                     sweep_line.current_y = stop->bottom;
 627                 }
 628
 629                 update |= sweep_line_delete (&sweep_line, stop);
 630                 stop = rectangle_peek_stop (&sweep_line);
 631             }
 632
 633             if (update) {
 634                 active_edges_to_traps (&sweep_line);
 635                 update = FALSE;
 636             }
 637
 638             sweep_line.current_y = rectangle->top;
 639         }
 640
 641         do {
 642             sweep_line_insert (&sweep_line, rectangle);
 643         } while ((rectangle = rectangle_pop_start (&sweep_line)) != NULL &&
 644                  sweep_line.current_y == rectangle->top);
 645         update = TRUE;
 646     } while (rectangle);
 647
 648     while ((rectangle = rectangle_peek_stop (&sweep_line)) != NULL) {
 649         if (rectangle->bottom != sweep_line.current_y) {
 650             if (update) {
 651                 active_edges_to_traps (&sweep_line);
 652                 update = FALSE;
 653             }
 654
 655             sweep_line.current_y = rectangle->bottom;
 656         }
 657
 658         update |= sweep_line_delete (&sweep_line, rectangle);
 659     }
 660
 661     return CAIRO_STATUS_SUCCESS;
 662 }
 663
 664 cairo_status_t
 665 _cairo_bentley_ottmann_tessellate_rectangular_traps (cairo_traps_t *traps,
 666                                                      cairo_fill_rule_t fill_rule)
 667 {
 668     rectangle_t stack_rectangles[CAIRO_STACK_ARRAY_LENGTH (rectangle_t)];
 669     rectangle_t *stack_rectangles_ptrs[ARRAY_LENGTH (stack_rectangles) + 3];
 670     rectangle_t *rectangles, **rectangles_ptrs;
 671     cairo_status_t status;
 672     int i;
 673
 674     if (unlikely (traps->num_traps <= 1))
 675         return CAIRO_STATUS_SUCCESS;
 676
 677     assert (traps->is_rectangular);
 678
 679     dump_traps (traps, "bo-rects-traps-in.txt");
 680
 681     rectangles = stack_rectangles;
 682     rectangles_ptrs = stack_rectangles_ptrs;
 683     if (traps->num_traps > ARRAY_LENGTH (stack_rectangles)) {
 684         rectangles = _cairo_malloc_ab_plus_c (traps->num_traps,
 685                                               sizeof (rectangle_t) +
 686                                               sizeof (rectangle_t *),
 687                                               3*sizeof (rectangle_t *));
 688         if (unlikely (rectangles == NULL))
 689             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 690
 691         rectangles_ptrs = (rectangle_t **) (rectangles + traps->num_traps);
 692     }
 693
 694     for (i = 0; i < traps->num_traps; i++) {
 695         if (traps->traps[i].left.p1.x < traps->traps[i].right.p1.x) {
 696             rectangles[i].left.x = traps->traps[i].left.p1.x;
 697             rectangles[i].left.dir = 1;
 698
 699             rectangles[i].right.x = traps->traps[i].right.p1.x;
 700             rectangles[i].right.dir = -1;
 701         } else {
 702             rectangles[i].right.x = traps->traps[i].left.p1.x;
 703             rectangles[i].right.dir = 1;
 704
 705             rectangles[i].left.x = traps->traps[i].right.p1.x;
 706             rectangles[i].left.dir = -1;
 707         }
 708
 709         rectangles[i].left.right = NULL;
 710         rectangles[i].right.right = NULL;
 711
 712         rectangles[i].top = traps->traps[i].top;
 713         rectangles[i].bottom = traps->traps[i].bottom;
 714
 715         rectangles_ptrs[i+2] = &rectangles[i];
 716     }
 717     /* XXX incremental sort */
 718     _rectangle_sort (rectangles_ptrs+2, i);
 719
 720     _cairo_traps_clear (traps);
 721     status = _cairo_bentley_ottmann_tessellate_rectangular (rectangles_ptrs+2, i,
 722                                                             fill_rule,
 723                                                             TRUE, traps);
 724     traps->is_rectilinear = TRUE;
 725     traps->is_rectangular = TRUE;
 726
 727     if (rectangles != stack_rectangles)
 728         free (rectangles);
 729
 730     dump_traps (traps, "bo-rects-traps-out.txt");
 731
 732     return status;
 733 }
 734
 735 cairo_status_t
 736 _cairo_bentley_ottmann_tessellate_boxes (const cairo_boxes_t *in,
 737                                          cairo_fill_rule_t fill_rule,
 738                                          cairo_boxes_t *out)
 739 {
 740     rectangle_t stack_rectangles[CAIRO_STACK_ARRAY_LENGTH (rectangle_t)];
 741     rectangle_t *stack_rectangles_ptrs[ARRAY_LENGTH (stack_rectangles) + 3];
 742     rectangle_t *rectangles, **rectangles_ptrs;
 743     rectangle_t *stack_rectangles_chain[CAIRO_STACK_ARRAY_LENGTH (rectangle_t *) ];
 744     rectangle_t **rectangles_chain = NULL;
 745     const struct _cairo_boxes_chunk *chunk;
 746     cairo_status_t status;
 747     int i, j, y_min, y_max;
 748
 749     if (unlikely (in->num_boxes == 0)) {
 750         _cairo_boxes_clear (out);
 751         return CAIRO_STATUS_SUCCESS;
 752     }
 753
 754     if (in->num_boxes == 1) {
 755         if (in == out) {
 756             cairo_box_t *box = &in->chunks.base[0];
 757
 758             if (box->p1.x > box->p2.x) {
 759                 cairo_fixed_t tmp = box->p1.x;
 760                 box->p1.x = box->p2.x;
 761                 box->p2.x = tmp;
 762             }
 763         } else {
 764             cairo_box_t box = in->chunks.base[0];
 765
 766             if (box.p1.x > box.p2.x) {
 767                 cairo_fixed_t tmp = box.p1.x;
 768                 box.p1.x = box.p2.x;
 769                 box.p2.x = tmp;
 770             }
 771
 772             _cairo_boxes_clear (out);
 773             status = _cairo_boxes_add (out, CAIRO_ANTIALIAS_DEFAULT, &box);
 774             assert (status == CAIRO_STATUS_SUCCESS);
 775         }
 776         return CAIRO_STATUS_SUCCESS;
 777     }
 778
 779     y_min = INT_MAX; y_max = INT_MIN;
 780     for (chunk = &in->chunks; chunk != NULL; chunk = chunk->next) {
 781         const cairo_box_t *box = chunk->base;
 782         for (i = 0; i < chunk->count; i++) {
 783             if (box[i].p1.y < y_min)
 784                 y_min = box[i].p1.y;
 785             if (box[i].p1.y > y_max)
 786                 y_max = box[i].p1.y;
 787         }
 788     }
 789     y_min = _cairo_fixed_integer_floor (y_min);
 790     y_max = _cairo_fixed_integer_floor (y_max) + 1;
 791     y_max -= y_min;
 792
 793     if (y_max < in->num_boxes) {
 794         rectangles_chain = stack_rectangles_chain;
 795         if (y_max > ARRAY_LENGTH (stack_rectangles_chain)) {
 796             rectangles_chain = _cairo_malloc_ab (y_max, sizeof (rectangle_t *));
 797             if (unlikely (rectangles_chain == NULL))
 798                 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 799         }
 800         memset (rectangles_chain, 0, y_max * sizeof (rectangle_t*));
 801     }
 802
 803     rectangles = stack_rectangles;
 804     rectangles_ptrs = stack_rectangles_ptrs;
 805     if (in->num_boxes > ARRAY_LENGTH (stack_rectangles)) {
 806         rectangles = _cairo_malloc_ab_plus_c (in->num_boxes,
 807                                               sizeof (rectangle_t) +
 808                                               sizeof (rectangle_t *),
 809                                               3*sizeof (rectangle_t *));
 810         if (unlikely (rectangles == NULL)) {
 811             if (rectangles_chain != stack_rectangles_chain)
 812                 free (rectangles_chain);
 813             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 814         }
 815
 816         rectangles_ptrs = (rectangle_t **) (rectangles + in->num_boxes);
 817     }
 818
 819     j = 0;
 820     for (chunk = &in->chunks; chunk != NULL; chunk = chunk->next) {
 821         const cairo_box_t *box = chunk->base;
 822         for (i = 0; i < chunk->count; i++) {
 823             int h;
 824
 825             if (box[i].p1.x < box[i].p2.x) {
 826                 rectangles[j].left.x = box[i].p1.x;
 827                 rectangles[j].left.dir = 1;
 828
 829                 rectangles[j].right.x = box[i].p2.x;
 830                 rectangles[j].right.dir = -1;
 831             } else {
 832                 rectangles[j].right.x = box[i].p1.x;
 833                 rectangles[j].right.dir = 1;
 834
 835                 rectangles[j].left.x = box[i].p2.x;
 836                 rectangles[j].left.dir = -1;
 837             }
 838
 839             rectangles[j].left.right = NULL;
 840             rectangles[j].right.right = NULL;
 841
 842             rectangles[j].top = box[i].p1.y;
 843             rectangles[j].bottom = box[i].p2.y;
 844
 845             if (rectangles_chain) {
 846                 h = _cairo_fixed_integer_floor (box[i].p1.y) - y_min;
 847                 rectangles[j].left.next = (edge_t *)rectangles_chain[h];
 848                 rectangles_chain[h] = &rectangles[j];
 849             } else {
 850                 rectangles_ptrs[j+2] = &rectangles[j];
 851             }
 852             j++;
 853         }
 854     }
 855
 856     if (rectangles_chain) {
 857         j = 2;
 858         for (y_min = 0; y_min < y_max; y_min++) {
 859             rectangle_t *r;
 860             int start = j;
 861             for (r = rectangles_chain[y_min]; r; r = (rectangle_t *)r->left.next)
 862                 rectangles_ptrs[j++] = r;
 863             if (j > start + 1)
 864                 _rectangle_sort (rectangles_ptrs + start, j - start);
 865         }
 866
 867         if (rectangles_chain != stack_rectangles_chain)
 868             free (rectangles_chain);
 869
 870         j -= 2;
 871     } else {
 872         _rectangle_sort (rectangles_ptrs + 2, j);
 873     }
 874
 875     _cairo_boxes_clear (out);
 876     status = _cairo_bentley_ottmann_tessellate_rectangular (rectangles_ptrs+2, j,
 877                                                             fill_rule,
 878                                                             FALSE, out);
 879     if (rectangles != stack_rectangles)
 880         free (rectangles);
 881
 882     return status;
 883 }