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                 if (left->right != NULL)
 491                     edge_end_box (sweep, left, top);
 492                 pos = right;
 493                 continue;
 494             }
 495
 496             do {
 497                 /* End all subsumed traps */
 498                 if (unlikely (right->right != NULL))
 499                     edge_end_box (sweep, right, top);
 500
 501                 /* Greedily search for the closing edge, so that we generate
 502                  * the * maximal span width with the minimal number of
 503                  * boxes.
 504                  */
 505                 winding += right->dir;
 506                 if (winding == 0 && right->x != right->next->x)
 507                     break;
 508
 509                 right = right->next;
 510             } while (TRUE);
 511
 512             edge_start_or_continue_box (sweep, left, right, top);
 513
 514             pos = right->next;
 515         } while (pos != &sweep->tail);
 516     } else {
 517         do {
 518             edge_t *right = pos->next;
 519             int count = 0;
 520
 521             do {
 522                 /* End all subsumed traps */
 523                 if (unlikely (right->right != NULL))
 524                     edge_end_box (sweep, right, top);
 525
 526                     /* skip co-linear edges */
 527                 if (++count & 1 && right->x != right->next->x)
 528                     break;
 529
 530                 right = right->next;
 531             } while (TRUE);
 532
 533             edge_start_or_continue_box (sweep, pos, right, top);
 534
 535             pos = right->next;
 536         } while (pos != &sweep->tail);
 537     }
 538
 539     sweep->last_y = sweep->current_y;
 540 }
 541
 542 static inline void
 543 sweep_line_delete_edge (sweep_line_t *sweep, edge_t *edge)
 544 {
 545     if (edge->right != NULL) {
 546         edge_t *next = edge->next;
 547         if (next->x == edge->x) {
 548             next->top = edge->top;
 549             next->right = edge->right;
 550         } else
 551             edge_end_box (sweep, edge, sweep->current_y);
 552     }
 553
 554     if (sweep->cursor == edge)
 555         sweep->cursor = edge->prev;
 556
 557     edge->prev->next = edge->next;
 558     edge->next->prev = edge->prev;
 559 }
 560
 561 static inline cairo_bool_t
 562 sweep_line_delete (sweep_line_t *sweep, rectangle_t *rectangle)
 563 {
 564     cairo_bool_t update;
 565
 566     update = TRUE;
 567     if (sweep->fill_rule == CAIRO_FILL_RULE_WINDING &&
 568         rectangle->left.prev->dir == rectangle->left.dir)
 569     {
 570         update = rectangle->left.next != &rectangle->right;
 571     }
 572
 573     sweep_line_delete_edge (sweep, &rectangle->left);
 574     sweep_line_delete_edge (sweep, &rectangle->right);
 575
 576     rectangle_pop_stop (sweep);
 577     return update;
 578 }
 579
 580 static inline void
 581 sweep_line_insert (sweep_line_t *sweep, rectangle_t *rectangle)
 582 {
 583     if (sweep->insert)
 584         sweep->insert->prev = &rectangle->right;
 585     rectangle->right.next = sweep->insert;
 586     rectangle->right.prev = &rectangle->left;
 587     rectangle->left.next = &rectangle->right;
 588     rectangle->left.prev = NULL;
 589     sweep->insert = &rectangle->left;
 590     if (rectangle->left.x < sweep->insert_x)
 591         sweep->insert_x = rectangle->left.x;
 592
 593     pqueue_push (sweep, rectangle);
 594 }
 595
 596 static cairo_status_t
 597 _cairo_bentley_ottmann_tessellate_rectangular (rectangle_t      **rectangles,
 598                                                int                        num_rectangles,
 599                                                cairo_fill_rule_t          fill_rule,
 600                                                cairo_bool_t              do_traps,
 601                                                void                     *container)
 602 {
 603     sweep_line_t sweep_line;
 604     rectangle_t *rectangle;
 605     cairo_status_t status;
 606     cairo_bool_t update = FALSE;
 607
 608     sweep_line_init (&sweep_line,
 609                      rectangles, num_rectangles,
 610                      fill_rule,
 611                      do_traps, container);
 612     if ((status = setjmp (sweep_line.unwind)))
 613         return status;
 614
 615     rectangle = rectangle_pop_start (&sweep_line);
 616     do {
 617         if (rectangle->top != sweep_line.current_y) {
 618             rectangle_t *stop;
 619
 620             stop = rectangle_peek_stop (&sweep_line);
 621             while (stop != NULL && stop->bottom < rectangle->top) {
 622                 if (stop->bottom != sweep_line.current_y) {
 623                     if (update) {
 624                         active_edges_to_traps (&sweep_line);
 625                         update = FALSE;
 626                     }
 627
 628                     sweep_line.current_y = stop->bottom;
 629                 }
 630
 631                 update |= sweep_line_delete (&sweep_line, stop);
 632                 stop = rectangle_peek_stop (&sweep_line);
 633             }
 634
 635             if (update) {
 636                 active_edges_to_traps (&sweep_line);
 637                 update = FALSE;
 638             }
 639
 640             sweep_line.current_y = rectangle->top;
 641         }
 642
 643         do {
 644             sweep_line_insert (&sweep_line, rectangle);
 645         } while ((rectangle = rectangle_pop_start (&sweep_line)) != NULL &&
 646                  sweep_line.current_y == rectangle->top);
 647         update = TRUE;
 648     } while (rectangle);
 649
 650     while ((rectangle = rectangle_peek_stop (&sweep_line)) != NULL) {
 651         if (rectangle->bottom != sweep_line.current_y) {
 652             if (update) {
 653                 active_edges_to_traps (&sweep_line);
 654                 update = FALSE;
 655             }
 656             sweep_line.current_y = rectangle->bottom;
 657         }
 658
 659         update |= sweep_line_delete (&sweep_line, rectangle);
 660     }
 661
 662     return CAIRO_STATUS_SUCCESS;
 663 }
 664
 665 cairo_status_t
 666 _cairo_bentley_ottmann_tessellate_rectangular_traps (cairo_traps_t *traps,
 667                                                      cairo_fill_rule_t fill_rule)
 668 {
 669     rectangle_t stack_rectangles[CAIRO_STACK_ARRAY_LENGTH (rectangle_t)];
 670     rectangle_t *stack_rectangles_ptrs[ARRAY_LENGTH (stack_rectangles) + 3];
 671     rectangle_t *rectangles, **rectangles_ptrs;
 672     cairo_status_t status;
 673     int i;
 674
 675     if (unlikely (traps->num_traps <= 1))
 676         return CAIRO_STATUS_SUCCESS;
 677
 678     assert (traps->is_rectangular);
 679
 680     dump_traps (traps, "bo-rects-traps-in.txt");
 681
 682     rectangles = stack_rectangles;
 683     rectangles_ptrs = stack_rectangles_ptrs;
 684     if (traps->num_traps > ARRAY_LENGTH (stack_rectangles)) {
 685         rectangles = _cairo_malloc_ab_plus_c (traps->num_traps,
 686                                               sizeof (rectangle_t) +
 687                                               sizeof (rectangle_t *),
 688                                               3*sizeof (rectangle_t *));
 689         if (unlikely (rectangles == NULL))
 690             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 691
 692         rectangles_ptrs = (rectangle_t **) (rectangles + traps->num_traps);
 693     }
 694
 695     for (i = 0; i < traps->num_traps; i++) {
 696         if (traps->traps[i].left.p1.x < traps->traps[i].right.p1.x) {
 697             rectangles[i].left.x = traps->traps[i].left.p1.x;
 698             rectangles[i].left.dir = 1;
 699
 700             rectangles[i].right.x = traps->traps[i].right.p1.x;
 701             rectangles[i].right.dir = -1;
 702         } else {
 703             rectangles[i].right.x = traps->traps[i].left.p1.x;
 704             rectangles[i].right.dir = 1;
 705
 706             rectangles[i].left.x = traps->traps[i].right.p1.x;
 707             rectangles[i].left.dir = -1;
 708         }
 709
 710         rectangles[i].left.right = NULL;
 711         rectangles[i].right.right = NULL;
 712
 713         rectangles[i].top = traps->traps[i].top;
 714         rectangles[i].bottom = traps->traps[i].bottom;
 715
 716         rectangles_ptrs[i+2] = &rectangles[i];
 717     }
 718     /* XXX incremental sort */
 719     _rectangle_sort (rectangles_ptrs+2, i);
 720
 721     _cairo_traps_clear (traps);
 722     status = _cairo_bentley_ottmann_tessellate_rectangular (rectangles_ptrs+2, i,
 723                                                             fill_rule,
 724                                                             TRUE, traps);
 725     traps->is_rectilinear = TRUE;
 726     traps->is_rectangular = TRUE;
 727
 728     if (rectangles != stack_rectangles)
 729         free (rectangles);
 730
 731     dump_traps (traps, "bo-rects-traps-out.txt");
 732
 733     return status;
 734 }
 735
 736 cairo_status_t
 737 _cairo_bentley_ottmann_tessellate_boxes (const cairo_boxes_t *in,
 738                                          cairo_fill_rule_t fill_rule,
 739                                          cairo_boxes_t *out)
 740 {
 741     rectangle_t stack_rectangles[CAIRO_STACK_ARRAY_LENGTH (rectangle_t)];
 742     rectangle_t *stack_rectangles_ptrs[ARRAY_LENGTH (stack_rectangles) + 3];
 743     rectangle_t *rectangles, **rectangles_ptrs;
 744     rectangle_t *stack_rectangles_chain[CAIRO_STACK_ARRAY_LENGTH (rectangle_t *) ];
 745     rectangle_t **rectangles_chain = NULL;
 746     const struct _cairo_boxes_chunk *chunk;
 747     cairo_status_t status;
 748     int i, j, y_min, y_max;
 749
 750     if (unlikely (in->num_boxes == 0)) {
 751         _cairo_boxes_clear (out);
 752         return CAIRO_STATUS_SUCCESS;
 753     }
 754
 755     if (in->num_boxes == 1) {
 756         if (in == out) {
 757             cairo_box_t *box = &in->chunks.base[0];
 758
 759             if (box->p1.x > box->p2.x) {
 760                 cairo_fixed_t tmp = box->p1.x;
 761                 box->p1.x = box->p2.x;
 762                 box->p2.x = tmp;
 763             }
 764         } else {
 765             cairo_box_t box = in->chunks.base[0];
 766
 767             if (box.p1.x > box.p2.x) {
 768                 cairo_fixed_t tmp = box.p1.x;
 769                 box.p1.x = box.p2.x;
 770                 box.p2.x = tmp;
 771             }
 772
 773             _cairo_boxes_clear (out);
 774             status = _cairo_boxes_add (out, CAIRO_ANTIALIAS_DEFAULT, &box);
 775             assert (status == CAIRO_STATUS_SUCCESS);
 776         }
 777         return CAIRO_STATUS_SUCCESS;
 778     }
 779
 780     y_min = INT_MAX; y_max = INT_MIN;
 781     for (chunk = &in->chunks; chunk != NULL; chunk = chunk->next) {
 782         const cairo_box_t *box = chunk->base;
 783         for (i = 0; i < chunk->count; i++) {
 784             if (box[i].p1.y < y_min)
 785                 y_min = box[i].p1.y;
 786             if (box[i].p1.y > y_max)
 787                 y_max = box[i].p1.y;
 788         }
 789     }
 790     y_min = _cairo_fixed_integer_floor (y_min);
 791     y_max = _cairo_fixed_integer_floor (y_max) + 1;
 792     y_max -= y_min;
 793
 794     if (y_max < in->num_boxes) {
 795         rectangles_chain = stack_rectangles_chain;
 796         if (y_max > ARRAY_LENGTH (stack_rectangles_chain)) {
 797             rectangles_chain = _cairo_malloc_ab (y_max, sizeof (rectangle_t *));
 798             if (unlikely (rectangles_chain == NULL))
 799                 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 800         }
 801         memset (rectangles_chain, 0, y_max * sizeof (rectangle_t*));
 802     }
 803
 804     rectangles = stack_rectangles;
 805     rectangles_ptrs = stack_rectangles_ptrs;
 806     if (in->num_boxes > ARRAY_LENGTH (stack_rectangles)) {
 807         rectangles = _cairo_malloc_ab_plus_c (in->num_boxes,
 808                                               sizeof (rectangle_t) +
 809                                               sizeof (rectangle_t *),
 810                                               3*sizeof (rectangle_t *));
 811         if (unlikely (rectangles == NULL)) {
 812             if (rectangles_chain != stack_rectangles_chain)
 813                 free (rectangles_chain);
 814             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 815         }
 816
 817         rectangles_ptrs = (rectangle_t **) (rectangles + in->num_boxes);
 818     }
 819
 820     j = 0;
 821     for (chunk = &in->chunks; chunk != NULL; chunk = chunk->next) {
 822         const cairo_box_t *box = chunk->base;
 823         for (i = 0; i < chunk->count; i++) {
 824             int h;
 825
 826             if (box[i].p1.x < box[i].p2.x) {
 827                 rectangles[j].left.x = box[i].p1.x;
 828                 rectangles[j].left.dir = 1;
 829
 830                 rectangles[j].right.x = box[i].p2.x;
 831                 rectangles[j].right.dir = -1;
 832             } else {
 833                 rectangles[j].right.x = box[i].p1.x;
 834                 rectangles[j].right.dir = 1;
 835
 836                 rectangles[j].left.x = box[i].p2.x;
 837                 rectangles[j].left.dir = -1;
 838             }
 839
 840             rectangles[j].left.right = NULL;
 841             rectangles[j].right.right = NULL;
 842
 843             rectangles[j].top = box[i].p1.y;
 844             rectangles[j].bottom = box[i].p2.y;
 845
 846             if (rectangles_chain) {
 847                 h = _cairo_fixed_integer_floor (box[i].p1.y) - y_min;
 848                 rectangles[j].left.next = (edge_t *)rectangles_chain[h];
 849                 rectangles_chain[h] = &rectangles[j];
 850             } else {
 851                 rectangles_ptrs[j+2] = &rectangles[j];
 852             }
 853             j++;
 854         }
 855     }
 856
 857     if (rectangles_chain) {
 858         j = 2;
 859         for (y_min = 0; y_min < y_max; y_min++) {
 860             rectangle_t *r;
 861             int start = j;
 862             for (r = rectangles_chain[y_min]; r; r = (rectangle_t *)r->left.next)
 863                 rectangles_ptrs[j++] = r;
 864             if (j > start + 1)
 865                 _rectangle_sort (rectangles_ptrs + start, j - start);
 866         }
 867
 868         if (rectangles_chain != stack_rectangles_chain)
 869             free (rectangles_chain);
 870
 871         j -= 2;
 872     } else {
 873         _rectangle_sort (rectangles_ptrs + 2, j);
 874     }
 875
 876     _cairo_boxes_clear (out);
 877     status = _cairo_bentley_ottmann_tessellate_rectangular (rectangles_ptrs+2, j,
 878                                                             fill_rule,
 879                                                             FALSE, out);
 880     if (rectangles != stack_rectangles)
 881         free (rectangles);
 882
 883     return status;
 884 }