summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--src/Makefile.sources1
-rw-r--r--src/cairo-bentley-ottmann-rectangular.c733
-rw-r--r--src/cairo-clip.c26
-rw-r--r--src/cairo-path-fill.c40
-rw-r--r--src/cairo-path-stroke.c3
-rw-r--r--src/cairo-surface-fallback.c95
-rw-r--r--src/cairo-traps.c28
-rw-r--r--src/cairoint.h5
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);