summaryrefslogtreecommitdiff
path: root/src/cairo-line.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/cairo-line.c')
-rw-r--r--src/cairo-line.c306
1 files changed, 306 insertions, 0 deletions
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);
+}