stroke,traps: Emit join without loss of precision

As the target renderers operate at a different sample resolution then we
use internally for coordinate representation, there is always a potential
for discrepancies in the line gradients when passing around trapezoids.
To overcome this, the protocol specification of trapezoids uses the full
lines and vertical range as opposed to vertices and so long as we always
use the same lines for conjoint trapezoids, they remain abutting in the
rasteriser.

Bugzilla: https://bugs.freedesktop.org/show_bug.cgi?id=84115
Testcase: bug-84115
Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>

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);
+}