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, 7 insertions, 225 deletions

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