diff options
-rw-r--r-- | src/Makefile.sources | 1 | ||||
-rw-r--r-- | src/cairo-bentley-ottmann-rectangular.c | 733 | ||||
-rw-r--r-- | src/cairo-clip.c | 26 | ||||
-rw-r--r-- | src/cairo-path-fill.c | 40 | ||||
-rw-r--r-- | src/cairo-path-stroke.c | 3 | ||||
-rw-r--r-- | src/cairo-surface-fallback.c | 95 | ||||
-rw-r--r-- | src/cairo-traps.c | 28 | ||||
-rw-r--r-- | src/cairoint.h | 5 |
8 files changed, 883 insertions, 48 deletions
diff --git a/src/Makefile.sources b/src/Makefile.sources index 156bae26..c8da2363 100644 --- a/src/Makefile.sources +++ b/src/Makefile.sources @@ -100,6 +100,7 @@ cairo_sources = \ cairo-atomic.c \ cairo-base85-stream.c \ cairo-bentley-ottmann.c \ + cairo-bentley-ottmann-rectangular.c \ cairo-bentley-ottmann-rectilinear.c \ cairo.c \ cairo-cache.c \ diff --git a/src/cairo-bentley-ottmann-rectangular.c b/src/cairo-bentley-ottmann-rectangular.c new file mode 100644 index 00000000..a805f578 --- /dev/null +++ b/src/cairo-bentley-ottmann-rectangular.c @@ -0,0 +1,733 @@ +/* + * 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 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-combsort-private.h" +#include "cairo-list-private.h" + +typedef struct _cairo_bo_rectangle cairo_bo_rectangle_t; +typedef struct _cairo_bo_edge cairo_bo_edge_t; + +/* A deferred trapezoid of an edge */ +typedef struct _cairo_bo_trap { + cairo_bo_edge_t *right; + int32_t top; +} cairo_bo_trap_t; + +struct _cairo_bo_edge { + int x; + int dir; + cairo_bo_trap_t deferred_trap; + cairo_list_t link; +}; + +struct _cairo_bo_rectangle { + cairo_bo_edge_t left, right; + int top, bottom; +}; + +/* 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 _pqueue { + int size, max_size; + + cairo_bo_rectangle_t **elements; + cairo_bo_rectangle_t *elements_embedded[1024]; +} pqueue_t; + +typedef struct _cairo_bo_sweep_line { + cairo_bo_rectangle_t **rectangles; + pqueue_t stop; + cairo_list_t sweep; + cairo_list_t *current_left, *current_right; + int32_t current_y; + int32_t last_y; +} cairo_bo_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 +cairo_bo_rectangle_compare_start (const cairo_bo_rectangle_t *a, + const cairo_bo_rectangle_t *b) +{ + return a->top - b->top; +} + +static inline int +_cairo_bo_rectangle_compare_stop (const cairo_bo_rectangle_t *a, + const cairo_bo_rectangle_t *b) +{ + return a->bottom - b->bottom; +} + +static inline void +_pqueue_init (pqueue_t *pq) +{ + pq->max_size = ARRAY_LENGTH (pq->elements_embedded); + pq->size = 0; + + pq->elements = pq->elements_embedded; + pq->elements[PQ_FIRST_ENTRY] = NULL; +} + +static inline void +_pqueue_fini (pqueue_t *pq) +{ + if (pq->elements != pq->elements_embedded) + free (pq->elements); +} + +static cairo_status_t +_pqueue_grow (pqueue_t *pq) +{ + cairo_bo_rectangle_t **new_elements; + pq->max_size *= 2; + + if (pq->elements == pq->elements_embedded) { + new_elements = _cairo_malloc_ab (pq->max_size, + sizeof (cairo_bo_rectangle_t *)); + if (unlikely (new_elements == NULL)) + return _cairo_error (CAIRO_STATUS_NO_MEMORY); + + memcpy (new_elements, pq->elements_embedded, + sizeof (pq->elements_embedded)); + } else { + new_elements = _cairo_realloc_ab (pq->elements, + pq->max_size, + sizeof (cairo_bo_rectangle_t *)); + if (unlikely (new_elements == NULL)) + return _cairo_error (CAIRO_STATUS_NO_MEMORY); + } + + pq->elements = new_elements; + return CAIRO_STATUS_SUCCESS; +} + +static inline cairo_status_t +_pqueue_push (pqueue_t *pq, cairo_bo_rectangle_t *rectangle) +{ + cairo_bo_rectangle_t **elements; + int i, parent; + + if (unlikely (pq->size + 1 == pq->max_size)) { + cairo_status_t status; + + status = _pqueue_grow (pq); + if (unlikely (status)) + return status; + } + + elements = pq->elements; + + for (i = ++pq->size; + i != PQ_FIRST_ENTRY && + _cairo_bo_rectangle_compare_stop (rectangle, + elements[parent = PQ_PARENT_INDEX (i)]) < 0; + i = parent) + { + elements[i] = elements[parent]; + } + + elements[i] = rectangle; + + return CAIRO_STATUS_SUCCESS; +} + +static inline void +_pqueue_pop (pqueue_t *pq) +{ + cairo_bo_rectangle_t **elements = pq->elements; + cairo_bo_rectangle_t *tail; + int child, i; + + tail = elements[pq->size--]; + if (pq->size == 0) { + elements[PQ_FIRST_ENTRY] = NULL; + return; + } + + for (i = PQ_FIRST_ENTRY; + (child = PQ_LEFT_CHILD_INDEX (i)) <= pq->size; + i = child) + { + if (child != pq->size && + _cairo_bo_rectangle_compare_stop (elements[child+1], + elements[child]) < 0) + { + child++; + } + + if (_cairo_bo_rectangle_compare_stop (elements[child], tail) >= 0) + break; + + elements[i] = elements[child]; + } + elements[i] = tail; +} + +static inline cairo_bo_rectangle_t * +_cairo_bo_rectangle_pop_start (cairo_bo_sweep_line_t *sweep_line) +{ + return *sweep_line->rectangles++; +} + +static inline cairo_bo_rectangle_t * +_cairo_bo_rectangle_peek_stop (cairo_bo_sweep_line_t *sweep_line) +{ + return sweep_line->stop.elements[PQ_FIRST_ENTRY]; +} + +CAIRO_COMBSORT_DECLARE (_cairo_bo_rectangle_sort, + cairo_bo_rectangle_t *, + cairo_bo_rectangle_compare_start) + +static void +_cairo_bo_sweep_line_init (cairo_bo_sweep_line_t *sweep_line, + cairo_bo_rectangle_t **rectangles, + int num_rectangles) +{ + _cairo_bo_rectangle_sort (rectangles, num_rectangles); + rectangles[num_rectangles] = NULL; + sweep_line->rectangles = rectangles; + + cairo_list_init (&sweep_line->sweep); + sweep_line->current_left = &sweep_line->sweep; + sweep_line->current_right = &sweep_line->sweep; + sweep_line->current_y = INT32_MIN; + sweep_line->last_y = INT32_MIN; + + _pqueue_init (&sweep_line->stop); +} + +static void +_cairo_bo_sweep_line_fini (cairo_bo_sweep_line_t *sweep_line) +{ + _pqueue_fini (&sweep_line->stop); +} + +static inline cairo_bo_edge_t * +link_to_edge (cairo_list_t *elt) +{ + return cairo_container_of (elt, cairo_bo_edge_t, link); +} + +static cairo_status_t +_cairo_bo_edge_end_trap (cairo_bo_edge_t *left, + int32_t bot, + cairo_traps_t *traps) +{ + cairo_bo_trap_t *trap = &left->deferred_trap; + + /* Only emit (trivial) non-degenerate trapezoids with positive height. */ + if (likely (trap->top < bot)) { + cairo_line_t _left = { + { left->x, trap->top }, + { left->x, bot }, + }, _right = { + { trap->right->x, trap->top }, + { trap->right->x, bot }, + }; + _cairo_traps_add_trap (traps, trap->top, bot, &_left, &_right); + } + + trap->right = NULL; + + return _cairo_traps_status (traps); +} + +/* 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 cairo_status_t +_cairo_bo_edge_start_or_continue_trap (cairo_bo_edge_t *left, + cairo_bo_edge_t *right, + int top, + cairo_traps_t *traps) +{ + cairo_status_t status; + + if (left->deferred_trap.right == right) + return CAIRO_STATUS_SUCCESS; + + if (left->deferred_trap.right != NULL) { + if (right != NULL && left->deferred_trap.right->x == right->x) { + /* continuation on right, so just swap edges */ + left->deferred_trap.right = right; + return CAIRO_STATUS_SUCCESS; + } + + status = _cairo_bo_edge_end_trap (left, top, traps); + if (unlikely (status)) + return status; + } + + if (right != NULL && left->x != right->x) { + left->deferred_trap.top = top; + left->deferred_trap.right = right; + } + + return CAIRO_STATUS_SUCCESS; +} + +static inline cairo_status_t +_active_edges_to_traps (cairo_bo_sweep_line_t *sweep, + cairo_fill_rule_t fill_rule, + cairo_traps_t *traps) +{ + int top = sweep->current_y; + cairo_list_t *pos = &sweep->sweep; + cairo_status_t status; + + if (sweep->last_y == sweep->current_y) + return CAIRO_STATUS_SUCCESS; + + if (fill_rule == CAIRO_FILL_RULE_WINDING) { + do { + cairo_bo_edge_t *left, *right; + int in_out; + + pos = pos->next; + if (pos == &sweep->sweep) + break; + + left = link_to_edge (pos); + in_out = left->dir; + + /* Check if there is a co-linear edge with an existing trap */ + if (left->deferred_trap.right == NULL) { + right = link_to_edge (pos->next); + while (unlikely (right->x == left->x)) { + if (right->deferred_trap.right != NULL) { + /* continuation on left */ + left->deferred_trap = right->deferred_trap; + right->deferred_trap.right = NULL; + break; + } + + right = link_to_edge (right->link.next); + } + } + + /* Greedily search for the closing edge, so that we generate the + * maximal span width with the minimal number of trapezoids. + */ + + right = link_to_edge (left->link.next); + do { + /* End all subsumed traps */ + if (right->deferred_trap.right != NULL) { + status = _cairo_bo_edge_end_trap (right, top, traps); + if (unlikely (status)) + return status; + } + + in_out += right->dir; + if (in_out == 0) { + /* skip co-linear edges */ + if (likely (right->link.next == &sweep->sweep || + right->x != link_to_edge (right->link.next)->x)) + { + break; + } + } + + right = link_to_edge (right->link.next); + } while (TRUE); + + status = _cairo_bo_edge_start_or_continue_trap (left, right, + top, traps); + if (unlikely (status)) + return status; + + pos = &right->link; + } while (TRUE); + } else { + cairo_bo_edge_t *left, *right; + do { + int in_out = 0; + + pos = pos->next; + if (pos == &sweep->sweep) + break; + + left = link_to_edge (pos); + + pos = pos->next; + do { + right = link_to_edge (pos); + if (right->deferred_trap.right != NULL) { + status = _cairo_bo_edge_end_trap (right, top, traps); + if (unlikely (status)) + return status; + } + + if ((in_out++ & 1) == 0) { + cairo_list_t *next; + cairo_bool_t skip = FALSE; + + /* skip co-linear edges */ + next = pos->next; + if (next != &sweep->sweep) + skip = right->x == link_to_edge (next)->x; + + if (! skip) + break; + } + pos = pos->next; + } while (TRUE); + + right = pos == &sweep->sweep ? NULL : link_to_edge (pos); + status = _cairo_bo_edge_start_or_continue_trap (left, right, + top, traps); + if (unlikely (status)) + return status; + } while (right != NULL); + } + + sweep->last_y = sweep->current_y; + return CAIRO_STATUS_SUCCESS; +} + +static inline cairo_status_t +_cairo_bo_sweep_line_delete_edge (cairo_bo_sweep_line_t *sweep_line, + cairo_bo_edge_t *edge, + cairo_traps_t *traps) +{ + if (edge->deferred_trap.right != NULL) { + cairo_bo_edge_t *next = link_to_edge (edge->link.next); + if (&next->link != &sweep_line->sweep && next->x == edge->x) { + next->deferred_trap = edge->deferred_trap; + } else { + cairo_status_t status; + + status = _cairo_bo_edge_end_trap (edge, + sweep_line->current_y, + traps); + if (unlikely (status)) + return status; + } + } + + if (sweep_line->current_left == &edge->link) + sweep_line->current_left = edge->link.prev; + + if (sweep_line->current_right == &edge->link) + sweep_line->current_right = edge->link.next; + + cairo_list_del (&edge->link); + + return CAIRO_STATUS_SUCCESS; +} + +static inline cairo_status_t +_cairo_bo_sweep_line_delete (cairo_bo_sweep_line_t *sweep_line, + cairo_bo_rectangle_t *rectangle, + cairo_fill_rule_t fill_rule, + cairo_traps_t *traps) +{ + cairo_status_t status; + + if (rectangle->bottom != sweep_line->current_y) { + status = _active_edges_to_traps (sweep_line, fill_rule, traps); + if (unlikely (status)) + return status; + + sweep_line->current_y = rectangle->bottom; + } + + status = _cairo_bo_sweep_line_delete_edge (sweep_line, + &rectangle->left, + traps); + if (unlikely (status)) + return status; + + status = _cairo_bo_sweep_line_delete_edge (sweep_line, + &rectangle->right, + traps); + if (unlikely (status)) + return status; + + _pqueue_pop (&sweep_line->stop); + return CAIRO_STATUS_SUCCESS; +} + +static cairo_bool_t +validate_sweep_line (cairo_bo_sweep_line_t *sweep_line) +{ + int32_t last_x = INT32_MIN; + cairo_bo_edge_t *edge; + cairo_list_foreach_entry (edge, cairo_bo_edge_t, &sweep_line->sweep, link) { + if (edge->x < last_x) + return FALSE; + last_x = edge->x; + } + return TRUE; +} +static inline cairo_status_t +_cairo_bo_sweep_line_insert (cairo_bo_sweep_line_t *sweep_line, + cairo_bo_rectangle_t *rectangle, + cairo_fill_rule_t fill_rule, + cairo_traps_t *traps) +{ + cairo_list_t *pos; + cairo_status_t status; + + if (rectangle->top != sweep_line->current_y) { + cairo_bo_rectangle_t *stop; + + stop = _cairo_bo_rectangle_peek_stop (sweep_line); + while (stop != NULL && stop->bottom < rectangle->top) { + status = _cairo_bo_sweep_line_delete (sweep_line, stop, + fill_rule, traps); + if (unlikely (status)) + return status; + + stop = _cairo_bo_rectangle_peek_stop (sweep_line); + } + + status = _active_edges_to_traps (sweep_line, fill_rule, traps); + if (unlikely (status)) + return status; + + sweep_line->current_y = rectangle->top; + } + + /* right edge */ + pos = sweep_line->current_right; + if (pos != &sweep_line->sweep) { + int cmp; + + cmp = link_to_edge (pos)->x - rectangle->right.x; + if (cmp < 0) { + while (pos->next != &sweep_line->sweep && + link_to_edge (pos->next)->x - rectangle->right.x < 0) + { + pos = pos->next; + } + } else if (cmp > 0) { + do { + pos = pos->prev; + } while (pos != &sweep_line->sweep && + link_to_edge (pos)->x - rectangle->right.x > 0); + } + + cairo_list_add (&rectangle->right.link, pos); + } else { + cairo_list_add_tail (&rectangle->right.link, pos); + } + sweep_line->current_right = &rectangle->right.link; + assert (validate_sweep_line (sweep_line)); + + /* left edge */ + pos = sweep_line->current_left; + if (pos != &sweep_line->sweep) { + int cmp; + + if (link_to_edge (pos)->x >= rectangle->right.x) { + pos = rectangle->right.link.prev; + if (pos == &sweep_line->sweep) + goto left_done; + } + + cmp = link_to_edge (pos)->x - rectangle->left.x; + if (cmp < 0) { + while (pos->next != &sweep_line->sweep && + link_to_edge (pos->next)->x - rectangle->left.x < 0) + { + pos = pos->next; + } + } else if (cmp > 0) { + do { + pos = pos->prev; + } while (pos != &sweep_line->sweep && + link_to_edge (pos)->x - rectangle->left.x > 0); + } + } + left_done: + cairo_list_add (&rectangle->left.link, pos); + sweep_line->current_left = &rectangle->left.link; + assert (validate_sweep_line (sweep_line)); + + return _pqueue_push (&sweep_line->stop, rectangle); +} + +static cairo_status_t +_cairo_bentley_ottmann_tessellate_rectangular (cairo_bo_rectangle_t **rectangles, + int num_rectangles, + cairo_fill_rule_t fill_rule, + cairo_traps_t *traps) +{ + cairo_bo_sweep_line_t sweep_line; + cairo_bo_rectangle_t *rectangle; + cairo_status_t status = CAIRO_STATUS_SUCCESS; + + _cairo_bo_sweep_line_init (&sweep_line, rectangles, num_rectangles); + + while ((rectangle = _cairo_bo_rectangle_pop_start (&sweep_line)) != NULL) { + status = _cairo_bo_sweep_line_insert (&sweep_line, rectangle, + fill_rule, traps); + if (unlikely (status)) + goto BAIL; + } + + while ((rectangle = _cairo_bo_rectangle_peek_stop (&sweep_line)) != NULL) { + status = _cairo_bo_sweep_line_delete (&sweep_line, rectangle, + fill_rule, traps); + if (unlikely (status)) + goto BAIL; + } + +BAIL: + _cairo_bo_sweep_line_fini (&sweep_line); + return status; +} + +cairo_status_t +_cairo_bentley_ottmann_tessellate_rectangular_traps (cairo_traps_t *traps, + cairo_fill_rule_t fill_rule) +{ + cairo_bo_rectangle_t stack_rectangles[CAIRO_STACK_ARRAY_LENGTH (cairo_bo_rectangle_t)]; + cairo_bo_rectangle_t *rectangles; + cairo_bo_rectangle_t *stack_rectangles_ptrs[ARRAY_LENGTH (stack_rectangles) + 1]; + cairo_bo_rectangle_t **rectangles_ptrs; + cairo_status_t status; + int i; + + if (unlikely (traps->num_traps == 0)) + 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 (cairo_bo_rectangle_t) + + sizeof (cairo_bo_rectangle_t *), + sizeof (cairo_bo_rectangle_t *)); + if (unlikely (rectangles == NULL)) + return _cairo_error (CAIRO_STATUS_NO_MEMORY); + + rectangles_ptrs = (cairo_bo_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.deferred_trap.right = NULL; + cairo_list_init (&rectangles[i].left.link); + + rectangles[i].right.deferred_trap.right = NULL; + cairo_list_init (&rectangles[i].right.link); + + rectangles[i].top = traps->traps[i].top; + rectangles[i].bottom = traps->traps[i].bottom; + + rectangles_ptrs[i] = &rectangles[i]; + } + + _cairo_traps_clear (traps); + status = _cairo_bentley_ottmann_tessellate_rectangular (rectangles_ptrs, i, + fill_rule, + 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; +} diff --git a/src/cairo-clip.c b/src/cairo-clip.c index 8d68e47e..cd6cfec1 100644 --- a/src/cairo-clip.c +++ b/src/cairo-clip.c @@ -755,7 +755,7 @@ _region_clip_to_boxes (const cairo_region_t *region, goto CLEANUP; } - status = _cairo_bentley_ottmann_tessellate_rectilinear_traps (&traps, CAIRO_FILL_RULE_WINDING); + status = _cairo_bentley_ottmann_tessellate_rectangular_traps (&traps, CAIRO_FILL_RULE_WINDING); if (unlikely (status)) goto CLEANUP; @@ -804,25 +804,35 @@ _rectilinear_clip_to_boxes (const cairo_path_fixed_t *path, cairo_traps_t traps; cairo_status_t status; + _cairo_traps_init (&traps); + _cairo_traps_limit (&traps, *boxes, *num_boxes); + _cairo_polygon_init (&polygon); _cairo_polygon_limit (&polygon, *boxes, *num_boxes); + status = _cairo_path_fixed_fill_rectilinear_to_traps (path, + fill_rule, + &traps); + if (unlikely (_cairo_status_is_error (status))) + goto CLEANUP; + if (status == CAIRO_STATUS_SUCCESS) + goto BOXES; + /* tolerance will be ignored as the path is rectilinear */ status = _cairo_path_fixed_fill_to_polygon (path, 0., &polygon); if (unlikely (status)) - goto CLEANUP_POLYGON; + goto CLEANUP; if (polygon.num_edges == 0) { *num_boxes = 0; } else { - _cairo_traps_init (&traps); - status = _cairo_bentley_ottmann_tessellate_rectilinear_polygon (&traps, &polygon, fill_rule); if (likely (status == CAIRO_STATUS_SUCCESS)) { int i; + BOXES: i = *size_boxes; if (i < 0) i = -i; @@ -835,7 +845,7 @@ _rectilinear_clip_to_boxes (const cairo_path_fixed_t *path, new_boxes = _cairo_malloc_ab (new_size, sizeof (cairo_box_t)); if (unlikely (new_boxes == NULL)) { status = _cairo_error (CAIRO_STATUS_NO_MEMORY); - goto CLEANUP_TRAPS; + goto CLEANUP; } if (*size_boxes > 0) @@ -853,13 +863,11 @@ _rectilinear_clip_to_boxes (const cairo_path_fixed_t *path, } *num_boxes = i; } - - CLEANUP_TRAPS: - _cairo_traps_fini (&traps); } - CLEANUP_POLYGON: + CLEANUP: _cairo_polygon_fini (&polygon); + _cairo_traps_fini (&traps); return status; } diff --git a/src/cairo-path-fill.c b/src/cairo-path-fill.c index 3daf2461..870a987f 100644 --- a/src/cairo-path-fill.c +++ b/src/cairo-path-fill.c @@ -356,6 +356,9 @@ _cairo_path_fixed_fill_rectilinear_to_traps (const cairo_path_fixed_t *path, cairo_box_t box; cairo_status_t status; + traps->is_rectilinear = TRUE; + traps->is_rectangular = TRUE; + if (_cairo_path_fixed_is_box (path, &box)) { if (box.p1.x > box.p2.x) { cairo_fixed_t t; @@ -374,24 +377,11 @@ _cairo_path_fixed_fill_rectilinear_to_traps (const cairo_path_fixed_t *path, } return _cairo_traps_tessellate_rectangle (traps, &box.p1, &box.p2); - } else if (fill_rule == CAIRO_FILL_RULE_WINDING) { + } else { cairo_path_fixed_iter_t iter; - int last_cw = -1; _cairo_path_fixed_iter_init (&iter, path); while (_cairo_path_fixed_iter_is_fill_box (&iter, &box)) { - int cw = 0; - - if (box.p1.x > box.p2.x) { - cairo_fixed_t t; - - t = box.p1.x; - box.p1.x = box.p2.x; - box.p2.x = t; - - cw = ! cw; - } - if (box.p1.y > box.p2.y) { cairo_fixed_t t; @@ -399,25 +389,23 @@ _cairo_path_fixed_fill_rectilinear_to_traps (const cairo_path_fixed_t *path, box.p1.y = box.p2.y; box.p2.y = t; - cw = ! cw; + t = box.p1.x; + box.p1.x = box.p2.x; + box.p2.x = t; } - if (last_cw < 0) - last_cw = cw; - else if (last_cw != cw) - goto out; - status = _cairo_traps_tessellate_rectangle (traps, &box.p1, &box.p2); - if (unlikely (status)) + if (unlikely (status)) { + _cairo_traps_clear (traps); return status; + } } if (_cairo_path_fixed_iter_at_end (&iter)) - return CAIRO_STATUS_SUCCESS; - } + return _cairo_bentley_ottmann_tessellate_rectangular_traps (traps, fill_rule); - out: - _cairo_traps_clear (traps); - return CAIRO_INT_STATUS_UNSUPPORTED; + _cairo_traps_clear (traps); + return CAIRO_INT_STATUS_UNSUPPORTED; + } } diff --git a/src/cairo-path-stroke.c b/src/cairo-path-stroke.c index 69300da3..5c4f4fc7 100644 --- a/src/cairo-path-stroke.c +++ b/src/cairo-path-stroke.c @@ -2029,8 +2029,9 @@ _cairo_path_fixed_stroke_rectilinear_to_traps (const cairo_path_fixed_t *path, status = _cairo_rectilinear_stroker_emit_segments (&rectilinear_stroker); traps->is_rectilinear = 1; + traps->is_rectangular = 1; /* As we incrementally tessellate, we do not eliminate self-intersections */ - traps->has_intersections = traps->num_traps != 0; + traps->has_intersections = traps->num_traps > 1; BAIL: _cairo_rectilinear_stroker_fini (&rectilinear_stroker); diff --git a/src/cairo-surface-fallback.c b/src/cairo-surface-fallback.c index 4dc8ebbc..2755e16c 100644 --- a/src/cairo-surface-fallback.c +++ b/src/cairo-surface-fallback.c @@ -634,6 +634,87 @@ _clip_and_composite_region (const cairo_pattern_t *src, return status; } +/* avoid using region code to re-validate boxes */ +static cairo_status_t +_fill_rectangles (cairo_surface_t *dst, + cairo_operator_t op, + const cairo_pattern_t *src, + cairo_traps_t *traps, + cairo_clip_t *clip) +{ + const cairo_color_t *color; + cairo_rectangle_int_t stack_rects[CAIRO_STACK_ARRAY_LENGTH (cairo_rectangle_int_t)]; + cairo_rectangle_int_t *rects = stack_rects; + cairo_status_t status; + int i; + + if (! traps->is_rectilinear || ! traps->maybe_region) + return CAIRO_INT_STATUS_UNSUPPORTED; + + /* XXX: convert clip region to geometric boxes? */ + if (clip != NULL) + return CAIRO_INT_STATUS_UNSUPPORTED; + + /* XXX: fallback for the region_subtract() operation */ + if (! _cairo_operator_bounded_by_mask (op)) + return CAIRO_INT_STATUS_UNSUPPORTED; + + if (! (src->type == CAIRO_PATTERN_TYPE_SOLID || op == CAIRO_OPERATOR_CLEAR)) + return CAIRO_INT_STATUS_UNSUPPORTED; + + if (traps->has_intersections) { + if (traps->is_rectangular) { + status = _cairo_bentley_ottmann_tessellate_rectangular_traps (traps, CAIRO_FILL_RULE_WINDING); + } else { + status = _cairo_bentley_ottmann_tessellate_rectilinear_traps (traps, CAIRO_FILL_RULE_WINDING); + } + if (unlikely (status)) + return status; + } + + for (i = 0; i < traps->num_traps; i++) { + if (! _cairo_fixed_is_integer (traps->traps[i].top) || + ! _cairo_fixed_is_integer (traps->traps[i].bottom) || + ! _cairo_fixed_is_integer (traps->traps[i].left.p1.x) || + ! _cairo_fixed_is_integer (traps->traps[i].right.p1.x)) + { + traps->maybe_region = FALSE; + return CAIRO_INT_STATUS_UNSUPPORTED; + } + } + + if (traps->num_traps > ARRAY_LENGTH (stack_rects)) { + rects = _cairo_malloc_ab (traps->num_traps, + sizeof (cairo_rectangle_int_t)); + if (unlikely (rects == NULL)) + return _cairo_error (CAIRO_STATUS_NO_MEMORY); + } + + for (i = 0; i < traps->num_traps; i++) { + int x1 = _cairo_fixed_integer_part (traps->traps[i].left.p1.x); + int y1 = _cairo_fixed_integer_part (traps->traps[i].top); + int x2 = _cairo_fixed_integer_part (traps->traps[i].right.p1.x); + int y2 = _cairo_fixed_integer_part (traps->traps[i].bottom); + + rects[i].x = x1; + rects[i].y = y1; + rects[i].width = x2 - x1; + rects[i].height = y2 - y1; + } + + if (op == CAIRO_OPERATOR_CLEAR) + color = CAIRO_COLOR_TRANSPARENT; + else + color = &((cairo_solid_pattern_t *)src)->color; + + status = _cairo_surface_fill_rectangles (dst, op, color, rects, i); + + if (rects != stack_rects) + free (rects); + + return status; +} + /* Warning: This call modifies the coordinates of traps */ static cairo_status_t _clip_and_composite_trapezoids (const cairo_pattern_t *src, @@ -671,6 +752,10 @@ _clip_and_composite_trapezoids (const cairo_pattern_t *src, { cairo_region_t *trap_region = NULL; + status = _fill_rectangles (dst, op, src, traps, clip); + if (status != CAIRO_INT_STATUS_UNSUPPORTED) + return status; + status = _cairo_traps_extract_region (traps, &trap_region); if (unlikely (_cairo_status_is_error (status))) return status; @@ -713,12 +798,12 @@ _clip_and_composite_trapezoids (const cairo_pattern_t *src, /* No fast path, exclude self-intersections and clip trapezoids. */ if (traps->has_intersections) { - if (traps->is_rectilinear) - status = _cairo_bentley_ottmann_tessellate_rectilinear_traps (traps, - CAIRO_FILL_RULE_WINDING); + if (traps->is_rectangular) + status = _cairo_bentley_ottmann_tessellate_rectangular_traps (traps, CAIRO_FILL_RULE_WINDING); + else if (traps->is_rectilinear) + status = _cairo_bentley_ottmann_tessellate_rectilinear_traps (traps, CAIRO_FILL_RULE_WINDING); else - status = _cairo_bentley_ottmann_tessellate_traps (traps, - CAIRO_FILL_RULE_WINDING); + status = _cairo_bentley_ottmann_tessellate_traps (traps, CAIRO_FILL_RULE_WINDING); if (unlikely (status)) return status; } diff --git a/src/cairo-traps.c b/src/cairo-traps.c index d5b41e5d..d6fec260 100644 --- a/src/cairo-traps.c +++ b/src/cairo-traps.c @@ -53,6 +53,7 @@ _cairo_traps_init (cairo_traps_t *traps) traps->maybe_region = 1; traps->is_rectilinear = 0; + traps->is_rectangular = 0; traps->num_traps = 0; @@ -79,6 +80,7 @@ _cairo_traps_clear (cairo_traps_t *traps) traps->maybe_region = 1; traps->is_rectilinear = 0; + traps->is_rectangular = 0; traps->num_traps = 0; traps->has_intersections = FALSE; @@ -170,6 +172,7 @@ _cairo_traps_init_boxes (cairo_traps_t *traps, traps->num_traps = num_boxes; traps->is_rectilinear = TRUE; + traps->is_rectangular = TRUE; trap = &traps->traps[0]; while (num_boxes--) { @@ -206,6 +209,12 @@ _cairo_traps_tessellate_rectangle (cairo_traps_t *traps, cairo_line_t right; cairo_fixed_t top, bottom; + if (top_left->y == bottom_right->y) + return CAIRO_STATUS_SUCCESS; + + if (top_left->x == bottom_right->x) + return CAIRO_STATUS_SUCCESS; + left.p1.x = left.p2.x = top_left->x; left.p1.y = right.p1.y = top_left->y; right.p1.x = right.p2.x = bottom_right->x; @@ -214,15 +223,17 @@ _cairo_traps_tessellate_rectangle (cairo_traps_t *traps, top = top_left->y; bottom = bottom_right->y; - if (top == bottom) - return CAIRO_STATUS_SUCCESS; - - if (left.p1.x == right.p1.x) - return CAIRO_STATUS_SUCCESS; - if (traps->num_limits) { + cairo_bool_t reversed; int n; + /* support counter-clockwise winding for rectangular tessellation */ + reversed = top_left->x > bottom_right->x; + if (reversed) { + right.p1.x = right.p2.x = top_left->x; + left.p1.x = left.p2.x = bottom_right->x; + } + for (n = 0; n < traps->num_limits; n++) { const cairo_box_t *limits = &traps->limits[n]; cairo_line_t _left, _right; @@ -275,7 +286,10 @@ _cairo_traps_tessellate_rectangle (cairo_traps_t *traps, if (left.p1.x >= right.p1.x) continue; - _cairo_traps_add_trap (traps, _top, _bottom, &_left, &_right); + if (reversed) + _cairo_traps_add_trap (traps, _top, _bottom, &_right, &_left); + else + _cairo_traps_add_trap (traps, _top, _bottom, &_left, &_right); } } else { _cairo_traps_add_trap (traps, top, bottom, &left, &right); diff --git a/src/cairoint.h b/src/cairoint.h index 4db99d6a..a3cc6c75 100644 --- a/src/cairoint.h +++ b/src/cairoint.h @@ -963,6 +963,7 @@ typedef struct _cairo_traps { unsigned int maybe_region : 1; /* hint: 0 implies that it cannot be */ unsigned int has_intersections : 1; unsigned int is_rectilinear : 1; + unsigned int is_rectangular : 1; int num_traps; int traps_size; @@ -2407,6 +2408,10 @@ _cairo_bentley_ottmann_tessellate_traps (cairo_traps_t *traps, cairo_fill_rule_t fill_rule); cairo_private cairo_status_t +_cairo_bentley_ottmann_tessellate_rectangular_traps (cairo_traps_t *traps, + cairo_fill_rule_t fill_rule); + +cairo_private cairo_status_t _cairo_bentley_ottmann_tessellate_rectilinear_traps (cairo_traps_t *traps, cairo_fill_rule_t fill_rule); |