[cairo-commit] 2 commits - src/cairo-bentley-ottmann.c src/cairo-line.c src/cairo-line-inline.h src/cairo-line-private.h src/cairo-path-stroke-traps.c src/cairo-traps.c src/cairo-traps-private.h src/Makefile.sources test/coverage.c test/reference
Chris Wilson
ickle at kemper.freedesktop.org
Mon Sep 29 00:42:37 PDT 2014
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 +++++++-
test/coverage.c | 55 +++++
test/reference/coverage-rhombus.ref.png |binary
10 files changed, 585 insertions(+), 257 deletions(-)
New commits:
commit 06b9f8fa2d179850cda8a0a103896bc011ce46d6
Author: Chris Wilson <chris at chris-wilson.co.uk>
Date: Mon Sep 22 12:53:08 2014 +0100
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 at chris-wilson.co.uk>
diff --git a/src/Makefile.sources b/src/Makefile.sources
index c946cad..fac24d7 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 \
@@ -176,6 +178,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 at cworth.org>
+ * Chris Wilson <chris at 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 8b6e30f..520a3e5 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..3aa0052 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:
commit 5c03b20732b84370950f0c7e5648da86ef45a571
Author: Chris Wilson <chris at chris-wilson.co.uk>
Date: Mon Sep 29 08:37:56 2014 +0100
test/coverage: Exercise invariance under mirror symmetry
Massimo noticed that the record/record-flip were not being rasterised as
identical mirror images due to a half-subpixel offset in the tor scan
converter. This test attempts to reproduce this error by rendering a
rhombus around the origin of each cell (that is it generates 4 mirror
images of a triangle in the 4 different orientations0. The expectation
is that each pixel in the group is lit identically as the coverage is
identical.
References: https://bugs.freedesktop.org/show_bug.cgi?id=84396
Signed-off-by: Chris Wilson <chris at chris-wilson.co.uk>
diff --git a/test/coverage.c b/test/coverage.c
index 2c037eb..a58fc5f 100644
--- a/test/coverage.c
+++ b/test/coverage.c
@@ -99,6 +99,54 @@ rectangles (cairo_t *cr, int width, int height)
}
static cairo_test_status_t
+rhombus (cairo_t *cr, int width, int height)
+{
+ int x, y;
+
+ cairo_set_source_rgb (cr, 0.0, 0.0, 0.0);
+ cairo_paint (cr);
+
+#if GENERATE_REFERENCE
+ for (y = 0; y < WIDTH; y++) {
+ for (x = 0; x < WIDTH; x++) {
+ cairo_set_source_rgba (cr, 1, 1, 1,
+ x * y / (2. * WIDTH * WIDTH));
+ cairo_rectangle (cr, 2*x, 2*y, 2, 2);
+ cairo_fill (cr);
+ }
+ }
+#else
+ cairo_set_operator (cr, CAIRO_OPERATOR_OVER);
+ cairo_set_source_rgb (cr, 1, 1, 1);
+
+ for (y = 0; y < WIDTH; y++) {
+ double yf = y / (double) WIDTH;
+ for (x = 0; x < WIDTH; x++) {
+ double xf = x / (double) WIDTH;
+
+ cairo_move_to (cr,
+ 2*x + 1 - xf,
+ 2*y + 1);
+ cairo_line_to (cr,
+ 2*x + 1,
+ 2*y + 1 - yf);
+ cairo_line_to (cr,
+ 2*x + 1 + xf,
+ 2*y + 1);
+ cairo_line_to (cr,
+ 2*x + 1,
+ 2*y + 1 + yf);
+ cairo_close_path (cr);
+ }
+ }
+
+ cairo_fill (cr);
+#endif
+
+ return CAIRO_TEST_SUCCESS;
+}
+
+static cairo_test_status_t
intersecting_quads (cairo_t *cr, int width, int height)
{
int x, y, channel;
@@ -365,6 +413,13 @@ CAIRO_TEST (coverage_rectangles,
WIDTH, HEIGHT,
NULL, rectangles)
+CAIRO_TEST (coverage_rhombus,
+ "Check the fidelity of the rasterisation.",
+ NULL, /* keywords */
+ "target=raster slow", /* requirements */
+ 2*WIDTH, 2*WIDTH,
+ NULL, rhombus)
+
CAIRO_TEST (coverage_intersecting_quads,
"Check the fidelity of the rasterisation.",
NULL, /* keywords */
diff --git a/test/reference/coverage-rhombus.ref.png b/test/reference/coverage-rhombus.ref.png
new file mode 100644
index 0000000..51e0835
Binary files /dev/null and b/test/reference/coverage-rhombus.ref.png differ
More information about the cairo-commit
mailing list