summaryrefslogtreecommitdiff
path: root/Build/source/libs/cairo/cairo-src/src/cairo-polygon.c
diff options
context:
space:
mode:
Diffstat (limited to 'Build/source/libs/cairo/cairo-src/src/cairo-polygon.c')
-rw-r--r--Build/source/libs/cairo/cairo-src/src/cairo-polygon.c608
1 files changed, 608 insertions, 0 deletions
diff --git a/Build/source/libs/cairo/cairo-src/src/cairo-polygon.c b/Build/source/libs/cairo/cairo-src/src/cairo-polygon.c
new file mode 100644
index 00000000000..b0424f6e72e
--- /dev/null
+++ b/Build/source/libs/cairo/cairo-src/src/cairo-polygon.c
@@ -0,0 +1,608 @@
+/* -*- Mode: c; c-basic-offset: 4; indent-tabs-mode: t; tab-width: 8; -*- */
+/* cairo - a vector graphics library with display and print output
+ *
+ * Copyright © 2002 University of Southern California
+ *
+ * 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 University of Southern
+ * California.
+ *
+ * Contributor(s):
+ * Carl D. Worth <cworth@cworth.org>
+ */
+
+#include "cairoint.h"
+
+#include "cairo-boxes-private.h"
+#include "cairo-contour-private.h"
+#include "cairo-error-private.h"
+
+#define DEBUG_POLYGON 0
+
+#if DEBUG_POLYGON && !NDEBUG
+static void
+assert_last_edge_is_valid(cairo_polygon_t *polygon,
+ const cairo_box_t *limit)
+{
+ cairo_edge_t *edge;
+ cairo_fixed_t x;
+
+ edge = &polygon->edges[polygon->num_edges-1];
+
+ assert (edge->bottom > edge->top);
+ assert (edge->top >= limit->p1.y);
+ assert (edge->bottom <= limit->p2.y);
+
+ x = _cairo_edge_compute_intersection_x_for_y (&edge->line.p1,
+ &edge->line.p2,
+ edge->top);
+ assert (x >= limit->p1.x);
+ assert (x <= limit->p2.x);
+
+ x = _cairo_edge_compute_intersection_x_for_y (&edge->line.p1,
+ &edge->line.p2,
+ edge->bottom);
+ assert (x >= limit->p1.x);
+ assert (x <= limit->p2.x);
+}
+#else
+#define assert_last_edge_is_valid(p, l)
+#endif
+
+static void
+_cairo_polygon_add_edge (cairo_polygon_t *polygon,
+ const cairo_point_t *p1,
+ const cairo_point_t *p2,
+ int dir);
+
+void
+_cairo_polygon_limit (cairo_polygon_t *polygon,
+ const cairo_box_t *limits,
+ int num_limits)
+{
+ int n;
+
+ polygon->limits = limits;
+ polygon->num_limits = num_limits;
+
+ if (polygon->num_limits) {
+ polygon->limit = limits[0];
+ for (n = 1; n < num_limits; n++) {
+ if (limits[n].p1.x < polygon->limit.p1.x)
+ polygon->limit.p1.x = limits[n].p1.x;
+
+ if (limits[n].p1.y < polygon->limit.p1.y)
+ polygon->limit.p1.y = limits[n].p1.y;
+
+ if (limits[n].p2.x > polygon->limit.p2.x)
+ polygon->limit.p2.x = limits[n].p2.x;
+
+ if (limits[n].p2.y > polygon->limit.p2.y)
+ polygon->limit.p2.y = limits[n].p2.y;
+ }
+ }
+}
+
+void
+_cairo_polygon_limit_to_clip (cairo_polygon_t *polygon,
+ const cairo_clip_t *clip)
+{
+ if (clip)
+ _cairo_polygon_limit (polygon, clip->boxes, clip->num_boxes);
+ else
+ _cairo_polygon_limit (polygon, 0, 0);
+}
+
+void
+_cairo_polygon_init (cairo_polygon_t *polygon,
+ const cairo_box_t *limits,
+ int num_limits)
+{
+ VG (VALGRIND_MAKE_MEM_UNDEFINED (polygon, sizeof (cairo_polygon_t)));
+
+ polygon->status = CAIRO_STATUS_SUCCESS;
+
+ polygon->num_edges = 0;
+
+ polygon->edges = polygon->edges_embedded;
+ polygon->edges_size = ARRAY_LENGTH (polygon->edges_embedded);
+
+ polygon->extents.p1.x = polygon->extents.p1.y = INT32_MAX;
+ polygon->extents.p2.x = polygon->extents.p2.y = INT32_MIN;
+
+ _cairo_polygon_limit (polygon, limits, num_limits);
+}
+
+void
+_cairo_polygon_init_with_clip (cairo_polygon_t *polygon,
+ const cairo_clip_t *clip)
+{
+ if (clip)
+ _cairo_polygon_init (polygon, clip->boxes, clip->num_boxes);
+ else
+ _cairo_polygon_init (polygon, 0, 0);
+}
+
+cairo_status_t
+_cairo_polygon_init_boxes (cairo_polygon_t *polygon,
+ const cairo_boxes_t *boxes)
+{
+ const struct _cairo_boxes_chunk *chunk;
+ int i;
+
+ VG (VALGRIND_MAKE_MEM_UNDEFINED (polygon, sizeof (cairo_polygon_t)));
+
+ polygon->status = CAIRO_STATUS_SUCCESS;
+
+ polygon->num_edges = 0;
+
+ polygon->edges = polygon->edges_embedded;
+ polygon->edges_size = ARRAY_LENGTH (polygon->edges_embedded);
+ if (boxes->num_boxes > ARRAY_LENGTH (polygon->edges_embedded)/2) {
+ polygon->edges_size = 2 * boxes->num_boxes;
+ polygon->edges = _cairo_malloc_ab (polygon->edges_size,
+ 2*sizeof(cairo_edge_t));
+ if (unlikely (polygon->edges == NULL))
+ return polygon->status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
+ }
+
+ polygon->extents.p1.x = polygon->extents.p1.y = INT32_MAX;
+ polygon->extents.p2.x = polygon->extents.p2.y = INT32_MIN;
+
+ polygon->limits = NULL;
+ polygon->num_limits = 0;
+
+ for (chunk = &boxes->chunks; chunk != NULL; chunk = chunk->next) {
+ for (i = 0; i < chunk->count; i++) {
+ cairo_point_t p1, p2;
+
+ p1 = chunk->base[i].p1;
+ p2.x = p1.x;
+ p2.y = chunk->base[i].p2.y;
+ _cairo_polygon_add_edge (polygon, &p1, &p2, 1);
+
+ p1 = chunk->base[i].p2;
+ p2.x = p1.x;
+ p2.y = chunk->base[i].p1.y;
+ _cairo_polygon_add_edge (polygon, &p1, &p2, 1);
+ }
+ }
+
+ return polygon->status;
+}
+
+cairo_status_t
+_cairo_polygon_init_box_array (cairo_polygon_t *polygon,
+ cairo_box_t *boxes,
+ int num_boxes)
+{
+ int i;
+
+ VG (VALGRIND_MAKE_MEM_UNDEFINED (polygon, sizeof (cairo_polygon_t)));
+
+ polygon->status = CAIRO_STATUS_SUCCESS;
+
+ polygon->num_edges = 0;
+
+ polygon->edges = polygon->edges_embedded;
+ polygon->edges_size = ARRAY_LENGTH (polygon->edges_embedded);
+ if (num_boxes > ARRAY_LENGTH (polygon->edges_embedded)/2) {
+ polygon->edges_size = 2 * num_boxes;
+ polygon->edges = _cairo_malloc_ab (polygon->edges_size,
+ 2*sizeof(cairo_edge_t));
+ if (unlikely (polygon->edges == NULL))
+ return polygon->status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
+ }
+
+ polygon->extents.p1.x = polygon->extents.p1.y = INT32_MAX;
+ polygon->extents.p2.x = polygon->extents.p2.y = INT32_MIN;
+
+ polygon->limits = NULL;
+ polygon->num_limits = 0;
+
+ for (i = 0; i < num_boxes; i++) {
+ cairo_point_t p1, p2;
+
+ p1 = boxes[i].p1;
+ p2.x = p1.x;
+ p2.y = boxes[i].p2.y;
+ _cairo_polygon_add_edge (polygon, &p1, &p2, 1);
+
+ p1 = boxes[i].p2;
+ p2.x = p1.x;
+ p2.y = boxes[i].p1.y;
+ _cairo_polygon_add_edge (polygon, &p1, &p2, 1);
+ }
+
+ return polygon->status;
+}
+
+
+void
+_cairo_polygon_fini (cairo_polygon_t *polygon)
+{
+ if (polygon->edges != polygon->edges_embedded)
+ free (polygon->edges);
+
+ VG (VALGRIND_MAKE_MEM_NOACCESS (polygon, sizeof (cairo_polygon_t)));
+}
+
+/* make room for at least one more edge */
+static cairo_bool_t
+_cairo_polygon_grow (cairo_polygon_t *polygon)
+{
+ cairo_edge_t *new_edges;
+ int old_size = polygon->edges_size;
+ int new_size = 4 * old_size;
+
+ if (CAIRO_INJECT_FAULT ()) {
+ polygon->status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
+ return FALSE;
+ }
+
+ if (polygon->edges == polygon->edges_embedded) {
+ new_edges = _cairo_malloc_ab (new_size, sizeof (cairo_edge_t));
+ if (new_edges != NULL)
+ memcpy (new_edges, polygon->edges, old_size * sizeof (cairo_edge_t));
+ } else {
+ new_edges = _cairo_realloc_ab (polygon->edges,
+ new_size, sizeof (cairo_edge_t));
+ }
+
+ if (unlikely (new_edges == NULL)) {
+ polygon->status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
+ return FALSE;
+ }
+
+ polygon->edges = new_edges;
+ polygon->edges_size = new_size;
+
+ return TRUE;
+}
+
+static void
+_add_edge (cairo_polygon_t *polygon,
+ const cairo_point_t *p1,
+ const cairo_point_t *p2,
+ int top, int bottom,
+ int dir)
+{
+ cairo_edge_t *edge;
+
+ assert (top < bottom);
+
+ if (unlikely (polygon->num_edges == polygon->edges_size)) {
+ if (! _cairo_polygon_grow (polygon))
+ return;
+ }
+
+ edge = &polygon->edges[polygon->num_edges++];
+ edge->line.p1 = *p1;
+ edge->line.p2 = *p2;
+ edge->top = top;
+ edge->bottom = bottom;
+ edge->dir = dir;
+
+ if (top < polygon->extents.p1.y)
+ polygon->extents.p1.y = top;
+ if (bottom > polygon->extents.p2.y)
+ polygon->extents.p2.y = bottom;
+
+ if (p1->x < polygon->extents.p1.x || p1->x > polygon->extents.p2.x) {
+ cairo_fixed_t x = p1->x;
+ if (top != p1->y)
+ x = _cairo_edge_compute_intersection_x_for_y (p1, p2, top);
+ if (x < polygon->extents.p1.x)
+ polygon->extents.p1.x = x;
+ if (x > polygon->extents.p2.x)
+ polygon->extents.p2.x = x;
+ }
+
+ if (p2->x < polygon->extents.p1.x || p2->x > polygon->extents.p2.x) {
+ cairo_fixed_t x = p2->x;
+ if (bottom != p2->y)
+ x = _cairo_edge_compute_intersection_x_for_y (p1, p2, bottom);
+ if (x < polygon->extents.p1.x)
+ polygon->extents.p1.x = x;
+ if (x > polygon->extents.p2.x)
+ polygon->extents.p2.x = x;
+ }
+}
+
+static void
+_add_clipped_edge (cairo_polygon_t *polygon,
+ const cairo_point_t *p1,
+ const cairo_point_t *p2,
+ const int top, const int bottom,
+ const int dir)
+{
+ cairo_point_t bot_left, top_right;
+ cairo_fixed_t top_y, bot_y;
+ int n;
+
+ for (n = 0; n < polygon->num_limits; n++) {
+ const cairo_box_t *limits = &polygon->limits[n];
+ cairo_fixed_t pleft, pright;
+
+ if (top >= limits->p2.y)
+ continue;
+ if (bottom <= limits->p1.y)
+ continue;
+
+ bot_left.x = limits->p1.x;
+ bot_left.y = limits->p2.y;
+
+ top_right.x = limits->p2.x;
+ top_right.y = limits->p1.y;
+
+ /* The useful region */
+ top_y = MAX (top, limits->p1.y);
+ bot_y = MIN (bottom, limits->p2.y);
+
+ /* The projection of the edge on the horizontal axis */
+ pleft = MIN (p1->x, p2->x);
+ pright = MAX (p1->x, p2->x);
+
+ if (limits->p1.x <= pleft && pright <= limits->p2.x) {
+ /* Projection of the edge completely contained in the box:
+ * clip vertically by restricting top and bottom */
+
+ _add_edge (polygon, p1, p2, top_y, bot_y, dir);
+ assert_last_edge_is_valid (polygon, limits);
+ } else if (pright <= limits->p1.x) {
+ /* Projection of the edge to the left of the box:
+ * replace with the left side of the box (clipped top/bottom) */
+
+ _add_edge (polygon, &limits->p1, &bot_left, top_y, bot_y, dir);
+ assert_last_edge_is_valid (polygon, limits);
+ } else if (limits->p2.x <= pleft) {
+ /* Projection of the edge to the right of the box:
+ * replace with the right side of the box (clipped top/bottom) */
+
+ _add_edge (polygon, &top_right, &limits->p2, top_y, bot_y, dir);
+ assert_last_edge_is_valid (polygon, limits);
+ } else {
+ /* The edge and the box intersect in a generic way */
+ cairo_fixed_t left_y, right_y;
+ cairo_bool_t top_left_to_bottom_right;
+
+ /*
+ * The edge intersects the lines corresponding to the left
+ * and right sides of the limit box at left_y and right_y,
+ * but we need to add edges for the range from top_y to
+ * bot_y.
+ *
+ * For both intersections, there are three cases:
+ *
+ * 1) It is outside the vertical range of the limit
+ * box. In this case we can simply further clip the
+ * edge we will be emitting (i.e. restrict its
+ * top/bottom limits to those of the limit box).
+ *
+ * 2) It is inside the vertical range of the limit
+ * box. In this case, we need to add the vertical edge
+ * connecting the correct vertex to the intersection,
+ * in order to preserve the winding count.
+ *
+ * 3) It is exactly on the box. In this case, do nothing.
+ *
+ * These operations restrict the active range (stored in
+ * top_y/bot_y) so that the p1-p2 edge is completely
+ * inside the box if it is clipped to this vertical range.
+ */
+
+ top_left_to_bottom_right = (p1->x <= p2->x) == (p1->y <= p2->y);
+ if (top_left_to_bottom_right) {
+ if (pleft >= limits->p1.x) {
+ left_y = top_y;
+ } else {
+ left_y = _cairo_edge_compute_intersection_y_for_x (p1, p2,
+ limits->p1.x);
+ if (_cairo_edge_compute_intersection_x_for_y (p1, p2, left_y) < limits->p1.x)
+ left_y++;
+ }
+
+ left_y = MIN (left_y, bot_y);
+ if (top_y < left_y) {
+ _add_edge (polygon, &limits->p1, &bot_left,
+ top_y, left_y, dir);
+ assert_last_edge_is_valid (polygon, limits);
+ top_y = left_y;
+ }
+
+ if (pright <= limits->p2.x) {
+ right_y = bot_y;
+ } else {
+ right_y = _cairo_edge_compute_intersection_y_for_x (p1, p2,
+ limits->p2.x);
+ if (_cairo_edge_compute_intersection_x_for_y (p1, p2, right_y) > limits->p2.x)
+ right_y--;
+ }
+
+ right_y = MAX (right_y, top_y);
+ if (bot_y > right_y) {
+ _add_edge (polygon, &top_right, &limits->p2,
+ right_y, bot_y, dir);
+ assert_last_edge_is_valid (polygon, limits);
+ bot_y = right_y;
+ }
+ } else {
+ if (pright <= limits->p2.x) {
+ right_y = top_y;
+ } else {
+ right_y = _cairo_edge_compute_intersection_y_for_x (p1, p2,
+ limits->p2.x);
+ if (_cairo_edge_compute_intersection_x_for_y (p1, p2, right_y) > limits->p2.x)
+ right_y++;
+ }
+
+ right_y = MIN (right_y, bot_y);
+ if (top_y < right_y) {
+ _add_edge (polygon, &top_right, &limits->p2,
+ top_y, right_y, dir);
+ assert_last_edge_is_valid (polygon, limits);
+ top_y = right_y;
+ }
+
+ if (pleft >= limits->p1.x) {
+ left_y = bot_y;
+ } else {
+ left_y = _cairo_edge_compute_intersection_y_for_x (p1, p2,
+ limits->p1.x);
+ if (_cairo_edge_compute_intersection_x_for_y (p1, p2, left_y) < limits->p1.x)
+ left_y--;
+ }
+
+ left_y = MAX (left_y, top_y);
+ if (bot_y > left_y) {
+ _add_edge (polygon, &limits->p1, &bot_left,
+ left_y, bot_y, dir);
+ assert_last_edge_is_valid (polygon, limits);
+ bot_y = left_y;
+ }
+ }
+
+ if (top_y != bot_y) {
+ _add_edge (polygon, p1, p2, top_y, bot_y, dir);
+ assert_last_edge_is_valid (polygon, limits);
+ }
+ }
+ }
+}
+
+static void
+_cairo_polygon_add_edge (cairo_polygon_t *polygon,
+ const cairo_point_t *p1,
+ const cairo_point_t *p2,
+ int dir)
+{
+ /* drop horizontal edges */
+ if (p1->y == p2->y)
+ return;
+
+ if (p1->y > p2->y) {
+ const cairo_point_t *t;
+ t = p1, p1 = p2, p2 = t;
+ dir = -dir;
+ }
+
+ if (polygon->num_limits) {
+ if (p2->y <= polygon->limit.p1.y)
+ return;
+
+ if (p1->y >= polygon->limit.p2.y)
+ return;
+
+ _add_clipped_edge (polygon, p1, p2, p1->y, p2->y, dir);
+ } else
+ _add_edge (polygon, p1, p2, p1->y, p2->y, dir);
+}
+
+cairo_status_t
+_cairo_polygon_add_external_edge (void *polygon,
+ const cairo_point_t *p1,
+ const cairo_point_t *p2)
+{
+ _cairo_polygon_add_edge (polygon, p1, p2, 1);
+ return _cairo_polygon_status (polygon);
+}
+
+cairo_status_t
+_cairo_polygon_add_line (cairo_polygon_t *polygon,
+ const cairo_line_t *line,
+ int top, int bottom,
+ int dir)
+{
+ /* drop horizontal edges */
+ if (line->p1.y == line->p2.y)
+ return CAIRO_STATUS_SUCCESS;
+
+ if (bottom <= top)
+ return CAIRO_STATUS_SUCCESS;
+
+ if (polygon->num_limits) {
+ if (line->p2.y <= polygon->limit.p1.y)
+ return CAIRO_STATUS_SUCCESS;
+
+ if (line->p1.y >= polygon->limit.p2.y)
+ return CAIRO_STATUS_SUCCESS;
+
+ _add_clipped_edge (polygon, &line->p1, &line->p2, top, bottom, dir);
+ } else
+ _add_edge (polygon, &line->p1, &line->p2, top, bottom, dir);
+
+ return polygon->status;
+}
+
+cairo_status_t
+_cairo_polygon_add_contour (cairo_polygon_t *polygon,
+ const cairo_contour_t *contour)
+{
+ const struct _cairo_contour_chain *chain;
+ const cairo_point_t *prev = NULL;
+ int i;
+
+ if (contour->chain.num_points <= 1)
+ return CAIRO_INT_STATUS_SUCCESS;
+
+ prev = &contour->chain.points[0];
+ for (chain = &contour->chain; chain; chain = chain->next) {
+ for (i = 0; i < chain->num_points; i++) {
+ _cairo_polygon_add_edge (polygon, prev, &chain->points[i],
+ contour->direction);
+ prev = &chain->points[i];
+ }
+ }
+
+ return polygon->status;
+}
+
+void
+_cairo_polygon_translate (cairo_polygon_t *polygon, int dx, int dy)
+{
+ int n;
+
+ dx = _cairo_fixed_from_int (dx);
+ dy = _cairo_fixed_from_int (dy);
+
+ polygon->extents.p1.x += dx;
+ polygon->extents.p2.x += dx;
+ polygon->extents.p1.y += dy;
+ polygon->extents.p2.y += dy;
+
+ for (n = 0; n < polygon->num_edges; n++) {
+ cairo_edge_t *e = &polygon->edges[n];
+
+ e->top += dy;
+ e->bottom += dy;
+
+ e->line.p1.x += dx;
+ e->line.p2.x += dx;
+ e->line.p1.y += dy;
+ e->line.p2.y += dy;
+ }
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-20 15:27:50 +0000