summaryrefslogtreecommitdiff
path: root/libs/cairo-1.16.0/src/cairo-boxes-intersect.c
diff options
context:
space:
mode:
Diffstat (limited to 'libs/cairo-1.16.0/src/cairo-boxes-intersect.c')
-rw-r--r--libs/cairo-1.16.0/src/cairo-boxes-intersect.c690
1 files changed, 690 insertions, 0 deletions
diff --git a/libs/cairo-1.16.0/src/cairo-boxes-intersect.c b/libs/cairo-1.16.0/src/cairo-boxes-intersect.c
new file mode 100644
index 0000000..96ae663
--- /dev/null
+++ b/libs/cairo-1.16.0/src/cairo-boxes-intersect.c
@@ -0,0 +1,690 @@
+/*
+ * Copyright © 2004 Carl Worth
+ * Copyright © 2006 Red Hat, Inc.
+ * Copyright © 2009 Chris Wilson
+ * Copyright © 2011 Intel Corporation
+ *
+ * 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 <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 a_or_b;
+ 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 _pqueue {
+ int size, max_size;
+
+ rectangle_t **elements;
+ rectangle_t *elements_embedded[1024];
+} pqueue_t;
+
+typedef struct _sweep_line {
+ rectangle_t **rectangles;
+ pqueue_t pq;
+ edge_t head, tail;
+ edge_t *insert_left, *insert_right;
+ int32_t current_y;
+ int32_t last_y;
+
+ 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_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_bool_t
+pqueue_grow (pqueue_t *pq)
+{
+ rectangle_t **new_elements;
+ pq->max_size *= 2;
+
+ if (pq->elements == pq->elements_embedded) {
+ new_elements = _cairo_malloc_ab (pq->max_size,
+ sizeof (rectangle_t *));
+ if (unlikely (new_elements == NULL))
+ return FALSE;
+
+ memcpy (new_elements, pq->elements_embedded,
+ sizeof (pq->elements_embedded));
+ } else {
+ new_elements = _cairo_realloc_ab (pq->elements,
+ pq->max_size,
+ sizeof (rectangle_t *));
+ if (unlikely (new_elements == NULL))
+ return FALSE;
+ }
+
+ pq->elements = new_elements;
+ return TRUE;
+}
+
+static inline void
+pqueue_push (sweep_line_t *sweep, rectangle_t *rectangle)
+{
+ rectangle_t **elements;
+ int i, parent;
+
+ if (unlikely (sweep->pq.size + 1 == sweep->pq.max_size)) {
+ if (unlikely (! pqueue_grow (&sweep->pq))) {
+ longjmp (sweep->unwind,
+ _cairo_error (CAIRO_STATUS_NO_MEMORY));
+ }
+ }
+
+ elements = sweep->pq.elements;
+ for (i = ++sweep->pq.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
+pqueue_pop (pqueue_t *pq)
+{
+ rectangle_t **elements = pq->elements;
+ 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 &&
+ 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->pq.elements[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)
+{
+ _rectangle_sort (rectangles, num_rectangles);
+ rectangles[num_rectangles] = NULL;
+ sweep_line->rectangles = rectangles;
+
+ sweep_line->head.x = INT32_MIN;
+ sweep_line->head.right = NULL;
+ sweep_line->head.dir = 0;
+ sweep_line->head.next = &sweep_line->tail;
+ sweep_line->tail.x = INT32_MAX;
+ sweep_line->tail.right = NULL;
+ sweep_line->tail.dir = 0;
+ sweep_line->tail.prev = &sweep_line->head;
+
+ sweep_line->insert_left = &sweep_line->tail;
+ sweep_line->insert_right = &sweep_line->tail;
+
+ sweep_line->current_y = INT32_MIN;
+ sweep_line->last_y = INT32_MIN;
+
+ pqueue_init (&sweep_line->pq);
+}
+
+static void
+sweep_line_fini (sweep_line_t *sweep_line)
+{
+ pqueue_fini (&sweep_line->pq);
+}
+
+static void
+end_box (sweep_line_t *sweep_line, edge_t *left, int32_t bot, cairo_boxes_t *out)
+{
+ if (likely (left->top < bot)) {
+ cairo_status_t status;
+ 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 (out, 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
+start_or_continue_box (sweep_line_t *sweep_line,
+ edge_t *left,
+ edge_t *right,
+ int top,
+ cairo_boxes_t *out)
+{
+ if (left->right == right)
+ return;
+
+ if (left->right != NULL) {
+ if (right != NULL && left->right->x == right->x) {
+ /* continuation on right, so just swap edges */
+ left->right = right;
+ return;
+ }
+
+ end_box (sweep_line, left, top, out);
+ }
+
+ if (right != NULL && left->x != right->x) {
+ left->top = top;
+ left->right = right;
+ }
+}
+
+static inline int is_zero(const int *winding)
+{
+ return winding[0] == 0 || winding[1] == 0;
+}
+
+static inline void
+active_edges (sweep_line_t *sweep, cairo_boxes_t *out)
+{
+ int top = sweep->current_y;
+ int winding[2] = { 0 };
+ edge_t *pos;
+
+ if (sweep->last_y == sweep->current_y)
+ return;
+
+ pos = sweep->head.next;
+ if (pos == &sweep->tail)
+ return;
+
+ do {
+ edge_t *left, *right;
+
+ left = pos;
+ do {
+ winding[left->a_or_b] += left->dir;
+ if (!is_zero (winding))
+ break;
+ if (left->next == &sweep->tail)
+ goto out;
+
+ if (unlikely (left->right != NULL))
+ end_box (sweep, left, top, out);
+
+ left = left->next;
+ } while (1);
+
+ right = left->next;
+ do {
+ if (unlikely (right->right != NULL))
+ end_box (sweep, right, top, out);
+
+ winding[right->a_or_b] += right->dir;
+ if (is_zero (winding)) {
+ /* skip co-linear edges */
+ if (likely (right->x != right->next->x))
+ break;
+ }
+
+ right = right->next;
+ } while (TRUE);
+
+ start_or_continue_box (sweep, left, right, top, out);
+
+ pos = right->next;
+ } while (pos != &sweep->tail);
+
+out:
+ sweep->last_y = sweep->current_y;
+}
+
+static inline void
+sweep_line_delete_edge (sweep_line_t *sweep_line, edge_t *edge, cairo_boxes_t *out)
+{
+ if (edge->right != NULL) {
+ edge_t *next = edge->next;
+ if (next->x == edge->x) {
+ next->top = edge->top;
+ next->right = edge->right;
+ } else {
+ end_box (sweep_line, edge, sweep_line->current_y, out);
+ }
+ }
+
+ if (sweep_line->insert_left == edge)
+ sweep_line->insert_left = edge->next;
+ if (sweep_line->insert_right == edge)
+ sweep_line->insert_right = edge->next;
+
+ edge->prev->next = edge->next;
+ edge->next->prev = edge->prev;
+}
+
+static inline void
+sweep_line_delete (sweep_line_t *sweep,
+ rectangle_t *rectangle,
+ cairo_boxes_t *out)
+{
+ sweep_line_delete_edge (sweep, &rectangle->left, out);
+ sweep_line_delete_edge (sweep, &rectangle->right, out);
+
+ pqueue_pop (&sweep->pq);
+}
+
+static inline void
+insert_edge (edge_t *edge, edge_t *pos)
+{
+ if (pos->x != edge->x) {
+ if (pos->x > edge->x) {
+ do {
+ UNROLL3({
+ if (pos->prev->x <= edge->x)
+ break;
+ pos = pos->prev;
+ })
+ } while (TRUE);
+ } else {
+ do {
+ UNROLL3({
+ pos = pos->next;
+ if (pos->x >= edge->x)
+ break;
+ })
+ } while (TRUE);
+ }
+ }
+
+ pos->prev->next = edge;
+ edge->prev = pos->prev;
+ edge->next = pos;
+ pos->prev = edge;
+}
+
+static inline void
+sweep_line_insert (sweep_line_t *sweep, rectangle_t *rectangle)
+{
+ edge_t *pos;
+
+ /* right edge */
+ pos = sweep->insert_right;
+ insert_edge (&rectangle->right, pos);
+ sweep->insert_right = &rectangle->right;
+
+ /* left edge */
+ pos = sweep->insert_left;
+ if (pos->x > sweep->insert_right->x)
+ pos = sweep->insert_right->prev;
+ insert_edge (&rectangle->left, pos);
+ sweep->insert_left = &rectangle->left;
+
+ pqueue_push (sweep, rectangle);
+}
+
+static cairo_status_t
+intersect (rectangle_t **rectangles, int num_rectangles, cairo_boxes_t *out)
+{
+ sweep_line_t sweep_line;
+ rectangle_t *rectangle;
+ cairo_status_t status;
+
+ sweep_line_init (&sweep_line, rectangles, num_rectangles);
+ if ((status = setjmp (sweep_line.unwind)))
+ goto unwind;
+
+ 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) {
+ active_edges (&sweep_line, out);
+ sweep_line.current_y = stop->bottom;
+ }
+
+ sweep_line_delete (&sweep_line, stop, out);
+
+ stop = rectangle_peek_stop (&sweep_line);
+ }
+
+ active_edges (&sweep_line, out);
+ sweep_line.current_y = rectangle->top;
+ }
+
+ sweep_line_insert (&sweep_line, rectangle);
+ } while ((rectangle = rectangle_pop_start (&sweep_line)) != NULL);
+
+ while ((rectangle = rectangle_peek_stop (&sweep_line)) != NULL) {
+ if (rectangle->bottom != sweep_line.current_y) {
+ active_edges (&sweep_line, out);
+ sweep_line.current_y = rectangle->bottom;
+ }
+
+ sweep_line_delete (&sweep_line, rectangle, out);
+ }
+
+unwind:
+ sweep_line_fini (&sweep_line);
+ return status;
+}
+
+static cairo_status_t
+_cairo_boxes_intersect_with_box (const cairo_boxes_t *boxes,
+ const cairo_box_t *box,
+ cairo_boxes_t *out)
+{
+ cairo_status_t status;
+ int i, j;
+
+ if (out == boxes) { /* inplace update */
+ struct _cairo_boxes_chunk *chunk;
+
+ out->num_boxes = 0;
+ for (chunk = &out->chunks; chunk != NULL; chunk = chunk->next) {
+ for (i = j = 0; i < chunk->count; i++) {
+ cairo_box_t *b = &chunk->base[i];
+
+ b->p1.x = MAX (b->p1.x, box->p1.x);
+ b->p1.y = MAX (b->p1.y, box->p1.y);
+ b->p2.x = MIN (b->p2.x, box->p2.x);
+ b->p2.y = MIN (b->p2.y, box->p2.y);
+ if (b->p1.x < b->p2.x && b->p1.y < b->p2.y) {
+ if (i != j)
+ chunk->base[j] = *b;
+ j++;
+ }
+ }
+ /* XXX unlink empty chains? */
+ chunk->count = j;
+ out->num_boxes += j;
+ }
+ } else {
+ const struct _cairo_boxes_chunk *chunk;
+
+ _cairo_boxes_clear (out);
+ _cairo_boxes_limit (out, box, 1);
+ for (chunk = &boxes->chunks; chunk != NULL; chunk = chunk->next) {
+ for (i = 0; i < chunk->count; i++) {
+ status = _cairo_boxes_add (out,
+ CAIRO_ANTIALIAS_DEFAULT,
+ &chunk->base[i]);
+ if (unlikely (status))
+ return status;
+ }
+ }
+ }
+
+ return CAIRO_STATUS_SUCCESS;
+}
+
+cairo_status_t
+_cairo_boxes_intersect (const cairo_boxes_t *a,
+ const cairo_boxes_t *b,
+ cairo_boxes_t *out)
+{
+ rectangle_t stack_rectangles[CAIRO_STACK_ARRAY_LENGTH (rectangle_t)];
+ rectangle_t *rectangles;
+ rectangle_t *stack_rectangles_ptrs[ARRAY_LENGTH (stack_rectangles) + 1];
+ rectangle_t **rectangles_ptrs;
+ const struct _cairo_boxes_chunk *chunk;
+ cairo_status_t status;
+ int i, j, count;
+
+ if (unlikely (a->num_boxes == 0 || b->num_boxes == 0)) {
+ _cairo_boxes_clear (out);
+ return CAIRO_STATUS_SUCCESS;
+ }
+
+ if (a->num_boxes == 1) {
+ cairo_box_t box = a->chunks.base[0];
+ return _cairo_boxes_intersect_with_box (b, &box, out);
+ }
+ if (b->num_boxes == 1) {
+ cairo_box_t box = b->chunks.base[0];
+ return _cairo_boxes_intersect_with_box (a, &box, out);
+ }
+
+ rectangles = stack_rectangles;
+ rectangles_ptrs = stack_rectangles_ptrs;
+ count = a->num_boxes + b->num_boxes;
+ if (count > ARRAY_LENGTH (stack_rectangles)) {
+ rectangles = _cairo_malloc_ab_plus_c (count,
+ sizeof (rectangle_t) +
+ sizeof (rectangle_t *),
+ sizeof (rectangle_t *));
+ if (unlikely (rectangles == NULL))
+ return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+
+ rectangles_ptrs = (rectangle_t **) (rectangles + count);
+ }
+
+ j = 0;
+ for (chunk = &a->chunks; chunk != NULL; chunk = chunk->next) {
+ const cairo_box_t *box = chunk->base;
+ for (i = 0; i < chunk->count; i++) {
+ 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.a_or_b = 0;
+ rectangles[j].left.right = NULL;
+ rectangles[j].right.a_or_b = 0;
+ rectangles[j].right.right = NULL;
+
+ rectangles[j].top = box[i].p1.y;
+ rectangles[j].bottom = box[i].p2.y;
+
+ rectangles_ptrs[j] = &rectangles[j];
+ j++;
+ }
+ }
+ for (chunk = &b->chunks; chunk != NULL; chunk = chunk->next) {
+ const cairo_box_t *box = chunk->base;
+ for (i = 0; i < chunk->count; i++) {
+ 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.a_or_b = 1;
+ rectangles[j].left.right = NULL;
+ rectangles[j].right.a_or_b = 1;
+ rectangles[j].right.right = NULL;
+
+ rectangles[j].top = box[i].p1.y;
+ rectangles[j].bottom = box[i].p2.y;
+
+ rectangles_ptrs[j] = &rectangles[j];
+ j++;
+ }
+ }
+ assert (j == count);
+
+ _cairo_boxes_clear (out);
+ status = intersect (rectangles_ptrs, j, out);
+ if (rectangles != stack_rectangles)
+ free (rectangles);
+
+ return status;
+}