summaryrefslogtreecommitdiff
path: root/src/cairo-bentley-ottmann-rectangular.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/cairo-bentley-ottmann-rectangular.c')
-rw-r--r--src/cairo-bentley-ottmann-rectangular.c884
1 files changed, 884 insertions, 0 deletions
diff --git a/src/cairo-bentley-ottmann-rectangular.c b/src/cairo-bentley-ottmann-rectangular.c
new file mode 100644
index 000000000..5541bdc3a
--- /dev/null
+++ b/src/cairo-bentley-ottmann-rectangular.c
@@ -0,0 +1,884 @@
+/*
+ * Copyright © 2004 Carl Worth
+ * Copyright © 2006 Red Hat, Inc.
+ * Copyright © 2009 Chris Wilson
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it either under the terms of the GNU Lesser General Public
+ * License version 2.1 as published by the Free Software Foundation
+ * (the "LGPL") or, at your option, under the terms of the Mozilla
+ * Public License Version 1.1 (the "MPL"). If you do not alter this
+ * notice, a recipient may use your version of this file under either
+ * the MPL or the LGPL.
+ *
+ * You should have received a copy of the LGPL along with this library
+ * in the file COPYING-LGPL-2.1; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
+ * You should have received a copy of the MPL along with this library
+ * in the file COPYING-MPL-1.1
+ *
+ * The contents of this file are subject to the Mozilla Public License
+ * Version 1.1 (the "License"); you may not use this file except in
+ * compliance with the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
+ * OF ANY KIND, either express or implied. See the LGPL or the MPL for
+ * the specific language governing rights and limitations.
+ *
+ * The Original Code is the cairo graphics library.
+ *
+ * The Initial Developer of the Original Code is Carl Worth
+ *
+ * Contributor(s):
+ * Carl D. Worth <cworth@cworth.org>
+ * Chris Wilson <chris@chris-wilson.co.uk>
+ */
+
+/* Provide definitions for standalone compilation */
+#include "cairoint.h"
+
+#include "cairo-boxes-private.h"
+#include "cairo-error-private.h"
+#include "cairo-combsort-inline.h"
+#include "cairo-list-private.h"
+#include "cairo-traps-private.h"
+
+#include <setjmp.h>
+
+typedef struct _rectangle rectangle_t;
+typedef struct _edge edge_t;
+
+struct _edge {
+ edge_t *next, *prev;
+ edge_t *right;
+ cairo_fixed_t x, top;
+ int dir;
+};
+
+struct _rectangle {
+ edge_t left, right;
+ int32_t top, bottom;
+};
+
+#define UNROLL3(x) x x x
+
+/* the parent is always given by index/2 */
+#define PQ_PARENT_INDEX(i) ((i) >> 1)
+#define PQ_FIRST_ENTRY 1
+
+/* left and right children are index * 2 and (index * 2) +1 respectively */
+#define PQ_LEFT_CHILD_INDEX(i) ((i) << 1)
+
+typedef struct _sweep_line {
+ rectangle_t **rectangles;
+ rectangle_t **stop;
+ edge_t head, tail, *insert, *cursor;
+ int32_t current_y;
+ int32_t last_y;
+ int stop_size;
+
+ int32_t insert_x;
+ cairo_fill_rule_t fill_rule;
+
+ cairo_bool_t do_traps;
+ void *container;
+
+ jmp_buf unwind;
+} sweep_line_t;
+
+#define DEBUG_TRAPS 0
+
+#if DEBUG_TRAPS
+static void
+dump_traps (cairo_traps_t *traps, const char *filename)
+{
+ FILE *file;
+ int n;
+
+ if (getenv ("CAIRO_DEBUG_TRAPS") == NULL)
+ return;
+
+ file = fopen (filename, "a");
+ if (file != NULL) {
+ for (n = 0; n < traps->num_traps; n++) {
+ fprintf (file, "%d %d L:(%d, %d), (%d, %d) R:(%d, %d), (%d, %d)\n",
+ traps->traps[n].top,
+ traps->traps[n].bottom,
+ traps->traps[n].left.p1.x,
+ traps->traps[n].left.p1.y,
+ traps->traps[n].left.p2.x,
+ traps->traps[n].left.p2.y,
+ traps->traps[n].right.p1.x,
+ traps->traps[n].right.p1.y,
+ traps->traps[n].right.p2.x,
+ traps->traps[n].right.p2.y);
+ }
+ fprintf (file, "\n");
+ fclose (file);
+ }
+}
+#else
+#define dump_traps(traps, filename)
+#endif
+
+static inline int
+rectangle_compare_start (const rectangle_t *a,
+ const rectangle_t *b)
+{
+ return a->top - b->top;
+}
+
+static inline int
+rectangle_compare_stop (const rectangle_t *a,
+ const rectangle_t *b)
+{
+ return a->bottom - b->bottom;
+}
+
+static inline void
+pqueue_push (sweep_line_t *sweep, rectangle_t *rectangle)
+{
+ rectangle_t **elements;
+ int i, parent;
+
+ elements = sweep->stop;
+ for (i = ++sweep->stop_size;
+ i != PQ_FIRST_ENTRY &&
+ rectangle_compare_stop (rectangle,
+ elements[parent = PQ_PARENT_INDEX (i)]) < 0;
+ i = parent)
+ {
+ elements[i] = elements[parent];
+ }
+
+ elements[i] = rectangle;
+}
+
+static inline void
+rectangle_pop_stop (sweep_line_t *sweep)
+{
+ rectangle_t **elements = sweep->stop;
+ rectangle_t *tail;
+ int child, i;
+
+ tail = elements[sweep->stop_size--];
+ if (sweep->stop_size == 0) {
+ elements[PQ_FIRST_ENTRY] = NULL;
+ return;
+ }
+
+ for (i = PQ_FIRST_ENTRY;
+ (child = PQ_LEFT_CHILD_INDEX (i)) <= sweep->stop_size;
+ i = child)
+ {
+ if (child != sweep->stop_size &&
+ rectangle_compare_stop (elements[child+1],
+ elements[child]) < 0)
+ {
+ child++;
+ }
+
+ if (rectangle_compare_stop (elements[child], tail) >= 0)
+ break;
+
+ elements[i] = elements[child];
+ }
+ elements[i] = tail;
+}
+
+static inline rectangle_t *
+rectangle_pop_start (sweep_line_t *sweep_line)
+{
+ return *sweep_line->rectangles++;
+}
+
+static inline rectangle_t *
+rectangle_peek_stop (sweep_line_t *sweep_line)
+{
+ return sweep_line->stop[PQ_FIRST_ENTRY];
+}
+
+CAIRO_COMBSORT_DECLARE (_rectangle_sort,
+ rectangle_t *,
+ rectangle_compare_start)
+
+static void
+sweep_line_init (sweep_line_t *sweep_line,
+ rectangle_t **rectangles,
+ int num_rectangles,
+ cairo_fill_rule_t fill_rule,
+ cairo_bool_t do_traps,
+ void *container)
+{
+ rectangles[-2] = NULL;
+ rectangles[-1] = NULL;
+ rectangles[num_rectangles] = NULL;
+ sweep_line->rectangles = rectangles;
+ sweep_line->stop = rectangles - 2;
+ sweep_line->stop_size = 0;
+
+ sweep_line->insert = NULL;
+ sweep_line->insert_x = INT_MAX;
+ sweep_line->cursor = &sweep_line->tail;
+
+ sweep_line->head.dir = 0;
+ sweep_line->head.x = INT32_MIN;
+ sweep_line->head.right = NULL;
+ sweep_line->head.prev = NULL;
+ sweep_line->head.next = &sweep_line->tail;
+ sweep_line->tail.prev = &sweep_line->head;
+ sweep_line->tail.next = NULL;
+ sweep_line->tail.right = NULL;
+ sweep_line->tail.x = INT32_MAX;
+ sweep_line->tail.dir = 0;
+
+ sweep_line->current_y = INT32_MIN;
+ sweep_line->last_y = INT32_MIN;
+
+ sweep_line->fill_rule = fill_rule;
+ sweep_line->container = container;
+ sweep_line->do_traps = do_traps;
+}
+
+static void
+edge_end_box (sweep_line_t *sweep_line, edge_t *left, int32_t bot)
+{
+ cairo_status_t status = CAIRO_STATUS_SUCCESS;
+
+ /* Only emit (trivial) non-degenerate trapezoids with positive height. */
+ if (likely (left->top < bot)) {
+ if (sweep_line->do_traps) {
+ cairo_line_t _left = {
+ { left->x, left->top },
+ { left->x, bot },
+ }, _right = {
+ { left->right->x, left->top },
+ { left->right->x, bot },
+ };
+ _cairo_traps_add_trap (sweep_line->container, left->top, bot, &_left, &_right);
+ status = _cairo_traps_status ((cairo_traps_t *) sweep_line->container);
+ } else {
+ cairo_box_t box;
+
+ box.p1.x = left->x;
+ box.p1.y = left->top;
+ box.p2.x = left->right->x;
+ box.p2.y = bot;
+
+ status = _cairo_boxes_add (sweep_line->container,
+ CAIRO_ANTIALIAS_DEFAULT,
+ &box);
+ }
+ }
+ if (unlikely (status))
+ longjmp (sweep_line->unwind, status);
+
+ left->right = NULL;
+}
+
+/* Start a new trapezoid at the given top y coordinate, whose edges
+ * are `edge' and `edge->next'. If `edge' already has a trapezoid,
+ * then either add it to the traps in `traps', if the trapezoid's
+ * right edge differs from `edge->next', or do nothing if the new
+ * trapezoid would be a continuation of the existing one. */
+static inline void
+edge_start_or_continue_box (sweep_line_t *sweep_line,
+ edge_t *left,
+ edge_t *right,
+ int top)
+{
+ if (left->right == right)
+ return;
+
+ if (left->right != NULL) {
+ if (left->right->x == right->x) {
+ /* continuation on right, so just swap edges */
+ left->right = right;
+ return;
+ }
+
+ edge_end_box (sweep_line, left, top);
+ }
+
+ if (left->x != right->x) {
+ left->top = top;
+ left->right = right;
+ }
+}
+/*
+ * Merge two sorted edge lists.
+ * Input:
+ * - head_a: The head of the first list.
+ * - head_b: The head of the second list; head_b cannot be NULL.
+ * Output:
+ * Returns the head of the merged list.
+ *
+ * Implementation notes:
+ * To make it fast (in particular, to reduce to an insertion sort whenever
+ * one of the two input lists only has a single element) we iterate through
+ * a list until its head becomes greater than the head of the other list,
+ * then we switch their roles. As soon as one of the two lists is empty, we
+ * just attach the other one to the current list and exit.
+ * Writes to memory are only needed to "switch" lists (as it also requires
+ * attaching to the output list the list which we will be iterating next) and
+ * to attach the last non-empty list.
+ */
+static edge_t *
+merge_sorted_edges (edge_t *head_a, edge_t *head_b)
+{
+ edge_t *head, *prev;
+ int32_t x;
+
+ prev = head_a->prev;
+ if (head_a->x <= head_b->x) {
+ head = head_a;
+ } else {
+ head_b->prev = prev;
+ head = head_b;
+ goto start_with_b;
+ }
+
+ do {
+ x = head_b->x;
+ while (head_a != NULL && head_a->x <= x) {
+ prev = head_a;
+ head_a = head_a->next;
+ }
+
+ head_b->prev = prev;
+ prev->next = head_b;
+ if (head_a == NULL)
+ return head;
+
+start_with_b:
+ x = head_a->x;
+ while (head_b != NULL && head_b->x <= x) {
+ prev = head_b;
+ head_b = head_b->next;
+ }
+
+ head_a->prev = prev;
+ prev->next = head_a;
+ if (head_b == NULL)
+ return head;
+ } while (1);
+}
+
+/*
+ * Sort (part of) a list.
+ * Input:
+ * - list: The list to be sorted; list cannot be NULL.
+ * - limit: Recursion limit.
+ * Output:
+ * - head_out: The head of the sorted list containing the first 2^(level+1) elements of the
+ * input list; if the input list has fewer elements, head_out be a sorted list
+ * containing all the elements of the input list.
+ * Returns the head of the list of unprocessed elements (NULL if the sorted list contains
+ * all the elements of the input list).
+ *
+ * Implementation notes:
+ * Special case single element list, unroll/inline the sorting of the first two elements.
+ * Some tail recursion is used since we iterate on the bottom-up solution of the problem
+ * (we start with a small sorted list and keep merging other lists of the same size to it).
+ */
+static edge_t *
+sort_edges (edge_t *list,
+ unsigned int level,
+ edge_t **head_out)
+{
+ edge_t *head_other, *remaining;
+ unsigned int i;
+
+ head_other = list->next;
+
+ if (head_other == NULL) {
+ *head_out = list;
+ return NULL;
+ }
+
+ remaining = head_other->next;
+ if (list->x <= head_other->x) {
+ *head_out = list;
+ head_other->next = NULL;
+ } else {
+ *head_out = head_other;
+ head_other->prev = list->prev;
+ head_other->next = list;
+ list->prev = head_other;
+ list->next = NULL;
+ }
+
+ for (i = 0; i < level && remaining; i++) {
+ remaining = sort_edges (remaining, i, &head_other);
+ *head_out = merge_sorted_edges (*head_out, head_other);
+ }
+
+ return remaining;
+}
+
+static edge_t *
+merge_unsorted_edges (edge_t *head, edge_t *unsorted)
+{
+ sort_edges (unsorted, UINT_MAX, &unsorted);
+ return merge_sorted_edges (head, unsorted);
+}
+
+static void
+active_edges_insert (sweep_line_t *sweep)
+{
+ edge_t *prev;
+ int x;
+
+ x = sweep->insert_x;
+ prev = sweep->cursor;
+ if (prev->x > x) {
+ do {
+ prev = prev->prev;
+ } while (prev->x > x);
+ } else {
+ while (prev->next->x < x)
+ prev = prev->next;
+ }
+
+ prev->next = merge_unsorted_edges (prev->next, sweep->insert);
+ sweep->cursor = sweep->insert;
+ sweep->insert = NULL;
+ sweep->insert_x = INT_MAX;
+}
+
+static inline void
+active_edges_to_traps (sweep_line_t *sweep)
+{
+ int top = sweep->current_y;
+ edge_t *pos;
+
+ if (sweep->last_y == sweep->current_y)
+ return;
+
+ if (sweep->insert)
+ active_edges_insert (sweep);
+
+ pos = sweep->head.next;
+ if (pos == &sweep->tail)
+ return;
+
+ if (sweep->fill_rule == CAIRO_FILL_RULE_WINDING) {
+ do {
+ edge_t *left, *right;
+ int winding;
+
+ left = pos;
+ winding = left->dir;
+
+ right = left->next;
+
+ /* Check if there is a co-linear edge with an existing trap */
+ while (right->x == left->x) {
+ if (right->right != NULL) {
+ assert (left->right == NULL);
+ /* continuation on left */
+ left->top = right->top;
+ left->right = right->right;
+ right->right = NULL;
+ }
+ winding += right->dir;
+ right = right->next;
+ }
+
+ if (winding == 0) {
+ if (left->right != NULL)
+ edge_end_box (sweep, left, top);
+ pos = right;
+ continue;
+ }
+
+ do {
+ /* End all subsumed traps */
+ if (unlikely (right->right != NULL))
+ edge_end_box (sweep, right, top);
+
+ /* Greedily search for the closing edge, so that we generate
+ * the * maximal span width with the minimal number of
+ * boxes.
+ */
+ winding += right->dir;
+ if (winding == 0 && right->x != right->next->x)
+ break;
+
+ right = right->next;
+ } while (TRUE);
+
+ edge_start_or_continue_box (sweep, left, right, top);
+
+ pos = right->next;
+ } while (pos != &sweep->tail);
+ } else {
+ do {
+ edge_t *right = pos->next;
+ int count = 0;
+
+ do {
+ /* End all subsumed traps */
+ if (unlikely (right->right != NULL))
+ edge_end_box (sweep, right, top);
+
+ /* skip co-linear edges */
+ if (++count & 1 && right->x != right->next->x)
+ break;
+
+ right = right->next;
+ } while (TRUE);
+
+ edge_start_or_continue_box (sweep, pos, right, top);
+
+ pos = right->next;
+ } while (pos != &sweep->tail);
+ }
+
+ sweep->last_y = sweep->current_y;
+}
+
+static inline void
+sweep_line_delete_edge (sweep_line_t *sweep, edge_t *edge)
+{
+ if (edge->right != NULL) {
+ edge_t *next = edge->next;
+ if (next->x == edge->x) {
+ next->top = edge->top;
+ next->right = edge->right;
+ } else
+ edge_end_box (sweep, edge, sweep->current_y);
+ }
+
+ if (sweep->cursor == edge)
+ sweep->cursor = edge->prev;
+
+ edge->prev->next = edge->next;
+ edge->next->prev = edge->prev;
+}
+
+static inline cairo_bool_t
+sweep_line_delete (sweep_line_t *sweep, rectangle_t *rectangle)
+{
+ cairo_bool_t update;
+
+ update = TRUE;
+ if (sweep->fill_rule == CAIRO_FILL_RULE_WINDING &&
+ rectangle->left.prev->dir == rectangle->left.dir)
+ {
+ update = rectangle->left.next != &rectangle->right;
+ }
+
+ sweep_line_delete_edge (sweep, &rectangle->left);
+ sweep_line_delete_edge (sweep, &rectangle->right);
+
+ rectangle_pop_stop (sweep);
+ return update;
+}
+
+static inline void
+sweep_line_insert (sweep_line_t *sweep, rectangle_t *rectangle)
+{
+ if (sweep->insert)
+ sweep->insert->prev = &rectangle->right;
+ rectangle->right.next = sweep->insert;
+ rectangle->right.prev = &rectangle->left;
+ rectangle->left.next = &rectangle->right;
+ rectangle->left.prev = NULL;
+ sweep->insert = &rectangle->left;
+ if (rectangle->left.x < sweep->insert_x)
+ sweep->insert_x = rectangle->left.x;
+
+ pqueue_push (sweep, rectangle);
+}
+
+static cairo_status_t
+_cairo_bentley_ottmann_tessellate_rectangular (rectangle_t **rectangles,
+ int num_rectangles,
+ cairo_fill_rule_t fill_rule,
+ cairo_bool_t do_traps,
+ void *container)
+{
+ sweep_line_t sweep_line;
+ rectangle_t *rectangle;
+ cairo_status_t status;
+ cairo_bool_t update = FALSE;
+
+ sweep_line_init (&sweep_line,
+ rectangles, num_rectangles,
+ fill_rule,
+ do_traps, container);
+ if ((status = setjmp (sweep_line.unwind)))
+ return status;
+
+ rectangle = rectangle_pop_start (&sweep_line);
+ do {
+ if (rectangle->top != sweep_line.current_y) {
+ rectangle_t *stop;
+
+ stop = rectangle_peek_stop (&sweep_line);
+ while (stop != NULL && stop->bottom < rectangle->top) {
+ if (stop->bottom != sweep_line.current_y) {
+ if (update) {
+ active_edges_to_traps (&sweep_line);
+ update = FALSE;
+ }
+
+ sweep_line.current_y = stop->bottom;
+ }
+
+ update |= sweep_line_delete (&sweep_line, stop);
+ stop = rectangle_peek_stop (&sweep_line);
+ }
+
+ if (update) {
+ active_edges_to_traps (&sweep_line);
+ update = FALSE;
+ }
+
+ sweep_line.current_y = rectangle->top;
+ }
+
+ do {
+ sweep_line_insert (&sweep_line, rectangle);
+ } while ((rectangle = rectangle_pop_start (&sweep_line)) != NULL &&
+ sweep_line.current_y == rectangle->top);
+ update = TRUE;
+ } while (rectangle);
+
+ while ((rectangle = rectangle_peek_stop (&sweep_line)) != NULL) {
+ if (rectangle->bottom != sweep_line.current_y) {
+ if (update) {
+ active_edges_to_traps (&sweep_line);
+ update = FALSE;
+ }
+ sweep_line.current_y = rectangle->bottom;
+ }
+
+ update |= sweep_line_delete (&sweep_line, rectangle);
+ }
+
+ return CAIRO_STATUS_SUCCESS;
+}
+
+cairo_status_t
+_cairo_bentley_ottmann_tessellate_rectangular_traps (cairo_traps_t *traps,
+ cairo_fill_rule_t fill_rule)
+{
+ rectangle_t stack_rectangles[CAIRO_STACK_ARRAY_LENGTH (rectangle_t)];
+ rectangle_t *stack_rectangles_ptrs[ARRAY_LENGTH (stack_rectangles) + 3];
+ rectangle_t *rectangles, **rectangles_ptrs;
+ cairo_status_t status;
+ int i;
+
+ if (unlikely (traps->num_traps <= 1))
+ return CAIRO_STATUS_SUCCESS;
+
+ assert (traps->is_rectangular);
+
+ dump_traps (traps, "bo-rects-traps-in.txt");
+
+ rectangles = stack_rectangles;
+ rectangles_ptrs = stack_rectangles_ptrs;
+ if (traps->num_traps > ARRAY_LENGTH (stack_rectangles)) {
+ rectangles = _cairo_malloc_ab_plus_c (traps->num_traps,
+ sizeof (rectangle_t) +
+ sizeof (rectangle_t *),
+ 3*sizeof (rectangle_t *));
+ if (unlikely (rectangles == NULL))
+ return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+
+ rectangles_ptrs = (rectangle_t **) (rectangles + traps->num_traps);
+ }
+
+ for (i = 0; i < traps->num_traps; i++) {
+ if (traps->traps[i].left.p1.x < traps->traps[i].right.p1.x) {
+ rectangles[i].left.x = traps->traps[i].left.p1.x;
+ rectangles[i].left.dir = 1;
+
+ rectangles[i].right.x = traps->traps[i].right.p1.x;
+ rectangles[i].right.dir = -1;
+ } else {
+ rectangles[i].right.x = traps->traps[i].left.p1.x;
+ rectangles[i].right.dir = 1;
+
+ rectangles[i].left.x = traps->traps[i].right.p1.x;
+ rectangles[i].left.dir = -1;
+ }
+
+ rectangles[i].left.right = NULL;
+ rectangles[i].right.right = NULL;
+
+ rectangles[i].top = traps->traps[i].top;
+ rectangles[i].bottom = traps->traps[i].bottom;
+
+ rectangles_ptrs[i+2] = &rectangles[i];
+ }
+ /* XXX incremental sort */
+ _rectangle_sort (rectangles_ptrs+2, i);
+
+ _cairo_traps_clear (traps);
+ status = _cairo_bentley_ottmann_tessellate_rectangular (rectangles_ptrs+2, i,
+ fill_rule,
+ TRUE, traps);
+ traps->is_rectilinear = TRUE;
+ traps->is_rectangular = TRUE;
+
+ if (rectangles != stack_rectangles)
+ free (rectangles);
+
+ dump_traps (traps, "bo-rects-traps-out.txt");
+
+ return status;
+}
+
+cairo_status_t
+_cairo_bentley_ottmann_tessellate_boxes (const cairo_boxes_t *in,
+ cairo_fill_rule_t fill_rule,
+ cairo_boxes_t *out)
+{
+ rectangle_t stack_rectangles[CAIRO_STACK_ARRAY_LENGTH (rectangle_t)];
+ rectangle_t *stack_rectangles_ptrs[ARRAY_LENGTH (stack_rectangles) + 3];
+ rectangle_t *rectangles, **rectangles_ptrs;
+ rectangle_t *stack_rectangles_chain[CAIRO_STACK_ARRAY_LENGTH (rectangle_t *) ];
+ rectangle_t **rectangles_chain = NULL;
+ const struct _cairo_boxes_chunk *chunk;
+ cairo_status_t status;
+ int i, j, y_min, y_max;
+
+ if (unlikely (in->num_boxes == 0)) {
+ _cairo_boxes_clear (out);
+ return CAIRO_STATUS_SUCCESS;
+ }
+
+ if (in->num_boxes == 1) {
+ if (in == out) {
+ cairo_box_t *box = &in->chunks.base[0];
+
+ if (box->p1.x > box->p2.x) {
+ cairo_fixed_t tmp = box->p1.x;
+ box->p1.x = box->p2.x;
+ box->p2.x = tmp;
+ }
+ } else {
+ cairo_box_t box = in->chunks.base[0];
+
+ if (box.p1.x > box.p2.x) {
+ cairo_fixed_t tmp = box.p1.x;
+ box.p1.x = box.p2.x;
+ box.p2.x = tmp;
+ }
+
+ _cairo_boxes_clear (out);
+ status = _cairo_boxes_add (out, CAIRO_ANTIALIAS_DEFAULT, &box);
+ assert (status == CAIRO_STATUS_SUCCESS);
+ }
+ return CAIRO_STATUS_SUCCESS;
+ }
+
+ y_min = INT_MAX; y_max = INT_MIN;
+ for (chunk = &in->chunks; chunk != NULL; chunk = chunk->next) {
+ const cairo_box_t *box = chunk->base;
+ for (i = 0; i < chunk->count; i++) {
+ if (box[i].p1.y < y_min)
+ y_min = box[i].p1.y;
+ if (box[i].p1.y > y_max)
+ y_max = box[i].p1.y;
+ }
+ }
+ y_min = _cairo_fixed_integer_floor (y_min);
+ y_max = _cairo_fixed_integer_floor (y_max) + 1;
+ y_max -= y_min;
+
+ if (y_max < in->num_boxes) {
+ rectangles_chain = stack_rectangles_chain;
+ if (y_max > ARRAY_LENGTH (stack_rectangles_chain)) {
+ rectangles_chain = _cairo_malloc_ab (y_max, sizeof (rectangle_t *));
+ if (unlikely (rectangles_chain == NULL))
+ return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+ }
+ memset (rectangles_chain, 0, y_max * sizeof (rectangle_t*));
+ }
+
+ rectangles = stack_rectangles;
+ rectangles_ptrs = stack_rectangles_ptrs;
+ if (in->num_boxes > ARRAY_LENGTH (stack_rectangles)) {
+ rectangles = _cairo_malloc_ab_plus_c (in->num_boxes,
+ sizeof (rectangle_t) +
+ sizeof (rectangle_t *),
+ 3*sizeof (rectangle_t *));
+ if (unlikely (rectangles == NULL)) {
+ if (rectangles_chain != stack_rectangles_chain)
+ free (rectangles_chain);
+ return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+ }
+
+ rectangles_ptrs = (rectangle_t **) (rectangles + in->num_boxes);
+ }
+
+ j = 0;
+ for (chunk = &in->chunks; chunk != NULL; chunk = chunk->next) {
+ const cairo_box_t *box = chunk->base;
+ for (i = 0; i < chunk->count; i++) {
+ int h;
+
+ if (box[i].p1.x < box[i].p2.x) {
+ rectangles[j].left.x = box[i].p1.x;
+ rectangles[j].left.dir = 1;
+
+ rectangles[j].right.x = box[i].p2.x;
+ rectangles[j].right.dir = -1;
+ } else {
+ rectangles[j].right.x = box[i].p1.x;
+ rectangles[j].right.dir = 1;
+
+ rectangles[j].left.x = box[i].p2.x;
+ rectangles[j].left.dir = -1;
+ }
+
+ rectangles[j].left.right = NULL;
+ rectangles[j].right.right = NULL;
+
+ rectangles[j].top = box[i].p1.y;
+ rectangles[j].bottom = box[i].p2.y;
+
+ if (rectangles_chain) {
+ h = _cairo_fixed_integer_floor (box[i].p1.y) - y_min;
+ rectangles[j].left.next = (edge_t *)rectangles_chain[h];
+ rectangles_chain[h] = &rectangles[j];
+ } else {
+ rectangles_ptrs[j+2] = &rectangles[j];
+ }
+ j++;
+ }
+ }
+
+ if (rectangles_chain) {
+ j = 2;
+ for (y_min = 0; y_min < y_max; y_min++) {
+ rectangle_t *r;
+ int start = j;
+ for (r = rectangles_chain[y_min]; r; r = (rectangle_t *)r->left.next)
+ rectangles_ptrs[j++] = r;
+ if (j > start + 1)
+ _rectangle_sort (rectangles_ptrs + start, j - start);
+ }
+
+ if (rectangles_chain != stack_rectangles_chain)
+ free (rectangles_chain);
+
+ j -= 2;
+ } else {
+ _rectangle_sort (rectangles_ptrs + 2, j);
+ }
+
+ _cairo_boxes_clear (out);
+ status = _cairo_bentley_ottmann_tessellate_rectangular (rectangles_ptrs+2, j,
+ fill_rule,
+ FALSE, out);
+ if (rectangles != stack_rectangles)
+ free (rectangles);
+
+ return status;
+}