From 28d16176960e908983aaa3926faddc374209de78 Mon Sep 17 00:00:00 2001 From: Akira Kakuto Date: Mon, 28 Dec 2015 11:39:07 +0000 Subject: cairo-1.14.6 git-svn-id: svn://tug.org/texlive/trunk@39210 c570f23f-e606-0410-a88d-b1316a301751 --- Build/source/libs/cairo/cairo-src/src/cairo-line.c | 306 +++++++++++++++++++++ 1 file changed, 306 insertions(+) create mode 100644 Build/source/libs/cairo/cairo-src/src/cairo-line.c (limited to 'Build/source/libs/cairo/cairo-src/src/cairo-line.c') diff --git a/Build/source/libs/cairo/cairo-src/src/cairo-line.c b/Build/source/libs/cairo/cairo-src/src/cairo-line.c new file mode 100644 index 00000000000..cb13927bdce --- /dev/null +++ b/Build/source/libs/cairo/cairo-src/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 + * Chris Wilson + * + */ + +#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); +} -- cgit v1.2.3