diff options
Diffstat (limited to 'libs/cairo-1.16.0/src/cairo-bentley-ottmann-rectangular.c')
| -rw-r--r-- | libs/cairo-1.16.0/src/cairo-bentley-ottmann-rectangular.c | 895 |
1 files changed, 0 insertions, 895 deletions
diff --git a/libs/cairo-1.16.0/src/cairo-bentley-ottmann-rectangular.c b/libs/cairo-1.16.0/src/cairo-bentley-ottmann-rectangular.c deleted file mode 100644 index 65f95d7..0000000 --- a/libs/cairo-1.16.0/src/cairo-bentley-ottmann-rectangular.c +++ /dev/null @@ -1,895 +0,0 @@ -/* - * 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; - - sweep_line_init (&sweep_line, - rectangles, num_rectangles, - fill_rule, - do_traps, container); - if ((status = setjmp (sweep_line.unwind))) - return status; - - update = FALSE; - - 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; - - assert (traps->is_rectangular); - - if (unlikely (traps->num_traps <= 1)) { - if (traps->num_traps == 1) { - cairo_trapezoid_t *trap = traps->traps; - if (trap->left.p1.x > trap->right.p1.x) { - cairo_line_t tmp = trap->left; - trap->left = trap->right; - trap->right = tmp; - } - } - return CAIRO_STATUS_SUCCESS; - } - - 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; -} |