diff options
Diffstat (limited to 'libs/cairo-1.16.0/src/cairo-traps.c')
| -rw-r--r-- | libs/cairo-1.16.0/src/cairo-traps.c | 1123 |
1 files changed, 1123 insertions, 0 deletions
diff --git a/libs/cairo-1.16.0/src/cairo-traps.c b/libs/cairo-1.16.0/src/cairo-traps.c new file mode 100644 index 0000000..1b74848 --- /dev/null +++ b/libs/cairo-1.16.0/src/cairo-traps.c @@ -0,0 +1,1123 @@ +/* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */ +/* + * Copyright © 2002 Keith Packard + * Copyright © 2007 Red Hat, Inc. + * + * 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 Keith Packard + * + * Contributor(s): + * Keith R. Packard <keithp@keithp.com> + * Carl D. Worth <cworth@cworth.org> + * + * 2002-07-15: Converted from XRenderCompositeDoublePoly to #cairo_trap_t. Carl D. Worth + */ + +#include "cairoint.h" + +#include "cairo-box-inline.h" +#include "cairo-boxes-private.h" +#include "cairo-error-private.h" +#include "cairo-line-private.h" +#include "cairo-region-private.h" +#include "cairo-slope-private.h" +#include "cairo-traps-private.h" +#include "cairo-spans-private.h" + +/* private functions */ + +void +_cairo_traps_init (cairo_traps_t *traps) +{ + VG (VALGRIND_MAKE_MEM_UNDEFINED (traps, sizeof (cairo_traps_t))); + + traps->status = CAIRO_STATUS_SUCCESS; + + traps->maybe_region = 1; + traps->is_rectilinear = 0; + traps->is_rectangular = 0; + + traps->num_traps = 0; + + traps->traps_size = ARRAY_LENGTH (traps->traps_embedded); + traps->traps = traps->traps_embedded; + + traps->num_limits = 0; + traps->has_intersections = FALSE; +} + +void +_cairo_traps_limit (cairo_traps_t *traps, + const cairo_box_t *limits, + int num_limits) +{ + int i; + + traps->limits = limits; + traps->num_limits = num_limits; + + traps->bounds = limits[0]; + for (i = 1; i < num_limits; i++) + _cairo_box_add_box (&traps->bounds, &limits[i]); +} + +void +_cairo_traps_init_with_clip (cairo_traps_t *traps, + const cairo_clip_t *clip) +{ + _cairo_traps_init (traps); + if (clip) + _cairo_traps_limit (traps, clip->boxes, clip->num_boxes); +} + +void +_cairo_traps_clear (cairo_traps_t *traps) +{ + traps->status = CAIRO_STATUS_SUCCESS; + + traps->maybe_region = 1; + traps->is_rectilinear = 0; + traps->is_rectangular = 0; + + traps->num_traps = 0; + traps->has_intersections = FALSE; +} + +void +_cairo_traps_fini (cairo_traps_t *traps) +{ + if (traps->traps != traps->traps_embedded) + free (traps->traps); + + VG (VALGRIND_MAKE_MEM_UNDEFINED (traps, sizeof (cairo_traps_t))); +} + +/* make room for at least one more trap */ +static cairo_bool_t +_cairo_traps_grow (cairo_traps_t *traps) +{ + cairo_trapezoid_t *new_traps; + int new_size = 4 * traps->traps_size; + + if (CAIRO_INJECT_FAULT ()) { + traps->status = _cairo_error (CAIRO_STATUS_NO_MEMORY); + return FALSE; + } + + if (traps->traps == traps->traps_embedded) { + new_traps = _cairo_malloc_ab (new_size, sizeof (cairo_trapezoid_t)); + if (new_traps != NULL) + memcpy (new_traps, traps->traps, sizeof (traps->traps_embedded)); + } else { + new_traps = _cairo_realloc_ab (traps->traps, + new_size, sizeof (cairo_trapezoid_t)); + } + + if (unlikely (new_traps == NULL)) { + traps->status = _cairo_error (CAIRO_STATUS_NO_MEMORY); + return FALSE; + } + + traps->traps = new_traps; + traps->traps_size = new_size; + return TRUE; +} + +void +_cairo_traps_add_trap (cairo_traps_t *traps, + cairo_fixed_t top, cairo_fixed_t bottom, + const cairo_line_t *left, + const cairo_line_t *right) +{ + cairo_trapezoid_t *trap; + + assert (left->p1.y != left->p2.y); + assert (right->p1.y != right->p2.y); + assert (bottom > top); + + if (unlikely (traps->num_traps == traps->traps_size)) { + if (unlikely (! _cairo_traps_grow (traps))) + return; + } + + trap = &traps->traps[traps->num_traps++]; + trap->top = top; + trap->bottom = bottom; + trap->left = *left; + trap->right = *right; +} + +static void +_cairo_traps_add_clipped_trap (cairo_traps_t *traps, + cairo_fixed_t _top, cairo_fixed_t _bottom, + const cairo_line_t *_left, + const cairo_line_t *_right) +{ + /* Note: With the goofy trapezoid specification, (where an + * arbitrary two points on the lines can specified for the left + * and right edges), these limit checks would not work in + * general. For example, one can imagine a trapezoid entirely + * within the limits, but with two points used to specify the left + * edge entirely to the right of the limits. Fortunately, for our + * purposes, cairo will never generate such a crazy + * trapezoid. Instead, cairo always uses for its points the + * extreme positions of the edge that are visible on at least some + * trapezoid. With this constraint, it's impossible for both + * points to be outside the limits while the relevant edge is + * entirely inside the limits. + */ + if (traps->num_limits) { + const cairo_box_t *b = &traps->bounds; + cairo_fixed_t top = _top, bottom = _bottom; + cairo_line_t left = *_left, right = *_right; + + /* Trivially reject if trapezoid is entirely to the right or + * to the left of the limits. */ + if (left.p1.x >= b->p2.x && left.p2.x >= b->p2.x) + return; + + if (right.p1.x <= b->p1.x && right.p2.x <= b->p1.x) + return; + + /* And reject if the trapezoid is entirely above or below */ + if (top >= b->p2.y || bottom <= b->p1.y) + return; + + /* Otherwise, clip the trapezoid to the limits. We only clip + * where an edge is entirely outside the limits. If we wanted + * to be more clever, we could handle cases where a trapezoid + * edge intersects the edge of the limits, but that would + * require slicing this trapezoid into multiple trapezoids, + * and I'm not sure the effort would be worth it. */ + if (top < b->p1.y) + top = b->p1.y; + + if (bottom > b->p2.y) + bottom = b->p2.y; + + if (left.p1.x <= b->p1.x && left.p2.x <= b->p1.x) + left.p1.x = left.p2.x = b->p1.x; + + if (right.p1.x >= b->p2.x && right.p2.x >= b->p2.x) + right.p1.x = right.p2.x = b->p2.x; + + /* Trivial discards for empty trapezoids that are likely to + * be produced by our tessellators (most notably convex_quad + * when given a simple rectangle). + */ + if (top >= bottom) + return; + + /* cheap colinearity check */ + if (right.p1.x <= left.p1.x && right.p1.y == left.p1.y && + right.p2.x <= left.p2.x && right.p2.y == left.p2.y) + return; + + _cairo_traps_add_trap (traps, top, bottom, &left, &right); + } else + _cairo_traps_add_trap (traps, _top, _bottom, _left, _right); +} + +static int +_compare_point_fixed_by_y (const void *av, const void *bv) +{ + const cairo_point_t *a = av, *b = bv; + int ret = a->y - b->y; + if (ret == 0) + ret = a->x - b->x; + return ret; +} + +void +_cairo_traps_tessellate_convex_quad (cairo_traps_t *traps, + const cairo_point_t q[4]) +{ + int a, b, c, d; + int i; + cairo_slope_t ab, ad; + cairo_bool_t b_left_of_d; + cairo_line_t left; + cairo_line_t right; + + /* Choose a as a point with minimal y */ + a = 0; + for (i = 1; i < 4; i++) + if (_compare_point_fixed_by_y (&q[i], &q[a]) < 0) + a = i; + + /* b and d are adjacent to a, while c is opposite */ + b = (a + 1) % 4; + c = (a + 2) % 4; + d = (a + 3) % 4; + + /* Choose between b and d so that b.y is less than d.y */ + if (_compare_point_fixed_by_y (&q[d], &q[b]) < 0) { + b = (a + 3) % 4; + d = (a + 1) % 4; + } + + /* Without freedom left to choose anything else, we have four + * cases to tessellate. + * + * First, we have to determine the Y-axis sort of the four + * vertices, (either abcd or abdc). After that we need to detemine + * which edges will be "left" and which will be "right" in the + * resulting trapezoids. This can be determined by computing a + * slope comparison of ab and ad to determine if b is left of d or + * not. + * + * Note that "left of" here is in the sense of which edges should + * be the left vs. right edges of the trapezoid. In particular, b + * left of d does *not* mean that b.x is less than d.x. + * + * This should hopefully be made clear in the lame ASCII art + * below. Since the same slope comparison is used in all cases, we + * compute it before testing for the Y-value sort. */ + + /* Note: If a == b then the ab slope doesn't give us any + * information. In that case, we can replace it with the ac (or + * equivalenly the bc) slope which gives us exactly the same + * information we need. At worst the names of the identifiers ab + * and b_left_of_d are inaccurate in this case, (would be ac, and + * c_left_of_d). */ + if (q[a].x == q[b].x && q[a].y == q[b].y) + _cairo_slope_init (&ab, &q[a], &q[c]); + else + _cairo_slope_init (&ab, &q[a], &q[b]); + + _cairo_slope_init (&ad, &q[a], &q[d]); + + b_left_of_d = _cairo_slope_compare (&ab, &ad) > 0; + + if (q[c].y <= q[d].y) { + if (b_left_of_d) { + /* Y-sort is abcd and b is left of d, (slope(ab) > slope (ad)) + * + * top bot left right + * _a a a + * / / /| |\ a.y b.y ab ad + * b / b | b \ + * / / | | \ \ b.y c.y bc ad + * c / c | c \ + * | / \| \ \ c.y d.y cd ad + * d d d + */ + left.p1 = q[a]; left.p2 = q[b]; + right.p1 = q[a]; right.p2 = q[d]; + _cairo_traps_add_clipped_trap (traps, q[a].y, q[b].y, &left, &right); + left.p1 = q[b]; left.p2 = q[c]; + _cairo_traps_add_clipped_trap (traps, q[b].y, q[c].y, &left, &right); + left.p1 = q[c]; left.p2 = q[d]; + _cairo_traps_add_clipped_trap (traps, q[c].y, q[d].y, &left, &right); + } else { + /* Y-sort is abcd and b is right of d, (slope(ab) <= slope (ad)) + * + * a a a_ + * /| |\ \ \ a.y b.y ad ab + * / b | b \ b + * / / | | \ \ b.y c.y ad bc + * / c | c \ c + * / / |/ \ | c.y d.y ad cd + * d d d + */ + left.p1 = q[a]; left.p2 = q[d]; + right.p1 = q[a]; right.p2 = q[b]; + _cairo_traps_add_clipped_trap (traps, q[a].y, q[b].y, &left, &right); + right.p1 = q[b]; right.p2 = q[c]; + _cairo_traps_add_clipped_trap (traps, q[b].y, q[c].y, &left, &right); + right.p1 = q[c]; right.p2 = q[d]; + _cairo_traps_add_clipped_trap (traps, q[c].y, q[d].y, &left, &right); + } + } else { + if (b_left_of_d) { + /* Y-sort is abdc and b is left of d, (slope (ab) > slope (ad)) + * + * a a a + * // / \ |\ a.y b.y ab ad + * /b/ b \ b \ + * / / \ \ \ \ b.y d.y bc ad + * /d/ \ d \ d + * // \ / \| d.y c.y bc dc + * c c c + */ + left.p1 = q[a]; left.p2 = q[b]; + right.p1 = q[a]; right.p2 = q[d]; + _cairo_traps_add_clipped_trap (traps, q[a].y, q[b].y, &left, &right); + left.p1 = q[b]; left.p2 = q[c]; + _cairo_traps_add_clipped_trap (traps, q[b].y, q[d].y, &left, &right); + right.p1 = q[d]; right.p2 = q[c]; + _cairo_traps_add_clipped_trap (traps, q[d].y, q[c].y, &left, &right); + } else { + /* Y-sort is abdc and b is right of d, (slope (ab) <= slope (ad)) + * + * a a a + * /| / \ \\ a.y b.y ad ab + * / b / b \b\ + * / / / / \ \ b.y d.y ad bc + * d / d / \d\ + * |/ \ / \\ d.y c.y dc bc + * c c c + */ + left.p1 = q[a]; left.p2 = q[d]; + right.p1 = q[a]; right.p2 = q[b]; + _cairo_traps_add_clipped_trap (traps, q[a].y, q[b].y, &left, &right); + right.p1 = q[b]; right.p2 = q[c]; + _cairo_traps_add_clipped_trap (traps, q[b].y, q[d].y, &left, &right); + left.p1 = q[d]; left.p2 = q[c]; + _cairo_traps_add_clipped_trap (traps, q[d].y, q[c].y, &left, &right); + } + } +} + +static void add_tri (cairo_traps_t *traps, + int y1, int y2, + const cairo_line_t *left, + const cairo_line_t *right) +{ + if (y2 < y1) { + int tmp = y1; + y1 = y2; + y2 = tmp; + } + + if (cairo_lines_compare_at_y (left, right, y1) > 0) { + const cairo_line_t *tmp = left; + left = right; + right = tmp; + } + + _cairo_traps_add_clipped_trap (traps, y1, y2, left, right); +} + +void +_cairo_traps_tessellate_triangle_with_edges (cairo_traps_t *traps, + const cairo_point_t t[3], + const cairo_point_t edges[4]) +{ + cairo_line_t lines[3]; + + if (edges[0].y <= edges[1].y) { + lines[0].p1 = edges[0]; + lines[0].p2 = edges[1]; + } else { + lines[0].p1 = edges[1]; + lines[0].p2 = edges[0]; + } + + if (edges[2].y <= edges[3].y) { + lines[1].p1 = edges[2]; + lines[1].p2 = edges[3]; + } else { + lines[1].p1 = edges[3]; + lines[1].p2 = edges[2]; + } + + if (t[1].y == t[2].y) { + add_tri (traps, t[0].y, t[1].y, &lines[0], &lines[1]); + return; + } + + if (t[1].y <= t[2].y) { + lines[2].p1 = t[1]; + lines[2].p2 = t[2]; + } else { + lines[2].p1 = t[2]; + lines[2].p2 = t[1]; + } + + if (((t[1].y - t[0].y) < 0) ^ ((t[2].y - t[0].y) < 0)) { + add_tri (traps, t[0].y, t[1].y, &lines[0], &lines[2]); + add_tri (traps, t[0].y, t[2].y, &lines[1], &lines[2]); + } else if (abs(t[1].y - t[0].y) < abs(t[2].y - t[0].y)) { + add_tri (traps, t[0].y, t[1].y, &lines[0], &lines[1]); + add_tri (traps, t[1].y, t[2].y, &lines[2], &lines[1]); + } else { + add_tri (traps, t[0].y, t[2].y, &lines[1], &lines[0]); + add_tri (traps, t[1].y, t[2].y, &lines[2], &lines[0]); + } +} + +/** + * _cairo_traps_init_boxes: + * @traps: a #cairo_traps_t + * @box: an array box that will each be converted to a single trapezoid + * to store in @traps. + * + * Initializes a #cairo_traps_t to contain an array of rectangular + * trapezoids. + **/ +cairo_status_t +_cairo_traps_init_boxes (cairo_traps_t *traps, + const cairo_boxes_t *boxes) +{ + cairo_trapezoid_t *trap; + const struct _cairo_boxes_chunk *chunk; + + _cairo_traps_init (traps); + + while (traps->traps_size < boxes->num_boxes) { + if (unlikely (! _cairo_traps_grow (traps))) { + _cairo_traps_fini (traps); + return _cairo_error (CAIRO_STATUS_NO_MEMORY); + } + } + + traps->num_traps = boxes->num_boxes; + traps->is_rectilinear = TRUE; + traps->is_rectangular = TRUE; + traps->maybe_region = boxes->is_pixel_aligned; + + trap = &traps->traps[0]; + for (chunk = &boxes->chunks; chunk != NULL; chunk = chunk->next) { + const cairo_box_t *box; + int i; + + box = chunk->base; + for (i = 0; i < chunk->count; i++) { + trap->top = box->p1.y; + trap->bottom = box->p2.y; + + trap->left.p1 = box->p1; + trap->left.p2.x = box->p1.x; + trap->left.p2.y = box->p2.y; + + trap->right.p1.x = box->p2.x; + trap->right.p1.y = box->p1.y; + trap->right.p2 = box->p2; + + box++, trap++; + } + } + + return CAIRO_STATUS_SUCCESS; +} + +cairo_status_t +_cairo_traps_tessellate_rectangle (cairo_traps_t *traps, + const cairo_point_t *top_left, + const cairo_point_t *bottom_right) +{ + cairo_line_t left; + 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; + left.p2.y = right.p2.y = bottom_right->y; + + top = top_left->y; + bottom = bottom_right->y; + + if (traps->num_limits) { + cairo_bool_t reversed; + int n; + + if (top >= traps->bounds.p2.y || bottom <= traps->bounds.p1.y) + return CAIRO_STATUS_SUCCESS; + + /* 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; + } + + if (left.p1.x >= traps->bounds.p2.x || right.p1.x <= traps->bounds.p1.x) + return CAIRO_STATUS_SUCCESS; + + for (n = 0; n < traps->num_limits; n++) { + const cairo_box_t *limits = &traps->limits[n]; + cairo_line_t _left, _right; + cairo_fixed_t _top, _bottom; + + if (top >= limits->p2.y) + continue; + if (bottom <= limits->p1.y) + continue; + + /* Trivially reject if trapezoid is entirely to the right or + * to the left of the limits. */ + if (left.p1.x >= limits->p2.x) + continue; + if (right.p1.x <= limits->p1.x) + continue; + + /* Otherwise, clip the trapezoid to the limits. */ + _top = top; + if (_top < limits->p1.y) + _top = limits->p1.y; + + _bottom = bottom; + if (_bottom > limits->p2.y) + _bottom = limits->p2.y; + + if (_bottom <= _top) + continue; + + _left = left; + if (_left.p1.x < limits->p1.x) { + _left.p1.x = limits->p1.x; + _left.p1.y = limits->p1.y; + _left.p2.x = limits->p1.x; + _left.p2.y = limits->p2.y; + } + + _right = right; + if (_right.p1.x > limits->p2.x) { + _right.p1.x = limits->p2.x; + _right.p1.y = limits->p1.y; + _right.p2.x = limits->p2.x; + _right.p2.y = limits->p2.y; + } + + if (left.p1.x >= right.p1.x) + continue; + + 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); + } + + return traps->status; +} + +void +_cairo_traps_translate (cairo_traps_t *traps, int x, int y) +{ + cairo_fixed_t xoff, yoff; + cairo_trapezoid_t *t; + int i; + + /* Ugh. The cairo_composite/(Render) interface doesn't allow + an offset for the trapezoids. Need to manually shift all + the coordinates to align with the offset origin of the + intermediate surface. */ + + xoff = _cairo_fixed_from_int (x); + yoff = _cairo_fixed_from_int (y); + + for (i = 0, t = traps->traps; i < traps->num_traps; i++, t++) { + t->top += yoff; + t->bottom += yoff; + t->left.p1.x += xoff; + t->left.p1.y += yoff; + t->left.p2.x += xoff; + t->left.p2.y += yoff; + t->right.p1.x += xoff; + t->right.p1.y += yoff; + t->right.p2.x += xoff; + t->right.p2.y += yoff; + } +} + +void +_cairo_trapezoid_array_translate_and_scale (cairo_trapezoid_t *offset_traps, + cairo_trapezoid_t *src_traps, + int num_traps, + double tx, double ty, + double sx, double sy) +{ + int i; + cairo_fixed_t xoff = _cairo_fixed_from_double (tx); + cairo_fixed_t yoff = _cairo_fixed_from_double (ty); + + if (sx == 1.0 && sy == 1.0) { + for (i = 0; i < num_traps; i++) { + offset_traps[i].top = src_traps[i].top + yoff; + offset_traps[i].bottom = src_traps[i].bottom + yoff; + offset_traps[i].left.p1.x = src_traps[i].left.p1.x + xoff; + offset_traps[i].left.p1.y = src_traps[i].left.p1.y + yoff; + offset_traps[i].left.p2.x = src_traps[i].left.p2.x + xoff; + offset_traps[i].left.p2.y = src_traps[i].left.p2.y + yoff; + offset_traps[i].right.p1.x = src_traps[i].right.p1.x + xoff; + offset_traps[i].right.p1.y = src_traps[i].right.p1.y + yoff; + offset_traps[i].right.p2.x = src_traps[i].right.p2.x + xoff; + offset_traps[i].right.p2.y = src_traps[i].right.p2.y + yoff; + } + } else { + cairo_fixed_t xsc = _cairo_fixed_from_double (sx); + cairo_fixed_t ysc = _cairo_fixed_from_double (sy); + + for (i = 0; i < num_traps; i++) { + offset_traps[i].top = _cairo_fixed_mul (src_traps[i].top + yoff, ysc); + offset_traps[i].bottom = _cairo_fixed_mul (src_traps[i].bottom + yoff, ysc); + offset_traps[i].left.p1.x = _cairo_fixed_mul (src_traps[i].left.p1.x + xoff, xsc); + offset_traps[i].left.p1.y = _cairo_fixed_mul (src_traps[i].left.p1.y + yoff, ysc); + offset_traps[i].left.p2.x = _cairo_fixed_mul (src_traps[i].left.p2.x + xoff, xsc); + offset_traps[i].left.p2.y = _cairo_fixed_mul (src_traps[i].left.p2.y + yoff, ysc); + offset_traps[i].right.p1.x = _cairo_fixed_mul (src_traps[i].right.p1.x + xoff, xsc); + offset_traps[i].right.p1.y = _cairo_fixed_mul (src_traps[i].right.p1.y + yoff, ysc); + offset_traps[i].right.p2.x = _cairo_fixed_mul (src_traps[i].right.p2.x + xoff, xsc); + offset_traps[i].right.p2.y = _cairo_fixed_mul (src_traps[i].right.p2.y + yoff, ysc); + } + } +} + +static cairo_bool_t +_cairo_trap_contains (cairo_trapezoid_t *t, cairo_point_t *pt) +{ + cairo_slope_t slope_left, slope_pt, slope_right; + + if (t->top > pt->y) + return FALSE; + if (t->bottom < pt->y) + return FALSE; + + _cairo_slope_init (&slope_left, &t->left.p1, &t->left.p2); + _cairo_slope_init (&slope_pt, &t->left.p1, pt); + + if (_cairo_slope_compare (&slope_left, &slope_pt) < 0) + return FALSE; + + _cairo_slope_init (&slope_right, &t->right.p1, &t->right.p2); + _cairo_slope_init (&slope_pt, &t->right.p1, pt); + + if (_cairo_slope_compare (&slope_pt, &slope_right) < 0) + return FALSE; + + return TRUE; +} + +cairo_bool_t +_cairo_traps_contain (const cairo_traps_t *traps, + double x, double y) +{ + int i; + cairo_point_t point; + + point.x = _cairo_fixed_from_double (x); + point.y = _cairo_fixed_from_double (y); + + for (i = 0; i < traps->num_traps; i++) { + if (_cairo_trap_contains (&traps->traps[i], &point)) + return TRUE; + } + + return FALSE; +} + +static cairo_fixed_t +_line_compute_intersection_x_for_y (const cairo_line_t *line, + cairo_fixed_t y) +{ + return _cairo_edge_compute_intersection_x_for_y (&line->p1, &line->p2, y); +} + +void +_cairo_traps_extents (const cairo_traps_t *traps, + cairo_box_t *extents) +{ + int i; + + if (traps->num_traps == 0) { + extents->p1.x = extents->p1.y = 0; + extents->p2.x = extents->p2.y = 0; + return; + } + + extents->p1.x = extents->p1.y = INT32_MAX; + extents->p2.x = extents->p2.y = INT32_MIN; + + for (i = 0; i < traps->num_traps; i++) { + const cairo_trapezoid_t *trap = &traps->traps[i]; + + if (trap->top < extents->p1.y) + extents->p1.y = trap->top; + if (trap->bottom > extents->p2.y) + extents->p2.y = trap->bottom; + + if (trap->left.p1.x < extents->p1.x) { + cairo_fixed_t x = trap->left.p1.x; + if (trap->top != trap->left.p1.y) { + x = _line_compute_intersection_x_for_y (&trap->left, + trap->top); + if (x < extents->p1.x) + extents->p1.x = x; + } else + extents->p1.x = x; + } + if (trap->left.p2.x < extents->p1.x) { + cairo_fixed_t x = trap->left.p2.x; + if (trap->bottom != trap->left.p2.y) { + x = _line_compute_intersection_x_for_y (&trap->left, + trap->bottom); + if (x < extents->p1.x) + extents->p1.x = x; + } else + extents->p1.x = x; + } + + if (trap->right.p1.x > extents->p2.x) { + cairo_fixed_t x = trap->right.p1.x; + if (trap->top != trap->right.p1.y) { + x = _line_compute_intersection_x_for_y (&trap->right, + trap->top); + if (x > extents->p2.x) + extents->p2.x = x; + } else + extents->p2.x = x; + } + if (trap->right.p2.x > extents->p2.x) { + cairo_fixed_t x = trap->right.p2.x; + if (trap->bottom != trap->right.p2.y) { + x = _line_compute_intersection_x_for_y (&trap->right, + trap->bottom); + if (x > extents->p2.x) + extents->p2.x = x; + } else + extents->p2.x = x; + } + } +} + +static cairo_bool_t +_mono_edge_is_vertical (const cairo_line_t *line) +{ + return _cairo_fixed_integer_round_down (line->p1.x) == _cairo_fixed_integer_round_down (line->p2.x); +} + +static cairo_bool_t +_traps_are_pixel_aligned (cairo_traps_t *traps, + cairo_antialias_t antialias) +{ + int i; + + if (antialias == CAIRO_ANTIALIAS_NONE) { + for (i = 0; i < traps->num_traps; i++) { + if (! _mono_edge_is_vertical (&traps->traps[i].left) || + ! _mono_edge_is_vertical (&traps->traps[i].right)) + { + traps->maybe_region = FALSE; + return FALSE; + } + } + } else { + for (i = 0; i < traps->num_traps; i++) { + if (traps->traps[i].left.p1.x != traps->traps[i].left.p2.x || + traps->traps[i].right.p1.x != traps->traps[i].right.p2.x || + ! _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 FALSE; + } + } + } + + return TRUE; +} + +/** + * _cairo_traps_extract_region: + * @traps: a #cairo_traps_t + * @region: a #cairo_region_t + * + * Determines if a set of trapezoids are exactly representable as a + * cairo region. If so, the passed-in region is initialized to + * the area representing the given traps. It should be finalized + * with cairo_region_fini(). If not, %CAIRO_INT_STATUS_UNSUPPORTED + * is returned. + * + * Return value: %CAIRO_STATUS_SUCCESS, %CAIRO_INT_STATUS_UNSUPPORTED + * or %CAIRO_STATUS_NO_MEMORY + **/ +cairo_int_status_t +_cairo_traps_extract_region (cairo_traps_t *traps, + cairo_antialias_t antialias, + cairo_region_t **region) +{ + cairo_rectangle_int_t stack_rects[CAIRO_STACK_ARRAY_LENGTH (cairo_rectangle_int_t)]; + cairo_rectangle_int_t *rects = stack_rects; + cairo_int_status_t status; + int i, rect_count; + + /* we only treat this a hint... */ + if (antialias != CAIRO_ANTIALIAS_NONE && ! traps->maybe_region) + return CAIRO_INT_STATUS_UNSUPPORTED; + + if (! _traps_are_pixel_aligned (traps, antialias)) { + 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); + } + + rect_count = 0; + for (i = 0; i < traps->num_traps; i++) { + int x1, y1, x2, y2; + + if (antialias == CAIRO_ANTIALIAS_NONE) { + x1 = _cairo_fixed_integer_round_down (traps->traps[i].left.p1.x); + y1 = _cairo_fixed_integer_round_down (traps->traps[i].top); + x2 = _cairo_fixed_integer_round_down (traps->traps[i].right.p1.x); + y2 = _cairo_fixed_integer_round_down (traps->traps[i].bottom); + } else { + x1 = _cairo_fixed_integer_part (traps->traps[i].left.p1.x); + y1 = _cairo_fixed_integer_part (traps->traps[i].top); + x2 = _cairo_fixed_integer_part (traps->traps[i].right.p1.x); + y2 = _cairo_fixed_integer_part (traps->traps[i].bottom); + } + + if (x2 > x1 && y2 > y1) { + rects[rect_count].x = x1; + rects[rect_count].y = y1; + rects[rect_count].width = x2 - x1; + rects[rect_count].height = y2 - y1; + rect_count++; + } + } + + + *region = cairo_region_create_rectangles (rects, rect_count); + status = (*region)->status; + + if (rects != stack_rects) + free (rects); + + return status; +} + +cairo_bool_t +_cairo_traps_to_boxes (cairo_traps_t *traps, + cairo_antialias_t antialias, + cairo_boxes_t *boxes) +{ + int i; + + for (i = 0; i < traps->num_traps; i++) { + if (traps->traps[i].left.p1.x != traps->traps[i].left.p2.x || + traps->traps[i].right.p1.x != traps->traps[i].right.p2.x) + return FALSE; + } + + _cairo_boxes_init (boxes); + + boxes->num_boxes = traps->num_traps; + boxes->chunks.base = (cairo_box_t *) traps->traps; + boxes->chunks.count = traps->num_traps; + boxes->chunks.size = traps->num_traps; + + if (antialias != CAIRO_ANTIALIAS_NONE) { + for (i = 0; i < traps->num_traps; i++) { + /* Note the traps and boxes alias so we need to take the local copies first. */ + cairo_fixed_t x1 = traps->traps[i].left.p1.x; + cairo_fixed_t x2 = traps->traps[i].right.p1.x; + cairo_fixed_t y1 = traps->traps[i].top; + cairo_fixed_t y2 = traps->traps[i].bottom; + + boxes->chunks.base[i].p1.x = x1; + boxes->chunks.base[i].p1.y = y1; + boxes->chunks.base[i].p2.x = x2; + boxes->chunks.base[i].p2.y = y2; + + if (boxes->is_pixel_aligned) { + boxes->is_pixel_aligned = + _cairo_fixed_is_integer (x1) && _cairo_fixed_is_integer (y1) && + _cairo_fixed_is_integer (x2) && _cairo_fixed_is_integer (y2); + } + } + } else { + boxes->is_pixel_aligned = TRUE; + + for (i = 0; i < traps->num_traps; i++) { + /* Note the traps and boxes alias so we need to take the local copies first. */ + cairo_fixed_t x1 = traps->traps[i].left.p1.x; + cairo_fixed_t x2 = traps->traps[i].right.p1.x; + cairo_fixed_t y1 = traps->traps[i].top; + cairo_fixed_t y2 = traps->traps[i].bottom; + + /* round down here to match Pixman's behavior when using traps. */ + boxes->chunks.base[i].p1.x = _cairo_fixed_round_down (x1); + boxes->chunks.base[i].p1.y = _cairo_fixed_round_down (y1); + boxes->chunks.base[i].p2.x = _cairo_fixed_round_down (x2); + boxes->chunks.base[i].p2.y = _cairo_fixed_round_down (y2); + } + } + + return TRUE; +} + +/* moves trap points such that they become the actual corners of the trapezoid */ +static void +_sanitize_trap (cairo_trapezoid_t *t) +{ + cairo_trapezoid_t s = *t; + +#define FIX(lr, tb, p) \ + if (t->lr.p.y != t->tb) { \ + t->lr.p.x = s.lr.p2.x + _cairo_fixed_mul_div_floor (s.lr.p1.x - s.lr.p2.x, s.tb - s.lr.p2.y, s.lr.p1.y - s.lr.p2.y); \ + t->lr.p.y = s.tb; \ + } + FIX (left, top, p1); + FIX (left, bottom, p2); + FIX (right, top, p1); + FIX (right, bottom, p2); +} + +cairo_private cairo_status_t +_cairo_traps_path (const cairo_traps_t *traps, + cairo_path_fixed_t *path) +{ + int i; + + for (i = 0; i < traps->num_traps; i++) { + cairo_status_t status; + cairo_trapezoid_t trap = traps->traps[i]; + + if (trap.top == trap.bottom) + continue; + + _sanitize_trap (&trap); + + status = _cairo_path_fixed_move_to (path, trap.left.p1.x, trap.top); + if (unlikely (status)) return status; + status = _cairo_path_fixed_line_to (path, trap.right.p1.x, trap.top); + if (unlikely (status)) return status; + status = _cairo_path_fixed_line_to (path, trap.right.p2.x, trap.bottom); + if (unlikely (status)) return status; + status = _cairo_path_fixed_line_to (path, trap.left.p2.x, trap.bottom); + if (unlikely (status)) return status; + status = _cairo_path_fixed_close_path (path); + if (unlikely (status)) return status; + } + + return CAIRO_STATUS_SUCCESS; +} + +void +_cairo_debug_print_traps (FILE *file, const cairo_traps_t *traps) +{ + cairo_box_t extents; + int n; + +#if 0 + if (traps->has_limits) { + printf ("%s: limits=(%d, %d, %d, %d)\n", + filename, + traps->limits.p1.x, traps->limits.p1.y, + traps->limits.p2.x, traps->limits.p2.y); + } +#endif + + _cairo_traps_extents (traps, &extents); + fprintf (file, "extents=(%d, %d, %d, %d)\n", + extents.p1.x, extents.p1.y, + extents.p2.x, extents.p2.y); + + 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); + } +} + +struct cairo_trap_renderer { + cairo_span_renderer_t base; + cairo_traps_t *traps; +}; + +static cairo_status_t +span_to_traps (void *abstract_renderer, int y, int h, + const cairo_half_open_span_t *spans, unsigned num_spans) +{ + struct cairo_trap_renderer *r = abstract_renderer; + cairo_fixed_t top, bot; + + if (num_spans == 0) + return CAIRO_STATUS_SUCCESS; + + top = _cairo_fixed_from_int (y); + bot = _cairo_fixed_from_int (y + h); + do { + if (spans[0].coverage) { + cairo_fixed_t x0 = _cairo_fixed_from_int(spans[0].x); + cairo_fixed_t x1 = _cairo_fixed_from_int(spans[1].x); + cairo_line_t left = { { x0, top }, { x0, bot } }, + right = { { x1, top }, { x1, bot } }; + _cairo_traps_add_trap (r->traps, top, bot, &left, &right); + } + spans++; + } while (--num_spans > 1); + + return CAIRO_STATUS_SUCCESS; +} + +cairo_int_status_t +_cairo_rasterise_polygon_to_traps (cairo_polygon_t *polygon, + cairo_fill_rule_t fill_rule, + cairo_antialias_t antialias, + cairo_traps_t *traps) +{ + struct cairo_trap_renderer renderer; + cairo_scan_converter_t *converter; + cairo_int_status_t status; + cairo_rectangle_int_t r; + + TRACE ((stderr, "%s: fill_rule=%d, antialias=%d\n", + __FUNCTION__, fill_rule, antialias)); + assert(antialias == CAIRO_ANTIALIAS_NONE); + + renderer.traps = traps; + renderer.base.render_rows = span_to_traps; + + _cairo_box_round_to_rectangle (&polygon->extents, &r); + converter = _cairo_mono_scan_converter_create (r.x, r.y, + r.x + r.width, + r.y + r.height, + fill_rule); + status = _cairo_mono_scan_converter_add_polygon (converter, polygon); + if (likely (status == CAIRO_INT_STATUS_SUCCESS)) + status = converter->generate (converter, &renderer.base); + converter->destroy (converter); + return status; +} |