diff options
Diffstat (limited to 'libs/cairo-1.16.0/src/cairo-polygon.c')
-rw-r--r-- | libs/cairo-1.16.0/src/cairo-polygon.c | 608 |
1 files changed, 608 insertions, 0 deletions
diff --git a/libs/cairo-1.16.0/src/cairo-polygon.c b/libs/cairo-1.16.0/src/cairo-polygon.c new file mode 100644 index 0000000..0e0b813 --- /dev/null +++ b/libs/cairo-1.16.0/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_UNDEFINED (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; + } +} |