Attachment 106708 Details for Bug 84115 – Eliminate precision loss when emitting line joins

[patch] Eliminate precision loss when emitting line joins

0001-stroke-traps-Emit-join-without-loss-of-precision.patch (text/plain), 31.48 KB, created by Chris Wilson on 2014-09-23 07:00:18 UTC

(hide)

Description:

Filename:

MIME Type:

Creator: Chris Wilson

Created: 2014-09-23 07:00:18 UTC

Size: 31.48 KB

patch

obsolete

>From de22e1c4921d39043e6e974c3c234f6266771c05 Mon Sep 17 00:00:00 2001
>From: Chris Wilson <chris@chris-wilson.co.uk>
>Date: Mon, 22 Sep 2014 12:53:08 +0100
>Subject: [PATCH] stroke,traps: Emit join without loss of precision
>
>Bugzilla: https://bugs.freedesktop.org/show_bug.cgi?id=84115
>Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
>---
> src/Makefile.sources          |   3 +
> src/cairo-bentley-ottmann.c   | 232 +-------------------------------
> src/cairo-line-inline.h       |  48 +++++++
> src/cairo-line-private.h      |  50 +++++++
> src/cairo-line.c              | 306 ++++++++++++++++++++++++++++++++++++++++++
> src/cairo-path-stroke-traps.c |  55 +++++---
> src/cairo-traps-private.h     |   8 +-
> src/cairo-traps.c             |  85 ++++++++++--
> 8 files changed, 530 insertions(+), 257 deletions(-)
> create mode 100644 src/cairo-line-inline.h
> create mode 100644 src/cairo-line-private.h
> create mode 100644 src/cairo-line.c
>
>diff --git a/src/Makefile.sources b/src/Makefile.sources
>index 4abf57d..1247bff 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 \
>@@ -175,6 +177,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 0e1a3f5..91e41f9 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 0000000..71cc5e7
>--- /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 0000000..ad401ef
>--- /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 0000000..cb13927
>--- /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 304dea7..7f03c89 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 7fef062..dcaf40d 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 9f1d4a7..091b154 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:
>-- 
>1.9.3
>

Actions: View | Splinter Review

Attachments on bug 84115: 106572 | 106672 | 106708

Use of freedesktop.org services, including Bugzilla, is subject to our Code of Conduct. How we collect and use information is described in our Privacy Policy.