diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/Makefile.sources | 3 | ||||
| -rw-r--r-- | src/cairo-bentley-ottmann.c | 232 | ||||
| -rw-r--r-- | src/cairo-line-inline.h | 48 | ||||
| -rw-r--r-- | src/cairo-line-private.h | 50 | ||||
| -rw-r--r-- | src/cairo-line.c | 306 | ||||
| -rw-r--r-- | src/cairo-path-stroke-traps.c | 55 | ||||
| -rw-r--r-- | src/cairo-traps-private.h | 8 | ||||
| -rw-r--r-- | src/cairo-traps.c | 85 |
8 files changed, 530 insertions, 257 deletions
diff --git a/src/Makefile.sources b/src/Makefile.sources index c946cad01..fac24d79d 100644 --- a/src/Makefile.sources +++ b/src/Makefile.sources @@ -84,6 +84,8 @@ cairo_private = \ cairo-image-info-private.h \ cairo-image-surface-inline.h \ cairo-image-surface-private.h \ + cairo-line-inline.h \ + cairo-line-private.h \ cairo-list-inline.h \ cairo-list-private.h \ cairo-malloc-private.h \ @@ -176,6 +178,7 @@ cairo_sources = \ cairo-image-info.c \ cairo-image-source.c \ cairo-image-surface.c \ + cairo-line.c \ cairo-lzw.c \ cairo-matrix.c \ cairo-mask-compositor.c \ diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c index 0e1a3f570..91e41f9c3 100644 --- a/src/cairo-bentley-ottmann.c +++ b/src/cairo-bentley-ottmann.c @@ -38,9 +38,10 @@ /* Provide definitions for standalone compilation */ #include "cairoint.h" +#include "cairo-combsort-inline.h" #include "cairo-error-private.h" #include "cairo-freelist-private.h" -#include "cairo-combsort-inline.h" +#include "cairo-line-inline.h" #include "cairo-traps-private.h" #define DEBUG_PRINT_STATE 0 @@ -307,156 +308,6 @@ _slope_compare (const cairo_bo_edge_t *a, } } -/* - * We need to compare the x-coordinates of a pair of lines for a particular y, - * without loss of precision. - * - * The x-coordinate along an edge for a given y is: - * X = A_x + (Y - A_y) * A_dx / A_dy - * - * So the inequality we wish to test is: - * A_x + (Y - A_y) * A_dx / A_dy ∘ B_x + (Y - B_y) * B_dx / B_dy, - * where ∘ is our inequality operator. - * - * By construction, we know that A_dy and B_dy (and (Y - A_y), (Y - B_y)) are - * all positive, so we can rearrange it thus without causing a sign change: - * A_dy * B_dy * (A_x - B_x) ∘ (Y - B_y) * B_dx * A_dy - * - (Y - A_y) * A_dx * B_dy - * - * Given the assumption that all the deltas fit within 32 bits, we can compute - * this comparison directly using 128 bit arithmetic. For certain, but common, - * input we can reduce this down to a single 32 bit compare by inspecting the - * deltas. - * - * (And put the burden of the work on developing fast 128 bit ops, which are - * required throughout the tessellator.) - * - * See the similar discussion for _slope_compare(). - */ -static int -edges_compare_x_for_y_general (const cairo_bo_edge_t *a, - const cairo_bo_edge_t *b, - int32_t y) -{ - /* XXX: We're assuming here that dx and dy will still fit in 32 - * bits. That's not true in general as there could be overflow. We - * should prevent that before the tessellation algorithm - * begins. - */ - int32_t dx; - int32_t adx, ady; - int32_t bdx, bdy; - enum { - HAVE_NONE = 0x0, - HAVE_DX = 0x1, - HAVE_ADX = 0x2, - HAVE_DX_ADX = HAVE_DX | HAVE_ADX, - HAVE_BDX = 0x4, - HAVE_DX_BDX = HAVE_DX | HAVE_BDX, - HAVE_ADX_BDX = HAVE_ADX | HAVE_BDX, - HAVE_ALL = HAVE_DX | HAVE_ADX | HAVE_BDX - } have_dx_adx_bdx = HAVE_ALL; - - /* don't bother solving for abscissa if the edges' bounding boxes - * can be used to order them. */ - { - int32_t amin, amax; - int32_t bmin, bmax; - if (a->edge.line.p1.x < a->edge.line.p2.x) { - amin = a->edge.line.p1.x; - amax = a->edge.line.p2.x; - } else { - amin = a->edge.line.p2.x; - amax = a->edge.line.p1.x; - } - if (b->edge.line.p1.x < b->edge.line.p2.x) { - bmin = b->edge.line.p1.x; - bmax = b->edge.line.p2.x; - } else { - bmin = b->edge.line.p2.x; - bmax = b->edge.line.p1.x; - } - if (amax < bmin) return -1; - if (amin > bmax) return +1; - } - - ady = a->edge.line.p2.y - a->edge.line.p1.y; - adx = a->edge.line.p2.x - a->edge.line.p1.x; - if (adx == 0) - have_dx_adx_bdx &= ~HAVE_ADX; - - bdy = b->edge.line.p2.y - b->edge.line.p1.y; - bdx = b->edge.line.p2.x - b->edge.line.p1.x; - if (bdx == 0) - have_dx_adx_bdx &= ~HAVE_BDX; - - dx = a->edge.line.p1.x - b->edge.line.p1.x; - if (dx == 0) - have_dx_adx_bdx &= ~HAVE_DX; - -#define L _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (ady, bdy), dx) -#define A _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (adx, bdy), y - a->edge.line.p1.y) -#define B _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (bdx, ady), y - b->edge.line.p1.y) - switch (have_dx_adx_bdx) { - default: - case HAVE_NONE: - return 0; - case HAVE_DX: - /* A_dy * B_dy * (A_x - B_x) ∘ 0 */ - return dx; /* ady * bdy is positive definite */ - case HAVE_ADX: - /* 0 ∘ - (Y - A_y) * A_dx * B_dy */ - return adx; /* bdy * (y - a->top.y) is positive definite */ - case HAVE_BDX: - /* 0 ∘ (Y - B_y) * B_dx * A_dy */ - return -bdx; /* ady * (y - b->top.y) is positive definite */ - case HAVE_ADX_BDX: - /* 0 ∘ (Y - B_y) * B_dx * A_dy - (Y - A_y) * A_dx * B_dy */ - if ((adx ^ bdx) < 0) { - return adx; - } else if (a->edge.line.p1.y == b->edge.line.p1.y) { /* common origin */ - cairo_int64_t adx_bdy, bdx_ady; - - /* ∴ A_dx * B_dy ∘ B_dx * A_dy */ - - adx_bdy = _cairo_int32x32_64_mul (adx, bdy); - bdx_ady = _cairo_int32x32_64_mul (bdx, ady); - - return _cairo_int64_cmp (adx_bdy, bdx_ady); - } else - return _cairo_int128_cmp (A, B); - case HAVE_DX_ADX: - /* A_dy * (A_x - B_x) ∘ - (Y - A_y) * A_dx */ - if ((-adx ^ dx) < 0) { - return dx; - } else { - cairo_int64_t ady_dx, dy_adx; - - ady_dx = _cairo_int32x32_64_mul (ady, dx); - dy_adx = _cairo_int32x32_64_mul (a->edge.line.p1.y - y, adx); - - return _cairo_int64_cmp (ady_dx, dy_adx); - } - case HAVE_DX_BDX: - /* B_dy * (A_x - B_x) ∘ (Y - B_y) * B_dx */ - if ((bdx ^ dx) < 0) { - return dx; - } else { - cairo_int64_t bdy_dx, dy_bdx; - - bdy_dx = _cairo_int32x32_64_mul (bdy, dx); - dy_bdx = _cairo_int32x32_64_mul (y - b->edge.line.p1.y, bdx); - - return _cairo_int64_cmp (bdy_dx, dy_bdx); - } - case HAVE_ALL: - /* XXX try comparing (a->edge.line.p2.x - b->edge.line.p2.x) et al */ - return _cairo_int128_cmp (L, _cairo_int128_sub (B, A)); - } -#undef B -#undef A -#undef L -} /* * We need to compare the x-coordinate of a line for a particular y wrt to a @@ -510,58 +361,6 @@ edge_compare_for_y_against_x (const cairo_bo_edge_t *a, return _cairo_int64_cmp (L, R); } -static int -edges_compare_x_for_y (const cairo_bo_edge_t *a, - const cairo_bo_edge_t *b, - int32_t y) -{ - /* If the sweep-line is currently on an end-point of a line, - * then we know its precise x value (and considering that we often need to - * compare events at end-points, this happens frequently enough to warrant - * special casing). - */ - enum { - HAVE_NEITHER = 0x0, - HAVE_AX = 0x1, - HAVE_BX = 0x2, - HAVE_BOTH = HAVE_AX | HAVE_BX - } have_ax_bx = HAVE_BOTH; - int32_t ax, bx; - - if (y == a->edge.line.p1.y) - ax = a->edge.line.p1.x; - else if (y == a->edge.line.p2.y) - ax = a->edge.line.p2.x; - else - have_ax_bx &= ~HAVE_AX; - - if (y == b->edge.line.p1.y) - bx = b->edge.line.p1.x; - else if (y == b->edge.line.p2.y) - bx = b->edge.line.p2.x; - else - have_ax_bx &= ~HAVE_BX; - - switch (have_ax_bx) { - default: - case HAVE_NEITHER: - return edges_compare_x_for_y_general (a, b, y); - case HAVE_AX: - return -edge_compare_for_y_against_x (b, y, ax); - case HAVE_BX: - return edge_compare_for_y_against_x (a, y, bx); - case HAVE_BOTH: - return ax - bx; - } -} - -static inline int -_line_equal (const cairo_line_t *a, const cairo_line_t *b) -{ - return a->p1.x == b->p1.x && a->p1.y == b->p1.y && - a->p2.x == b->p2.x && a->p2.y == b->p2.y; -} - static inline int _cairo_bo_sweep_line_compare_edges (const cairo_bo_sweep_line_t *sweep_line, const cairo_bo_edge_t *a, @@ -569,28 +368,11 @@ _cairo_bo_sweep_line_compare_edges (const cairo_bo_sweep_line_t *sweep_line, { int cmp; - /* compare the edges if not identical */ - if (! _line_equal (&a->edge.line, &b->edge.line)) { - if (MAX (a->edge.line.p1.x, a->edge.line.p2.x) < - MIN (b->edge.line.p1.x, b->edge.line.p2.x)) - return -1; - else if (MIN (a->edge.line.p1.x, a->edge.line.p2.x) > - MAX (b->edge.line.p1.x, b->edge.line.p2.x)) - return 1; - - cmp = edges_compare_x_for_y (a, b, sweep_line->current_y); - if (cmp) - return cmp; - - /* The two edges intersect exactly at y, so fall back on slope - * comparison. We know that this compare_edges function will be - * called only when starting a new edge, (not when stopping an - * edge), so we don't have to worry about conditionally inverting - * the sense of _slope_compare. */ - cmp = _slope_compare (a, b); - if (cmp) + cmp = cairo_lines_compare_at_y (&a->edge.line, + &b->edge.line, + sweep_line->current_y); + if (cmp) return cmp; - } /* We've got two collinear edges now. */ return b->edge.bottom - a->edge.bottom; @@ -1090,7 +872,7 @@ _cairo_bo_event_queue_insert_if_intersect_below_current_y (cairo_bo_event_queue_ MIN (right->edge.line.p1.x, right->edge.line.p2.x)) return CAIRO_STATUS_SUCCESS; - if (_line_equal (&left->edge.line, &right->edge.line)) + if (cairo_lines_equal (&left->edge.line, &right->edge.line)) return CAIRO_STATUS_SUCCESS; /* The names "left" and "right" here are correct descriptions of diff --git a/src/cairo-line-inline.h b/src/cairo-line-inline.h new file mode 100644 index 000000000..71cc5e7eb --- /dev/null +++ b/src/cairo-line-inline.h @@ -0,0 +1,48 @@ +/* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */ +/* cairo - a vector graphics library with display and print output + * + * Copyright © 2014 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. + * + */ + +#ifndef CAIRO_LINE_INLINE_H +#define CAIRO_LINE_INLINE_H + +#include "cairo-types-private.h" +#include "cairo-compiler-private.h" +#include "cairo-fixed-private.h" +#include "cairo-line-private.h" + +static inline int +cairo_lines_equal (const cairo_line_t *a, const cairo_line_t *b) +{ + return (a->p1.x == b->p1.x && a->p1.y == b->p1.y && + a->p2.x == b->p2.x && a->p2.y == b->p2.y); +} + +#endif /* CAIRO_LINE_INLINE_H */ diff --git a/src/cairo-line-private.h b/src/cairo-line-private.h new file mode 100644 index 000000000..ad401ef81 --- /dev/null +++ b/src/cairo-line-private.h @@ -0,0 +1,50 @@ +/* cairo - a vector graphics library with display and print output + * + * Copyright © 2014 Intel Corporation, 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 University of Southern + * California. + * + */ + +#ifndef CAIRO_LINE_PRIVATE_H +#define CAIRO_LINE_PRIVATE_H + +#include "cairo-compiler-private.h" +#include "cairo-error-private.h" +#include "cairo-types-private.h" + +CAIRO_BEGIN_DECLS + +int cairo_lines_compare_at_y(const cairo_line_t *a, + const cairo_line_t *b, + int y); + +CAIRO_END_DECLS + +#endif /* CAIRO_LINE_PRIVATE_H */ diff --git a/src/cairo-line.c b/src/cairo-line.c new file mode 100644 index 000000000..cb13927bd --- /dev/null +++ b/src/cairo-line.c @@ -0,0 +1,306 @@ +/* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */ +/* + * Copyright © 2004 Carl Worth + * Copyright © 2006 Red Hat, Inc. + * Copyright © 2008 Chris Wilson + * Copyright © 2014 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 Keith Packard + * + * Contributor(s): + * Carl D. Worth <cworth@cworth.org> + * Chris Wilson <chris@chris-wilson.co.uk> + * + */ + +#include "cairoint.h" + +#include "cairo-line-inline.h" +#include "cairo-slope-private.h" + +static int +line_compare_for_y_against_x (const cairo_line_t *a, + int32_t y, + int32_t x) +{ + int32_t adx, ady; + int32_t dx, dy; + cairo_int64_t L, R; + + if (x < a->p1.x && x < a->p2.x) + return 1; + if (x > a->p1.x && x > a->p2.x) + return -1; + + adx = a->p2.x - a->p1.x; + dx = x - a->p1.x; + + if (adx == 0) + return -dx; + if (dx == 0 || (adx ^ dx) < 0) + return adx; + + dy = y - a->p1.y; + ady = a->p2.y - a->p1.y; + + L = _cairo_int32x32_64_mul (dy, adx); + R = _cairo_int32x32_64_mul (dx, ady); + + return _cairo_int64_cmp (L, R); +} + +/* + * We need to compare the x-coordinates of a pair of lines for a particular y, + * without loss of precision. + * + * The x-coordinate along an edge for a given y is: + * X = A_x + (Y - A_y) * A_dx / A_dy + * + * So the inequality we wish to test is: + * A_x + (Y - A_y) * A_dx / A_dy ∘ B_x + (Y - B_y) * B_dx / B_dy, + * where ∘ is our inequality operator. + * + * By construction, we know that A_dy and B_dy (and (Y - A_y), (Y - B_y)) are + * all positive, so we can rearrange it thus without causing a sign change: + * A_dy * B_dy * (A_x - B_x) ∘ (Y - B_y) * B_dx * A_dy + * - (Y - A_y) * A_dx * B_dy + * + * Given the assumption that all the deltas fit within 32 bits, we can compute + * this comparison directly using 128 bit arithmetic. For certain, but common, + * input we can reduce this down to a single 32 bit compare by inspecting the + * deltas. + * + * (And put the burden of the work on developing fast 128 bit ops, which are + * required throughout the tessellator.) + * + * See the similar discussion for _slope_compare(). + */ +static int +lines_compare_x_for_y_general (const cairo_line_t *a, + const cairo_line_t *b, + int32_t y) +{ + /* XXX: We're assuming here that dx and dy will still fit in 32 + * bits. That's not true in general as there could be overflow. We + * should prevent that before the tessellation algorithm + * begins. + */ + int32_t dx; + int32_t adx, ady; + int32_t bdx, bdy; + enum { + HAVE_NONE = 0x0, + HAVE_DX = 0x1, + HAVE_ADX = 0x2, + HAVE_DX_ADX = HAVE_DX | HAVE_ADX, + HAVE_BDX = 0x4, + HAVE_DX_BDX = HAVE_DX | HAVE_BDX, + HAVE_ADX_BDX = HAVE_ADX | HAVE_BDX, + HAVE_ALL = HAVE_DX | HAVE_ADX | HAVE_BDX + } have_dx_adx_bdx = HAVE_ALL; + + ady = a->p2.y - a->p1.y; + adx = a->p2.x - a->p1.x; + if (adx == 0) + have_dx_adx_bdx &= ~HAVE_ADX; + + bdy = b->p2.y - b->p1.y; + bdx = b->p2.x - b->p1.x; + if (bdx == 0) + have_dx_adx_bdx &= ~HAVE_BDX; + + dx = a->p1.x - b->p1.x; + if (dx == 0) + have_dx_adx_bdx &= ~HAVE_DX; + +#define L _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (ady, bdy), dx) +#define A _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (adx, bdy), y - a->p1.y) +#define B _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (bdx, ady), y - b->p1.y) + switch (have_dx_adx_bdx) { + default: + case HAVE_NONE: + return 0; + case HAVE_DX: + /* A_dy * B_dy * (A_x - B_x) ∘ 0 */ + return dx; /* ady * bdy is positive definite */ + case HAVE_ADX: + /* 0 ∘ - (Y - A_y) * A_dx * B_dy */ + return adx; /* bdy * (y - a->top.y) is positive definite */ + case HAVE_BDX: + /* 0 ∘ (Y - B_y) * B_dx * A_dy */ + return -bdx; /* ady * (y - b->top.y) is positive definite */ + case HAVE_ADX_BDX: + /* 0 ∘ (Y - B_y) * B_dx * A_dy - (Y - A_y) * A_dx * B_dy */ + if ((adx ^ bdx) < 0) { + return adx; + } else if (a->p1.y == b->p1.y) { /* common origin */ + cairo_int64_t adx_bdy, bdx_ady; + + /* ∴ A_dx * B_dy ∘ B_dx * A_dy */ + + adx_bdy = _cairo_int32x32_64_mul (adx, bdy); + bdx_ady = _cairo_int32x32_64_mul (bdx, ady); + + return _cairo_int64_cmp (adx_bdy, bdx_ady); + } else + return _cairo_int128_cmp (A, B); + case HAVE_DX_ADX: + /* A_dy * (A_x - B_x) ∘ - (Y - A_y) * A_dx */ + if ((-adx ^ dx) < 0) { + return dx; + } else { + cairo_int64_t ady_dx, dy_adx; + + ady_dx = _cairo_int32x32_64_mul (ady, dx); + dy_adx = _cairo_int32x32_64_mul (a->p1.y - y, adx); + + return _cairo_int64_cmp (ady_dx, dy_adx); + } + case HAVE_DX_BDX: + /* B_dy * (A_x - B_x) ∘ (Y - B_y) * B_dx */ + if ((bdx ^ dx) < 0) { + return dx; + } else { + cairo_int64_t bdy_dx, dy_bdx; + + bdy_dx = _cairo_int32x32_64_mul (bdy, dx); + dy_bdx = _cairo_int32x32_64_mul (y - b->p1.y, bdx); + + return _cairo_int64_cmp (bdy_dx, dy_bdx); + } + case HAVE_ALL: + /* XXX try comparing (a->p2.x - b->p2.x) et al */ + return _cairo_int128_cmp (L, _cairo_int128_sub (B, A)); + } +#undef B +#undef A +#undef L +} + +static int +lines_compare_x_for_y (const cairo_line_t *a, + const cairo_line_t *b, + int32_t y) +{ + /* If the sweep-line is currently on an end-point of a line, + * then we know its precise x value (and considering that we often need to + * compare events at end-points, this happens frequently enough to warrant + * special casing). + */ + enum { + HAVE_NEITHER = 0x0, + HAVE_AX = 0x1, + HAVE_BX = 0x2, + HAVE_BOTH = HAVE_AX | HAVE_BX + } have_ax_bx = HAVE_BOTH; + int32_t ax, bx; + + if (y == a->p1.y) + ax = a->p1.x; + else if (y == a->p2.y) + ax = a->p2.x; + else + have_ax_bx &= ~HAVE_AX; + + if (y == b->p1.y) + bx = b->p1.x; + else if (y == b->p2.y) + bx = b->p2.x; + else + have_ax_bx &= ~HAVE_BX; + + switch (have_ax_bx) { + default: + case HAVE_NEITHER: + return lines_compare_x_for_y_general (a, b, y); + case HAVE_AX: + return -line_compare_for_y_against_x (b, y, ax); + case HAVE_BX: + return line_compare_for_y_against_x (a, y, bx); + case HAVE_BOTH: + return ax - bx; + } +} + +static int bbox_compare (const cairo_line_t *a, + const cairo_line_t *b) +{ + int32_t amin, amax; + int32_t bmin, bmax; + + if (a->p1.x < a->p2.x) { + amin = a->p1.x; + amax = a->p2.x; + } else { + amin = a->p2.x; + amax = a->p1.x; + } + + if (b->p1.x < b->p2.x) { + bmin = b->p1.x; + bmax = b->p2.x; + } else { + bmin = b->p2.x; + bmax = b->p1.x; + } + + if (amax < bmin) + return -1; + + if (amin > bmax) + return +1; + + return 0; +} + +int cairo_lines_compare_at_y (const cairo_line_t *a, + const cairo_line_t *b, + int y) +{ + cairo_slope_t sa, sb; + int ret; + + if (cairo_lines_equal (a, b)) + return 0; + + /* Don't bother solving for abscissa if the edges' bounding boxes + * can be used to order them. + */ + ret = bbox_compare (a, b); + if (ret) + return ret; + + ret = lines_compare_x_for_y (a, b, y); + if (ret) + return ret; + + _cairo_slope_init (&sa, &a->p1, &a->p2); + _cairo_slope_init (&sb, &b->p1, &b->p2); + + return _cairo_slope_compare (&sb, &sa); +} diff --git a/src/cairo-path-stroke-traps.c b/src/cairo-path-stroke-traps.c index 8b6e30f6c..520a3e5b9 100644 --- a/src/cairo-path-stroke-traps.c +++ b/src/cairo-path-stroke-traps.c @@ -249,9 +249,11 @@ join (struct stroker *stroker, in->dev_slope.y * out->dev_slope.y) < stroker->spline_cusp_tolerance) { int start, stop; - cairo_point_t tri[3]; + cairo_point_t tri[3], edges[4]; cairo_pen_t *pen = &stroker->pen; + edges[0] = in->cw; + edges[1] = in->ccw; tri[0] = in->point; tri[1] = *inpt; if (clockwise) { @@ -261,8 +263,13 @@ join (struct stroker *stroker, while (start != stop) { tri[2] = in->point; translate_point (&tri[2], &pen->vertices[start].point); - _cairo_traps_tessellate_triangle (stroker->traps, tri); + edges[2] = in->point; + edges[3] = tri[2]; + _cairo_traps_tessellate_triangle_with_edges (stroker->traps, + tri, edges); tri[1] = tri[2]; + edges[0] = edges[2]; + edges[1] = edges[3]; if (start-- == 0) start += pen->num_vertices; @@ -274,17 +281,29 @@ join (struct stroker *stroker, while (start != stop) { tri[2] = in->point; translate_point (&tri[2], &pen->vertices[start].point); - _cairo_traps_tessellate_triangle (stroker->traps, tri); + edges[2] = in->point; + edges[3] = tri[2]; + _cairo_traps_tessellate_triangle_with_edges (stroker->traps, + tri, edges); tri[1] = tri[2]; + edges[0] = edges[2]; + edges[1] = edges[3]; if (++start == pen->num_vertices) start = 0; } } tri[2] = *outpt; - _cairo_traps_tessellate_triangle (stroker->traps, tri); - break; + edges[2] = out->cw; + edges[3] = out->ccw; + _cairo_traps_tessellate_triangle_with_edges (stroker->traps, + tri, edges); + } else { + cairo_point_t t[] = { in->point, *inpt, *outpt }; + cairo_point_t e[] = { in->cw, in->ccw, out->cw, out->ccw }; + _cairo_traps_tessellate_triangle_with_edges (stroker->traps, t, e); } + break; case CAIRO_LINE_JOIN_MITER: default: { @@ -442,12 +461,9 @@ join (struct stroker *stroker, } case CAIRO_LINE_JOIN_BEVEL: { - cairo_point_t tri[3]; - tri[0] = in->point; - tri[1] = *inpt; - tri[2] = *outpt; - - _cairo_traps_tessellate_triangle (stroker->traps, tri); + cairo_point_t t[] = { in->point, *inpt, *outpt }; + cairo_point_t e[] = { in->cw, in->ccw, out->cw, out->ccw }; + _cairo_traps_tessellate_triangle_with_edges (stroker->traps, t, e); break; } } @@ -460,7 +476,7 @@ add_cap (struct stroker *stroker, cairo_stroke_face_t *f) case CAIRO_LINE_CAP_ROUND: { int start, stop; cairo_slope_t in_slope, out_slope; - cairo_point_t tri[3]; + cairo_point_t tri[3], edges[4]; cairo_pen_t *pen = &stroker->pen; in_slope = f->dev_vector; @@ -468,19 +484,29 @@ add_cap (struct stroker *stroker, cairo_stroke_face_t *f) out_slope.dy = -in_slope.dy; _cairo_pen_find_active_cw_vertices (pen, &in_slope, &out_slope, &start, &stop); + edges[0] = f->cw; + edges[1] = f->ccw; tri[0] = f->point; tri[1] = f->cw; while (start != stop) { tri[2] = f->point; translate_point (&tri[2], &pen->vertices[start].point); - _cairo_traps_tessellate_triangle (stroker->traps, tri); + edges[2] = f->point; + edges[3] = tri[2]; + _cairo_traps_tessellate_triangle_with_edges (stroker->traps, + tri, edges); tri[1] = tri[2]; + edges[0] = edges[2]; + edges[1] = edges[3]; if (++start == pen->num_vertices) start = 0; } tri[2] = f->ccw; - _cairo_traps_tessellate_triangle (stroker->traps, tri); + edges[2] = f->cw; + edges[3] = f->ccw; + _cairo_traps_tessellate_triangle_with_edges (stroker->traps, + tri, edges); break; } @@ -932,7 +958,6 @@ spline_to (void *closure, cairo_point_t rectangle[4]; compute_face (&stroker->current_face.point, tangent, stroker, &face); - join (stroker, &stroker->current_face, &face); rectangle[0] = face.cw; diff --git a/src/cairo-traps-private.h b/src/cairo-traps-private.h index 7fef062a4..dcaf40d18 100644 --- a/src/cairo-traps-private.h +++ b/src/cairo-traps-private.h @@ -91,8 +91,9 @@ cairo_private void _cairo_traps_translate (cairo_traps_t *traps, int x, int y); cairo_private void -_cairo_traps_tessellate_triangle (cairo_traps_t *traps, - const cairo_point_t t[3]); +_cairo_traps_tessellate_triangle_with_edges (cairo_traps_t *traps, + const cairo_point_t t[3], + const cairo_point_t edges[4]); cairo_private void _cairo_traps_tessellate_convex_quad (cairo_traps_t *traps, @@ -106,7 +107,8 @@ _cairo_traps_tessellate_rectangle (cairo_traps_t *traps, cairo_private void _cairo_traps_add_trap (cairo_traps_t *traps, cairo_fixed_t top, cairo_fixed_t bottom, - cairo_line_t *left, cairo_line_t *right); + const cairo_line_t *left, + const cairo_line_t *right); cairo_private int _cairo_traps_contain (const cairo_traps_t *traps, diff --git a/src/cairo-traps.c b/src/cairo-traps.c index 9f1d4a7f5..3aa0052f9 100644 --- a/src/cairo-traps.c +++ b/src/cairo-traps.c @@ -42,6 +42,7 @@ #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" @@ -149,10 +150,15 @@ _cairo_traps_grow (cairo_traps_t *traps) void _cairo_traps_add_trap (cairo_traps_t *traps, cairo_fixed_t top, cairo_fixed_t bottom, - cairo_line_t *left, cairo_line_t *right) + 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; @@ -168,7 +174,8 @@ _cairo_traps_add_trap (cairo_traps_t *traps, static void _cairo_traps_add_clipped_trap (cairo_traps_t *traps, cairo_fixed_t _top, cairo_fixed_t _bottom, - cairo_line_t *_left, cairo_line_t *_right) + 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 @@ -386,23 +393,73 @@ _cairo_traps_tessellate_convex_quad (cairo_traps_t *traps, } } -/* A triangle is simply a degenerate case of a convex - * quadrilateral. We would not benefit from having any distinct - * implementation of triangle vs. quadrilateral tessellation here. */ -void -_cairo_traps_tessellate_triangle (cairo_traps_t *traps, - const cairo_point_t t[3]) +static void add_tri (cairo_traps_t *traps, + int y1, int y2, + const cairo_line_t *left, + const cairo_line_t *right) { - cairo_point_t quad[4]; + if (y2 < y1) { + int tmp = y1; + y1 = y2; + y2 = tmp; + } - quad[0] = t[0]; - quad[1] = t[0]; - quad[2] = t[1]; - quad[3] = t[2]; + if (cairo_lines_compare_at_y (left, right, y1) > 0) { + const cairo_line_t *tmp = left; + left = right; + right = tmp; + } - _cairo_traps_tessellate_convex_quad (traps, quad); + _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: |