summaryrefslogtreecommitdiff
path: root/libs/cairo-1.16.0/src/cairo-bentley-ottmann-rectilinear.c
diff options
context:
space:
mode:
Diffstat (limited to 'libs/cairo-1.16.0/src/cairo-bentley-ottmann-rectilinear.c')
-rw-r--r--libs/cairo-1.16.0/src/cairo-bentley-ottmann-rectilinear.c600
1 files changed, 600 insertions, 0 deletions
diff --git a/libs/cairo-1.16.0/src/cairo-bentley-ottmann-rectilinear.c b/libs/cairo-1.16.0/src/cairo-bentley-ottmann-rectilinear.c
new file mode 100644
index 0000000..7c0be69
--- /dev/null
+++ b/libs/cairo-1.16.0/src/cairo-bentley-ottmann-rectilinear.c
@@ -0,0 +1,600 @@
+/*
+ * Copyright © 2004 Carl Worth
+ * Copyright © 2006 Red Hat, Inc.
+ * Copyright © 2008 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-combsort-inline.h"
+#include "cairo-error-private.h"
+#include "cairo-traps-private.h"
+
+typedef struct _cairo_bo_edge cairo_bo_edge_t;
+typedef struct _cairo_bo_trap cairo_bo_trap_t;
+
+/* A deferred trapezoid of an edge */
+struct _cairo_bo_trap {
+ cairo_bo_edge_t *right;
+ int32_t top;
+};
+
+struct _cairo_bo_edge {
+ cairo_edge_t edge;
+ cairo_bo_edge_t *prev;
+ cairo_bo_edge_t *next;
+ cairo_bo_trap_t deferred_trap;
+};
+
+typedef enum {
+ CAIRO_BO_EVENT_TYPE_START,
+ CAIRO_BO_EVENT_TYPE_STOP
+} cairo_bo_event_type_t;
+
+typedef struct _cairo_bo_event {
+ cairo_bo_event_type_t type;
+ cairo_point_t point;
+ cairo_bo_edge_t *edge;
+} cairo_bo_event_t;
+
+typedef struct _cairo_bo_sweep_line {
+ cairo_bo_event_t **events;
+ cairo_bo_edge_t *head;
+ cairo_bo_edge_t *stopped;
+ int32_t current_y;
+ cairo_bo_edge_t *current_edge;
+} cairo_bo_sweep_line_t;
+
+static inline int
+_cairo_point_compare (const cairo_point_t *a,
+ const cairo_point_t *b)
+{
+ int cmp;
+
+ cmp = a->y - b->y;
+ if (likely (cmp))
+ return cmp;
+
+ return a->x - b->x;
+}
+
+static inline int
+_cairo_bo_edge_compare (const cairo_bo_edge_t *a,
+ const cairo_bo_edge_t *b)
+{
+ int cmp;
+
+ cmp = a->edge.line.p1.x - b->edge.line.p1.x;
+ if (likely (cmp))
+ return cmp;
+
+ return b->edge.bottom - a->edge.bottom;
+}
+
+static inline int
+cairo_bo_event_compare (const cairo_bo_event_t *a,
+ const cairo_bo_event_t *b)
+{
+ int cmp;
+
+ cmp = _cairo_point_compare (&a->point, &b->point);
+ if (likely (cmp))
+ return cmp;
+
+ cmp = a->type - b->type;
+ if (cmp)
+ return cmp;
+
+ return a - b;
+}
+
+static inline cairo_bo_event_t *
+_cairo_bo_event_dequeue (cairo_bo_sweep_line_t *sweep_line)
+{
+ return *sweep_line->events++;
+}
+
+CAIRO_COMBSORT_DECLARE (_cairo_bo_event_queue_sort,
+ cairo_bo_event_t *,
+ cairo_bo_event_compare)
+
+static void
+_cairo_bo_sweep_line_init (cairo_bo_sweep_line_t *sweep_line,
+ cairo_bo_event_t **events,
+ int num_events)
+{
+ _cairo_bo_event_queue_sort (events, num_events);
+ events[num_events] = NULL;
+ sweep_line->events = events;
+
+ sweep_line->head = NULL;
+ sweep_line->current_y = INT32_MIN;
+ sweep_line->current_edge = NULL;
+}
+
+static void
+_cairo_bo_sweep_line_insert (cairo_bo_sweep_line_t *sweep_line,
+ cairo_bo_edge_t *edge)
+{
+ if (sweep_line->current_edge != NULL) {
+ cairo_bo_edge_t *prev, *next;
+ int cmp;
+
+ cmp = _cairo_bo_edge_compare (sweep_line->current_edge, edge);
+ if (cmp < 0) {
+ prev = sweep_line->current_edge;
+ next = prev->next;
+ while (next != NULL && _cairo_bo_edge_compare (next, edge) < 0)
+ prev = next, next = prev->next;
+
+ prev->next = edge;
+ edge->prev = prev;
+ edge->next = next;
+ if (next != NULL)
+ next->prev = edge;
+ } else if (cmp > 0) {
+ next = sweep_line->current_edge;
+ prev = next->prev;
+ while (prev != NULL && _cairo_bo_edge_compare (prev, edge) > 0)
+ next = prev, prev = next->prev;
+
+ next->prev = edge;
+ edge->next = next;
+ edge->prev = prev;
+ if (prev != NULL)
+ prev->next = edge;
+ else
+ sweep_line->head = edge;
+ } else {
+ prev = sweep_line->current_edge;
+ edge->prev = prev;
+ edge->next = prev->next;
+ if (prev->next != NULL)
+ prev->next->prev = edge;
+ prev->next = edge;
+ }
+ } else {
+ sweep_line->head = edge;
+ }
+
+ sweep_line->current_edge = edge;
+}
+
+static void
+_cairo_bo_sweep_line_delete (cairo_bo_sweep_line_t *sweep_line,
+ cairo_bo_edge_t *edge)
+{
+ if (edge->prev != NULL)
+ edge->prev->next = edge->next;
+ else
+ sweep_line->head = edge->next;
+
+ if (edge->next != NULL)
+ edge->next->prev = edge->prev;
+
+ if (sweep_line->current_edge == edge)
+ sweep_line->current_edge = edge->prev ? edge->prev : edge->next;
+}
+
+static inline cairo_bool_t
+edges_collinear (const cairo_bo_edge_t *a, const cairo_bo_edge_t *b)
+{
+ return a->edge.line.p1.x == b->edge.line.p1.x;
+}
+
+static cairo_status_t
+_cairo_bo_edge_end_trap (cairo_bo_edge_t *left,
+ int32_t bot,
+ cairo_bool_t do_traps,
+ void *container)
+{
+ cairo_bo_trap_t *trap = &left->deferred_trap;
+ cairo_status_t status = CAIRO_STATUS_SUCCESS;
+
+ /* Only emit (trivial) non-degenerate trapezoids with positive height. */
+ if (likely (trap->top < bot)) {
+ if (do_traps) {
+ _cairo_traps_add_trap (container,
+ trap->top, bot,
+ &left->edge.line, &trap->right->edge.line);
+ status = _cairo_traps_status ((cairo_traps_t *) container);
+ } else {
+ cairo_box_t box;
+
+ box.p1.x = left->edge.line.p1.x;
+ box.p1.y = trap->top;
+ box.p2.x = trap->right->edge.line.p1.x;
+ box.p2.y = bot;
+ status = _cairo_boxes_add (container, CAIRO_ANTIALIAS_DEFAULT, &box);
+ }
+ }
+
+ trap->right = NULL;
+
+ return status;
+}
+
+/* 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_bool_t do_traps,
+ void *container)
+{
+ cairo_status_t status;
+
+ if (left->deferred_trap.right == right)
+ return CAIRO_STATUS_SUCCESS;
+
+ if (left->deferred_trap.right != NULL) {
+ if (right != NULL && edges_collinear (left->deferred_trap.right, right))
+ {
+ /* continuation on right, so just swap edges */
+ left->deferred_trap.right = right;
+ return CAIRO_STATUS_SUCCESS;
+ }
+
+ status = _cairo_bo_edge_end_trap (left, top, do_traps, container);
+ if (unlikely (status))
+ return status;
+ }
+
+ if (right != NULL && ! edges_collinear (left, right)) {
+ 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_edge_t *left,
+ int32_t top,
+ cairo_fill_rule_t fill_rule,
+ cairo_bool_t do_traps,
+ void *container)
+{
+ cairo_bo_edge_t *right;
+ cairo_status_t status;
+
+ if (fill_rule == CAIRO_FILL_RULE_WINDING) {
+ while (left != NULL) {
+ int in_out;
+
+ /* Greedily search for the closing edge, so that we generate the
+ * maximal span width with the minimal number of trapezoids.
+ */
+ in_out = left->edge.dir;
+
+ /* Check if there is a co-linear edge with an existing trap */
+ right = left->next;
+ if (left->deferred_trap.right == NULL) {
+ while (right != NULL && right->deferred_trap.right == NULL)
+ right = right->next;
+
+ if (right != NULL && edges_collinear (left, right)) {
+ /* continuation on left */
+ left->deferred_trap = right->deferred_trap;
+ right->deferred_trap.right = NULL;
+ }
+ }
+
+ /* End all subsumed traps */
+ right = left->next;
+ while (right != NULL) {
+ if (right->deferred_trap.right != NULL) {
+ status = _cairo_bo_edge_end_trap (right, top, do_traps, container);
+ if (unlikely (status))
+ return status;
+ }
+
+ in_out += right->edge.dir;
+ if (in_out == 0) {
+ /* skip co-linear edges */
+ if (right->next == NULL ||
+ ! edges_collinear (right, right->next))
+ {
+ break;
+ }
+ }
+
+ right = right->next;
+ }
+
+ status = _cairo_bo_edge_start_or_continue_trap (left, right, top,
+ do_traps, container);
+ if (unlikely (status))
+ return status;
+
+ left = right;
+ if (left != NULL)
+ left = left->next;
+ }
+ } else {
+ while (left != NULL) {
+ int in_out = 0;
+
+ right = left->next;
+ while (right != NULL) {
+ if (right->deferred_trap.right != NULL) {
+ status = _cairo_bo_edge_end_trap (right, top, do_traps, container);
+ if (unlikely (status))
+ return status;
+ }
+
+ if ((in_out++ & 1) == 0) {
+ cairo_bo_edge_t *next;
+ cairo_bool_t skip = FALSE;
+
+ /* skip co-linear edges */
+ next = right->next;
+ if (next != NULL)
+ skip = edges_collinear (right, next);
+
+ if (! skip)
+ break;
+ }
+
+ right = right->next;
+ }
+
+ status = _cairo_bo_edge_start_or_continue_trap (left, right, top,
+ do_traps, container);
+ if (unlikely (status))
+ return status;
+
+ left = right;
+ if (left != NULL)
+ left = left->next;
+ }
+ }
+
+ return CAIRO_STATUS_SUCCESS;
+}
+
+static cairo_status_t
+_cairo_bentley_ottmann_tessellate_rectilinear (cairo_bo_event_t **start_events,
+ int num_events,
+ cairo_fill_rule_t fill_rule,
+ cairo_bool_t do_traps,
+ void *container)
+{
+ cairo_bo_sweep_line_t sweep_line;
+ cairo_bo_event_t *event;
+ cairo_status_t status;
+
+ _cairo_bo_sweep_line_init (&sweep_line, start_events, num_events);
+
+ while ((event = _cairo_bo_event_dequeue (&sweep_line))) {
+ if (event->point.y != sweep_line.current_y) {
+ status = _active_edges_to_traps (sweep_line.head,
+ sweep_line.current_y,
+ fill_rule, do_traps, container);
+ if (unlikely (status))
+ return status;
+
+ sweep_line.current_y = event->point.y;
+ }
+
+ switch (event->type) {
+ case CAIRO_BO_EVENT_TYPE_START:
+ _cairo_bo_sweep_line_insert (&sweep_line, event->edge);
+ break;
+
+ case CAIRO_BO_EVENT_TYPE_STOP:
+ _cairo_bo_sweep_line_delete (&sweep_line, event->edge);
+
+ if (event->edge->deferred_trap.right != NULL) {
+ status = _cairo_bo_edge_end_trap (event->edge,
+ sweep_line.current_y,
+ do_traps, container);
+ if (unlikely (status))
+ return status;
+ }
+
+ break;
+ }
+ }
+
+ return CAIRO_STATUS_SUCCESS;
+}
+
+cairo_status_t
+_cairo_bentley_ottmann_tessellate_rectilinear_polygon_to_boxes (const cairo_polygon_t *polygon,
+ cairo_fill_rule_t fill_rule,
+ cairo_boxes_t *boxes)
+{
+ cairo_status_t status;
+ cairo_bo_event_t stack_events[CAIRO_STACK_ARRAY_LENGTH (cairo_bo_event_t)];
+ cairo_bo_event_t *events;
+ cairo_bo_event_t *stack_event_ptrs[ARRAY_LENGTH (stack_events) + 1];
+ cairo_bo_event_t **event_ptrs;
+ cairo_bo_edge_t stack_edges[ARRAY_LENGTH (stack_events)];
+ cairo_bo_edge_t *edges;
+ int num_events;
+ int i, j;
+
+ if (unlikely (polygon->num_edges == 0))
+ return CAIRO_STATUS_SUCCESS;
+
+ num_events = 2 * polygon->num_edges;
+
+ events = stack_events;
+ event_ptrs = stack_event_ptrs;
+ edges = stack_edges;
+ if (num_events > ARRAY_LENGTH (stack_events)) {
+ events = _cairo_malloc_ab_plus_c (num_events,
+ sizeof (cairo_bo_event_t) +
+ sizeof (cairo_bo_edge_t) +
+ sizeof (cairo_bo_event_t *),
+ sizeof (cairo_bo_event_t *));
+ if (unlikely (events == NULL))
+ return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+
+ event_ptrs = (cairo_bo_event_t **) (events + num_events);
+ edges = (cairo_bo_edge_t *) (event_ptrs + num_events + 1);
+ }
+
+ for (i = j = 0; i < polygon->num_edges; i++) {
+ edges[i].edge = polygon->edges[i];
+ edges[i].deferred_trap.right = NULL;
+ edges[i].prev = NULL;
+ edges[i].next = NULL;
+
+ event_ptrs[j] = &events[j];
+ events[j].type = CAIRO_BO_EVENT_TYPE_START;
+ events[j].point.y = polygon->edges[i].top;
+ events[j].point.x = polygon->edges[i].line.p1.x;
+ events[j].edge = &edges[i];
+ j++;
+
+ event_ptrs[j] = &events[j];
+ events[j].type = CAIRO_BO_EVENT_TYPE_STOP;
+ events[j].point.y = polygon->edges[i].bottom;
+ events[j].point.x = polygon->edges[i].line.p1.x;
+ events[j].edge = &edges[i];
+ j++;
+ }
+
+ status = _cairo_bentley_ottmann_tessellate_rectilinear (event_ptrs, j,
+ fill_rule,
+ FALSE, boxes);
+ if (events != stack_events)
+ free (events);
+
+ return status;
+}
+
+cairo_status_t
+_cairo_bentley_ottmann_tessellate_rectilinear_traps (cairo_traps_t *traps,
+ cairo_fill_rule_t fill_rule)
+{
+ cairo_bo_event_t stack_events[CAIRO_STACK_ARRAY_LENGTH (cairo_bo_event_t)];
+ cairo_bo_event_t *events;
+ cairo_bo_event_t *stack_event_ptrs[ARRAY_LENGTH (stack_events) + 1];
+ cairo_bo_event_t **event_ptrs;
+ cairo_bo_edge_t stack_edges[ARRAY_LENGTH (stack_events)];
+ cairo_bo_edge_t *edges;
+ cairo_status_t status;
+ int i, j, k;
+
+ if (unlikely (traps->num_traps == 0))
+ return CAIRO_STATUS_SUCCESS;
+
+ assert (traps->is_rectilinear);
+
+ i = 4 * traps->num_traps;
+
+ events = stack_events;
+ event_ptrs = stack_event_ptrs;
+ edges = stack_edges;
+ if (i > ARRAY_LENGTH (stack_events)) {
+ events = _cairo_malloc_ab_plus_c (i,
+ sizeof (cairo_bo_event_t) +
+ sizeof (cairo_bo_edge_t) +
+ sizeof (cairo_bo_event_t *),
+ sizeof (cairo_bo_event_t *));
+ if (unlikely (events == NULL))
+ return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+
+ event_ptrs = (cairo_bo_event_t **) (events + i);
+ edges = (cairo_bo_edge_t *) (event_ptrs + i + 1);
+ }
+
+ for (i = j = k = 0; i < traps->num_traps; i++) {
+ edges[k].edge.top = traps->traps[i].top;
+ edges[k].edge.bottom = traps->traps[i].bottom;
+ edges[k].edge.line = traps->traps[i].left;
+ edges[k].edge.dir = 1;
+ edges[k].deferred_trap.right = NULL;
+ edges[k].prev = NULL;
+ edges[k].next = NULL;
+
+ event_ptrs[j] = &events[j];
+ events[j].type = CAIRO_BO_EVENT_TYPE_START;
+ events[j].point.y = traps->traps[i].top;
+ events[j].point.x = traps->traps[i].left.p1.x;
+ events[j].edge = &edges[k];
+ j++;
+
+ event_ptrs[j] = &events[j];
+ events[j].type = CAIRO_BO_EVENT_TYPE_STOP;
+ events[j].point.y = traps->traps[i].bottom;
+ events[j].point.x = traps->traps[i].left.p1.x;
+ events[j].edge = &edges[k];
+ j++;
+ k++;
+
+ edges[k].edge.top = traps->traps[i].top;
+ edges[k].edge.bottom = traps->traps[i].bottom;
+ edges[k].edge.line = traps->traps[i].right;
+ edges[k].edge.dir = -1;
+ edges[k].deferred_trap.right = NULL;
+ edges[k].prev = NULL;
+ edges[k].next = NULL;
+
+ event_ptrs[j] = &events[j];
+ events[j].type = CAIRO_BO_EVENT_TYPE_START;
+ events[j].point.y = traps->traps[i].top;
+ events[j].point.x = traps->traps[i].right.p1.x;
+ events[j].edge = &edges[k];
+ j++;
+
+ event_ptrs[j] = &events[j];
+ events[j].type = CAIRO_BO_EVENT_TYPE_STOP;
+ events[j].point.y = traps->traps[i].bottom;
+ events[j].point.x = traps->traps[i].right.p1.x;
+ events[j].edge = &edges[k];
+ j++;
+ k++;
+ }
+
+ _cairo_traps_clear (traps);
+ status = _cairo_bentley_ottmann_tessellate_rectilinear (event_ptrs, j,
+ fill_rule,
+ TRUE, traps);
+ traps->is_rectilinear = TRUE;
+
+ if (events != stack_events)
+ free (events);
+
+ return status;
+}
generated by cgit v1.2.1 (git 2.18.0) at 2024-11-01 17:25:07 +0000